含有跨迭代数据依赖关系循环的自动并行化

Automatic Parallelization for Loops Carried Data Dependence Between Iterations

OpenMP是为在多处理机上编写并行程序而设计的一个应用编程接口,在串行程序中简单插入OpenMP编译指导语句,编译器就可自动将串行程序并行化.但用OpenMP对for循环进行并行化时,要求循环各次迭代之间不能含有数据依赖关系.文中提出了一种对含有跨迭代数据依赖关系的for循环进行OpenMP自动并行化的方法.该方法首先对串行程序的GCC抽象语法树文本进行冗余信息消除,以提取程序的有用信息;然后利用这些信息分析循环是否含有跨迭代数据依赖关系,若有则采用预计算(pre-computation)技术消除跨迭代数据依赖关系;最后自动生成带有OpenMP编译指导语句的并行程序.实验结果表明该方法对于某些含有跨迭代数据依赖关系的循环来说是有效的.

OpenMP is an application programming interface for designing parallel programs on multiprocessor systems. The compiler can automatically parallelize a sequential program by simply inserting OpenMP compiler directives. However, it must be ensured that no data dependence exists between iterations when parallelizing loops using OpenMP. The paper proposes a method of automatically parallelizing loops carded data dependence between iterations using OpenMP. First, it needs to eliminate redundant information in the GCC abstract syntax tree text of a sequential program to extract useful information. Then analyze the data dependence between iterations according to the useful information, and eliminate the data dependence using the pre-computation technique. Finally, a parallel program with OpenMP compiler directives corresponding to the sequential program is automatically generated. The experiment results show that the method proposed by the paper is effective for some loops carried data dependence between iterations.