融合面积估算和多目标优化的硬件任务划分算法

doi:10.3969/j.issn.1000-436x.2013.02.006

摘要/Abstract

摘要：

摘要：针对可重构计算机系统配置次数（划分块数）的最小化问题，提出了一种融合面积估算和多目标优化的硬件任务划分算法。该算法每次划分均进行硬件资源面积的估算，并且通过充分考虑可重构资源的使用、一个数据流图所有划分块执行延迟总和、划分模块间边数等因素构造了新的探测函数prior_assigned()，该函数能够计算每个就绪节点的优先权值，新算法通过该值能动态调整就绪列表任务节点的调度次序。实验结果表明，与现有的层划分、簇划分、增强静态列表、多目标时域划分、簇层次敏感等5种划分算法相比，该算法能获得最少的模块数，并且随着可重构处理单元面积的增大，除层划分算法之外，其执行延迟的均值也是最小的。

关键词: 可重构计算, 时域划分, 最小化模块数, 资源约束, 探测函数, 多目标优化

Abstract:

In order to minimize the number of configuration (i.e.the number of partitioned modules) issue in reconfigurable computing systems, a hardware-task partitioning algorithm merged area estimation with multi-objective optimization was presented.It could estimate the area of hardware resource in each partitioning.Also, the detection function prior_assigned() was constructed with the guideline of making good use of reconfigurable resources,the execution delay sum of all partitioning modules of a data flow graph, number of edges between modules, etc.The detection function could calculate priority values of nodes.The proposed algorithm could adjust dynamically the schedu ing order of the ready list task-nodes by the priority values.Experimental results show that the proposed algorithm can get less modules than that of level-based partitioning, cluster based partitioning, enhanced static list, multi-objective temporal partitioning and level sensitive cluster based partitioning algorithms, and it can also obtain the least average execution delay with increase of the area of reconfigurable processing unit except level-based partitioning.

Key words: reconfigurable computing, temporal partitioning, minimum number of modules, resource restraint, detection function, multi-objective optimization

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

Nai-jin CHEN,Jian-hui JIANG. Hardware-task partitioning algorithm merged area estimation with multi-objective optimization[J]. Journal on Communications, 2013, 34(2): 40-55.

图/表 19

图1

图2

图3

表1

图4

图5

图6

表2

图7

表3

图8

图9

图10

图11

表4

表5

表6

表7

表8

参考文献 14

[1]	CARDOSO J M P , DINII C D , et al. Compiling for recon?gurable computing: a survey[J]. ACM Computing Surveys, 2010,42(4): 1301-1365.
[2]	COMPTON K , HAUCK S . Reconfigurable computing: a survey of systems and software[J]. ACM Computing Surveys, 2002,4(2): 171-210.
[3]	DASU A , PANCHANATHAN S . Reconfigurable media processing[J]. Elsevier’s Parallel Computing, Special Issue on Parallel Computing in Image and Video Processing, 2002,28(7/8): 1111-1139.
[4]	CAMPI F , TOMA M , LODI A , et al. A VLIW processor with reconfigurable instruction set for embedded applications[J]. IEEE Journal of Solid-State Circuits, 2003,38(11): 1876-1886.
[5]	王大伟, 窦勇, 李思昆 . 核心循环到粗粒度可重构体系结构的流水化映射[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.
[6]	于苏东, 刘雷波, 尹首一等. 嵌入式粗粒度可重构处理器的软硬件协同设计流程[J]. 电子学报, 2009,37(5): 1136-1140. YU S D , LIU L B , YIN S Y , et al. Hardware-software co-design flow for embedded coarse-grained reconfigurable processor[J]. Acta Electronica Sinica, 2009,37(5): 1136-1140.
[7]	DIMITROULAKOS G , GEORGIOPOULOS S , GALANIS M D , et al. Resource aware mapping on coarse grained reconfigurable arrays[J]. Microprocessors and Microsystems, 2009,33(2): 91-105.
[8]	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.
[9]	GPURNA K M , BHATIA D . Temporal partitioning and scheduling data flow graphs for reconfigurable computers[J]. IEEE Transactions on Computers, 1999,48(6): 579-590.
[10]	周博, 邱卫东, 谌勇辉等. 基于簇的层次敏感的可重构系统任务划分算法[J]. 计算机辅助设计与图形学学报, 2006,18(5): 667-673. ZHOU B , QIU W D , CHEN Y H , et al. A level sensitive cluster based partitioning algorithms for reconfigurable systems[J]. Journal of Computer Aided Design ＆ Computer Graphics, 2006,18(5): 667-673.
[11]	JIANG Y C , WANG J F . Temporal partitioning data flow graphs for dynamically reconfigurable computing[J]. IEEE Transactions on Very Large Scale Integration Systems, 2007,15(12): 1351-1361.
[12]	潘雪增, 孙康, 陆魁军等. 动态可重构系统任务时域划分算法[J]. 浙江大学学报（工学版）, 2007,41(11): 1839-1844. PAN X Z , SUN K , LU K J , et al. Temporal task partitioning algorithm for dynamically reconfigurable systems[J]. Journal of Zhejiang University（Engineering Science）, 2007,41(11): 1839-1844.
[13]	CARDOSO J M P , NETO H C . An enhanced static-list scheduling algorithm for temporal partitioning onto RPU[A]. Proceedings of 1999 IFIP International Conference on Very Large Scale Intetion[C]. Lisbon, 1999.485-496.
[14]	陈乃金, 江建慧, 陈昕等. 一种考虑执行延迟最小化和资源约束的改进层划分算法[J]. 电子学报, 2012,40(5): 1055-1066. CHEN N J , JIANG J H , CHEN X , et al. An improved level partitioning algorithm considering minimum execution delay and resource restraints[J]. Acta Electronica Sinica, 2012,40(5): 1055-1066.

运算类型	时延(单位：时钟周期)	占用硬件资源(单位:CLB)
加法	1	5
乘法	2	27
取模	4	50
减法	1	13
逻辑比较	1	17
异或	1	5
逻辑左移	1	5

划分用例				操作单元数量
划分用例	总数	加法	减法	乘法	取模	逻辑比较	异或	左移
SODE	11	2	2	6	—	1	—	—
FEAL	34	6	—	—	4	—	20	4
FFT4	12	4	4	4	—	—	—	—
FFT8	36	12	12	12	—	—	—	—
EWF	34	28	—	6	—	—	—	—
EWF6	204	168	—	36	—	—	—	—
FDCT	42	13	13	16	—	—	—	—
FDCT6	252	78	78	96	—	—	—	—
MATRIX4	112	48	—	64	—	—	—	—
DCT8	90	40	16	34	—	—	—	—
MEDIAN	19	—	—	—	—	19	—	—
BTREE32	31	—	—	—	—	31	—	—

划分用例		M			N			SD
划分用例	AEMO1	AEMO	D%	AEMO1	AEMO	D%	AEMO1	AEMO	D%
SODE	544	444	-20 0 0	455	355	-25 0 0	13 11 10	13 11 10	000
FEAL	766	765	0 0 -17	15 14 13	15 12 15	0 -14 15	29 25 27	28 28 26	-3 12 -4
FFT4	433	433	000	677	477	-33 0 0	996	10 9 6	11 0 0
FFT8	11 9 8	10 9 8	-90 0	20 23 21	26 24 20	30 4 -5	31 27 23	19 25 22	-39 -7 -4
EWF	765	655	-14 -17 0	18 15 16	19 16 13	6 7 -19	30 25 25	26 25 21	-13 0 -16
EWF6	38 29 25	5 29 25	-80 0	109 97 102	115 114 102	6 18 0	150 118 107	111 96 94	-26 -19 -12
FDCT	13 12 10	13 12 10	000	26 25 20	30 26 24	15 4 20	26 28 30	30 31 29	-15 11 -3
FDCT6	75 72 60	75 68 56	0 -6 -7	52 155 118	163 168 155	7 8 31	186 168 173	192 170 144	3 1 -17
MATRIX4	37 33 32	37 33 32	000	76 48 36	75 48 36	-10 0	79 98 109	80 98 109	100
DCT8	30 22 21	25 22 19	-17 0 -10	51 43 42	60 47 47	18 9 12	82 64 67	64 67 61	-22 5 -9
MEDIAN	775	775	000	10 16 12	11 14 12	-10 -13 0	18 9 13	17 11 13	-6 -22 0
BTREE32	11 11 8	11 11 8	000	10 29 16	10 28 16	0 -3 0	21 12 17	21 13 17	080
平均D%	— — —	— — —	-14 -12 -11	— — —	— — —	129	— — —	— — —	-11 -1 -9

划分用例		M			N			SD
划分用例	LBP	AEMO	D%	LBP	AEMO	D%	LBP	AEMO	D%
SODE	6 5 5	4 4 4	-33 -20 -20	7 7 7	3 5 5	-57 -29 -29	10 8 8	13 11 10	30 38 25
FEAL	9 8 7	7 6 5	-22 -25 -29	21 21 19	15 12 15	-29 -43 -37	24 22 23	28 28 26	17 27 30
FFT4	5 4 4	4 3 3	-20 -25 -25	8 6 7	4 7 7	-50 -17 -14	6 8 6	10 9 6	67 13 33
FFT8	12 11 10	10 9 8	-17 -18 -20	28 28 28	26 24 20	-7 -14 -29	18 18 15	19 25 22	6 39 47
EWF	9 7 6	6 5 5	-33 -29 -17	24 20 15	19 16 13	-21 -20 -20	23 19 18	26 25 21	13 32 22
EWF6	42 32 28	35 29 25	-17 -9 -11	172 174 166	115 114 102	-33 -35 -41	73 55 51	111 96 94	52 75 88
FDCT	15 13 13	13 12 10	-13 -8 -23	34 33 33	30 26 24	-12 -21 -33	24 22 22	30 31 29	25 41 46
FDCT6	79 74 66	75 68 56	-5 -8 -15	204 204 204	163 168 155	-20 -18 -27	129 127 115	192 170 144	49 34 35
MATRIX4	38 37 36	37 33 32	-3 -11 -11	96 96 95	75 48 36	-22 -50 -62	70 68 68	80 98 109	14 44 60
DCT8	27 25 23	25 22 19	-7 -12 -17	79 82 77	60 47 47	-24 -43 -33	47 42 41	64 67 61	36 60 29
MEDIAN	8 8 6	7 7 5	-13 -13 -17	15 15 14	11 14 12	-27 7 -21	11 11 11	17 11 13	55 0 18
BTREE32	12 12 9	11 11 8	-8 -8 -11	29 29 28	10 28 16	-66 -3 -43	12 12 9	21 13 17	75 8 89
平均D%	— — —	— — —	-16 -16 -18	— — —	— — —	-31 -24 -32	— — —	— — —	37 37 44

划分用例		M			N			SD
划分用例	CBP	AEMO	D%	CBP	AEMO	D%	CBP	AEMO	D%
SODE	5 5 5	4 4 4	-20 -20 -20	334	3 5 5	0 67 25	13 13 10	13 11 10	0 -15 0
FEAL	8 8 7	7 6 5	-13 -25 -29	16 14 13	15 12 15	-6 -14 15	30 31 29	28 28 26	-7 -10 -10
FFT4	5 5 4	4 3 3	-20 -40 -25	545	4 7 7	-20 75 40	11 13 10	10 9 6	-9 -31 -40
FFT8	12 12 10	10 9 8	-17 -25 -20	20 18 17	26 24 20	30 33 18	33 40 30	19 25 22	-42 -38 -27
EWF	8 7 6	6 5 5	-25 -29 -17	15 10 10	19 16 13	27 60 30	32 35 29	26 25 21	-19 -29 -28
EWF6	38 32 28	35 29 25	-8 -9 -11	90 70 70	115 114 102	28 63 46	177 190 174	111 96 94	-37 -50 -46
FDCT	15 13 12	13 12 10	-13 -8 -17	28 26 23	30 26 24	7 0 4	40 37 34	30 31 29	-25 -16 -15
FDCT6	85 73 62	75 68 56	-12 -7 -10	160 158 138	163 168 155	2 6 12	235 213 199	192 170 144	-18 -20 -28
MATRIX4	39 35 34	37 33 32	-5 -6 -6	63 47 51	75 48 36	19 2 29	89 102 108	80 98 109	-10 -4 1
DCT8	30 23 23	25 22 19	-17 -4 -17	42 38 33	60 47 47	43 24 42	95 80 81	64 67 61	-33 -16 -25
MEDIAN	8 8 6	7 7 5	-13 -13 -17	11 11 11	11 14 12	0 27 9	17 17 15	17 11 13	0 -35 -13
BTREE32	12 12 9	11 11 8	-8 -8 -11	10 10 17	10 28 16	0 180 6	21 21 19	21 13 17	0 -38 -11
平均D%	— — —	— — —	-14 -16 -17	— — —	— — —	14 48 23	— — —	— — —	-22 -25 -22