镜像分解技术实现CFD程序自相关循环并行化的研究

On Making Self-Dependent Loops in Parallel CFD(Computational Fluid Dynamics) Program Solvable with Wave-Front Method

针对 CFD( Computational Fluid Dynamics)程序中常见的自相关循环结构 ,分析了波前并行技术不能对其进行并行化的原因 ,针对其相关实质 ,提出了自相关循环的镜像分解技术 ,通过消除跨迭代的反相关 ,实现自相关循环结构的波前并行 ,完成自相关循环的并行化。

Self dependent loops are both forward dictionary dependent and backward dictionary dependent; thus they are not solvable with wave front method. We propose writing the self dependent loops into a new form with only forward dictionary dependency, thus making them solvable with wave front method. Self dependent loops are nested loop structures in serial program. These loops appear frequently in CFD programs, and cannot be parallelized by ordinary methods, thus the efficiency of resultant parallel CFD programs is much lowered. We propose what we call mirror image decomposition to parallelize self dependent loops. Section 1 proves that backward dictionary dependency causes wave front method to be ineffective. Section 2 analyzes that forward dictionary dependency depends on new values of array elements, while backward dictionary dependency depends on old ones. Thus, these two kinds of dependencies can be mirror image decomposed as shown in Fig.2. Backward dictionary dependency can be eliminated by data duplicating. So the nested loops can be rewritten into a new form, which has only forward dictionary dependency. The new form can be processed by wave front method. We give our algorithm in detail in Fig.3. In 2002, we applied our mirror image decomposition method in the development of a certain parallel CFD program and obtained very good results.