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

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

Abstract

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

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.

Figures/Tables 22

References 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.

Metrics

Recommended 0

No Suggested Reading articles found!

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

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

RichHTML

PDF

Knowledge

Cited

Abstract

Cite this article

share this article

Figures/Tables 22

References 21

Related Articles 4

Metrics

Recommended 0

划分基准	S_SD						C_CON						T_TOTAL
划分基准	PTBNA		PTBA		△%		PTBNA		PTBA		△%		PTBNA		PTBA		△%
FEAL	25	24	25	21	?	?12.5	85	68	87	80	+2.4	+17.6	140	120	141	123	+0.7	+2.5
EWF6	63	38	71	56	+12.7	+47.4	357	289	404	353	+13.2	+22.1	607	500	656	559	+8.1	+11.8
FDCT6	81	57	85	57	+4.9	?	439	337	459	347	+4.6	+3	740	583	763	587	+3.1	+0.7
MATRIX4	39	27	45	32	+15.4	+18.5	197	163	234	190	+18.8	+16.6	361	314	404	334	+11.9	+6.4
MATRIX8	318	199	399	322	+25.5	+61.8	1 721	1 296	2 002	1 894	+16.3	+46.1	3 179	2 606	3 447	3 179	+8.4	+22.0
HHLFLIC	205	131	234	157	+14.1	+19.8	1 004	783	1 206	915	+20.1	+16.9	1 807	1 474	1 953	1 542	+8.1	+4.6
HHLFLC	198	139	235	168	+18.7	+20.9	1 124	886	1 284	1 050	+14.2	+18.5	1 972	1 653	2 100	1 719	+6.5	+4.0
平均△%	?	?	?	?	+13.0	+22.3	?	?	?	?	+12.8	+20.1	?	?	?	?	+6.7	+7.4

算法	M	N₁	N₂	S_SD	C_CON	T_TOTAL	P_POWER
PTNBA	2	9	9	6	21	49.5	335.831 738
PTBA	2	6	6	8	27	54.5	355.719 956

划分基准		RCA_5× ₅			RCA_8× ₈
划分基准	SPKM	PTBA	△%	SPKM	PTBA	△%
SODE	3	0	?100	3	0	?100
FFT4	12	0	?100	12	0	?100
FFT8	25	0	?100	21	0	?100
MEDIAN	11	0	?100	11	0	?100
IDCT	24	0	?100	25	0	?100
DCT32	85	0	?100	242	0	?100
H.264	366	0	?100	539	0	?100
平均△%	?	?	?100	?	?	?100

[1]	Youheng DONG, Geng ZHAO, Yingjie MA. Two-dimensional pseudo-random coupled map lattices system based on partitioned elementary cellular automata and its dynamic properties [J]. Journal on Communications, 2022, 43(1): 71-82.
[2]	Fuhong MIN,Hanyuan MA,Yaoda WANG. Surface sliding mode controller for chaotic oscillation in power system with power disturbance [J]. Journal on Communications, 2019, 40(1): 119-129.
[3]	Yi-bo ZHAO,Xiao-shu LUO,Dao-yang ZHANG,Jiu-chao FENG. Extending locked range of digital phase-locked loop by prediction estimation of states [J]. Journal on Communications, 2008, 29(9): 68-72.
[4]	Yong-ming TAN,Li-hu DENG. Chaotic dynamics behave from sampling phase-detector digital synthesizer loop [J]. Journal on Communications, 2006, 27(4): 49-53.

划分基准		RCA_5× ₅			RCA₈_× ₈
划分基准	PTBNA	PTBA	△%	PTBNA	PTBA	△%
SODE	290.305 878	176.024 368	?39.4	310.130 747	185.941 788	?40.0
FFT4	295.316 193	184.349 380	?37.6	315.151 062	194.266 800	?38.4
FFT8	650.756 165	556.362 854	?14.5	562.912 170	334.402 496	?40.6
MEDIAN	565.580 811	477.816 925	?15.5	605.250 549	389.999 664	?35.6
IDCT	740.941 772	643.233 765	?13.2	653.097 839	538.842 957	?17.5
DCT32	5 755.701 172	5 674.566 406	?1.4	4 345.958 984	4 341.089 355	?0.1
H.264	7 795.503 418	7 684.688 477	?1.4	7 024.743 164	5 925.490 723	?15.6
平均△%	?	?	?17.6	?	?	?26.8

划分基准			M						N₁						N₂
划分基准	PTBNA		PTBA		△%		PTBNA		PTBA		△%		PTBNA		PTBA		△%
SODE	2	2	1	1	?50	?50	2	2	0	0	?100	?100	2	2	0	0	?100	?100
FFT4	2	2	1	1	?50	?50	4	4	0	0	?100	?100	4	4	0	0	?100	?100
FFT8	4	3	3	1	?25	?66.7	18	16	10	0	?44.4	?100	18	16	9	0	?50	?100
MEDIAN	4	4	3	2	?25	?50	12	12	7	2	?41.7	?83.3	12	12	7	2	?41.7	?83.3
IDCT	4	3	3	2	?25	?33.3	20	15	14	8	?30	?46.7	20	15	14	8	?30	?46.7
DCT32	25	12	24	11	?4	?8.3	218	176	209	151	?4.1	?14.2	193	163	187	140	?3.1	?14.1
H.264	38	29	35	17	?7.9	?41.4	419	377	346	239	?17.4	?36.6	367	340	290	211	?21	?37.9
平均△%	?	?	?	?	?26.7	?42.8	?	?	?	?	?48.2	?68.7	?	?	?	?	?49.4	?68.9

划分基准			S_SD						C_CON						T_TOTAL
划分基准	PTBNA		PTBA		△%		PTBNA		PTBA		△%		PTBNA		PTBA		△%
SODE	6	6	6	6	?	?	45	45	29	29	?35.6	?35.6	62	62	44	44	?29	?29
FFT4	6	6	6	6	?	?	46	46	31	31	?32.6	?32.6	63	63	44	44	?30.2	?30.2
FFT8	13	9	14	9	+7.7	?	104	87	94	61	?9.6	?30	149	126	132	84	?11.4	?33.3
MEDIAN	9	9	12	9	+33.3	?	87	87	79	65	?9.2	?25.3	117	117	107	85	?8.5	?27.4
IDCT	20	14	18	18	?10	+28.6	122	105	111	92	?9	?12.4	200	172	180	156	?10	?9.3
DCT32	175	132	179	133	+2.3	+0.8	987	766	981	786	?0.6	+2.6	1 681	1 381	1 671	1 378	?0.6	?0.2
H.264	270	243	265	200	?1.9	?17.7	1 310	1 157	1 332	1 083	+1.7	?6.4	2 150	1 936	2 092	1 685	?2.7	?13.0
平均△%	?	?	?	?	+4.5	+1.7	?	?	?	?	-13.6	20.0	?	?	?	?	-13.2	-20.3

划分基准		RCA_5× ₅			RCA₈_× ₈
划分基准	SPKM	PTBA	△%	SPKM	PTBA	△%
SODE	176.024 368	176.024 368	?	185.941 788	185.941 788	?
FFT4	301.945 61	184.349 38	?38.9	321.780 464	194.266 8	?39.6
FFT8	562.991 349	556.362 854	?1.2	455.286 764	334.402 496	?26.6
MEDIAN	501.718 992	477.816 925	?4.8	376.740 836	389.999 664	+3.5
IDCT	881.740 791	643.233 765	?27	702.818 364	538.842 957	?23.3
DCT32	6 852.261 98	5 674.566 406	?17.2	5 419.308 55	4 341.089 355	?19.9
H.264	9 753.433 21	7 684.688 477	?21.2	7 818.512 181	5 925.490 723	?24.2
平均△%	?	?	?15.8	?	?	?18.6