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

摘要：

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

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

分类号：TP316(计算技术、计算机技术)

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

在线出版日期：2015-04-27（万方平台首次上网日期，不代表论文的发表时间）

页数：共10页

页码：754-763