On loop transformations for generalized cycle shrinking

TitleOn loop transformations for generalized cycle shrinking
Publication TypeJournal Article
Year of Publication1994
AuthorsShang, W, O'Keefe, MT, Fortes, JAB
JournalParallel and Distributed Systems, IEEE Transactions
Start Page193-204
Date Published02/1994
AbstractThis paper describes several loop transformation techniques for extracting parallelism from nested loop structures. Nested loops can then be scheduled to run in parallel so that execution time is minimized. One technique is called selective cycle shrinking, and the other is called true dependence cycle shrinking. It is shown how selective shrinking is related to linear scheduling of nested loops and how true dependence shrinking is related to conflict-free mappings of higher dimensional algorithms into lower dimensional processor arrays. Methods are proposed in this paper to find the selective and true dependence shrinkings with minimum total execution time by applying the techniques of finding optimal linear schedules and optimal and conflict-free mappings proposed by W. Shang and A.B. Fortes