基于图分割的流应用多处理器映射算法

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

摘要/Abstract

摘要：

为了充分利用多处理器平台所提供的计算资源，需要将应用以适当的方式映射到不同处理器，从而最大程度地挖掘应用所提供的并发性以满足应用严格的实时性要求。提出了并发图来量化、建模应用任务间的并发性，提出了一种基于自同步调度的并发图构建算法，并将任务映射问题转换成图分割问题，然后将并发图分割问题建模为纯0-1整数线性规划模型并采用ILP求解器获得最优解。采用了大量随机生成的同步数据流图以及一组实际应用对所提方法进行性能评估，实验结果表明所提方法性能优于已有算法。

关键词: 同步数据流图, 映射, 多处理器, 图分割

Abstract:

To take advantage of multiprocessor platform,it is a necessity to map tasks of the application properly onto different processors to exploit the concurrency in the application and thus meet the stringent timing requirements.Parallelism graph was proposed to quantify and model the concurrency among tasks of the application.An algorithm was also proposed to construct the parallelism graph based on the self-timed schedule and transform the mapping problem to a graph partitioning problem.The graph partitioning problem as a pure 0-1 integer linear programming model was further formulated and the ILP solver to find the optimal result.A lot of randomly generated synchronous dataflow graphs and a set of practical applications were used to evaluate the performance of the proposed method.The experimental results demonstrate that the proposed method outperforms available algorithms.

Key words: synchronous dataflow graph, mapping, multiprocessor, graph partition

唐麒,吴尚峰,施峻武,魏急波. 基于图分割的流应用多处理器映射算法[J]. 通信学报, 2016, 37(6): 137-143.

Qi TANG,Shang-feng WU,Jun-wu SHI,Ji-bo WEI. Graph partition based mapping algorithm on multiprocessors for streaming applications[J]. Journal on Communications, 2016, 37(6): 137-143.

图/表 5

图1

图2

图3

表1

表2

参考文献 14

[1]	LEE E A , MESSERSCHMITT D G . Static scheduling of synchronous data flow programs for digital signal processing[J]. IEEE Transactions on Computers, 1987,100(1): 24-35.
[2]	SRIRAM S , BHATTACHARYYA S S . Embedded multiprocessors:scheduling and synchronization[M]. CRC Press, 2012.
[3]	AUBANEL E . Resource-aware load balancing of parallel applications[M]// Handbook of research on grid technologies and utility computing:concepts for managing large-scale applications. 2009: 12-21.
[4]	STUIJK S , BASTEN T , GEILEN M ,et al. Multiprocessor resource allocation for throughput-constrained synchronous dataflow graphs[C]// The 44th Annual Design Automation Conference. 2007: 777-782.
[5]	AMBROSE J A , NAWINNE I , PARAMESWARAN S . Latencyconstrained binding of dataflow graphs to energy conscious GALSbased MPSoCs[C]// IEEE International Symposium on Circuits and System. 2013: 1212-1215.
[6]	TOPCUOGLU H , HARIRI S , WU M . Performance-effective and low-complexity task scheduling for heterogeneous computing[J]. IEEE Transactions on Parallel and Distributed Systems, 2002,13(3): 260-274.
[7]	SINNEN O . Task scheduling for parallel systems[M]. John Wiley ＆Sons, 2007.
[8]	STUIJK S , GEILEN M , BASTEN T . SDF3:SDF for free[C]// Conference on Application of Concurrency to System Design. 2006: 276-278.
[9]	HENDRICKSON B , KOLDA T G . Graph partitioning models for parallel computing[J]. Parallel Computing, 2000,26(12): 1519-1534.
[10]	GEILEN M . Synchronous dataflow scenarios[J]. ACM Transactions on Embedded Computing Systems, 2010,10(2): 16.
[11]	DAMAVANDPEYMA M , STUIJK S , BASTEN T ,et al. Schedule-extended synchronous dataflow graphs[J]. IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems, 2013,32(10): 1495-1508.
[12]	GHAMARIAN A H , GEILEN M , STUIJK S ,et al. Throughput analysis of synchronous data flow graphs[C]// Sixth International Conference on Application of Concurrency to System Design. 2006: 25-36.
[13]	BAMBHA N , KIANZAD V , KHANDELIA M ,et al. Intermediate representations for design automation of multiprocessor DSP systems[J]. Design Automation for Embedded Systems, 2002,7(4): 307-323.
[14]	WINSTON W L , GOLDBERG J B . Operations research:applications and algorithms[M]. Duxbury Press, 2004.

任务数	处理器数		吞吐量			割值			时间复杂度
任务数	处理器数	ILP	HEFT	LB	ILP	HEFT	LB	ILP	HEFT	LB
5	2	1.066	0.987	1	1.041	0.849	1	5.902	0.905	1
	4	1.198	0.719	1	1.024	0.641	1	4.057	0.876	1
10	2	1.120	1.077	1	1.143	1.016	1	9.765	1.109	1
	4	1.305	0.949	1	1.095	0.845	1	129.6	0.812	1
15	2	1.092	1.098	1	1.164	1.080	1	10.304	0.738	1
	4	1.263	1.128	1	1.132	0.978	1	3 006	0.604	1
平均值		1.174	0.993	1	1.100	0.902	1	527.6	0.841	1

应用		吞吐量			割值			时间复杂度
应用	ILP	HEFT	LB	ILP	HEFT	LB	ILP	HEFT	LB
MP3解码器1	1.076	0.951	1	1.002	0.980	1	35.44	0.383	1
MP3解码器2	1.160	0.922	1	1.187	0.923	1	1.037	1.071	1
调制解调器	1.096	0.924	1	1.186	0.820	1	1.647	0.470	1
信道均衡器	1.026	0.908	1	1.668	0.648	1	0.571	0.043	1
卫星接收器	1.014	1.069	1	1.135	1.122	1	0.981	1.000	1

[1]	张海波, 兰凯, 陈舟, 王汝言, 邹灿, 王明月. 车联网中基于环的匿名高效批量认证与组密钥协商协议[J]. 通信学报, 2023, 44(6): 103-116.
[2]	刘彩霞, 季新生, 邬江兴. 移动通信网的内生安全共性问题及破解之道[J]. 通信学报, 2022, 43(9): 70-79.
[3]	闫文浩, 姜子敬, 黄欣, 朱淑娟, 丁群. 广义二维多项式混沌映射及其在信息传输中的应用[J]. 通信学报, 2022, 43(9): 80-89.
[4]	王竹, 杨思琦, 李凤华, 耿魁, 彭婷婷, 史梦瑶. 高效可证明安全的无证书有序聚合签名方案[J]. 通信学报, 2022, 43(5): 58-67.
[5]	张海波, 陈舟, 黄宏武, 贺晓帆. VANET系统中基于中国剩余定理的群内相互认证密钥协商协议[J]. 通信学报, 2022, 43(1): 182-193.
[6]	张海波, 黄宏武, 刘开健, 贺晓帆. 车联网中可证安全的匿名可追溯快速组认证协议[J]. 通信学报, 2021, 42(6): 213-225.
[7]	鲁信金, 雷菁, 施育鑫. 基于旋转置乱的索引跳频抗干扰加密方法[J]. 通信学报, 2021, 42(12): 27-34.
[8]	诸天逸,李凤华,金伟,郭云川,房梁,成林. 互操作性与自治性平衡的跨域访问控制策略映射[J]. 通信学报, 2020, 41(9): 29-48.
[9]	曹利峰,卢新,高振升,杜学绘. 基于L-DHT的多租户虚拟域隔离构建方法[J]. 通信学报, 2020, 41(6): 184-201.
[10]	黄开枝,潘启润,袁泉,游伟,汤红波. 基于性能感知的网络切片部署方法[J]. 通信学报, 2019, 40(8): 114-122.
[11]	马英杰,赵耿,魏占祯,李兆斌,鞠磊. 基于量子混沌映射降低OFDM系统PAPR的算法研究[J]. 通信学报, 2019, 40(1): 195-200.
[12]	鄢懿,凃国防,张灿,高绍帅,陈德元. 基于混沌冗余和阈值控制的联合算术码双向编译码快速算法[J]. 通信学报, 2018, 39(2): 105-113.
[13]	刘璐,赵国庆. 数字波束成形中峰均比抑制方法的研究[J]. 通信学报, 2018, 39(2): 114-121.
[14]	贾姗,徐正全,胡传博,王豪. 基于重加密的随机映射指纹模板保护方案[J]. 通信学报, 2018, 39(2): 122-134.
[15]	张红旗,黄睿,杨英杰,常德显,张连成. 基于Q-learning的跨域服务链映射机制[J]. 通信学报, 2018, 39(12): 102-112.