臺灣博碩士論文加值系統

可重組FPGA (Field Programmable Gate Array)系統具有即時釋放硬體空間的能力。為了增加可重組FPGA系統的效能，此系統允許數個硬體工作(Hardware task)可以在同一時間被執行、配置與移除。因此FPGA硬體資源的管理方法在即時配置(Online placement)已成為研究的重點。現今國內外相關研究所提出的硬體資源管理方式幾乎都是以矩形空間的概念進行研究與探討。然而，在矩形空間的方法下可能會造成兩個問題：(1)FPGA硬體資源之破碎度增加；(2)Task的拒絕率(Rejection rate)提高。這些問題都會降低可重組系統架構的彈性與執行效能。另外，當硬體資源管理系統需要更換新的硬體工作(Hardware task)進入可重組系統時，舊的硬體工作的硬體資料需要做切換及儲存。然而，硬體在切換的過程需要使用大量的記憶體來儲存硬體內文(Hardware context)，並且耗費許多不必要的時間在讀取硬體內文上。因此，本論文提出具有硬體內文處理之多策略即時硬體工作配置方法來解決上述所提到的問題。
本論文所提出的方法包含兩個部分，分別是多策略即時硬體工作配置方法與硬體內文交換方法。在即時配置中，沒有辦法事先知道哪個硬體工作將是下一個要被執行。因此當可重組系統在一個未知硬體工作順序的情況下，可以即時找到一個最佳的配置空間，即可增加可重組系統的執行效能，同時提升配置品質(Placement Quality)與降低硬體工作的執行時間。因此，多策略即時硬體工作配置方法是被用來管理FPGA資源並尋找適合的可用空間給新進來的硬體工作。有效的候選空間可以是矩形空間或是非矩形空間，並且讓可重組系統的可配置空間達到最佳的使用率。由於目前FPGA是以Column-based的方式來進行配置。當找到候選空間之後並配置這個新進來的硬體工作時，將會影響到在相同的Column中其它正在執行的硬體工作。因此，硬體內文交換方法是為了使這些被影響的硬體工作能夠順利完成後續未完成的工作。另外，我們分析FPGA結構的特性以避免儲存多餘的資料，達到減少讀取硬體內文的時間與儲存硬體內文的記憶體大小。

The reconfigurable field programmable gate array (FPGA) system has the ability to real-time change hardware resource. To increase the efficiency of reconfigurable FPGAs, they allow several tasks to be executed, placed and removed at runtime. Therefore, FPGA hardware resource management in online placement is a critical research. Nowadays, most research on hardware resource management focus on a rectangular hardware space. However, the application of the rectangular space to a reconfigurable system raises two issues, which are (1) an increasing in the fragmentation of FPGA hardware resources, and (2) an increasing in the rejection rate of tasks. Both of above statements will reduce flexibility and performance of reconfigurable system architecture. Additionally, when an old hardware task is replaced by new hardware task in hardware resource management system, then register information of old hardware task must be switched and saved. However, such FPGA systems require a long time to read, and much memory to store the hardware context, when a hardware task is swapped out. Therefore, this dissertation proposes a multi-strategy online hardware task placement with context-switching methodology to solve these problems.
This dissertation proposes methodology consists of multi-strategy online hardware task placement and hardware context-switching. In online placement, the flow of hardware tasks is unknown in advance. If reconfigurable system can find out the adaptive free space to place a hardware task at runtime, then it will enhance the efficiency of reconfigurable system and placement quality, and reduce the execution time of hardware task. Therefore, the multi-strategy online hardware task placement are developed to manage FPGA resource and to find all rectangular or nonrectangular candidate space for placing newly arrived tasks. Current FPGA technology configures reconfigurable logic resources by the column-based method, which interferes with other hardware tasks in the same columns. Therefore, the hardware context-switching is developed to enable hardware tasks to be reloaded to complete unfinished work. In addition, this method can reduce the reconfiguration time and memory size of hardware context-switching by analyzing the characteristics of FPGA structure.

ABSTRACT(Chinese) i
ABSTRACT iii
ACKNOWLEDGEMENT(Chinese) v
CONTENTS vii
LIST OF TABLES ix
LIST OF FIGURES xi
Chapter 1 INTRODUCTION 1
1.1 Motivation 2
1.2 Multi-strategy Online Hardware Task Placement with Context-switching Flow Chart 4
1.3 Contributions 6
1.4 Thesis Organization 7
Chapter 2 PREVIOUS WORK 9
2.1 Online Placement 9
2.2 Hardware Context-switching 14
Chapter 3 ONLINE HARDWARE TASK PLACEMENT METHODOLOGY 17
3.1 Problem Formulation 18
3.1.1 Online Placement System Model 18
3.1.2 FPGA Model 19
3.1.3 Task Model 20
3.1.4 Evaluation Model 23
3.2 Online Placement Methodology 25
3.2.1 Free Space Matrix 26
3.2.2 Resolve Candidate Space 27
3.2.3 Multi-strategy Aware Filter 34
3.2.4 Online Placement Algorithm 39
Chapter 4 HARDWARE CONTEXT-SWITCHING METHODOLOGY 43
4.1 FPGA Configuration Structure 44
4.1.1 Frame Addressing 46
4.1.2 Configuration Registers 47
4.2 Hardware Context-switching Architecture without Microprocessor 49
4.3 Hardware Context-switching Architecture with Microprocessor 50
4.4 Hardware Context-switching Flow Chart 51
4.5 Module Database Memory and State Filter 53
4.6 Frame Addresses and Addressing Bit Indexes 57
4.7 Context Reading and Writing 59
4.7.1 CRW Flow Chart 59
4.7.2 CRW Algorithm 61
4.8 Performance Analysis 64
Chapter 5 EXPERIMENTAL RESULTS 69
5.1 Multi-strategy Online Hardware Task Placement 69
5.2 Hardware Context-switching 74
5.2.1 Random Task Sets 74
5.2.2 Real Design Examples 78
Chapter 6 CONCLUSIONS AND FUTURE WORK 83
6.1 Conclusions 83
6.2 Future Work 84
BIBLIOGRAPHY 87
APPENDIX 95
A. VITA 95
B. PUBLICATIONS 97

[1]http://www.xilinx.com, “Early Access Partial Reconfiguration User Guide,” UG208 (v1.2), September 9, 2008.
[2]A. A. ElFarag, H. M. El-Boghdadi, and S. I. Shaheen, “Fragmentation aware placement in reconfigurable devices,” in Proceedings of the 6th International Workshop on System on Chip for Real Time Applications, Dec. 2006, pp. 37-44.
[3]T. Y. Lee, Y. H. Fan, Y. M. Cheng, and C. C. Tsai, “Hardware-software partitioning for embedded multiprocessor FPGA systems,” International Journal of Innovative Computing, Information and Control, vol. 5, no. 10(A), pp. 3071-3083, 2009.
[4]K. Bazargan, R. Kastner, and M. Sarrafzadeh, “3-D floorplanning: simulated annealing and greedy placement methods for reconfigurable computing systems,” in Proceedings of the IEEE International Workshop on Rapid System Prototyping, July, 1999, pp. 38-43.
[5]R. P. Dick and N. K.Jha, “CORDS: hardware-software co-synthesis of reconfigurable real-time distributed embedded systems,” in Proceedings of the International Conference on Computer-Aided Design, November 8-12, 1998, pp. 62-68.
[6]A. Ahmadinia and J. Teich, “Speeding up online placement for XILINX FPGAs by reducing configuration overhead,” in Proceedings of the IFIP International Conference on VLSISOC, Dec. 2003, pp. 118-122.
[7]http://www.xilinx.com, “Virtex series configuration architecture user guide,” XAPP151 (v1.7), October 20, 2004.
[8]D. Mesquita, F. Moraes, J. P. L. Möller, and N. Calazans, “Remote and partial reconfiguration of FPGA: tools and trends,” in Proceedings of the International Parallel and Distributed Processing Symposium / Reconifgurable Architectures Workshop, April 2003.
[9]H. Walder and M. Platzner, “Online scheduling for block-partitioned reconfigurable devices,” in Proceedings of the Design Automation and Test in Europe, 2003, pp. 290-295.
[10]J. Tabero, J. Septién, H. Mecha, and D. Mozos, “Allocation heuristics and defragmentation measures for reconfigurable systems management,” Integration, the VLSI Journal, vol. 41, pp. 281-296, February 2008.
[11]K. Bazargan, R. Kastner, and M. Sarrafzadeh, “Fast template placement for reconfigurable computing systems,” IEEE Design and Test of Computers, vol. 17, pp. 68-83, 2000.
[12]H. Walder, C. Steiger, and M. Platzner, “Fast online task placement on FPGAs: Free space partitioning and 2D-hashing,” in Proceedings of the International Parallel and Distributed Processing Symposium, April 22-26, 2003, p. 178.
[13]A. Ahmadinia, C. Bobda, S. P. Fekete, J. Teich, and J. v.d. Veen, “Optimal free-space management and routing-conscious dynamic placement for reconfigurable devices,” IEEE Transactions on Computers, vol. 56, pp. 673-680, May 2007.
[14]S. P. Fekete, Jan C. van der Veen, A. Ahmadinia, D. Göhringer, M. Majer, and J. Teich, “Offline and online aspects of defragmenting the module layout of a partially reconfigurable device,” IEEE Transactions on Very Large Scale Integration Systems, vol. 16, pp. 1210-1219, September 2008.
[15]H. Kalte and M. Porrmann, “Context saving and restoring for multitasking in reconfigurable systems,” in Proceedings of International Conference on Field Programmable Logic and Applications, Aug. 24-26, 2005, pp. 223-228.
[16]M. Koester, M. Porrmann, and H. Kalte, “Relocation and defragmentation for heterogeneous reconfigurable system,” in Proceedings of International Conference on Engineering of Reconfigurable Systems and Algorithms, Jun. 26-29, 2006, pp. 70-76.
[17]H. Simmler, L. Levinson, and R. M¨anner, “Multitasking on FPGA coprocessors,” in Proceedings of the 10th International Conference on Field-Programmable Logic and Applications, August 2000, pp. 121-130.
[18]S. A. Guccione, D. Levi, and P. Sundararajan, “JBits: a java-based interface for reconfigurable computing,” in Proceedings of the 2th Annual Military and Aerospace Applications of Programmable Devices and Technologies Conference, September 1999, p. 27.
[19]T. Y. Lee, C. C. Hu, L. W. Lai, C. C. Tsai, and R. S. Hsiao, “Hardware context switching methodology for dynamically partially reconfigurable systems,” in Proceedings of the National Computer Symposium, December 20-21, 2007, pp. 300-310.
[20]K. Puttegowda, D. I. Lehn, J. H. Park, P. Athanas, and M. Jones, “Context switching in a run-time reconfigurable system,” The Journal of Supercomputing, vol. 26, pp. 239-257, November 2003.
[21]M. Ullmann, M. Huebner, B. Grimm, and J. Becker, “An FPGA run-time system for dynamical on-demand reconfiguration,” in Proceedings of the 18th International Parallel and Distributed Processing Symposium, April 26-30, 2004, pp. 135-142.
[22]J.-Y. Mignolet, V. Nollet, P. Coene, D. Verkest, S. Vernalde, and R. Lauwereins, “Infrastructure for design and management of relocatable tasks in a heterogeneous reconfigurable system-on-chip,” in Proceedings of the Design, Automation and Test in Europe Conference and Exhibition, March 2003, pp. 986-991.
[23]C. H. Huang and P. A. Hsiung, “Software-controlled dynamically swappable hardware design in partially reconfigurable systems,” EURASIP Journal on Embedded Systems, vol. 2008, Article ID 231940, 2008.
[24]J. Phillips, A. Sudarsanam, H. Samala, R. Kallam, J. Carver, and A. Dasu, “Methodology to derive context adaptable architectures for FPGAs,” IET Computers & Digital Techniques, vol. 3, pp. 124-141, January 2009.
[25]K. Compton and S. Hauck, “Reconfigurable computing: a survey of systems and software,” ACM Computing Surveys, vol. 34, pp. 171-210, June 2002.
[26]J. Septien, H. Mecha, D. Mozos, and J. Tabero, “2D defragmentation heuristics for hardware multitasking on reconfigurable devices,” in Proceedings of the 20th International Parallel and Distributed Processing Symposium, April 2006.
[27]J. Cui, Z. Gu, W. Liu, and Q. Deng, “An efficient algorithm for online soft real-time task placement on reconfigurable hardware devices,” in Proceedings of the 10th IEEE International Symposium on Object and Component-Oriented Real-Time Distributed Computing, May 2007, pp. 321-328.
[28]J. Tabero, J. Septien, H. Mecha, and D. Mozos, “Task placement heuristic based on 3D-adjacency and look-ahead in reconfigurable systems,” in Proceedings of the 11th Asia and South Pacific Design Automation Conference, 2006, pp. 396-401.
[29]M. Tomono, M. Nakanishi, S. Yamashita, K. Nakajima, and K. Watanabe, “A new approach to online FPGA placement,” in Proceedings of the 40th Annual Conference on Information Sciences and Systems, March 22-24, 2006, pp. 145-150.
[30]J. Cui, Q. Deng, X. He, and Z. Gu, “An efficient algorithm for online management of 2D area of partially reconfigurable FPGAs,” in Proceedings of the Design, Automation and Test in Europe, April 2007, pp. 129-134.
[31]Y. Lu, T. Marconi, G. N. Gaydadjiev, and K.L.M. Bertels, “An efficient algorithm for free resources management on the FPGA,” in Proceedings of the Design, Automation and Test in Europe, March 2008, pp. 1095-1098.
[32]R. P. Dick, D. L. Rhodes and W. Wolf, “TGFF: task graphs for free,” in Proceedings of the Sixth International Workshop Hardware/Software Codesign, Washington, USA, Mar. 15-18, 1998, pp. 97-101.
[33]L. Levinson, R. Männer, M. Sessler, and H. Simmler, “Preemptive multitasking on FPGAs,” in Proceedings of the Field-Programmable Custom Computing Machines Symposium, 2000, pp. 301-302.
[34]Xilinx website, http://www.xilinx.com/support/documentation/dt_planahead.htm
[35]T. Becker, W. Luk, and Y.K. Cheung, “Enhancing relocatability of partial bitstreams for run-time reconfiguration,” in Proceedings of the International Symposium on Field-Programmable Custom Computing Machines, April 23-25, 2007, pp. 35-44.
[36]M. Purnaprajna, M. Reformat, and W. Pedrycz, “Genetic algorithm for hardware-software partitioning and optimal resource allocation,” Journal of Systems Architecture, vol. 53, pp. 339-354, July 2007.
[37]P. A. Hsiung, C. S. Lin, and C. F. Liao, “Perfecto: A systemc-based design-space exploration framework for dynamically reconfigurable architectures,” ACM Transactions on Reconfigurable Technology and Systems, vol. 1, pp. 1-30, September 2008.
[38]F. Ferrandi, P. L. Lanzi, C. Pilato, D. Sciuto, and A. Tumeo, “Ant colony heuristic for mapping and scheduling tasks and communications on heterogeneous embedded systems,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 29, pp. 911-924, June 2010.
[39]R. Cordone, F. Redaelli, M. A. Redaelli, M. D. Santambrogio, and D. Sciuto, “Partitioning and scheduling of task graphs on partially dynamically reconfigurable FPGAs,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, vol. 28, pp. 662-675, May 2009.
[40]A. Ahmadinia, C. Bobda, S. P. Fekete, J. Teich, and J. v.d. Veen, “Optimal routing-conscious dynamic placement for reconfigurable devices,” in Proceeding of the Field Programmable Logic and Applications, August 2004, pp. 847-851.
[41]R.H. Gu¨ ting, “An optimal contour algorithm for ISO-oriented rectangles,” Journal Algorithms, vol. 5, pp. 303-326, 1984.
[42]W. Lipski Jr. and F.P. Preparata, “Finding the contour of a union of ISO-oriented rectangles,” Journal Algorithms, vol. 1, pp. 235-246, 1980, errata in 2 (1981), 105; corrigendum in 3 (1982), 301-302.
[43]F.P. Preparata and M.I. Shamos, “Computational Geometry: An Introduction,” Springer, 1985.
[44]S. M. Scalera and J. R. Vazquez, “The design and implementation of a context switching FPGA,” in Proceeding of the IEEE Symposium FPGAs for Custom Computing Machines, April 15-17, 1998, pp. 78-85.
[45]F. Berthelot, F. Nouvel, and D. Houzet, “A flexible system level design methodology targeting run-time reconfigurable FPGAs,” EURASIP Journal on Embedded Systems, vol. 2008, pp. 1-18, January 2008.
[46]C.-H. Huang, S.-S. Chang, and P.-A. Hsiung, “Generic wrapper design for dynamic swappable hardware IP in partially reconfigurable systems,” International Journal of Electrical Engineering, pp. 229-238, June 2007.
[47]C.-H. Huang, K.-J. Shih, C.-S. Lin, S.-S. Chang, and P.-A. Hsiung, “Dynamically swappable hardware design in partially reconfigurable systems,” in Proceedings of the IEEE International Symposium on Circuits and Systems, May 2007, pp. 2742-2745.
[48]http://www.xilinx.com, “Virtex-II platform FPGA user guide,” UG002, 2007.
[49]http://www.xilinx.com, “OPB HWICAP (v1.00.b),” DS208, July 26, 2006.
[50]Y. Birk and E. Fiksman, “Dynamic reconfiguration architectures for multi-context FPGAs,” Computers and Electrical Engineering, In Press, Corrected Proof, Available online 31 January 2009.
[51]http://www.xilinx.com, “Virtex-II pro and virtex-II pro x FPGA user guide,” UG012, 2007.
[52]H. Kalte and M. Porrmann, “REPLICA2Pro: task relocation by bitstream manipulation in virtex-II/pro FPGAs,” in Proceedings of the 3rd Conference on Computing Frontiers, May 3-5, 2006, pp. 403-412.
[53]C. Steiger, H. Walder, and M. Platzner, “Operating systems for reconfigurable embedded platforms: online scheduling of real-time tasks”, IEEE Transactions on Computers, vol. 53, pp. 1393-1407, November 2004.
[54]M. Hubner, C. Schuck, and J. Becker, “Elementary block based 2-dimensional dynamic and partial reconfiguration for Virtex-II FPGAs,” in Proceedings of the 20th International Parallel and Distributed Processing Symposium, April 25-29, 2006, p. 8
[55]H. Kalte, G. Lee, M. Porrmann, and U. Rückert, “REPLICA: a bitstream manipulation filter for module relocation in partial reconfigurable systems,” in Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium, April 4-8, 2005, p. 151b.
[56]Y. E. Krasteva, E. de la Torre, T. Riesgo and D. Joly, “Virtex II FPGA bitstream manipulation: application to reconfiguration control systems,” in Proceedings of the International Conference on Field Programmable Logic and Applications, Aug. 2006, pp. 1-4.
[57]http://www.xilinx.com, “Virtex FPGA series configuration and Readback,” xapp138, 2005.
[58]B. Blodget, C. Bobda, M. Huebne, and A. Niyonkuru, “Partial and dynamically reconfiguration of Xilinx Virtex-II FPGAs,” in Proceedings of the International Conference on Field-Programmable Logic and its Applications, Aug. 30-Sep. 1, 2004, pp. 801-810.
[59]S. Jovanovic, C. Tanougast, and S. Weber, “A hardware preemptive multitasking mechanism based on scan-path register structure for FPGA-based reconfigurable systems,” in Proceedings of the NASA/ESA Conference on Adaptive Hardware and Systems, Aug. 5-8, 2007, pp. 358-364.
[60]M. Esmaeildoust, M. Fazlali, A. Zakerolhosseini, and M. Karimi, “Fragmentation aware placement algorithm for a reconfigurable system,” in Proceedings of the Second International Conference on Electrical Engineering, March 25-26, 2008, pp. 1-5.
[61]http://www.xilinx.com, “Virtex-4 configuration user guide,” UG071, Jun. 2009.
[62]http://www.xilinx.com, “Virtex-5 configuration user guide,” UG191 (v3.8), Aug. 2009.