應用在動態可重組FPGA系統之相依性任務排程演算法

A Task Dependent Scheduling Algorithm for Dynamically Reconfigurable FPGA Systems

蔡志偉(Chih-Wei Tsai)

指導教授 ： 李宗演

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

https://doi.org/10.6841/NTUT.2009.00300

摘要

本論文提出一個相依性任務排程演算法，其主要目的在降低系統分割動態可重組化現場可規劃邏輯陣列(FPGA)時重組區域之間的通訊成本，本演算法包含有三個步驟，分別描述如下，首先系統分割後重組區域內的電路節點之間會有時間順序關係，因此應用「盡早排程」(As Soon As Possible, ASAP)與「盡晚排程」(As Late As Possible, ALAP)對各節點計算其執行順序，並計算各節點之權重值，並依此兩項參數來將工作任務(Task)排入重組區域中，其次利用「最大機率負載」的方法去改善同一時間內重組區域所需要處理的節點個數，使各時間內執行節點總數達到平衡。最後為了讓通訊連線均勻分散到各個重組區域之間，因此使用「降低最大通訊連線」方法，以減輕FPGA系統資料傳遞時間。從實驗結果上發現在使用本論文所提出之相依性任務排程演算法後，動態載入新的工作任務所需的通訊連線個數可降低12.1%~16.8%。

關鍵字

任務排程 ； 動態可重組FPGA系統 ； 任務相依性

並列摘要

In this thesis, a task dependent scheduling algorithm is proposed to reduce the communication cost in dynamically reconfigurable FPGA system. The proposed algorithm includes three steps which are shown in the following. First, the task nodes in reconfigurable areas generate after system partitioning. Therefore, the execution ordering and weight in each task node will be calculated by As Soon As Possible (ASAP) and As Late As Possible (ALAP) algorithms. The task node is scheduled into reconfigurable area depending on the execution ordering and weight in the task node. After that, we use probability of loading algorithm to balance the number of task node in each reconfigurable area. Finally, reducing maximum communication line method is applied to reduce the communication time in the reconfigurable FPGA system. Experimental results shown that the communication link in reconfigurable area is reduced by 12.1%~16.8% when our proposed task dependent scheduling algorithm is used.

並列關鍵字

Task Scheduling ； Dynamic Reconfigurable for FPGA System ； Task Dependent

參考文獻

[13]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 (ISCAS), Page. 2742–2745, May 2007.

[6]G.. M. Wu, J. M. Lin, and Y. W. Chang, “Generic ILP-based approaches for time-multiplexed FPGA partitioning,” IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, Vol. 20 No. 10,Page. 1266-1274, Oct. 2001.

[1]S. Trimberger, “Scheduling Designs into a Time-multiplexed FPGA,” International Symposium on Field Programmable Gate Arrays, Page. 153-160, Feb. 1998.

[2]S. Trimberger, “A time-multiplexed FPGA,” in Proc. IEEE Symp. FPGAs for Custom Computing Machines. Page. 22-28, March, 1997.

[3]D. Chang and M. Marek-sadowska, “Partitioning Sequential Circuits on Dynamically Reconfigurable FPGAs Computers,” IEEE Transactions on Computers, Vol. 48 No. 6, Page. 565-578, June 1999.