一种粗粒度可重构体系结构多目标优化映射算法

doi:10.3969/j.issn.0372-2112.2015.11.003

电子学报 ›› 2015, Vol. 43 ›› Issue (11): 2151-2160.DOI: 10.3969/j.issn.0372-2112.2015.11.003

一种粗粒度可重构体系结构多目标优化映射算法

陈乃金^1,3, 江建慧²

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

收稿日期:2015-02-28 修回日期:2015-06-05 出版日期:2015-11-25
- 作者简介:
- 陈乃金 男,1972年生于安徽合肥,天津大学博士后,安徽工程大学副教授,硕士生导师,主要研究方向为可重构计算、时域划分与映射、VLSI/SoC测试与容错等.E-mail:86naijinchen@tongji.edu.cn;江建慧 男,1964年生于浙江淳安,博士,同济大学教授,博士生导师,主要研究方向为VLSI/SoC测试与容错、可信系统与网络、软件可靠性工程等.E-mail:jhjiang@tongji.edu.cn
- 基金资助:
- 国家863高技术研究发展计划 (No.2009AA011705,No.2013AA013204); 国家自然科学基金重点项目 (No.61432017); 安徽省自然科学基金 (No.1408085MF124); 芜湖市科技计划自然科学基金 (No.芜科计字[2012]94号); 安徽工程大学国家自然科学预研基金; 安徽省高校省级自然科学基金重点项目 (No.Kj2015A003)

A Multi-Objective Optimization Mapping Algorithm for Coarse Grained Reconfigurable Architectures

CHEN Nai-jin^1,3, JIANG Jian-hui²

1. College of Computer and Information Science, Anhui Polytechnic University, Wuhu, Anhui 241000, China;
2. School of Software Engineering, Tongji University, Shanghai 201804, China;
3. School of Computer Science and Technology, Tianjin University, Tianjin 300072, China

Received:2015-02-28 Revised:2015-06-05 Online:2015-11-25 Published:2015-11-25

摘要/Abstract

摘要：

针对多约束下的行流水粗粒度可重构体系结构的硬件任务划分映射问题,提出了一种多目标优化映射算法.该算法根据运算节点执行时延、依赖度等因素构造了累加概率权值函数,在满足可重构单元面积和互连等约束下,通过该函数值动态调整就绪节点的映射调度次序,当一块可重构单元阵列当前行映射完毕后,就自动换行,当一块阵列被填满,就切换到下一块,当一个数据流图映射完毕后,就自动计算划分块数等参数.实验结果表明,与层贪婪映射算法相比,文中算法平均执行总周期降低了8.4%(RCA_4×4)和5.3%(RCA_6×6),与分裂压缩内核映射算法相比,文中算法平均执行总周期降低了20.6%(RCA_4×4)和21.0%(RCA_6×6),从而验证了文中提出算法的有效性.

关键词: 可重构单元阵列, 时域映射, 累加概率权值, 异步计算时延, 资源约束

Abstract:

Based on row pipelining coarse grained reconfigurable architecture(CGRA),we presented MOM(multi-objective optimization mapping) algorithm to solve the multi-constraints hardware task partitioning-mapping problem.The cumulative probability weight function was constructed by the execution delay of computing nodes and the dependence between two nodes,etc.With the constraints of reconfigurable cell area and interconnection,the proposed algorithm could adjust dynamically the scheduling order of the ready nodes by thefunction values.When a row of the RCA was mapped completely,MOM began on a new row.When the RCA was filled,MOM switched to the next one.When a DFG(data flow graph) was mapped completely,the number of modules and etc were calculated automatically in MOM.Experiment results show that the average execution total cycles of MOM decrease by 8.4%(RCA_4×4) and 5.3%(RCA_6×6) comparing with LBGM(level based greedy mapping) algorithm.Comparing with SPKM(split-push kernel mapping) algorithm,the average execution total cycles of MOM decrease by 20.6%(RCA_4×4) and 21%(RCA_6×6).Experimental evaluation confirms the efficiency of our approach.

Key words: reconfigurable cell array, temporal mapping, accumulation probability weight, asynchronous computation delay, resource constraint

中图分类号:

TP302

陈乃金, 江建慧. 一种粗粒度可重构体系结构多目标优化映射算法[J]. 电子学报, 2015, 43(11): 2151-2160.

CHEN Nai-jin, JIANG Jian-hui. A Multi-Objective Optimization Mapping Algorithm for Coarse Grained Reconfigurable Architectures[J]. Acta Electronica Sinica, 2015, 43(11): 2151-2160.

参考文献

[1] Cardoso J M P,Diniz C D,Weinhardt M.Compiling for reconfigurable computing:a survey[J]. ACM Computing Surveys,2010,42(4):1301-1365.
[2] Yoon J W,Lee J,Park S,et al. Architecture customization of on-chip reconfigurable accelerators[J]. ACM Transactions on Design Automation of Electronic Systems,2013,18(4):52:1-52:22.
[3] Zhao X,Erdogan A T,Arslan T.High-efficiency customized coarse-grained dynamically reconfigurable architecture for JPEG2000[J]. IEEE Transactions on Very Large Scale Integration Systems,2013,21(12):2343-2348.
[4] Kim Y,Lee J,Shrivastava A,et al.High throughput data mapping for coarse-grained reconfigurable architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2011,30(11):1599-1609.
[5] 杨子煜,严明,王大伟,等.面向CGRA循环流水映射的数据并行优化[J]. 计算机学报,2013,36(6):1280-1289. Yang Ziyu,Yan Ming,Wang Dawei,et al.Data parallelism optimization for the CGRA loop pipelining mapping[J]. Chinese Journal of Computers,2013,36(6):1280-1289.(in Chinese)
[6] Han K,Lee G,Choi K.Software-level approaches for tolerating transient faults in a coarse-grained reconfigurable architecture[J]. IEEE Transactions on Dependable and Secure Computing,2014,11(4):392-398.
[7] Yoon J W,Shrivastava A,Park S,et al.A graph drawing based spatial mapping algorithm for coarse-grained reconfigurable architectures[J]. IEEE Transactions on Very Large Scale Integration Systems,2009,17(11):1565-1578.
[8] Ferreira R S,Cardoso J M P,Damiany A,et al.Fast placement and routing by extending coarse-grained reconfigurable arrays with Omega Networks[J]. Journal of Systems Architecture,2011,57(8):761-777.
[9] Lee G,Choi K,Dutt N D.Mapping multi-domain applications onto coarse-grained reconfigurable architectures[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2011,30(5):637-650.
[10] Ansaloni G,Tanimura K,Pozzi L,et al.Integrated kernel partitioning and scheduling for coarse-grained reconfigurable arrays[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems,2012,31(12):1803-1816.
[11] Chen L,Mitra T.Graph minor approach for application mapping on CGRAs[J]. ACM Transactions on Reconfigurable Technology and Systems,2014,7(3):21:1-21:25.
[12] Miyamori T,Olukotun K,Budiu M,et al.REMARC:reconfigurable multimedia array coprocessor[J]. IEICE Transactions on Information and Systems,1999,E82-D(2):389-397.
[13] Goldstein S C,Schmit H,Budiu M,et al.PipeRench:A reconfigurable architecture and compiler[J]. Computer,2000,33(4):70-77.
[14] 魏少军,刘雷波,尹首一.可重构计算处理器技术[J]. 中国科学:信息科学,2012,42(12):1559-1576. Wei Shaojun,Liu Leibo,Yin Shouyi.Key techniques of reconfigurable computing processor[J]. Science China:Information Sciences,2012,42(12):1559-1576.(in Chinese)
[15] 陈乃金,江建慧,陈昕,等.一种考虑执行延迟最小化和资源约束的改进层划分算法[J]. 电子学报,2012,40(5):1055-1066. Chen Naijin,Jiang Jianhui,Chen Xin,et al.An improved level partitioning algorithm considering minimum execution delay and resource restraints[J]. Acta Electronica Sinica,2012,40(5):1055-1066.(in Chinese)
[16] 陈乃金,冯志勇,江建慧.用于二维RCA跨层数据传输的旁节点无冗余添加算法[J]. 通信学报,2015,36(4):2015132:1-17. Chen Naijin,Feng Zhiyong,Jiang Jianhui.Bypass node non-redundant adding algorithm for crossing-level data transmission in two-dimension reconfigurable cell array[J]. Journal on Communications,2015,36(4):2015132:1-17.(in Chinese)

一种粗粒度可重构体系结构多目标优化映射算法

A Multi-Objective Optimization Mapping Algorithm for Coarse Grained Reconfigurable Architectures

PDF

可视化

摘要/Abstract

引用本文

使用本文

参考文献

相关文章 4

编辑推荐

Metrics

[1]	王宏伟, 连捷, 夏浩. 通讯资源受限网络系统的非均匀采样切换控制[J]. 电子学报, 2018, 46(11): 2597-2603.
[2]	庞善臣. 一种基于资源约束的工作流建模及分析方法[J]. 电子学报, 2012, 40(8): 1497-1502.
[3]	陈乃金;;江建慧;陈昕;周洲;徐莹. 一种考虑执行延迟最小化和资源约束的改进层划分算法[J]. 电子学报, 2012, 40(5): 1055-1066.
[4]	刘胜, 范玉顺. 资源约束下实例在工作流中停留时间分析方法[J]. 电子学报, 2005, 33(10): 1867-1871.