" Cluster 2004 Abstract: Predicting Memory-Access Cost Based on Data Access Patterns

Predicting Memory-Access Cost Based on Data Access Patterns

Surendra Byna, et. al


The expanding processor-memory performance gap cause several scientific applications spend a major part of their execution time stalled in accessing memory. Loops are the basic blocks, where most of these data accesses take place. Memory performance improvement relies in optimizing these loop accesses. Loop transformations (e.g. loop unrolling, loop tiling) and array restructuring optimizations improve this performance by increasing the locality of memory accesses. However, to find the best optimization parameters dynamically at runtime, we need a fast and simple analytical model to predict the memory access cost. Most of the existing models are complex and impractical to be integrated in the automatic tuning systems. In this paper, we propose a simple, fast and reasonably accurate model that is capable of predicting the memory access cost based on a wide range of data access patterns. We classify the data access patterns that appear in the nested loops of scientific applications. We also discuss our applying this model in optimizing the performance of derived datatypes in Message Passing Interface (MPI) implementation.

Back to Program