Delivering High Performance to Parallel Applications Using Advanced Scheduling (Extended Abstract)

This paper presents a complete framework for the parallelization of nested loops by applying tiling transformation and automatically generating MPI code allowing for an advanced scheduling scheme. In particular, under advanced scheduling scheme we consider two separate techniques: first, the applica-tion of a suitable tiling transformation, and second the overlapping of computation and communication when executing the parallel program. As far as the choice of a scheduling-efficient tiling transformation is concerned, the data dependencies of the initial algorithm are taken into account and an appropriate transformation matrix is automatically generated according to a well-established theory. On the other hand, overlapping computation with communication partly hides the communication overhead and al-lows for a more efficient processor utilization. We address all issues concerning automatic paralleliza-tion of the initial algorithm. More specifically, we have developed a tool that automatically generates MPI C code and supports arbitrary tiling transformations as well as both communication schemes, e.g. the conventional receive-compute-send scheme and the overlapping one. We investigate the performance benefits in the total execution time of the parallel program attained by the use of the advanced scheduling scheme, and experimentally verify with the help of application-kernel benchmarks (SOR, ADI, Jacobi