行路由PEA广度贪心调度映射算法

来源：计算机工程与应用杂志2017年第14期北京时间：

作者：何瑞祥，陈乃金

单位：安徽工程大学 计算机与信息学院，安徽 芜湖 241000

摘要：粗粒度可重构单元阵列硬件任务的贪心映射是可重构计算要解决的核心问题。不同的阵列具有不同的硬件约束条件，针对行路由粗粒度可重构单元阵列提出一种广度贪心映射算法BGMA（Breadth Greedy Mapping Algorithm）。该算法首先从第一个节点开始依次扫描，如果节点满足条件则将其映射到PEA上，当遇到不满足映射条件的节点时，该算法将跳过该节点继续寻找满足约束条件的节点进行映射，通过与广度不贪心映射算法BNGMA（Breadth No Greedy Mapping Algorithm）相比较，BGMA的[N1]平均减少了35.1%（PEA6×6）和54.8%（PEA8×8），[N2]平均减少了35.6%（PEA6×6）和54.6%（PEA8×8），[CCON]平均减少了15.7%（PEA6×6）和26.2%（PEA8×8），[TTOTAL]平均减少了20.2%（PEA6×6）和32.1%（PEA8×8）。实验结果表明了贪心策略在映射算法中的重要性。

关键词：贪心映射,硬件约束,行路由,广度贪心,广度不贪心