Two Level Nested Loops Tiled Iteration Space Scheduling By Changing Wave-Front Angles Approach

Abstract: Most of scientific applications need high speed and powerful computations. Using the computational potential of multiple processors enables us to achieve this goal. This factor as well as the story of former sequential programs that were so costly in generation, culminated at the invention of a tool named as “super-compiler” to automatically convert sequential code into parallel code. Super compilers identify the hidden parallelism inside programs and convert sequential programs into parallel ones. As most of computational programs incorporate nested loops, the parallel execution of these loops increases the running speed of programs. So the parallelization of nested loops is crucial for increasing the execution speed of programs. One of the conversion stages of sequential nested loops into parallel ones is to schedule the tiled iteration space. Regarding the fact that, so far the block and cyclic approaches have been introduced , in this paper the wave-front approach and wave-angle shifts have been incorporated in the block and cyclic approaches in order to reduce the execution time of two-level nested loops.

Keywords: nested loops, Iteration Tiled Space, Scheduling, Wave Fronts.