摘要： 并行编译的两大工作是程序代码划分和调度。对于调度问题，目前已有大量的解决方案，但是针对代码划分提取并行性的研究工作却非常少。该文提出了通过合并结点来划分DAG图的新的划分算法。实例分析证明，该算法是一种有效的、低复杂度的自适应代码划分解决方案，并且适用于异构计算的任务图划分。

关键词: 并行编译, 有向无环图, 代码划分, 任务合并, 关键路径

Abstract: Two main phrases of the compiler of the parallel machine are the code partitioning to abstract parallelism and the scheduling phrase. There are many more solutions to the scheduling phrase in the literature, but few regards the code partitioning phrase. A novel adaptive algorithm for code partitioning which merges points to partition the directed acyclic graph (DAG) is presented. It has been proved through the case that the algorithm is an efficient and low complexity solution for code partitioning. It is also suitable to the task graph partitioning for heterogeneous computing.

Key words: parallel compiler, directed acyclic graph (DAG), code partitioning, task merging, critical path

中图分类号: 

• TP338