Coarse-grained loop parallelization: Iteration Space Slicing vs affine transformations

Automatic coarse-grained parallelization of program loops is of great importance for parallel computing systems. This paper presents the theory of Iteration Space Slicing aimed at extracting synchronization-free parallelism available in arbitrarily nested program loops. We demonstrate that Iteration Space Slicing algorithms permits for extracting more coarse-grained parallelism than that extracted by means of the Affine Transformation Framework provided that we are able to calculate the transitive closure of the union of relations describing all dependences in the affine loop. Experimental results show that by means of Iteration Space Slicing algorithms, we are able to extract coarse-grained parallelism for many loops of NAS and UTDSP benchmarks. Problems to be resolved in order to enhance the theory of Iteration Space Slicing are discussed.

Research highlights
► Iteration Space Slicing extracts synchronization-free parallelism in loops.
► It uses transitive closure of dependence relations.
► It exposes more parallelism than that extracted by affine transformations.
► Experimental results demonstrate effectiveness and efficiency of slicing.