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

摘要

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 architec-tures. 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 ar-eas 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 evalua-tion confirms the efficiency of our approach in order to solving multi-branch trees row parallel RCA and mapping algorithm.%针对多叉树任务数据流图的划分映射问题，基于粗粒度行并行可重构架构，提出一种行列剪枝映射算法.首先分析和比较了二维没有跳变近邻点点互连和行并行互连的可重构单元阵列的映射性能，通过3种类型的一次循环四阶多叉树映射实验结果表明(RCA4×4)，行并行架构执行总周期最大减少了63个周期，最少减少了20个周期；然后设计实现了行列剪枝映射算法，先按行剪枝映射，再对已映射节点的依赖后继进行列剪枝映射，在满足面积和互连等约束下考虑运算节点层次和入度等因素构造了排队函数，通过该函数值动态调整就绪列表节点的调度次序.实验结果表明，与放置路由算法相比，文中算法执行时间平均减少了15.7%(RCA4×4)和18.4%(RCA5×5)；与分裂压缩内核算法相比，该算法执行时间平均减少了30.0%(RCA4×4)和29.8%(RCA5×5)：从而验证了文中提出解决多叉树行并行可重构单元阵列及映射算法有效性.