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

作     者：陈乃金 江建慧 Chen Naijin;Jiang Jianhui

作者机构：安徽工程大学计算机与信息学院芜湖241000 同济大学软件学院上海201804 

出 版 物：《计算机辅助设计与图形学学报》 (Journal of Computer-Aided Design & Computer Graphics)

年 卷 期：2015年第27卷第4期

页      面：754-763页

核心收录：

学科分类：08[工学] 0835[工学-软件工程] 0811[工学-控制科学与工程] 0812[工学-计算机科学与技术（可授工学、理学学位）] 081202[工学-计算机软件与理论] 

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

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

摘      要：针对面积约束下的可重构硬件任务划分问题,提出一种通信成本和硬件碎片利用的簇划分算法.根据簇划分算法的思想,在某一硬件面积的约束下,从待调度的就绪队列中节点依次划入到当前块,在划分过程中,若遇到不满足要求的节点就跳过,并继续搜索可划入到当前块且没有增加块间边数的节点.每划入一个节点就更新其后继的入度,如果入度为0且满足要求,将其直接划入;否则动态考查其前驱,如果前驱所需的面积满足规定的阈值,则将该节点后继和前驱一并划入到当前块.通过充分考虑节点权值、节点间的依赖度、层次小的节点优先划入等因素构造响应比函数,以动态地调整就绪列表节点的调度次序.实验结果表明,与簇划分算法和簇层次敏感划分算法相比,文中算法在划分块间非原始I/O次数、划分块数等方面均获得了较好的改进;在减少块间通信成本方面,该算法具有合理性和可行性.