Static single assignment form for message-passing programs

This paper presents a novel scheme for maintaining accurate information abo ut distributed data in message-passing programs. We describe static single assignment (SSA) based algorithms to build up an intermediate representatio n of a sequential program while targeting code generation for distributed m emory machines employing the single program multiple data (SPMD) model of p rogramming. This SSA-based intermediate representation helps in a variety o f optimizations performed by our automatic parallelizing compiler, PARADIGM , which generates message passing programs and targets distributed memory m achines. In this paper. we concentrate on the semantics and implementation of this SSA-form for message-passing programs while giving some examples of the kind of optimizations they enable. We describe in detail the need for various kinds of merge functions to maintain the single assignment property of distributed data. We give algorithms for placement and semantics of the se merge functions and show how the requirements are substantially differen t owing to the presence of distributed data and arbitrary array addressing functions. This scheme has been incorporated in our compiler framework whic h can use uniform methods to compile, parallelize. and optimize a sequentia l program irrespective of the subscripts used in array addressing functions . Experimental results for a number of benchmarks on an IBM SP-2 show a sig nificant improve ment in the total runtimes owing to some of the optimizati ons enabled by the SSA-based intermediate representation. We have observed up to around 10-25 % reduction in total runtimes in our SSA-based schemes c ompared to non-SSA-based schemes on 16 processors.