Please wait a minute...
 首页  期刊介绍 期刊订阅 联系我们 横山亮次奖 百年刊庆
 
最新录用  |  预出版  |  当期目录  |  过刊浏览  |  阅读排行  |  下载排行  |  引用排行  |  横山亮次奖  |  百年刊庆
清华大学学报(自然科学版)  2016, Vol. 56 Issue (3): 246-252,261    DOI: 10.16511/j.cnki.qhdxxb.2016.21.004
  计算机科学与技术 本期目录 | 过刊浏览 | 高级检索 |
基于混合式两阶段的动态部分重构FPGA软硬件划分算法
马昱春1, 张超1, Luk Wayne2
1. 清华大学计算机科学与技术系, 北京 100084;
2. 帝国理工大学电子计算学系, 伦敦 SW72BZ
Hybrid two-stage HW/SW partitioning algorithm for dynamic partial reconfigurable FPGAs
MA Yuchun1, ZHANG Chao1, LUK Wayne2
1. Department of Computer Science and Technology, Tsinghua University, Beijing 100084, China;
2. Department of Computing, Imperial College, London SW72BZ, UK
全文: PDF(1130 KB)  
输出: BibTeX | EndNote (RIS)      
摘要 动态部分重构的特性大大提高了硬件设计的灵活性, 但传统的软硬件划分算法不再适用于针对这类硬件的系统设计。部分研究考虑了动态部分重构的特性, 并建立了混合整数线性规划(MILP)模型进行求解。但是由于MILP自身的限制, 求解时间特别长, 只能处理规模较小的问题。为了能够处理规模较大的问题, 并且缩短求解时间, 该文对MILP方法进行了详细的分析, 并且通过启发式算法确定部分关键任务的状态, 从而减小MILP的规模, 加快求解速度。实验结果表明: 与传统的数学规划方法相比, 在求解质量不变的情况下, 该算法可以得到最高约200倍的速度提升。
服务
把本文推荐给朋友
加入引用管理器
E-mail Alert
RSS
作者相关文章
马昱春
张超
Luk Wayne
关键词 软硬件划分动态部分重构启发式混合整数线性规划    
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.
Key wordsHW/SW partitioning    dynamic partial reconfiguration    heuristic method    mixed-integer linear programming (MILP)
收稿日期: 2015-03-02      出版日期: 2016-03-15
ZTFLH:  TP301.6  
引用本文:   
马昱春, 张超, Luk Wayne. 基于混合式两阶段的动态部分重构FPGA软硬件划分算法[J]. 清华大学学报(自然科学版), 2016, 56(3): 246-252,261.
MA Yuchun, ZHANG Chao, LUK Wayne. Hybrid two-stage HW/SW partitioning algorithm for dynamic partial reconfigurable FPGAs. Journal of Tsinghua University(Science and Technology), 2016, 56(3): 246-252,261.
链接本文:  
http://jst.tsinghuajournals.com/CN/10.16511/j.cnki.qhdxxb.2016.21.004  或          http://jst.tsinghuajournals.com/CN/Y2016/V56/I3/246
  图1 目标系统结构
  图2 任务依赖图
  图3 软硬件划分结果
  表1 任务基本信息
  图4 算法流程
  表2 停止条件对算法的影响
  表3 实验结果对比
[1] 张良, 徐成, 田峥, 等. 基于贪心算法和模拟退火算法的软硬件划分[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)
[2] 李正民, 郭金金, 吕莹莹. 一种嵌入式系统软硬件划分算法[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)
[3] 李春江. 面向动态可重构片上系统的过程级软硬件划分方法研究[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)
[4] Niemann R, Marwedel P. Hardware/software partitioning using integer programming[C]//European Design and Test Conference. Paris, France:IEEE Press, 1996:473-479.
[5] 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.
[6] 王璞, 武继刚. 高效软硬件划分算法及其提升技术[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)
[7] 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.
[8] 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.
[9] Xilinx. Partial Reconfiguration User Guide.[EB/OL].[2015-01-15].http://www.xilinx.com/support/documentation/sw_manuals/xilinx14_7/ug702.pdf.
[10] 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.
[11] 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.
[12] 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,
[13] UCSB. Benchmark[EB/OL].[2015-01-15]. http://express.ece.ucsb.edu/benchmark/.
[14] Lindo. Lindo Software Products[EB/OL].[2015-01-15]. http://www.lindo.com.
[1] 杜明, 郑凯文, 陈子阳, 周军锋. TFP:高效的最快路径查询处理方法[J]. 清华大学学报(自然科学版), 2020, 60(8): 656-663.
[2] 张灿荣, 钟明, 缪立新. 集装箱场地箱位分配问题[J]. 清华大学学报(自然科学版), 2015, 55(10): 1150-1156.
Viewed
Full text


Abstract

Cited

  Shared   
  Discussed   
版权所有 © 《清华大学学报(自然科学版)》编辑部
本系统由北京玛格泰克科技发展有限公司设计开发 技术支持:support@magtech.com.cn