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

陈乃金; 冯志勇; 江建慧

doi:10.11959/j.issn.1000-436x.2015132

您当前的位置：

首页 >

文章列表页 >

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

学术论文 | 更新时间：2024-06-05

- 用于二维RCA跨层数据传输的旁节点无冗余添加算法
- Bypass node non-redundant adding algorithm for crossing-level data transmission in two-dimension reconfigurable cell array
- 通信学报 2015年36卷第4期页码：35-51
- 作者机构：
  
  1. 天津大学计算机科学与技术学院，天津300072
  2. 安徽工程大学计算机与信息学院，安徽芜湖241000
  3. 同济大学软件学院，上海 201804
  1. 天津大学计算机科学与技术学院，天津300072；2.安徽工程大学计算机与信息学院，安徽芜湖241000；3.同济大学软件学院，上海 201804
- 作者简介：
  
  [ "陈乃金（1972-），男，安徽合肥人，天津大学博士后，安徽工程大学副教授、硕士生导师，主要研究方向为可重构计算、时域划分与映射、VLSI/SoC测试与容错等。" ]
  [ "冯志勇（1965-），男，内蒙古呼和浩特人，博士，天津大学教授、博士生导师，主要研究方向为语义大数据表示与存储等。" ]
  [ "江建慧（1964-），男，浙江淳安人，博士，同济大学教授、博士生导师，主要研究方向为可信系统与网络、软件可靠性工程、VLSI/SoC测试与容错等。" ]
- 基金信息：
  
  国家高技术研究发展计划（“863”计划）基金资助项目(2009AA011705);国家高技术研究发展计划(863计划)基金资助项目(2013AA013204);安徽省自然科学基金资助项目(1408085MF124);国家自然科学基金资助重点项目(61432017);)湖市科技计划自然科学基金资助项目(芜科计字[2012]95号)
- DOI：10.11959/j.issn.1000-436x.2015132
  中图分类号： TP302
- 网络出版日期：2015-04，
  
  纸质出版日期：2015-04-25
- 稿件说明：
移动端阅览
陈乃金, 冯志勇, 江建慧. 用于二维RCA跨层数据传输的旁节点无冗余添加算法[J]. 通信学报, 2015,36(4):35-51.

Nai-jin CHEN, Zhi-yong FENG, Jian-hui JIANG. Bypass node non-redundant adding algorithm for crossing-level data transmission in two-dimension reconfigurable cell array[J]. Journal on communications, 2015, 36(4): 35-51.
陈乃金, 冯志勇, 江建慧. 用于二维RCA跨层数据传输的旁节点无冗余添加算法[J]. 通信学报, 2015,36(4):35-51. DOI： 10.11959/j.issn.1000-436x.2015132.

Nai-jin CHEN, Zhi-yong FENG, Jian-hui JIANG. Bypass node non-redundant adding algorithm for crossing-level data transmission in two-dimension reconfigurable cell array[J]. Journal on communications, 2015, 36(4): 35-51. DOI： 10.11959/j.issn.1000-436x.2015132.

摘要

针对二维可重构单元阵列(RCA)硬件任务的跨层数据传输问题，提出了一种前序遍历回溯旁节点添加算法。该算法针对跨层输入树、跨层输出树2种类型的数据流图，保持了原有运算节点之间的逻辑关系，实现了旁节点的无冗余添加。给出了动态可重构系统划分映射的量化评估指标体系和流水化模型，给出了添加旁节点映射的临界条件。实验结果表明，基于相同的系统结构和划分映射算法，在满足临界条件的情况下，与不加旁节点映射算法相比，加旁节点映射在划分模块数，非原始输入输出次数、配置时间、总执行周期、功耗等方面均获得了较好的改进；与已有的先进算法相比，文中算法平均执行总周期降低了23.3%(RCA

5×5

)和30.5%(RCA

8×8

)，平均消耗功耗降低了15.7%(

5×5

)和18.6%(RCA

8×8

)，从而验证了所提方法的合理性和有效性。

Abstract

As for the problem of hardware task crossing-level data transmission，a preorder traversing backtracking adding_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 partit

ioning 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 adding_bypass_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 output 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%(RCA

5×5

)，30.5%(RCA

8×8

)，and the less average power consumption by 15.7%(RCA

5×5

)，18.6%(RCA

8×8

) than previous advanced split-push kernel mapping(SPKM).PTBA has rationality and effectiveness.

关键词

Keywords

references

CARDOSO J M P ， DINIZ P C ， WEINHARDT M . Compiling for reconfigurable computing:a survey [J ] . ACM Computing Surveys ， 2010 ， 42 ( 4 ): 1301 - 1365 .

SALVADOR R ， OTERO A ， MORA J ， et al . Self-reconfigurable evolvable hardware system for adaptive image processing [J ] . IEEE Transactions on Computers ， 2013 ， 62 ( 8 ): 1481 - 1493 .

AHN Y ， HAN K ， LEE G ， et al . SoCDAL:system-on-chip design accelerator [J ] . ACM Transactions on Design Automation of Electronic Systems ， 2008 ， 13 ( 1 ): 171 - 176 .

GOLDSTEIN S C ， SCHMIT H ， BUDIU M ， et al . PipeRench:a reconfigurable architecture and compiler [J ] . Computer ， 2000 ， 33 ( 4 ): 70 - 77 .

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 .

MEI B ， VERNALDE S ， VERKEST D ， et al . ADRES:an architecture with tightly coupled VLIW processor and coarse-grained reconfigurable matrix [A ] . Proceedings of 13th International Conference on Field Programmable Logic and Application [C ] . Lisbon Portugal，Springer Press ， 2003 . 61 - 70 .

SINGH H ， LEE M H ， LU G M ， et al . MorphoSys:an integrated reconfigureable system for data parallel and computation intensive applications [J ] . IEEE Transactions on Computers ， 2000 ， 49 ( 5 ): 465 - 481 .

窦勇，邬贵明，徐进辉，等 . 支持循环自流水的粗粒度可重构阵列体系结构 [J ] . 中国科学:信息科学， 2008 ， 38 ( 4 ): 579 - 591 .

DOU Y ， WU G M ， XU J H ， et al . A coarse-grained reconfigurable computing architecture with loop self-pipelining [J ] . Science China Information Sciences ， 2008 ， 38 ( 4 ): 579 - 591 .

MEI B ， VERNALDE S ， VERKEST D ， et al . DRESC:a retargetable compiler for coarse-grained reconfigurable architectures [A ] . Proceedings of 2002 IEEE International Conference on Field-Programmable Technology (FPT) [C ] . Hong Kong，China ， 2002 . 166 - 173 .

CARDOSO J M P ， WEINHARDT M . XPP-VC:AC compiler with temporal partitioning for the PACT-XPP architecture [A ] . Proceedings of 12th International Conference on Field-Programmable Logic and Applications (FPT) [C ] . Berlin ， 2002 . 864 - 874 .

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 .

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 ， 5 ( 30 ): 637 - 650 .

BEREKOVIC M ， KANSTEIN A ， MEI B ， et al . Mapping of nomadic multimedia applications on the ADRES reconfigurable array processor [J ] . Microprocessors and Microsystems ， 2009 ， 33 ( 4 ): 290 - 294 .

KIM W ， CHOI Y ， PARK H . Fast modulo scheduler utilizing patternized routes for coarse-grained reconfigurable architectures [J ] . ACM Transactions on Architecture and Code Optimization ， 2013 ， 10 ( 4 ): 1 - 58 .

王大伟，窦勇，李思昆 . 核心循环到粗粒度可重构体系结构的流水化映射 [J ] . 计算机学报， 2009 ， 32 ( 6 ): 1089 - 1099 .

WANG D W ， DOU Y ， LI S K . Loop kernel pipelining mapping onto coarse-grained reconfigurable architectures [J ] . Chinese Journal of Computers ， 2009 ， 32 ( 6 ): 1089 - 1099 .

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 ): 58:1 - 58:22 .

于苏东 . 可重构处理器的软硬件协同设计研究 [D ] . 北京:清华大学， 2009 .

YU S D . Research on the Software/Hardware Co-design for Reconfigurable Processor [D ] . Beijing:Tsinghua University ， 2009 .

魏少军，刘雷波，尹首一 . 可重构计算处理器技术 [J ] . 中国科学:信息科学， 2012 ， 42 ( 12 ): 1559 - 1576 .

WEI S J ， LIU L B ， YIN S Y . Key techniques of reconfigurable computing processor [J ] . Science China Information Sciences ， 2012 ， 42 ( 12 ): 1559 - 1576 .

孙康 . 可重构计算相关技术研究 [D ] . 杭州:浙江大学， 2007 .

SUN K . Research on Reconfigurable Computing Technologies [D ] . Hangzhou:Zhejiang University ， 2007 .

陈乃金，江建慧 . 融合面积估算和多目标优化的硬件任务划分算法 [J ] . 通信学报， 2013 ， 34 ( 2 ): 40 - 55 .

CHEN N J ， JIANG J H . Hardware-task partitioning algorithm merged area estimation with multi-objective optimization [J ] . Journal on Communications ， 2013 ， 34 ( 2 ): 40 - 55 .

EL-ARABY E ， GONZALEZ I，EL-GHAZAWI T . Virtualizing and sharing reconfigurable resources in high-performance reconfigurable computing systems [A ] . Proceedings of the Second International Workshop on High-Performance Reconfigurable Computing Technology and Applications [C ] . Austin，USA ， 2008 . 1 - 8 .

浏览量

687

下载量

CSCD

文章被引用时，请邮件提醒。

提交

工具集

关联资源

暂无数据