Metrics and Models for Reordering Transformations

TitleMetrics and Models for Reordering Transformations
Publication TypeReport
Year of Publication2004
AuthorsStrout, MM, Hovland, PD
Date Published06/2004
Other NumbersANL/MCS-P1167-0604
Abstract

<p>Irregular applications frequently exhibit poor performance on contemporary computer architectures, in large part because of their inefficient use of the memory hierarchy. Run-time data- and iteration-reordering transformations have been shown to improve the locality and therefore the performance of irregular benchmarks. This paper describes models for determining which combination of run-time data- and iteration-reordering transformations be viewed as approximating minimal linear arrangements on two separate hypergraphs: a spatial locality hypergraph on two separate hypergraphs: a spatial locality hypergraph and a temporal locality hypergraph. Our results measure the efficacy of locality metrics based on these hypergraphs in guiding the selection of data- and iteration-reordering heuristics. We also introduce new iteration- and data-reordering heuristics based on the hypergraph models that result in better performance than do previous heuristics.</p>

PDFhttp://www.mcs.anl.gov/papers/P1167.pdf