Détection de parallélisme dans les boucles imbriquées.
Date: December 1997
Abstract:
Many computer users would like to be able to run on parallel computers their ``sequential''
programs (written to be run on classical computers). Thus, it became necessary to know how to
transform, to ``parallelize'', the sequential programs into programs that can be run on parallel
computers. This parallelization must be automatic as it is needed by plain users. Before applying
any transformation to the original program, one must detect and quantify the parallelism it
implicitly contains, which requires to know the program dependences. Later on, it will be necessary
to reorder the computations to explicit the parallelism found. The aim of this thesis is to detect
the implicit parallelism, and to search for schedules that explicit it, for particular program
structures: set of nested loops. Our main goal was to understand the existing technics for
parallelism detection, and to find their strong and weak points. On one hand, we have studied the
main existing algorithms. On the other hand, we started from the theoretical model furnished by the
systems of uniform recurrence equations and we proposed an optimal algorithm to parallelize the
polyhedral reduced dependence graphs, a representation of dependences which generalizes the two
classical approximation modes. We compared this new algorithm with the classical ones and we
obtained a classification of the main algorithms. The problem of parallelism detection and
exhibition is one of the many phases of an automatic parallelizer. Therefore, we have looked at the
interactions between the problems of mapping and scheduling, and at the interactions between the
problems of parallelism detection and of ``false'' dependences removal.
