融合面积估算和多目标优化的硬件任务划分算法  

Hardware-task partitioning algorithm merged area estimation with multi-objective optimization

作　　者：陈乃金[1,2] 江建慧[1] 

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

出　　处：《通信学报》2013年第2期40-55,共16页Journal on Communications

基　　金：国家自然科学基金资助项目(60903033);国家高技术研究发展计划("863"计划)基金资助项目(2009AA011705)~~

摘　　要：针对可重构计算机系统配置次数(划分块数)的最小化问题,提出了一种融合面积估算和多目标优化的硬件任务划分算法。该算法每次划分均进行硬件资源面积的估算,并且通过充分考虑可重构资源的使用、一个数据流图所有划分块执行延迟总和、划分模块间边数等因素构造了新的探测函数prior_assigned(),该函数能够计算每个就绪节点的优先权值,新算法通过该值能动态调整就绪列表任务节点的调度次序。实验结果表明,与现有的层划分、簇划分、增强静态列表、多目标时域划分、簇层次敏感等5种划分算法相比,该算法能获得最少的模块数,并且随着可重构处理单元面积的增大,除层划分算法之外,其执行延迟的均值也是最小的。In order to minimize the number of configuration （i.e. the number of partitioned modules） issue in reconfigur- able computing systems, a hardware-task partitioning algorithm merged area estimation with multi-objective optimization was presented. It could estimate the area of hardware resource in each partitioning. Also, the detection function prior_assignedO was constructed with the guideline of making good use of reconfigurable resources, the execution delay sum of all partitioning modules of a^data flow graph, and number of edges between modules, etc. The detection function could calculate priority values of nodes. The proposed algorithm could adjust dynamically the scheduling order of the ready list task-nodes by the priority values. Experimental results show that the proposed algorithm can get less modules than that of level-based partitioning, cluster based partitioning, enhanced static list, multi-objective temporal partitioning and level sensitive cluster based partitioning algorithms, and it can also obtain the least average execution delay with in- crease of the area of reconfigurable processing unit except level-based partitioning.

关 键 词：可重构计算 时域划分 最小化模块数 资源约束 探测函数 多目标优化 

分 类 号：TP316[自动化与计算机技术—计算机软件与理论]