A Unified Framework for Systemic Loop Transformation

Abstract

This paper presents a formal mathematical framework which unifies the existing loop transformations.This framework also includes more general classes of loop transformations, which can extract more parallelism from a class of programs than the existing techniques.We classify schedules into three classes: unij'orm, subdomainvariant, and statement-variant.Viewing from the degree of parallelism to be gained by loop transformation, the schedules can also be classified as single-sequential level, multiple-sequential level, and mited schedules.We also illustrate the usefulness of the more general loop transformation with an example program.