Exploring memory access regularity in pointer-intensive application programs

Keqiang Wu, Resit Sendag, David J. Lilja

Research output: Contribution to journalArticle


Pointer-intensive and sparse numerical computations typically display irregular memory access behavior. This work presents a mathematical model, called the Self-tuning Adaptive Predictor (SAP), to characterize the behavior of load instructions in procedures with pointer-based data structures by using procedure call boundaries as the fundamental sampling frequency. This model incorporates information about the history of specific load instructions (temporal locality) and their neighboring loads (spatial locality) using a least-squares minimization approach. Simulation results on twelve of the most time-consuming procedures with pointer-based data structures from five of the SPEC2000 integer benchmark programs show that these pointerbased data structures demonstrate surprisingly regular memory access patterns. The prediction error at steady-state is within [-6%, +6%] on average.

Original languageEnglish (US)
Pages (from-to)472-476
Number of pages5
JournalLecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
StatePublished - Dec 1 2004


Cite this