Metrics and Models for Reordering Transformations

Paul Hovland
Argonne National Lab

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 previous heuristics.

(Joint work with Michelle Mills Strout)