基于分布式系统的可并行循环动态识别技术

A Run-Time Technique for Parallel Loop Identification Based on Distributed System

针对分布式环境下可抽取观察循环的不规则串行程序循环的动态依赖关系分析问题,提出了一个基于观察/执行模型的动态分析算法.其贡献是:(1) 算法可并行执行于分布式系统;(2) 直接分析具有拷入和最后赋值操作的循环;(3) 给出了循环的并行化方法;(4) 并不要求循环是完全可并行的,对某些部分可并行循环,也支持其并行执行.理论分析和实验表明,在处理器数量适当的情况下,循环可以并行时,可以获得很好的加速比;不能并行时,对串行执行增加的开销也是小的.从而为分布式环境下开发更多的循环并行性提供了一种新的手段.

An algorithm is presented to solve the problem of run-time parallel loop identification based on distributed system for the loops in irregular programs, from which inspective loops can be extracted. The contributions are: (1) The algorithm is fully parallel and can be run on a distributed system; (2) Loops with copy-in and last assignment attributes can be directly analyzed; (3) A method is given for a loop to parallel; (4) Some partial parallel loop can also be parallelized. The theoretical analysis and experimental results show that in adequate number of processors, if a loop is parallel, a good speedup can be obtained; if a loop is not parallel, the slowdown of serial executing is small. A new method is given for exploiting more loop paralizations on the distributed system.