ON LOOP TRANSFORMATIONS FOR GENERALIZED CYCLE SHRINKING

This paper describes several loop transformation techniques for extrac ting parallelism from nested loop structures. Nested loops can when be scheduled to run in parallel so that execution time is minimized. One technique is called selective cycle shrinking, and the other is calle d true dependence cycle shrinking. It is shown how selective shrinking is related to linear scheduling of nested loops and how true dependen ce shrinking is related to conflict-free mappings of higher dimensiona l algorithms into lower dimensional processor arrays. Methods are prop osed in this paper to find the selective and true dependence shrinking s with minimum total execution time by applying the techniques of find ing optimal linear schedules and optimal and conflict-free mappings pr oposed in Shang and Fortes.