@inproceedings{74de9a634ca94488a97ca4e3f3fc5fe9,
title = "Calculating stack distances efficiently",
abstract = "This paper1 describes our experience using the stack processing algorithm [6] for estimating the number of cache misses in scientific programs. By using a new data structure and various optimization techniques we obtain instrumented run-times within 50 to 100 times the original optimized runtimes of our benchmarks.",
keywords = "Cache modeling, Measurement and monitoring, Memory systems, Simulation",
author = "George Alm{\'a}si and Cǎlin Ca{\c s}caval and Padua, {David A.}",
note = "Funding Information: Caches have become one of the most important components in computer systems. As processor speed increases much faster than memory speed, the memory subsystem becomes the bottleneck. To alleviate this behavior, computer architects have designed deeper memory hierarchies, including several levels of cache. The stack algorithm [6] was originally designed for modeling virtual paging, i.e. to operate on a program trace consisting of virtual page references, but in the recent past has been used mainly to model cache behavior, by tracing cache line references [7, 8, 4, 10]. Different architectures exhibit different memory systems with caches organized in different configurations. In order to make the best use of the memory hierarchy, either the programmer or the compiler must be aware of the cache organization of the machine. We believe that the programmer should not be burdened with this responsibility, therefore we have developed a memory hierarchy model that helps the compiler to predict the number of cache misses, and thus reorganize the code to optimize the cache behavior. This memory model is based on the stack distances obtained from a stack processing algorithm [6]. The main advantage of the stack algorithm in simulating cache behavior is that it allows the estimation of the number of misses for caches of any size in a single pass through the 1This work was supported in part by NSF contract ACI98-70687. Publisher Copyright: Copyright 2002 ACM. Copyright: Copyright 2017 Elsevier B.V., All rights reserved.; 2002 Workshop on Memory System Performance, MSP 2002 ; Conference date: 16-06-2002",
year = "2002",
month = jun,
day = "16",
doi = "10.1145/773146.773043",
language = "English (US)",
series = "Proceedings of the 2002 Workshop on Memory System Performance, MSP 2002",
publisher = "Association for Computing Machinery, Inc",
pages = "37--43",
booktitle = "Proceedings of the 2002 Workshop on Memory System Performance, MSP 2002",
}