StatStack: Efficient modeling of LRU caches

Efficient execution on modern architectures requires good data locality, which can be measured by the powerful stack distance abstraction. Based on this abstraction, the miss rate for LRU caches of any size can be predicted. However, measuring stack distance requires the number of unique memory objects to be counted between successive accesses to the same data object, which requires complex and inefficient data collection. This paper presents a new efficient way of estimating the stack distances of an application. Instead of counting the number of unique memory objects touched between successive accesses to the same data, our scheme only requires the number of memory accesses to be counted, a task efficiently handled by existing builtin hardware counters. Furthermore, this information only needs to be captured for a small fraction of the memory accesses. A new efficient off-line algorithm is proposed to estimate the corresponding stack distance based on this sparse information. We evaluate the accuracy of the proposed estimation compared with full stack distance measurements for 28 of the applications in the SPEC CPU2006 benchmark suite. The estimation shows excellent accuracy based on information about only every 10,000th memory access.