Run-time reference clustering for cache performance optimization

We introduce a method for improving the cache performance of irregular computations in which data are referenced through run time defined indirection arrays. Such computations often arise in scientific problems. The presented method called Run-Time Reference Clustering (RTRC), is a run time analog of a compile time blocking used for dense matrix problems. RTRC uses the data partitioning and remapping techniques that are a part of distributed memory multiprocessor codes designed to minimize interprocessor communication. Remapping each set of local data decreases cache misses, the same way remapping the global data decreases off-processor references. We demonstrate the applicability and performance of the RTRC technique on several prevalent applications: Sparse Matrix-Vector Multiply, Particle-in-Cell, and CHARMM like codes. Performance results on SPARC-20, SP-2, and T3-D processors show that single node execution performance can be improved by as much as 35%