Redundant Computation Partitioning in Distributed-Memory Systems
Chen Li · Chinese Journal of Computers · 2003
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 optimizations.