Loop Shifting Conversion for the Parallelizing Compiler

K. Iwasawa and T. Kusaba (Japan)


parallelization, compiler, loop carrieddependence, loop independent dependence, loop conversion,OpenMP program


The paper describes an optimization technique for parallelizing compilers, called semi-circle loop conversion. Our pre-compiler will generate parallelized OpenMP C programs form serial C programs. The parallelizing conversion technique is shown. The conversion which shifts the loop in a semicircle is proposed in order to delete synchronization and data passing. When each repetition of the loop is executed in parallel, the conversion changes loop carries data dependency, which passes through the back edge once, into loop independent dependency. This conversion establishes the new origin of the loop repetition, and rearranges statements. It dose not produce new overheads in the loop such as the conditional jump and data copy, and it can also deal with multi nested loops and loop including the conditional structure. By using this conversion, it is possible to independently execute the loop in parallel, otherwise synchronization and communication is necessary.

Important Links:

Go Back