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

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

摘要/Abstract

摘要：

针对二维可重构单元阵列(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 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 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.

Key words: RCA, data flow graph, bypass node, critical condition, temporal partitioning and mapping

陈乃金,冯志勇,江建慧. 用于二维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.

图/表 22

图1

表1

表2

图2

图3

图4

图5

图6

图7

表3

表4

表5

表6

表7

图8

表8

表9

表10

表11

表12

表13

表14

参考文献 21

[1]	CARDOSO J M P ， DINIZ P C ， WEINHARDT M . Compiling for reconfigurable computing:a survey[J]. ACM Computing Surveys， 2010，42(4): 1301-1365.
[2]	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.
[3]	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.
[4]	GOLDSTEIN S C ， SCHMIT H ， BUDIU M ，et al. PipeRench:a reconfigurable architecture and compiler[J]. Computer， 2000，33(4): 70-77.
[5]	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.
[6]	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.
[7]	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.
[8]	窦勇，邬贵明，徐进辉，等. 支持循环自流水的粗粒度可重构阵列体系结构[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.
[9]	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.
[10]	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.
[11]	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.
[12]	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.
[13]	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.
[14]	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.
[15]	王大伟，窦勇，李思昆 . 核心循环到粗粒度可重构体系结构的流水化映射[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.
[16]	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.
[17]	于苏东 . 可重构处理器的软硬件协同设计研究[D]. 北京:清华大学， 2009. YU S D . Research on the Software/Hardware Co-design for Reconfigurable Processor[D]. Beijing:Tsinghua University， 2009.
[18]	魏少军，刘雷波，尹首一 . 可重构计算处理器技术[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.
[19]	孙康 . 可重构计算相关技术研究[D]. 杭州:浙江大学， 2007. SUN K . Research on Reconfigurable Computing Technologies[D]. Hangzhou:Zhejiang University， 2007.
[20]	陈乃金，江建慧 . 融合面积估算和多目标优化的硬件任务划分算法[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.
[21]	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.

CGRA名称	RC互连方式	行流水	RC间数据跨层传输	RCA块内数据通信大致模型
RipeRench	一维总线+RC上下NN行路由互连	支持	允许跨层	总线+PR+ALU+NN行互连
REMARC	两维总线+RC上下左右NN互连	支持	允许跨层	总线+数据RAM+ALU+NN
ADRES	RC上下左右NN+跨行（列）全互连	支持	允许跨层	FU+RF+NN
Morphosys	RC上下左右NN+跨行（列）全互连	支持	允许跨层	ALU+MULT+Shift+RF
LEAP	RC上下左右NN+开关路由器互连	支持	允许跨层	MPE+CPE+节点路由
REMUS	RC上下NN行路由互连	支持	不允许跨层	ALU+NN行路由

划分基准	CGRA	I_ID	S_SD	δ	划分基准	CGRA	I_ID	S_SD	δ
SODE	PipeRench	34	6	28	EWF6	PipeRench	1 342	39	1 303
	REMARC	32	6	26		REMARC	1 272	39	1 233
	ADRES	3	6	?3		ADRES	134	39	95
	LEAP	12	6	6		LEAP	536	39	497
FEAL	PipeRench	208	21	187	MATRIX4	PipeRench	638	25	613
	REMARC	200	21	179		REMARC	604	25	579
	ADRES	18	21	?3		ADRES	56	25	31
	LEAP	72	21	51		LEAP	224	25	199
FFT4	PipeRench	68	6	62	FDCT6	PipeRench	240	50	190
	REMARC	64	6	58		REMARC	228	50	178
	ADRES	8	6	2		ADRES	30	50	?20
	LEAP	24	6	18		LEAP	120	50	70
FFT8	PipeRench	272	9	263	MEDIAN	PipeRench	318	9	309
	REMARC	256	9	247		REMARC	300	9	291
	ADRES	24	9	15		ADRES	29	9	20
	LEAP	96	9	87		LEAP	124	9	115

划分基准	加法	减法	乘法	取模	逻辑比较	异或	左移	右移	等于	小于	小于等于	总数
SODE	2	2	6	?	1	?	?	?	?	?	?	11
FEAL	6	?	?	4	?	20	4	?	?	?	?	34
FFT4	4	4	4	?	?	?	?	?	?	?	?	12
FFT8	12	12	12	?	?	?	?	?	?	?	?	36
EWF6	168	?	36	?	?	?	?	?	?	?	?	204
FDCT6	78	78	96	?	?	?	?	?	?	?	?	252
MEDIAN	?	?	?	?	19	?	?	?	?	?	?	19
MATRIX4	48	?	64	?	?	?	?	?	?	?	?	112
MATRIX8	512	?	512	?	?	?	?	?	?	?	?	1 024
IDCT	18	14	11	?	?	?	1	10	?	?	?	54
DCT32	222	128	129	?	?	?	?	83	?	?	?	562
H.264	141	181	180	?	?	?	4	27	4	76	51	664
HHLFLIC	172	132	212	?	?	?	36	24	?	?	20	596
HHLFLC	152	212	136	?	?	?	12	60	?	52	24	648

划分基准		RCA_5× ₅			RCA₈_× ₈
划分基准	PTBNA	PTBA	△%	PTBNA	PTBA	△%
FEAL	523.139 282	529.768 677	+1.3	425.377 899	465.154 358	+9.4
EWF6	2 080.469 727	2 297.506 836	+10.4	1 659.671 875	1 871.812 866	+12.8
FDCT6	2 556.156 982	2 622.451 172	+2.6	1 900.166 870	1 933.313 843	+1.7
MATRIX4	1 149.136 108	1 333.026 367	+16.0	943.695 923	1 033.192 871	+9.5
MATRIX8	9 952.004 883	11 321.160 156	+13.8	7 170.777 832	9 722.280 273	+35.6
HHLFLIC	5 808.455 078	6 784.256 348	+16.8	4 388.795 898	4 897.500 488	+11.6
HHLFLC	6 539.376 465	7 253.467 773	+10.9	5 031.873 047	5 575.484 375	+10.8
平均△%	?	?	+10.3	?	?	+13.1

划分基准			M						N₁						N₂
划分基准	PTBNA		PTBA		△%		PTBNA		PTBA		△%		PTBNA		PTBA		△%
FEAL	3	2	3	2	?	?	13	10	12	4	?7.7	?60	12	10	11	4	?8.3	?60
EWF6	9	5	10	5	+11.1	?	123	102	117	83	?4.9	?18.6	101	93	95	67	?5.9	?28
FDCT6	11	5	11	5	?	?	102	70	101	64	?1.0	?8.6	98	68	97	62	?1.0	?8.8
MATRIX4	5	3	6	3	+20	?	53	52	53	40	?	?23.1	53	52	53	40	?	?23.1
MATRIX8	41	16	48	24	+17.1	+50	596	567	502	419	?15.8	?26.1	596	567	502	419	?15.8	?26.1
HHLFLIC	24	11	29	12	+20.8	+9.1	348	302	264	213	?24.1	?29.5	326	296	241	206	?26.1	?30.4
HHLFLC	28	14	31	14	+10.7	?	359	334	289	210	?19.5	?37.1	353	333	284	203	?19.5	?39.0
平均△%	?	?	?	?	+11.4	+8.4	?	?	?	?	?10.4	?29.0	?	?	?	?	?10.9	?30.8