|
|
- 2016
基于混合式两阶段的动态部分重构FPGA软硬件划分算法
|
Abstract:
动态部分重构的特性大大提高了硬件设计的灵活性, 但传统的软硬件划分算法不再适用于针对这类硬件的系统设计。部分研究考虑了动态部分重构的特性, 并建立了混合整数线性规划(MILP)模型进行求解。但是由于MILP自身的限制, 求解时间特别长, 只能处理规模较小的问题。为了能够处理规模较大的问题, 并且缩短求解时间, 该文对MILP方法进行了详细的分析, 并且通过启发式算法确定部分关键任务的状态, 从而减小MILP的规模, 加快求解速度。实验结果表明: 与传统的数学规划方法相比, 在求解质量不变的情况下, 该算法可以得到最高约200倍的速度提升。
Abstract：More and more hardware platforms are providing dynamic partial reconfiguration; thus, traditional hardware/software partitioning algorithms are no longer applicable. Some studies have analyzed the dynamic partial reconfiguration as mixed-integer linear programming (MILP) models to get solutions. However, the MILP models are slow and can only handle small problems. This paper uses heuristic algorithms to determine the status of some critical tasks to reduce the scale of the MILP problem for large problems. Tests show that this method is about 200 times faster with the same solution quality as the traditional mathematical programming method.
| [1] | HE Running, MA Yuchun, ZHAO Kang, et al. ISBA:An independent set-based algorithm for automated partial reconfiguration module generation[C]//International Conference on Computer-Aided Design (ICCAD). San Jose, CA, USA:IEEE Press, 2012:500-507. |
| [2] | MA Yuchun, LIU Jinglan, ZHANG Chao, et al. HW/SW partitioning for region-based dynamic partial reconfigurable FPGAs[C]//Computer Design (ICCD), IEEE International Conference on, Seoul, Korea, IEEE Press, 2014:470-476. |
| [3] | Hara Y, Tomiyama H, Honda S, et al. Proposal and quantitative analysis of the CHStone benchmark program suite for practical C-based high-level synthesis[J]. Journal of Information Processing, 2009(17), 242-254, |
| [4] | UCSB. Benchmark[EB/OL].[2015-01-15]. http://express.ece.ucsb.edu/benchmark/. |
| [5] | 张良, 徐成, 田峥, 等. 基于贪心算法和模拟退火算法的软硬件划分[J]. 计算机应用, 2013(07):1898-1902. ZHANG Liang, XU Cheng, TIAN Zheng, et al. Hardware/software partitioning based on greedy algorithm and simulated annealing algorithm[J]. Journal of Computer Applications, 2013(7):1898-1902. (in Chinese) |
| [6] | 李正民, 郭金金, 吕莹莹. 一种嵌入式系统软硬件划分算法[J]. 计算机仿真, 2011(10):204-207. LI Zhengmin, GUO Jinjin, LV Yingying. Simulation research on HW-SW partitioning of embedded system based on ant colony algorithm[J].Computer Simulation, 2011(10):204-207. (in Chinese) |
| [7] | 李春江. 面向动态可重构片上系统的过程级软硬件划分方法研究[D]. 长沙:湖南大学, 2010. LI Chunjiang. Research on Hardware and Software Partitioning Method on Process Level for Dynamically Reconfigurable System-on-Chip[D]. Changsha:Hunan University, 2010. (in Chinese) |
| [8] | Niemann R, Marwedel P. Hardware/software partitioning using integer programming[C]//European Design and Test Conference. Paris, France:IEEE Press, 1996:473-479. |
| [9] | Cordone R, Redaelli F, Redaelli M A, et al. Partitioning and scheduling of task graphs on partially dynamically reconfigurable FPGAs[J].Computer-Aided Design of Integrated Circuits and Systems, IEEE Transactions on, 2009,28(5):662-675. |
| [10] | 王璞, 武继刚. 高效软硬件划分算法及其提升技术[J]. 计算机科学, 2012(1):290-294. WANG Pu, WU Jigang. Efficient heursitic and tabu search for hardware/software partitioning[J].Computer Science,2012(1):290-294. (in Chinese) |
| [11] | Banerjee S, Bozorgzadeh E, Dutt N D. Integrating physical constraints in HW-SW partitioning for architectures with partial dynamic reconfiguration[J].Very Large Scale Integration (VLSI) Systems, IEEE Transactions on, 2006,14(11):1189-1202. |
| [12] | LIU Peng, WU Jigang, WANG Yongji. Integrated heuristic for hardware/software co-design on reconfigurable devices[C]//Parallel and Distributed Computing, Applications and Technologies (PDCAT). Beijing, China:IEEE Press, 2012:370-375. |
| [13] | Xilinx. Partial Reconfiguration User Guide.[EB/OL].[2015-01-15].http://www.xilinx.com/support/documentation/sw_manuals/xilinx14_7/ug702.pdf. |
| [14] | Lindo. Lindo Software Products[EB/OL].[2015-01-15]. http://www.lindo.com. |
