Determining schedules based on performance estimation
Wayne Kelly, William White Tison Pugh · 1993
In previous work, we presented a framework for unifying iteration reordering transformations such as loop interchange, loop distribution, loop skewing and statement reordering. The framework provides a uniform way to represent and reason about transformations. However, it does not provide a way to decide which transformation(s) should be applied to a given program. This paper describes a way to make such decisions within the context of the framework. The framework is based on the idea that a transformation can be represented as an affine mapping from the original iteration space to a new iteration space. We show how we can estimate the performance of a program by considering only the mapping from which it was produced. We also show how to produce an lower bound on performance given only a partially specified mapping. Our ability to estimate performance directly from mappings and to do so even for partially specified mappings allows us to efficiently find mappings which will produce goo...