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

Breadth greedy scheduling mapping algorithm for row routing PEA

作　　者：何瑞祥[1] 陈乃金[1] HE Ruixiang;CHEN Naijin(College of Computer and Information Science, Anhui Polytechnic University, Wuhu, Anhui 241000, China)

机构地区：[1]安徽工程大学计算机与信息学院,安徽芜湖241000

出　　处：《计算机工程与应用》2017年第14期65-69,75,共6页Computer Engineering and Applications

基　　金：安徽省自然科学基金(No.1408085MF124);安徽省高校省级自然科学基金重点项目(No.kj2015A003);安徽工程大学国家自然科学预研基金

摘　　要：粗粒度可重构单元阵列硬件任务的贪心映射是可重构计算要解决的核心问题。不同的阵列具有不同的硬件约束条件,针对行路由粗粒度可重构单元阵列提出一种广度贪心映射算法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.

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

分 类 号：TP302[自动化与计算机技术—计算机系统结构]