Graph partition based mapping algorithm on multiprocessors for streaming applications

Qi TANG; Shang-feng WU; Jun-wu SHI; Ji-bo WEI

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

您当前的位置：

首页 >

文章列表页 >

Graph partition based mapping algorithm on multiprocessors for streaming applications

Papers | 更新时间：2024-06-05

- Graph partition based mapping algorithm on multiprocessors for streaming applications
- Journal on Communications Vol. 37, Issue 6, Pages: 137-143(2016)
- 作者机构：
  
  国防科技大学电子科学与工程学院，湖南长沙 410073
- 作者简介：
- 基金信息：
  
  The National Natural Science Foundation of China(61471376)
- DOI：10.11959/j.issn.1000-436x.2016123
  CLC： TP399
- Online First：2016-06，
  
  Published：25 June 2016
- 稿件说明：
移动端阅览
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：

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 .

Views

1254

下载量

CSCD

Alert me when the article has been cited

提交

Tools

Publicity Resources

Cross-domain service chain mapping mechanism based on Q-learning

Denotation and application mechanism of complicated network shared management information model

Related Author

Hongqi ZHANG

Rui HUANG

Yingjie YANG

Dexian CHANG

Liancheng ZHANG

GAO Zhi-peng

QIU Xue-song

WANG Zhi-li

Related Institution

Cryptography Engineering Institute of Information Engineering University

State Key Laboratory of Networking and Switching Technology, Beijing University of Posts and Communications

AI问答

⁰