学会官网  |  加入学会  |  登录学会  |  English 

电子学报 ›› 2012, Vol. 40 ›› Issue (5): 1055-1066.DOI: 10.3969/j.issn.0372-2112.2012.05.032

• 科研通信 • 上一篇    下一篇

一种考虑执行延迟最小化和资源约束的改进层划分算法

陈乃金1,2,3, 江建慧1, 陈昕3, 周洲1, 徐莹1   

  1. 1. 同济大学软件学院, 上海 201804;2. 安徽工程大学计算机与信息学院, 安徽芜湖 241000;3. 同济大学电子与信息工程学院, 上海 201804
  • 收稿日期:2011-04-05 修回日期:2012-02-02 出版日期:2012-05-25
    • 通讯作者:
    • 江建慧
    • 基金资助:
    • 国家自然科学基金 (No.60903033); 国家863高技术研究发展计划 (No.2009AA011705)

An Improved Level Partitioning Algorithm Considering Minimum Execution Delay and Resource Restraints

CHEN Nai-jin1,2,3, JIANG Jian-hui1, CHEN Xin3, ZHOU Zhou1, XU Ying1   

  1. 1. School of Software Engineering, Tongji University, Shanghai 201804, China;2. College of Computer and Information Engineering, Anhui Polytechnic University, Wuhu, Anhui 241000, China;3. College of Electronics and Information Engineering, Tongji University, Shanghai 201804, China
  • Received:2011-04-05 Revised:2012-02-02 Online:2012-05-25 Published:2012-05-25

PDF

摘要： 本文提出了一种改进的层划分算法.该算法充分考虑了划分块的最小执行延迟和尽可能充分利用可重构资源,能够跟踪层划分算法节点分配过程并进行调整,消除了经典层划分算法不能动态更新就绪节点列表选取节点进行划分的缺陷.实验结果表明,与层划分算法相比,所提出的改进层划分算法在模块数、执行延迟和跨模块间的I/O边数等三个方面均获得了改进.与现有的簇划分、增强静态列表、多目标时域划分、簇层次敏感等四种划分算法相比,新算法能获得最少的执行延迟,并且随着可重构处理单元面积的增大,模块数的均值也是最小的.

关键词: 可重构计算, 时域划分, 层划分, 最小化执行延迟, 资源约束

Abstract: This paper presents an improved level based partitioning (ILBP) algorithm that considers sufficiently minimum execution delay and make good use of reconfigurable resources as soon as possible.ILBP can trace and adjust the node allocation process of level based partitioning (LBP) algorithm.ILBP can eliminate the disadvantage of LBP that can not update dynamically the ready list nodes for partitioning node selection.Experiment results show that the proposed ILBP algorithm can improve number of modules,execution delay and number of input-output edges crossing modules by comparing with LBP.By comparing with cluster based partitioning,enhanced static list,multi-objective temporal partitioning and level sensitive cluster based partitioning algorithms,the proposed algorithm can get the least execution delay,and it can also obtain the least average number of modules with increase of the area of reconfigurable processing unit.

Key words: reconfigurable computing, temporal partitioning, level-based partitioning, minimum execution delay, resource restraint

京ICP备12041980号-1　版权所有 ©《电子学报》编辑部