Integrating automatic data distribution and communication optimization
Mary Lou Soffa, Rajiv Gupta, Jodi Lynn Tims · 1998
The use of distributed memory parallel architectures in large scale scientific computing has become widely accepted due to the scalability and cost effectiveness of such systems. However, program development for distributed memory architectures is a complex task. The array variables of a program must be distributed to the memories of individual processors in such a way that sufficient parallelism is maintained and communication costs do not become prohibitive. Assuming the SPMD model of computation, this work develops and evaluates an integrated data distribution and communication optimization algorithm that automatically partitions a program's array variables based upon data interrelationships and communication cost estimates derived using global data flow analysis information. Communications that must occur are optimized using techniques of message aggregation, redundant communication elimination, and communication scheduling. This work first develops the Distribution Interrelationship Flowgraph (DIF) representation of a program utilized by the partitioning algorithm. The DIF enables array data flow analysis to be performed and explicitly represents those data interrelationships that affect data distribution decisions. A cost model is designed to associate a communication cost estimate with each interrelationship discovered. This cost model incorporates savings realizable from applicable communication optimizations. The cast estimates are used to group related array values for distribution. Each group of values is aligned and oriented to a common virtual data space that is partitioned using tiling techniques. Tile shape and size is determined based upon communication dependence vectors that model the data interrelationships not satisfied during alignment and orientation. An analysis of the distributions selected by the algorithm for various access patterns indicates that the heuristic is effective in choosing distributions that reduce the overall communication requirements of a program without adversely affecting the level of available parallelism. When appropriate, parallelism is reduced to avoid excessive communication within the innermost levels of a loop nest. Experimental results demonstrate the effectiveness of the dynamic distribution algorithm at reducing communication requirements of test programs. Further experiments indicate that the use of tiling techniques in defining distribution and the inclusion of communication optimization information into the cost model are important aspects of the developed technique.