臺灣博碩士論文加值系統

在RTR系統中，傳統上把整個可重組式硬體當成是一個重組和執行的單位。因此，在整個可重組式硬體尚未完成重組時是無法開始執行的。我們把這個可部份重組的硬體虛擬地切割成數個相同大小的區塊。重組和執行的單位即可變的較小。這使得某個區塊的重組時間可以和其它區塊的執行時間重疊。如此做可以隱藏掉部份的重組時間。
如此做之後會帶來一個新的問題，也就是Partitions-to-Blocks排程的問題。我們設計了分成兩個步驟的排程器。在第一個步驟中，我們將會從所有尚未被排過的Partitions中選出一個權重最高的。我們有三個考量點來決定權重。一個是這個Partition是否在緊急的路徑上。一個是這個Partition的對外連結邊數還有可以釋放的Partition數。另一個是這個Partition的執行時間。我們有兩個Partition的選擇策略，一個是Critical First，另一個是Utilization First。在第二個步驟中，我們將會選出一個區塊來讓由步驟一選出來權重最高的Partition放。如果該Partition是最後一個Partition，則我們會選擇一個區塊，而這區塊可以使得該Partition可最早完成執行。如果不是最後一個Partition，則我們會再往前看一個Partition，兩個一起來考量，並選出一個以這兩個Partition一起考量後最好的組合，並把組合中的安排給主要的Partition的那個Partition安排給主要的Partition。
結果顯示Utilization First的效果會比Critical First效果來的好。而且把小區塊當成是重組和執行的單位對於完成執行時間是有所改善的。

In run-time reconfigurable system, the whole partial reconfigurable hardware is viewed as a reconfiguration and execution unit traditionally. Therefore, execution cannot start until the finish reconfiguration of the whole partial reconfigurable hardware. We virtually divide the partial reconfigurable hardware into several equal-size blocks. The reconfiguration and execution unit is smaller. This can make reconfiguration of one block overlap with execution of other blocks. And this can hide some reconfiguration overhead.
Doing so will bring a new problem which is partitions-to-blocks scheduling. We design a two phases scheduler. Phase I will generate one highest priority partition from un-scheduled partitions. There are three considerations of the partition’s priority. One is the partition is on current critical path or not. Another is the number of outgoing edges and released partitions of the partition. The other is the execution time of the partition. We have two partition selection policies including of critical first and utilization first. Phase II will assign one block to the highest priority partition generated from Phase I. If the partition is the latest partition, we will assign one block to the partition so that the partition can finish execution earliest. If the partition is not the latest partition, we will look ahead one next future partition into consideration together. Choose one block to the primary partition so that these two partitions can release maximal resource with time.
The result shows that utilization first is better than critical first. And view a part of the whole partial reconfigurable hardware as a reconfiguration and execution unit can improve completion time of run-time reconfigurable system.

摘要………………………………………………………………………………… i
Abstract………………………………………………………………………………ii
誌謝…………………………………………………………………………………iii
Table of Content…………………………………………………………………… .iv
List of Figures……………………………………………………………………… .vi
List of Tables……………………………………………………………………… .viii
Chapter 1 Introduction……………………………………………………………… .1
1.1 Run-Time Reconfiguration………………………………………………… .2
1.2 Completion Time of RTR System ………………………………………… .4
1.3 Partially Reconfigurable…………………………………………………… .6
1.4 Motivation………………………………………………………………… .7
1.5 Objective ……………………………………………………………………9
1.6 Organization of This Thesis ……………………………………………… .10
Chapter 2 Background……………………………………………………………… .11
2.1 Reconfiguration Models……………………………………………………. 11
2.2 Temporal Partitioning………………………………………………………15
2.2.1 Level Based Partitioning ……………………………………………16
2.2.2 Cluster Based Partitioning………………………………………… . 19
2.3 Block Size Determination…………………………………………………. .22
Chapter 3 Design of Partitions-to-Blocks Scheduling Mechanism…………………….23
3.1 Scheduling Problem Description…………………………………………….23
3.2 Procedure of Partitions-to-Blocks Scheduling……………………………….24
3.3 Partitions-to-Blocks Scheduling Mechanism Design…………………………27
3.3.1 The Highest Priority Partition Generation…………………………….27
3.3.3.1 Earliest Non-empty Candidate Partition Set Determination……29
3.3.1.1 Current Critical Path………………………………………….32
3.3.1.3 Outgoing Edges and Released Partitions………………………36
3.3.1.4 Execution Time………………………………………………39
3.3.1.5 Partition Selection Policy…………………………………… 40
3.3.1.6 Critical First vs. Utilization First……………………………. 42
3.3.2 Block for the Partition Determination……………………………………. 43
3.3.2.1 Block Determination for the Latest Partition………………… 43
3.3.2.2 Block Determination for the General Case……………………47
Chapter 4 Simulation Environment and Result……………………………………… 49
4.1 Simulation Environment……………………………………………………49
4.2 Benchmarks……………………………………………………………… . 51
4.3 Simulation Results………………………………………………………… 52
Chapter 5 Conclusions and Future Research Topic………………………………… . 68
Reference……………………………………………………………………………73

[1] Karthikeya M. Gajjala Purna, Student Member, IEEE and Dinesh Bhatia, Member, IEEE, Temporal Partitioning and Scheduling Data Flow Graphs for Reconfigurable Computers, IEEE Transaction on Computers, 48 (6), JUNE, 1999
[2] Xilinx Corporation, San Jose, California, XC6200 Datasheet, 1997
[3] Xilinx Inc. The Programmable Logic Data Book, 1994
[4] Altera Inc.. Altera Mega Core Functions, http://www.altera.com/html/tools/megacore.html, SanJose, CA, 1999.
[5] Lucent Technology Inc.. FPGA Data Book, 1998.
[6] C. Ebeling, D.C. Cronquist, P. Franklin. RaPiD — Reconfigurable Pipelined Datapath. Lecture Notes in Computer Science 1142 — Field programmable Logic: Smart Applications, New Paradigms and Compilers. R.W. Hartenstein, M. Glesner, Eds. Berlin, Germany: Springer-Verlag, pp. 126-135, 1996.
[7] H. Schmit. Incremental Reconfiguration for Pipelined Applications. IEEE Symposium on FPGAs for Custom Computing Machines, pp. 47-55, 1997.
[8] S. Hauck, T. Fry, M. Hosler, J. Kao. The Chimaera Reconfigurable Functional Unit. IEEE Symposium on FPGAs for Custom Computing Machines, 1997.
[9] Andre DeHon. DPGA-coupled microprocessors: Commodity ICs for the early 21st century. In Duncan A. Buell and Kenneth L. Pocek, editors, Proceedings of the IEEE Workshop on FPGAs for Custom Computing Machines, pp 31-39, April 1994.
[10] Steve Trimberger, Khue Duong, and Bob Conn. Architecture issues and solutions for a high-capacity FPGA. Proceedings of the ACM/SIGDA International Symposium on Field Programmable Gate Arrays, pp. 3-9, February 1997.
[11] R. Wittig, P. Chow. OneChip: An FPGA Processor with Reconfigurable Logic. IEEE Symposium on FPGAs for Custom Computing Machines, 1996.
[12] V. Sarkar, Partitioning and Scheduling Parallel Programs for Multiprocessors. MIT Press, 1989.
[13] D.D. Gajski, N.D. Dutt, A.C.-H. Wu, and S.Y.-L. Lin, High-Level Synthesis, Introduction to Chip and System Design. Kluwer Academic, 1992.
[14] B. Stott, D. Johnson, and V. Akella, “Asynchronous 2-D Discrete Cosine Transformation Core Processor,” Proc. Int’l Conf. Computer Dsign, ICCD95, Oct. 1995.
[15] W.-H. Chen, C.H. Smith, and S.C. Fralick, “ A Fast Computational Algorithm for the Discrete Cosine Transformation, “ IEEE Trans. Comm., vol. 25, no. 9, pp. 1,004-1,009, Sept. 1977.