應用於FPGA可重組系統之多策略即時硬體工作配置與內文切換設計

Multi-Strategy Online Hardware Task Placement with Context-Switching for FPGA Reconfigurable Systems

胡哲郕(Che-Cheng Hu)

指導教授 ： 李宗演

國立臺北科技大學/電資學院/電腦與通訊研究所/博士(2011年)

摘要

可重組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.

並列關鍵字

Reconfigurable system ； online placement ； resource management ； multi-strategy ； hardware context-switching

參考文獻

[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.

[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.