考虑通信成本和硬件碎片利用的簇划分算法  

Considering Communication-Cost and Hardware-Fragment Utilization Cluster Partitioning Algorithm

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

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

出　　处：《计算机辅助设计与图形学学报》2015年第4期754-763,共10页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家"八六三"高技术研究发展计划(2009AA011705);国家自然科学基金重点项目(61432017);安徽省自然科学基金(1408085MF124);安徽省高等学校自然科学基金(KJ2012B010);芜湖市科技计划自然科学基金(芜科计字[2012]95号)

摘　　要：针对面积约束下的可重构硬件任务划分问题,提出一种通信成本和硬件碎片利用的簇划分算法.根据簇划分算法的思想,在某一硬件面积的约束下,从待调度的就绪队列中节点依次划入到当前块,在划分过程中,若遇到不满足要求的节点就跳过,并继续搜索可划入到当前块且没有增加块间边数的节点.每划入一个节点就更新其后继的入度,如果入度为0且满足要求,将其直接划入;否则动态考查其前驱,如果前驱所需的面积满足规定的阈值,则将该节点后继和前驱一并划入到当前块.通过充分考虑节点权值、节点间的依赖度、层次小的节点优先划入等因素构造响应比函数,以动态地调整就绪列表节点的调度次序.实验结果表明,与簇划分算法和簇层次敏感划分算法相比,文中算法在划分块间非原始I/O次数、划分块数等方面均获得了较好的改进;在减少块间通信成本方面,该算法具有合理性和可行性.To cope with the problem of reconfigurable hardware task partitioning under area constraints, this pa-per presents a Communication-cost and Hardware-fragment Utilization Cluster Partitioning (CHUCP) algorithm. According to the idea of cluster based partitioning (CBP) algorithm, the nodes from the ready queue to be sched-uled are partitioned sequentially to the current modules under the constraints of a hardware area. In the process of partitionings, the nodes, which do not meet the requirements, are overlooked, and the nodes, which do not in-crease in the number of edges between the two partitionings, are found and partitioned to the current partitionings. As a node is partitioned, the indegrees of its successors will be updated. If the indegrees of its successors are zero and meet the requirements, its successors will be partitioned; if the indegrees of its successors are not zero, its precursors will be examined dynamically. The areas of its precursors meet the specified thresholds, then its suc-cessors and precursors will be partitioned to the current modules. In order to adjust dynamically the lists of node scheduling order, the response ratio function is constructed with the guideline of making good use of the node weights, the dependence between two nodes, the priority of low level nodes, etc. In comparison with cluster based partitioning (CBP) and level sensitive cluster based partitioning (LSCBP) algorithm, the experimental results show that, the proposed algorithm can get better improvements in times of non-input and non-output, the number of mod-ules. As for decreasing the communication cost of modules, the proposed algorithm has rationality and feasibility.

关 键 词：可重构计算 时域划分 通信成本 资源约束 硬件碎片利用 

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