A Mathematical Cache Miss Analysis for Pointer Data Structures.
Hongli Zhang, Margaret Martonosi · 2001
As the gap between processor and memory performance widens, careful analyses and optimizations of cache memory behavior become increasingly important. While analysis of regular loop-based scientific programs has made significant progress, the analysis of less regular reference patterns has lagged somewhat. This paper presents basic analytic expressions for cache miss behavior in fundamental types of irregular programs: linked list traversals and binary tree searches. We compare our analytic expressions to simulation-based results. Although quite elementary, these simple expressions will form the foundation for our planned work in analyzing the behavior of database and other applications which have linked lists, trees, and other pointer data structures at their core. 1 Introduction As the speed gap between processor and memory widens, the study of cache memory is increasingly important. Through the effort of many researchers, formal theory for cache behavior of arrays in numeric progra...