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

唐麒; 吴尚峰; 施峻武; 魏急波

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

您当前的位置：

首页 >

文章列表页 >

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

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

- 基于图分割的流应用多处理器映射算法
- Graph partition based mapping algorithm on multiprocessors for streaming applications
- 通信学报 2016年37卷第6期页码：137-143
- 作者机构：
  
  国防科技大学电子科学与工程学院，湖南长沙 410073
- 作者简介：
  
  [ "唐麒（1986-），男，湖南益阳人，国防科技大学博士生，主要研究方向为软件无线电技术和嵌入式并行计算。" ]
  [ "吴尚峰（1986-），男，重庆人，国防科技大学博士生，主要研究方向为软件无线电技术。" ]
  [ "施峻武（1977-），男，云南曲靖人，国防科技大学讲师，主要研究方向为软件无线电技术。" ]
  [ "魏急波（1967-），男，湖南汉川人，国防科技大学教授、博士生导师，主要研究方向为通信信号处理与通信网络。" ]
- 基金信息：
  
  国家自然科学基金资助项目(61471376)
- DOI：10.11959/j.issn.1000-436x.2016123
  中图分类号： TP399
- 网络出版日期：2016-06，
  
  纸质出版日期：2016-06-25
- 稿件说明：
移动端阅览
唐麒, 吴尚峰, 施峻武, 等. 基于图分割的流应用多处理器映射算法[J]. 通信学报, 2016,37(6):137-143.

Qi TANG, Shang-feng WU, Jun-wu SHI, et al. Graph partition based mapping algorithm on multiprocessors for streaming applications[J]. Journal on communications, 2016, 37(6): 137-143.
唐麒, 吴尚峰, 施峻武, 等. 基于图分割的流应用多处理器映射算法[J]. 通信学报, 2016,37(6):137-143. DOI： 10.11959/j.issn.1000-436x.2016123.

Qi TANG, Shang-feng WU, Jun-wu SHI, et al. Graph partition based mapping algorithm on multiprocessors for streaming applications[J]. Journal on communications, 2016, 37(6): 137-143. DOI： 10.11959/j.issn.1000-436x.2016123.

摘要

为了充分利用多处理器平台所提供的计算资源，需要将应用以适当的方式映射到不同处理器，从而最大程度地挖掘应用所提供的并发性以满足应用严格的实时性要求。提出了并发图来量化、建模应用任务间的并发性，提出了一种基于自同步调度的并发图构建算法，并将任务映射问题转换成图分割问题，然后将并发图分割问题建模为纯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.

关键词

Keywords

references

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 .

SRIRAM S , BHATTACHARYYA S S . Embedded multiprocessors:scheduling and synchronization [M ] . CRC Press , 2012 .

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 .

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 .

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 .

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 .

SINNEN O . Task scheduling for parallel systems [M ] . John Wiley ＆Sons , 2007 .

STUIJK S , GEILEN M , BASTEN T . SDF3:SDF for free [C ] // Conference on Application of Concurrency to System Design . 2006 : 276 - 278 .

HENDRICKSON B , KOLDA T G . Graph partitioning models for parallel computing [J ] . Parallel Computing , 2000 , 26 ( 12 ): 1519 - 1534 .

GEILEN M . Synchronous dataflow scenarios [J ] . ACM Transactions on Embedded Computing Systems , 2010 , 10 ( 2 ): 16 .

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 .

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 .

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 .

WINSTON W L , GOLDBERG J B . Operations research:applications and algorithms [M ] . Duxbury Press , 2004 .

浏览量

692

下载量

CSCD

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

提交

工具集

关联资源

基于Q-learning的跨域服务链映射机制

复杂网络共享管理信息模型的表示与应用机制研究