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

Breadth greedy scheduling mapping algorithm for row routing PEA

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

Greedy mapping of hardware tasks in coarse-grained reconfigurable cell array is the key problem that reconfigurablecomputing should solve.Different arrays have different hardware constraints,this paper proposes a Breadth GreedyMapping Algorithm(BGMA)based on row routing coarse-grained reconfigurable cell array.The algorithm starts scanningfrom the first node,if the node satisfies the condition,it will be mapped to the PEA.When a node does not meet themapping conditions,the algorithm will skip the node to continue to find nodes that meet the constraints to map.To becompared with the Breadth No Greedy Mapping Algorithm(BNGMA),on average,the N1of BGMA decreased by35.1%(PEA6×6)and54.8%(PEA8×8),the N2of BGMA decreased by35.6%(PEA6×6)and54.6%(PEA8×8),the CCON of BGMAdecreased by15.7%(PEA6×6)and26.2%(PEA8×8),the TTOTAL of BGMA decreased by20.2%(PEA6×6)and32.1%(PEA8×8).Experimental evaluations confirm the importance of the greedy strategy in the mapping algorithm.