
Automatic Data Distribution for Distributed Memory Parallel Computers

Keywords 
Researchers 
Alignment problem, automatic parallelization, data distribution, data parallelism, distributed memory machines, distributed shared memory, linear algebra. 
Prof. Marc GENGLER (University of Marseilles, project leader),
Claude G. DIDERICH (Ph.D. student). 
Project period 
Funding Agency 
August 1995  September 1998. 
This project is funded by a special EPFL PhDgrant. 
Description 

 In recent years the need for techniques to parallelize numerical applications has increased. When parallelizing nested loops for distributed memory parallel computers, two major problems have to be solved: the scheduling of the loop iterations and the mapping of the computations and data elements onto the processors. The scheduling functions must satisfy all the data dependences existing in the sequential loop nests. The mapping functions must ensure that a given degree of parallelism is obtained. Furthermore they should minimize the amount of communication overhead due to non local data references.

 In this project we study the alignment problem, that is, the problem of mapping computation and data onto the processors, in a linear algebra framework. We start by studying the communicationfree alignment problem. We present and extend the algorithm for solving this problem introduced by Bau et al. (1994). In a second step we introduce the constantdegree parallelism alignment problem. It is the problem of finding computation and data mapping functions that minimize the number of remote data accesses for a given degree of parallelism. The problem is shown to be NPhard. An exact implicit enumeration algorithm is presented. It proceeds by enumerating all interesting subsets of alignment constraints to be satisfied. To allow large alignment problems to be solved we present an efficient heuristic and apply it to various benchmarks.

 The approach to the alignment problem used in this project is compared with related work. We shown that our framework is more general than other approaches using a linear algebra framework.

 Finally we study the relation between the scheduling and the alignment problem. First a sufficient condition for the existence of a non sequential scheduling function in the presence of data dependences is given. Compatible combinations of alignment and scheduling functions are characterized. We present an algorithm to compute a valid multidimensional scheduling function for a given computation mapping function. This algorithm is used as a building block to find a pair of compatible scheduling and alignment functions subject to a given cost function.


Publications 
Diderich C.G., Automatic Data Distribution for Distributed Memory Parallel Computers, PhD thesis No.1810, Swiss Federal Institute of Technology of Lausann (EPFL), June 1998 . 

Diderich C.G. and Gengler M., A General Solution to the Alignment Problem on Distributed Memory Machines, Proceedings of the 3rd Workshop on Automatic Data Layout and Performance Prediction (AP'97), Barcelona, Spain, Jan. 1997. 

Diderich C.G., and Gengler M., The Alignment Problem in a Linear Algebra Framework, Proceedings of the Hawaii International Conference on System Sciences (HICSS30), Software Technology Track, Wailea, Hawai`i, IEEE, Vol. I  Software Technology and Architecture, pp. 586595, January 1997. 

Diderich C.G., and Gengler M., A Heuristic Approach for Finding a Solution to the ConstantDegree Parallelism Alignment Problem, Proceedings of the International Conference of Parallel Architectures and Compilation Techniques (PACT '96), Boston, MA, October 1996. 

Diderich C. G., and Gengler M., Solving the ConstantDegree Parallelism Alignment Problem, Proceedings of EuroPar '96, Lyon, France, August 1996. 

Diderich C.G., and Gengler M., Solving the ConstantDegree Parallelism Alignment Problem, Tech. Report DI96/195, Swiss Federal Institute of Technology  Lausanne, Computer Science Department, Lausanne, Switzerland, June 1996. 

Diderich C. G., and Gengler M., Placement automatique des données sur des machines parallèles à mémoires distribuées, Proceedings of RenPar '96, Bordeaux, France, May 1996. 

Diderich C.G. and Gengler M., Automatic Data Distribution for Distributed Memory Parallel Computers (abstract), Proceedings of the SIPAR Workshop '95: Parallel and Distributed Systems, (N. Droux, ed.), pp. 1114, BielBienne, Switzerland, October 1995. 
