Determing Schedules based on Performance Estimation
Determing Schedules based on Performance Estimation
Files
Publication or External Link
Date
1998-10-15
Authors
Kelly, Wayne
Pugh, William
Advisor
Citation
DRUM DOI
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 a schedule that maps the original iteration space to
a new iteration space. We show how we can estimate the performance of a
program by considering only the schedule from which it was produced.
We also show how to produce an upper bound on performance given only a
partially specified schedule. Our ability to estimate performance
directly from schedules and to do so even for partially specified
schedules allows us to efficiently find schedules which will produce
good code.
(Also cross-referenced as UMIACS-TR-93-67)