构造串行程序对应的并行任务（DAG）图

计算机工程与应用 ›› 2007, Vol. 43 ›› Issue (1): 41-41.

构造串行程序对应的并行任务（DAG）图

郭龙,叶青,陈闳中

同济大学

收稿日期:2006-05-09 修回日期:1900-01-01 出版日期:2007-01-01 发布日期:2007-01-01
通讯作者: 郭龙 allenjack

Develop Direct Acyclic Graph (DAG) corresponding to serial program

,,HongZhong Chen

同济大学

Received:2006-05-09 Revised:1900-01-01 Online:2007-01-01 Published:2007-01-01

摘要/Abstract

摘要： 目前在并行计算研究领域中很大一部分工作是将串行程序并行化，如何发掘串行程序中存在的并行性，一个好的方法就是构造其对应的并行任务（DAG）图，对并行任务图的分析，调度和最终实现并行计算的工作已经有很多人做过，但是由串行程序构造DAG图的工作相对很少。本文分析了串行程序中存在的依赖关系，并以此为依据，提出了一种由现有的串行程序或者串行解决方案构造对应的并行任务（DAG）图的算法

关键词: 并行计算, DAG, 数据依赖, 控制依赖, 流依赖

Abstract: Currently most of the work in the Parallel computing field is converting serial program to parallel program. A good method to solve this problem is to develop Direct Acyclic Graph corresponding to the serial program, but most of the work now is contributing to the scheduling of the DAG. This paper analyzes the parallel property of serial program and the dependence of instructions in serial program, and then proposes an algorithm of developing the Direct Acyclic Graph corresponding to serial program.

Key words: Parallel computing, DAG, Data dependence, Control dependence, Flow dependence

郭龙,叶青,陈闳中. 构造串行程序对应的并行任务（DAG）图[J]. 计算机工程与应用, 2007, 43(1): 41-41.

,,HongZhong Chen. Develop Direct Acyclic Graph (DAG) corresponding to serial program[J]. Computer Engineering and Applications, 2007, 43(1): 41-41.

[1]	冯凯，李婧. k元n方体网络的子网络可靠性[J]. 计算机工程与应用, 2021, 57(16): 83-89.
[2]	李健，张大伟，姜晓明，向立云. 并行化洪水演进模拟研究综述[J]. 计算机工程与应用, 2021, 57(13): 1-7.
[3]	孙明，陈昕. 面向卷积神经网络的硬件加速器设计方法[J]. 计算机工程与应用, 2021, 57(13): 77-84.
[4]	叶颖诗，魏福义，蔡贤资. 基于并行计算的快速Dijkstra算法研究[J]. 计算机工程与应用, 2020, 56(6): 58-65.
[5]	杜伟，傅游. 基于GPU的最小二乘蒙特卡罗算法期权定价[J]. 计算机工程与应用, 2020, 56(4): 225-229.
[6]	金之雁，杨磊，林隽民，王哲. 广义共轭余差法的通信避免算法[J]. 计算机工程与应用, 2020, 56(3): 74-79.
[7]	刘家华，陈靖宇. 多核并行脉冲神经网络模拟器的设计[J]. 计算机工程与应用, 2020, 56(22): 244-250.
[8]	邬阳阳，汤建国. 大数据背景下粗糙集属性约简研究进展[J]. 计算机工程与应用, 2019, 55(6): 31-38.
[9]	刘军，李威，吴梦婷，陈起凤. Hadoop平台下新型图像并行处理模型设计[J]. 计算机工程与应用, 2019, 55(6): 186-190.
[10]	刘洋，陈经纬，冯勇，吴文渊. 并行LLL算法研究综述[J]. 计算机工程与应用, 2019, 55(16): 36-41.
[11]	曾有灵，陈耿铎，熊威，李喆. 基于Spark的CT图像FBP重建算法程序并行设计[J]. 计算机工程与应用, 2019, 55(10): 218-224.
[12]	姜悦宁1，2，3，贾宏光1，3，厉明1，3. 基于多核并行计算的无人机CFD数值模拟[J]. 计算机工程与应用, 2018, 54(7): 221-225.
[13]	魏子衿1，2，3，肖丽2，3. 基于区域分解的并行动态LOD构建算法[J]. 计算机工程与应用, 2018, 54(6): 168-177.
[14]	覃金帛1，曾志强1，2，梁藉1，杨明祥2，张健1. GPU并行优化技术在水利计算中的应用综述[J]. 计算机工程与应用, 2018, 54(3): 23-29.
[15]	陈宇峰，张铂，李林. 基于多核CPU+GPU运算的电磁场高效体绘制算法研究[J]. 计算机工程与应用, 2018, 54(18): 218-222.