SPMD Parallelization of Arbitrary Doacross Loops

To reach high performances on massively parallel machines, optimizing compilers have to treat very efficiently all loop-level parallelism. Irregular control and irregular data accesses commonly appear in realistic scientific applications. Moreover many programs involve loops with cross-iteration data dependences, called DOACROSS loops. In this paper we propose a general technique to parallelize such crucial programs. We show that it is possible to perform a data-driven parallelization of arbitrary DOACROSS loops using non-matching send/receive and asymmetrical point to point synchronisations based on structural clocks. Keywords: Automatic parallelization; Doacross Execution; Parallel Programming Languages; Asynchronous Data-Parallel Execution; Structural Clock; Irregular Algorithm. Citation : This Research Report is the preprint version of an article currently submitted to the Europar'97 international conference. R'esum'e Pour atteindre de hautes performances sur les machines mass..