Coarse-Grained Loop Parallelization: Iteration Space Slicing vs Affine Transformations
Anna Beletska, Włodzimierz Bielecki, Albert Cohen, Marek Pałkowski, Krzysztof Siedlecki · 2009
Automatic coarse-grained parallelization of program loops is of great importance for multi-core computing systems. This paper presents a comparison of Iteration SpaceSlicing and Affine Transformation Framework algorithms aimed at extracting coarse-grained parallelism available in arbitrarily nested parameterized affine loops. We demonstrate that Iteration Space Slicing permits for extracting more coarse-grained parallelism in comparison to the Affine Transformation Framework. Experimental results show that by means of Iteration SpaceSlicing algorithms, we are able to extract coarse-grained parallelism for most loops of the NAS and UTDSP benchmarks, and that there is a strong need in devising advanced algorithms for calculating the exact transitive closure of dependence relations in order to increase the applicability of that framework.