用于二维RCA跨层数据传输的旁节点无冗余添加算法  

Bypass node non-redundant adding algorithm for crossing-level data transmission in two-dimension reconfigurable cell array

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

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

出　　处：《通信学报》2015年第4期35-51,共17页Journal on Communications

基　　金：国家高技术研究发展计划("863"计划)基金资助项目(2009AA011705;2013AA013204);安徽省自然科学基金资助项目(1408085MF124);国家自然科学基金资助重点项目(61432017);芜湖市科技计划自然科学基金资助项目(芜科计字[2012]95号)~~

摘　　要：针对二维可重构单元阵列(RCA)硬件任务的跨层数据传输问题,提出了一种前序遍历回溯旁节点添加算法。该算法针对跨层输入树、跨层输出树2种类型的数据流图,保持了原有运算节点之间的逻辑关系,实现了旁节点的无冗余添加。给出了动态可重构系统划分映射的量化评估指标体系和流水化模型,给出了添加旁节点映射的临界条件。实验结果表明,基于相同的系统结构和划分映射算法,在满足临界条件的情况下,与不加旁节点映射算法相比,加旁节点映射在划分模块数,非原始输入输出次数、配置时间、总执行周期、功耗等方面均获得了较好的改进;与已有的先进算法相比,文中算法平均执行总周期降低了23.3%(RCA5×5)和30.5%(RCA8×8),平均消耗功耗降低了15.7%(RCA5×5)和18.6%(RCA8×8),从而验证了所提方法的合理性和有效性。As for the problem of hardware task crossing-level data transmission, a preorder traversing backtracking add- ing_bypass_node （PTBA） algorithm is presented which maintains logic relation among original computing nodes and does not add redundancy nodes based on data flow graph with crossing-level-in-tree（CLIT） and crossing-level-out- tree （CLOT）.The pipelined model of partitioning mapping and the quantitative evaluation indexes are presented for the dynamic reconfigurable system. The critical condition of PTBA mapping is proposed. Compared with preorder traversing backtracking no addingbypass node （PTBNA） mapping, and under the premise of critical condition,experimental results show PTBA mapping can improve the number of modules, the number of non-original input times and non-original out- put times, the total execution delay and powers of all partitioning based on the same system architecture and partitioning mapping algorithm. The proposed algorithm obtains the less average execution total cycles by 23.3%（RCA5×5）, 30.5%（RCA8×8）, and the less average power consumption by 15.7%（RCA5×5）,1 8.6%（RCA8×8） than previous advanced split-push kernel mapping（SPKM）. PTBA has rationality and effectiveness.

关 键 词：可重构单元阵列 数据流图 旁节点 临界条件 时域划分与映射 

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