應用於可重組系統之低記憶體可用空間紀錄方法

A New Low Memory Free Space Recording Method for Reconfigurable Systems

程固一(Ku-Yi Cheng)

指導教授 ： 李宗演

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

摘要

近年來，FPGA (Field-Programmable Gate Array)的動態部分可重組功能已發展到二維的可重組空間，系統功能(Task)不再是以佔用多少column數來配置到一維可重組空間，而是以矩形空間來配置到二維可重組空間，因此空間的紀錄方式也從陣列(Array)轉變成矩陣(Matrix)。但記錄空間所需要的記憶體使用量和掃描可用空間卻因FPGA的可重組空間越大，導致需要記錄的空間資料也變多，以及Task多次配置造成可用空間破碎，結果使得掃描可用空間變得更複雜。因此本論文提出以鏈結串列(Link List)的方式，記錄二維可重組空間中的可用空間，並且避免重複記錄資料所造成的浪費，所以只記錄可用空間中矩形有寬度變化時的相關座標值。此外在本論文中也提出兩種破碎度的計算方式，讓Task能在候選位置中選擇較佳的配置位置。最後本論文使用亂數產生的Task群組和真實功能的Task群組來做驗證，實驗結果顯示，我們的記錄方法有效的減少80.20%的記憶體使用量；資料結構的更新次數也減少了17.77%；破碎度計算次數也減少了57.72%。

關鍵字

動態可重組系統 ； 資料結構 ； 可用空間管理

並列摘要

Nowadays, dynamically partial reconfigurable FPGAs are proposed for the management of a 2D matrix reconfigurable area. Task places rectangle shape into 2D reconfigurable space instead of placing column based into 1D array reconfigurable area. Information of the memory size and free space will be increased greatly due to the fact that FPGA space is bigger than ever before. In addition, finding free space is intricate because space fragmentation is generated by replacement tasks. In this paper, we propose a recoding method that uses link-list to store the reconfigurable free space. The proposed method only records coordinate information width variation of rectangle in space. Therefore, the proposed method reduces the recoding space of redundancy data. The method proposed also offers two methods to select better position from candidate space for reducing fragmentation. We use random task sets and real task set to demonstrate the feasibility of the proposed recoding method. The experimental results show that proposed method reduces 80.20% on memory size, 17.77% on data update times, and 57.72% on fragmentation computing times.

並列關鍵字

Reconfigurable System ； Data Structure ； Free Space Management

參考文獻

[2] K. Bazargan, R. Kastner and M. Sarrafzadeh, “Fast Template Placement for Reconfigurable Computing Systems,” IEEE Design and Test, Vol. 17, no. 1, pp. 68-63, Jan. 2000.

[3] G. Wigley, D. Kearney, “Research Issues in Operating Systems for Reconfigurable Computing,” in Proc. of Int. Conf. on Engineering of Reconfigurable Systems and Algorithms (ERSA’02), pp.10-16, USA. 2002.

[4] A. Ahmadinia, C. Bobda, S. Fekete, J. Teich, and J. van der Veen , “Optimal Free-Space Management and Routing-Conscious Dynamic Placement for Reconfigurable Devices,” IEEE Trans. Comput., vol. 56, no. 5, pp. 673-680, May 2007.

[5] J. Septien, H. Mecha, D. Mozos and J. Tabero, “2D Defragmentation Heuristics for Hardware Multitasking on Reconfigurable Devices,” in Proc. of the 20th Int. Parallel and Distributed Processing Symp.(IPDPS’06), April 25-29, 2006.

[6] K. Compton, Z. Li, J. Cooley, S. Knol, and S. Hauck, “Configuration Relocation and Defragmentation for Run-Time Reconfigurable Computing,” IEEE Trans. on Very Large Scale Integration (VLSI) Systems, vol. 10, pp. 209-220, Jun 2002.