基于DAG图的自适应代码划分优化算法  

Adaptive Algorithm for Code Partitioning Based on DAG

作　　者：周静[1] 曾国荪[1] 

机构地区：[1]同济大学计算机科学及技术系

出　　处：《计算机工程》2007年第20期15-17,共3页Computer Engineering

基　　金：国家自然科学基金资助项目(60173026);上海科委重大项目(03DZ15029);上海高校网格技术E-研究院基金资助项目(200301-1)

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

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

分 类 号：TP338[自动化与计算机技术—计算机系统结构]