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

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