THE ALIGNMENT PROBLEM:
       AN OPTIMIZATION PROBLEM FOUND IN PARALLELIZING COMPILERS

                          Claude G. Diderich
          Swiss Federal Institute of Technology -- Lausanne
                     Computer Science Department
                    CH-1015 Lausanne, Switzerland


                               Abstract

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 the first part of this talk we introduce the alignment problem,
that is, the problem of mapping computation and data onto the
processors, using a linear algebra framework.  We present different
sub-problems of the alignment problem, study their complexity and give
some ideas about how to solve them.

In the second part of the talk we study the relation between the
scheduling and the alignment problem.  Compatible combinations of
alignment and scheduling functions are characterized.  An algorithm to
compute a valid multi-dimensional scheduling function for a given
computation mapping function is presented.


The work presented in this talk is joint work with Prof. Marc Gengler
(University of Marseilles) and Dr. Frederic Vivien (ENS Lyon).