通信学报 ›› 2016, Vol. 37 ›› Issue (6): 137-143.doi: 10.11959/j.issn.1000-436x.2016123

• 学术论文 • 上一篇    下一篇

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

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

  1. 国防科技大学电子科学与工程学院,湖南 长沙 410073
  • 出版日期:2016-06-25 发布日期:2017-08-04
  • 基金资助:
    国家自然科学基金资助项目

Graph partition based mapping algorithm on multiprocessors for streaming applications

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

  1. College of Electronic Science and Engineering,National University of Defense Technology,Changsha 410073,China
  • Online:2016-06-25 Published:2017-08-04
  • Supported by:
    The National Natural Science Foundation of China

摘要:

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

No Suggested Reading articles found!