Extracting Coarse-Grained Parallelism in Program Loops with the Slicing Framework

A novel approach for extracting coarse-grained parallelism being represented with independent and synchronization-requiring slices is presented. Each slice is composed of dependent iterations of perfectly nested loops. Presented algorithms work for both uniform and non-uniform loops. Our approach, based on operations on relations and sets, requires exact dependence analysis. Examples illustrating the proposed algorithm and results of experiments are presented.