多叉树数据流图粗粒度可重构单元阵列映射算法  

Mapping Algorithm of Coarse Grained Reconfigurable Cell Array for Multi- branch Tree Data Flow Graph

作　　者：陈乃金[1,2] 江建慧[3] 

机构地区：[1]安徽工程大学计算机与信息学院,芜湖241000 [2]天津大学计算机科学与技术学院,天津300072 [3]同济大学软件学院,上海201804

出　　处：《计算机辅助设计与图形学学报》2016年第7期1180-1187,共8页Journal of Computer-Aided Design & Computer Graphics

基　　金：国家“八六三”高技术研究发展计划(2009AA011705,2013AA013204);国家自然科学基金重点项目(61432017);安徽省自然科学基金(1408085MF124);安徽省高校自然科学基金重点项目(KJ2015A003);芜湖市科技计划自然科学基金(芜科计字[2012]94号);安徽工程大学国家自然科学预研基金

摘　　要：针对多叉树任务数据流图的划分映射问题,基于粗粒度行并行可重构架构,提出一种行列剪枝映射算法.首先分析和比较了二维没有跳变近邻点点互连和行并行互连的可重构单元阵列的映射性能,通过3种类型的一次循环四阶多叉树映射实验结果表明(RCA4×4),行并行架构执行总周期最大减少了63个周期,最少减少了20个周期;然后设计实现了行列剪枝映射算法,先按行剪枝映射,再对已映射节点的依赖后继进行列剪枝映射,在满足面积和互连等约束下考虑运算节点层次和入度等因素构造了排队函数,通过该函数值动态调整就绪列表节点的调度次序.实验结果表明,与放置路由算法相比,文中算法执行时间平均减少了15.7%(RCA4×4)和18.4%(RCA5×5);与分裂压缩内核算法相比,该算法执行时间平均减少了30.0%(RCA4×4)和29.8%(RCA5×5):从而验证了文中提出解决多叉树行并行可重构单元阵列及映射算法有效性.To cope with the problem of multi-branch tree temporal partitioning and mapping, this paper presented a row column pruning mapping(RCPM) algorithm based on grained row parallel(RP) reconfigurable architectures. Firstly, the mapping performances of two-dimensional no hop point-to-point near neighbor interconnect and RP interconnect reconfigurable cell array(RCA) were analysized and compared by three kinds of one loop four orders multi- branch trees. As for RP, experimental results show that the maximum reduction cycles are 63 and the minimum reduction are 20; Secondly, RCPM had been designed and implemented. The nodes were mapped by row pruning at first, the successor of mapped nodes were mapped by column pruning. In the constraints of areas and interconnects, in order to adjust dynamically the lists of node scheduling order, the queuing function was constructed with the guideline of the levels and the indegrees of computing nodes. The experiment results show that the average execution total cycles of RCPM decreased by 15.7%(RCA4×4) and18.4%(RCA5×5) comparing with place and router(PR) mapping algorithm. Comparing with split-push kernel mapping(SPKM)algorithm, the average execution total cycles of RCPM decreased by 30.0%(RCA4×4) and 29.8%(RCA5×5). Experimental evaluation confirms the efficiency of our approach in order to solving multi-branch trees row parallel RCA and mapping algorithm.

关 键 词：多叉树 行并行 可重构单元阵列 时域映射 资源约束 

分 类 号：TP18[自动化与计算机技术—控制理论与控制工程]