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

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

作　　者：陈乃金[1,2,3] 江建慧[1] 陈昕[3] 周洲[1] 徐莹[1] 

机构地区：[1]同济大学软件学院,上海201804 [2]安徽工程大学计算机与信息学院,安徽芜湖241000 [3]同济大学电子与信息工程学院,上海201804

出　　处：《电子学报》2012年第5期1055-1066,共12页Acta Electronica Sinica

基　　金：国家自然科学基金(No.60903033);国家863高技术研究发展计划(No.2009AA011705)

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

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

分 类 号：TP301.6[自动化与计算机技术—计算机系统结构]