Abstract: Greedy mapping of hardware tasks in coarse-grained reconfigurable cell array is the key problem that reconfigurable computing should solve. Different arrays have different hardware constraints, this paper proposes a Breadth Greedy Mapping Algorithm（BGMA） based on row routing coarse-grained reconfigurable cell array. The algorithm starts scanning from the first node, if the node satisfies the condition, it will be mapped to the PEA. When a node does not meet the mapping conditions, the algorithm will skip the node to continue to find nodes that meet the constraints to map. To be compared with the Breadth No Greedy Mapping Algorithm（BNGMA）, on average, the [N1]of BGMA decreased by 35.1%（PEA6×6） and 54.8%（PEA8×8）, the [N2] of BGMA decreased by 35.6%（PEA6×6） and 54.6%（PEA8×8）, the [CCON]of BGMA decreased by 15.7%（PEA6×6） and 26.2%（PEA8×8）, the [TTOTAL]of BGMA decreased by 20.2%（PEA6×6） and 32.1%（PEA8×8）. Experimental evaluations confirm the importance of the greedy strategy in the mapping algorithm.

Key words: greedy mapping, hardware constraint, row routing, breadth greedy, breadth no greedy

摘要： 粗粒度可重构单元阵列硬件任务的贪心映射是可重构计算要解决的核心问题。不同的阵列具有不同的硬件约束条件，针对行路由粗粒度可重构单元阵列提出一种广度贪心映射算法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）。实验结果表明了贪心策略在映射算法中的重要性。

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