Implementing stack simulation for highly-associative memories
- 2 April 1991
- journal article
- Published by Association for Computing Machinery (ACM) in ACM SIGMETRICS Performance Evaluation Review
- Vol. 19 (1), 212-213
- https://doi.org/10.1145/107972.107995
Abstract
Prior to this work, all implementations of stack simulation [MGS70] required more than linear time to process an address trace. In particular these implementations are often slow for highly-associative memories and traces with poor locality, as can be found in simulations of tile systems. We describe a new implementation of stack simulation where the refrrenced block and its stack distance are found using a hash table rather than by traversing the stack. The key to this implementation is that designers are rarely interested in a continuum of memory sizes, but instead desire metrics for only a discrete set of alternatives (e.g., powers of two). Our experimental evaluation shows the run-time of the new implementation to be linear in address trace length and independent of trace locality. Kim, et al., [KHW91] present the results of this research in more detail.Keywords
This publication has 5 references indexed in Scilit:
- Data cache management using frequency-based replacementPublished by Association for Computing Machinery (ACM) ,1990
- Generation and analysis of very long address tracesPublished by Association for Computing Machinery (ACM) ,1990
- Efficient methods for calculating the success function of fixed-space replacement policiesPublished by Office of Scientific and Technical Information (OSTI) ,1981
- Two Methods for the Efficient Analysis of Memory Address Trace DataIEEE Transactions on Software Engineering, 1977
- Evaluation techniques for storage hierarchiesIBM Systems Journal, 1970