動態部分可重組系統之蟻拓工作排程演算法

Ant-Colony Based Task Scheduling for Dynamic Partial Reconfigurable Systems

吳維中(Wei-Tsung Wu)

指導教授 ： 李宗演

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

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

摘要

目前現場可程式化閘陣列(Field Programmable Gate Array, FPGA)提供動態部分可重組(Dynamic Partial Reconfigurable, DPR)的功能，使得同一時間允許平行執行多個工作(Task)，且能在不影響其他工作的執行下，替換部分FPGA區域的電路功能，此舉可大幅增加系統設計的彈性、有效縮小電路體積。因此，為了充分發揮DPR FPGA的優點，我們需要一個良好的排程演算法，來優化Task的排程(Scheduling)、配置(Placement)與組態預取(Configuration Prefetching)，以提升硬體的使用率與縮短任務圖(Task Graphs)所需的執行時間。本論文改良蟻拓(Ant Colony System, ACS)演算法中的能見度參數，以及加入我們所提出的可用空間管理方法，使得ACS適用於1D DPR FPGA的相依性工作排程，旨在縮短相依性任務圖(Task Graph)之排程長度。本文使用TGFF (Task Graph for Free)來產生隨機相依性任務圖，實驗結果顯示本論文所提出的改良型蟻拓(IACS)工作排程演算法所求之任務圖排程長度較基因演算法(GA)平均減少24.7%，較原始型蟻拓(OACS)工作排程演算法平均減少3%；在解的收斂特性方面，實驗結果顯示IACS優於OACS與GA。

關鍵字

蟻拓演算法 ； 動態部分可重組FPGA ； 工作排程 ； 可用空間管理

並列摘要

Currently, FPGAs (Field Programmable Gate Array) have provided the functionality of dynamic partial reconfigurable, allowing scheduling multitasks that are non-overlapped either in time domain or in space domain onto the same FPGA, and switching the circuit functionality of partial FPGA without interfering other tasks execution. The volume and cost of products can be reduced by this feature. In order to minimize the overall execution time of a set of given dependent tasks, we need an efficient task scheduling algorithm to optimize the task scheduling, placement and configuration prefetching. In this paper, an ant-colony system (ACS) based task scheduling algorithm for dynamic partial reconfigurable systems (DPRS) is presented. We improved the visibility parameter of ACS, and made it suitable for DPRS dependent task scheduling by our proposed free space management method. The approach has been verified with TGFF (Task Graph for Free). Experiment results show that the average of scheduling length is reduced 24.7% compared to GA and 3% compared to OACS by the proposed Improved ACS (IACS). In solution-convergence property, IACS is better than OACS and GA.

並列關鍵字

Ant Colony System ； Dynamic Partial Reconfigurable FPGA ； Task Scheduling ； Free Space Management

參考文獻

[2] K. Compton and S. Hauck, “Reconfigurable computing: a survey of systems and software,” ACM Computing Surveys, Vol. 34, pp. 171-210, June 2002.

[3] Y. Qu, J.-P. Soininen, and J. Nurmi, “A genetic algorithm for Scheduling tasks onto dynamically reconfigurable hardware,” in Proc. of the IEEE International Symposium on Circuits and Systems, May 2007, pp. 161-164.

[4] Y. Qu, J.-P. Soininen, and J. Nurmi, “Static scheduling techniques for dependent tasks on dynamically reconfigurable devices,” Journal of Systems Architecture, Vol. 53, pp. 861-876, Nov. 2007.

[7] F. Redaelli, M. D. Santambrogio, and D. Sciuto, “Task Scheduling with Configuration Prefetching and Anti-Fragmentation techniques on Dynamically Reconfigurable Systems,” in Proc. of the Design, Automation and Test in Europe, Mar. 2008, pp. 519-522.

[8] Y. Qu, J.-P. Soininen, and J. Nurmi, “Improving the efficiency of run time reconfigurable devices by configuration locking,” in Proc. of the Design, Automation and Test in Europe, Mar. 2008, pp. 264-267.