分布存储系统中优化通信的冗余计算分割

Redundant Computation Partitioning in Distributed-Memory Systems

针对并行循环套序列 ,提出一种冗余计算分割的通信优化方法 .根据数据流分析 ,文中给出用以确定每个循环套的冗余计算量的一般方法 ,并在此基础上提出冗余计算分割的实现和判定 .针对规则依赖的程序 ,该文还提出了一个高效的冗余计算分割的实现方法 .该技术已经在一个并行编译器中实现 ,试验结果表明 ,它比传统的通信优化技术有明显的优越性 .

Maximize parallelism and minimize communication overheads are important issues in distributed-memory systems. Using ordinary computation partitioning methods, inter-loop communications cannot be avoided usually. This paper presents a communication optimization technique, named communication-free redundant computation partitioning, for parallel loop sequences. Based on dataflow analysis, a generic method is given to select computation redundancy properly for each partitioned loop nest, so as to eliminate inter-loop communications. Upon this, the implementation and criterion of communication-free redundant computation partitioning are given. An efficient algorithm is also provided for a certain class of programs, called regularly dependent programs. The technique spends very little redundant computation and space to get lesser communication. When the parallel loop sequence is enclosed by sequential loops, the technique can eliminate some data redistribution points for the program, simplifying the global deduction of data and computation partitioning. The technique has been realized in Autopar3.0, which is a parallelizing compiling system targeting at Dawning 3000 parallel machines. According to the results of experiments, the technique is superior to some well-known communication optimization.