Improving Locality For Adaptive Irregular Scientific Codes

Loading...
Thumbnail Image

Files

CS-TR-4039.ps (1.22 MB)
No. of downloads: 229
CS-TR-4039.pdf (494.67 KB)
No. of downloads: 1169

Publication or External Link

Date

1999-09-25

Advisor

Citation

DRUM DOI

Abstract

An important class of scientific codes access memory in an irregular manner. Because irregular access patterns reduce temporal and spatial locality, they tend to underutilize caches, resulting in poor performance. Researchers have shown that consecutively packing data relative to traversal order can significantly reduce cache miss rates by increasing spatial locality.
In this paper, we investigate techniques for using partitioning algorithms to improve locality in adaptive irregular codes. We develop parameters to guide both geometric (RCB) and graph partitioning (METIS) algorithms, and develop a new graph partitioning algorithm based on hierarchical clustering (GPART) which achieves good locality with low overhead. We also examine the effectiveness of locality optimizations for adaptive codes, where connection patterns dynamically change at intervals during program execution. We use a simple cost model to guide locality optimizations when access patterns change. Experiments on irregular scientific codes for a variety of meshes show our partitioning algorithms are effective for static and adaptive codes on both sequential and parallel machines. Improved locality also enhances the effectiveness of LocalWrite, a parallelization technique for irregular reductions based on the owner computes rule. Also cross-referenced as UMIACS-TR-99-41

Notes

Rights