@inproceedings{c07c8070bc5d4d0586f506b216499167,
title = "Metrics and models for reordering transformations",
abstract = "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 heuristics will result in the best performance for a given dataset. We propose that the data- and iteration-reordering transformations be viewed as approximating minimal linear arrangements 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.",
keywords = "Data locality, Inspector/executor, Locality metrics, Optimization, Run-time reordering transformations, Spatial locality graph, Temporal locality hypergraph",
author = "Strout, {Michelle Mills} and Hovland, {Paul D.}",
year = "2004",
doi = "10.1145/1065895.1065899",
language = "English (US)",
isbn = "1581139411",
series = "Proceedings of the ACM SIGPLAN Workshop on Memory System Performance, MSP 2004",
pages = "23--34",
booktitle = "Proceedings of the ACM SIGPLAN Workshop on Memory System Performance, MSP 2004",
note = "2nd ACM SIGPLAN Workshop on Memory Systems Performance, MSP 2004 ; Conference date: 08-06-2004 Through 08-06-2004",
}