Selecting A ne Mappings based on Performance EstimationWayne

Abstract

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 aane 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 speciied mapping. Our ability to estimate performance directly from mappings and to do so even for partially speciied mappings allows us to eeciently nd mappings which will produce good code. Abstract In KP93] 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 transforma-tion(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 aane 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 speciied mapping. Our ability to estimate performance directly from mappings and to do so even for partially speciied mappings allows us to eeciently nd mappings which will produce good code.

Topics

    0 Figures and Tables

      Download Full PDF Version (Non-Commercial Use)