以蟻群最佳化進行FPGA硬體多體實作工作排程之研究

FPGA Hardware Task Scheduling of Multiple Implementation Variants using Ant Colony Optimization

朱詩敏(Shih-Min Chu)

指導教授 ： 楊正仁

元智大學/資訊學院/資訊工程學系/碩士(2012年)

https://doi.org/10.6838/YZU.2012.00293

摘要

在可重組態計算架構中， FPGA 常被用來實作硬體加速功能，使整體運算效能得到提升。由於FPGA 晶片的硬體空間有限，大型且複雜的工作需進行多次重組態以完成整體工作，為了減少因重組態所造成的效能負擔，多組態工作排程便成為一個重要的議題。尤其在硬體工作有多體實作的情況下，工作排程更形複雜，這是由於多體實作的選擇同時影響到FPGA 硬體資源消耗與工作執行時間之間的權衡考量，因此在本研究中，我們提出了一個基於蟻群最佳化演算法(ACO) 的多組態工作排程演算法，並在實驗中，分別用實際案例和隨機工作案例來探討，同時與基因演算法(GA) 為基礎之多組態工作排程演算法比較。實驗結果顯示我們的方法能在更短的時間內找到更好的近似最佳工作排程，最多可減少平均10.62%的工作總執行時間。本研究並且使用田口方法來討論ACO 機制中的參數組合，找出適合不同案例的參數設定，使所提出的工作排程演算法能系統化的實用在實際工作排程問題上。

關鍵字

可重組態計算 ； 工作排程 ； 蟻群最佳化 ； 多體實作 ； 多組態 ； FPGA

並列摘要

In reconfigurable computing systems, FPGA is used for hardware acceleration to improve overall performance. Due to limited FPGA space, some large and complicated tasks need to be partitioned into several configurations. In order to reduce the reconfiguration overhead, task scheduling on multiple configurations becomes a challenging issue. In this research, we investigate this task scheduling problem and further consider a more realistic situation in which tasks may have multiple implementation variants. Considering multiple implementation variants complicates the task scheduling work because the choices of variants affect the tradeoff between the FPGA resource utilization and the task execution time. This thesis proposes a task scheduling scheme based on Ant Colony Optimization (ACO) for this problem. In the experiments, we use real cases as well as random task cases to compare the ACO-based scheme with a GA-based scheme. It shows that the ACO-based scheme can find a better task schedule in a shorter time, and improve up to 10.62% overall execution time. We also apply Taguchi methods to deicide appropriate ACO parameters in different cases. Therefore, the ACO-based scheme is feasible for practical use.

並列關鍵字

Implementation Variants ； Multiple Configurations ； FPGA ； Reconfigurable Computing ； Task Scheduling ； Ant Colony Optimization

參考文獻

[1] Sudarshan Banerjee, Elaheh Bozorgzadeh, and Nikil Dutt, "Integrating Physical Constraints in HW-SW Partitioning for Architectures with Partial Dynamic Reconfiguration," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 14, no. 11, pp. 1189–1202, Nov. 2006.

[2] Sudarshan Banerjee, Elaheh Bozorgzadeh, and Nikil Dutt, "Exploiting Applications Data-parallelism on Dynamically Reconfigurable Architectures: Placement and Architectural Considerations," IEEE Transactions on Very Large Scale Integration (VLSI) Systems, vol. 17, no. 2, pp. 234–247, Feb. 2009.

[6] Robert P. Dick, David L. Rhodes, and Wayne Wolf, "TGFF: Task Graphs for Free," in Proceedings of the 6th International Workshop on Hardware/Software Codesign (CODES '98), Seattle, Washington, USA, Mar. 1998, pp. 97–101.

[8] Marco Dorigo and Luca Maria Gambardella, "Ant Colony System: A Ccooperative Learning Approach to the Traveling Salesman Problem," IEEE Transactions on Evolutionary Computation, vol. 1, no. 1, pp. 53–66, Apr. 1997.

[10] Marco Dorigo and Thomas St‥utzle, "The Ant Colony Optimization Metaheuristic: Algorithms, Applications, and Advances," in Handbook of Metaheuristics, F. Glover and G. Kochenberger, Eds. Kluwer Academic Publishers, 2003, vol. 57, pp. 251–285.