應用於動態可重組系統之平行粒子群最佳化軟硬體分割演算法

Parallel Particle Swarm Optimization Based Hardware/Software Partitioning Algorithm for Dynamic Reconfigurable Systems

鍾佩昕(Pei-Hsin Chung)

指導教授 ： 李宗演

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

摘要

具有彈性、高效能及成本效益的可重組系統架構已可應用於嵌入式系統，隨著系統的複雜度增加，可利用軟硬體共同設計之軟硬體分割技術，以提升整體系統效能。本論文提出平行粒子群最佳化軟硬體分割演算法(Parallel Particle Swarm Optimization Hardware-Software Partitioning Algorithm, PPSO)應用於動態可重組FPGA系統，同時考量系統限制，如執行時間、硬體資源及成本等條件。藉由所提出的平行粒子群最佳化軟硬體分割演算法，利用平行方式計算所有粒子的適應函數並評估適應值，根據粒子本身的速度和位置以決定搜尋的範圍，具有快速的收斂。利用適應函數評估整體執行時間、硬體面積、執行的功率消耗以及軟體所占的記憶體，以找到最適合的軟硬體分割解。在實驗部份採用一維搜尋空間，以ADPCM語音編解碼系統、JPEG影像壓縮編碼系統及利用TGFF(Task Graph for Free)所產生的範例為實驗對象，從實驗結果中，本論文所提出的PPSO軟硬體分割演算法在執行各系統目標於單核心系統下的執行時間與GA(Genetic Algorithm)、SA(Simulated Annealing)及PSO演算法比較，分別降低87.1%、88.8%及92.1%；在雙核心系統下則本方法的執行時間與GA、SA及PSO演算法比較，可分別降低77.9%、83.5%及85.6%。

關鍵字

動態可重組 ； FPGA ； 軟硬體分割 ； 平行粒子群最佳化演算法

並列摘要

The flexibility, high performance and cost effectiveness of reconfigurable architectures are used for embedded systems applications. The hardware/software partitioning technique in hardware/software co-design is used to improve the system performance when the design system become complex. This study presents a Parallel Particle Swarm Optimization (PPSO) based hardware/software partitioning algorithm for dynamic reconfigurable FPGA system. The constraints of execution time, cost and power consumption are considered in the proposed PPSO method. The parallel fitness functions computing are used to evaluate the system particles in PPSO. The parameters of velocity and position in the particles are used to search the global adaptive solution with fast convergence. The design examples of ADPCM encode/decode system, JPEG encode system and Task Graph for Free (TGFF) in 1-D search space are used in experiments. The experimental results show that comparison of GA, SA, PSO and PPSO algorithms in running single CPU, the proposed method reduces 87.1%, 88.8% and 92.1% on execution time, respectively. Comparison of GA, SA, PSO and PPSO algorithms in running dual CPU, the proposed method reduces 77.9%, 83.5% and 85.6% on execution time, respectively.

並列關鍵字

Dynamic reconfigurable system ； FPGA ； hardware/software partitioning ； parallel particle swarm optimization algorithm (PPSO)

參考文獻

[1] M. D. Santambrogio, M. Redaelli, and M. Maggioni, “Task Graph Scheduling for Reconfigurable Architectures Driven by Reconfigurations Hiding and Resources Reuse,” in Proc. of the 19th ACM Great Lakes symposium on VLSI, May 2009, pp. 21-26.

[2] 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 conference on Design, automation and test in Europe, Mar. 2008, pp. 519-522.

[4] S. Banerjee, E. Bozorgzadeh, and N. Dutt, “Integrating Physical Constraints in HW–SW Partitioning for Architectures with Partial Dynamic Reconfiguration,” IEEE Trans. on Very Large Scale Integr. (VLSI) Syst., vol. 14, no. 11, pp. 1189–1202, Nov. 2006.

[5] M. M. Bassiri and H. S. Shahhoseini, “A HW/SW Partitioning Algorithm for Multitask Reconfigurable Embedded Systems,” in Proc. of the International Conference on Microelectronics, Dec. 2008, pp. 143-146.

[6] I. Taniguchi, K. Ueda, K. Sakanushi, Y. Takeuchi, and M. Imai, “Task Partitioning Oriented Architecture Exploration Method for Dynamic Reconfigurable Architectures,” in Proc. of 2006 IFIP International Conference on VLSI, Oct. 2006, pp. 290-295.