article

Free access

A model for estimating trace-sample miss ratios

Authors:

David A. Wood,

Mark D. Hill,

R. E. KesslerAuthors Info & Claims

ACM SIGMETRICS Performance Evaluation Review, Volume 19, Issue 1

Pages 79 - 89

https://doi.org/10.1145/107972.107981

Published: 02 April 1991 Publication History

PDF eReader

Abstract

Unknown references, also known as cold-start misses, arise during trace-driven simulation of uniprocessor caches because of the unknown initial conditions. Accurately estimating the miss ratio of unknown references, denoted by μ, is particularly important when simulating large caches with short trace samples, since many references may be unknown.In this paper we make three contributions regarding μ. First, we provide empirical evidence that μ is much larger than the overall miss ratio (e.g., 0.40 vs. 0.02). Prior work suggests that they should be the same. Second, we develop a model that explains our empirical results for long trace samples. In our model, each block frame is either live, if its next reference will hit, or dead, if its next reference will miss. We model each block frame as an alternating renewal process, and use the renewal-reward theorem to show that μ is simply the fraction of time block frames are dead. Finally, we extend the model to handle short trace samples and use it to develop several estimators of μ. Trace-driven simulation results show these estimators lead to better estimates of overall miss ratios than do previous methods.

References

[1]

Peter J. Bickel and Kjell A. Doksum. Mathematical Statistics. Holden-Day, Inc., San Francisco, 1977.

Google Scholar

[2]

Anita Borg, R. E. Kessler, and David W. Wall. Generation and analysis of very long address traces. In Proceedings of the 17th Annual International Symposium on Computer Architecture, pages 270-279, 1990.

Digital Library

Google Scholar

[3]

Malcom C. Easton and Ronald Fagin. Cold-start vs. warm-start miss ratios. Communications of the A CM, 21(10), October 1978.

Digital Library

Google Scholar

[4]

Leonard Kleinrock. Queueing Systems Volume 1: Theory. John Wiley and Sons, New York, 1975.

Google Scholar

[5]

S. Laha, J. H. Patel, and R. K. Iyer. Accurate low-cost methods for performance evaluation of cache memory systems. IEEE Transactions on Computers, 37(11):1325-1336, November 1988.

Digital Library

Google Scholar

[6]

Abraham Mendelson, Dominique Thi6baut, and Dhiraj Pradhan. Modeling live and dead lines in cache memory systems. Technical Report TR-90- CSE-14, Dept. of Electrical and Computer Engineering, University of Massachusetts, 1990.

Google Scholar

[7]

T.R. Puzak. Cache Memory Design. PhD thesis, University of Massachusetts, Amherst, MA, 1985.

Google Scholar

[8]

Sheldon M. Ross. Stochastzc Processes. John Wiley and Sons, New York, 1983.

Google Scholar

[9]

Alan Jay Smith. Cache memories. A CM Computing Surveys, 14(3):473-530, September 1982.

Digital Library

Google Scholar

[10]

Harold S. Stone. High-Performance Computer Architecture. Addison Wesley, second edition, 1990.

Digital Library

Google Scholar

[11]

Ronald W. Wolff. Stochastic Modeling and the Theory of Queues. Prentice-Hall, 1989.

Google Scholar

Cited By

View all

Kim MPark CHan MHan YKim S(2019)Epsim: A Scalable and Parallel Marssx86 Simulator With Exploiting Epoch-Based ExecutionIEEE Access10.1109/ACCESS.2018.28866307(4782-4794)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2018.2886630
Dube PTsao MZhang LBivens A(2012)Performance Modeling and Characterization of Large Last Level CachesProceedings of the 2012 IEEE 20th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems10.1109/MASCOTS.2012.50(379-388)Online publication date: 7-Aug-2012
https://dl.acm.org/doi/10.1109/MASCOTS.2012.50
Balasubramonian RJouppi NMuralimanohar N(2011)Multi-Core Cache HierarchiesSynthesis Lectures on Computer Architecture10.2200/S00365ED1V01Y201105CAC0176:3(1-153)Online publication date: 22-May-2011
https://doi.org/10.2200/S00365ED1V01Y201105CAC017
Show More Cited By

Index Terms

A model for estimating trace-sample miss ratios

Recommendations

A model for estimating trace-sample miss ratios
SIGMETRICS '91: Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems

Unknown references, also known as cold-start misses, arise during trace-driven simulation of uniprocessor caches because of the unknown initial conditions. Accurately estimating the miss ratio of unknown references, denoted by μ, is particularly ...
Trace Cache Miss Rate

Instruction fetch mechanism is a performance bottleneck of Superscalar and Simultaneous Multithreading Processors. A hardware mechanism, known as Trace Cache, is used in several processor architectures to improve instruction fetch performance. Most ...
Miss-Correlation Folding: Encoding Per-Block Miss Correlations in Compressed DRAM for Data Prefetching
IPDPS '12: Proceedings of the 2012 IEEE 26th International Parallel and Distributed Processing Symposium

Cache misses frequently exhibit repeated streaming behavior, i.e. a sequence of cache misses has a high tendency of being repeated. Correlation-based prefetchers record the missing streams in a history table for accurate prefetching. Saving a large miss ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGMETRICS Performance Evaluation Review

ACM SIGMETRICS Performance Evaluation Review Volume 19, Issue 1

May 1991

223 pages

ISSN:0163-5999

DOI:10.1145/107972

Editor:
Tom W. Keller
IBM Corp., Austin, TX

Issue’s Table of Contents

SIGMETRICS '91: Proceedings of the 1991 ACM SIGMETRICS conference on Measurement and modeling of computer systems
April 1991
228 pages
ISBN:0897913922
DOI:10.1145/107971
Chairman:
Tom W. Keller
IBM Corp, Austin, TX

Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than ACM must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from [email protected]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 02 April 1991

Published in SIGMETRICS Volume 19, Issue 1

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

119
Total Citations
View Citations
939
Total Downloads

Downloads (Last 12 months)61
Downloads (Last 6 weeks)20

Reflects downloads up to 21 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Kim MPark CHan MHan YKim S(2019)Epsim: A Scalable and Parallel Marssx86 Simulator With Exploiting Epoch-Based ExecutionIEEE Access10.1109/ACCESS.2018.28866307(4782-4794)Online publication date: 2019
https://doi.org/10.1109/ACCESS.2018.2886630
Dube PTsao MZhang LBivens A(2012)Performance Modeling and Characterization of Large Last Level CachesProceedings of the 2012 IEEE 20th International Symposium on Modeling, Analysis and Simulation of Computer and Telecommunication Systems10.1109/MASCOTS.2012.50(379-388)Online publication date: 7-Aug-2012
https://dl.acm.org/doi/10.1109/MASCOTS.2012.50
Balasubramonian RJouppi NMuralimanohar N(2011)Multi-Core Cache HierarchiesSynthesis Lectures on Computer Architecture10.2200/S00365ED1V01Y201105CAC0176:3(1-153)Online publication date: 22-May-2011
https://doi.org/10.2200/S00365ED1V01Y201105CAC017
Bryan T(2009)Statistical Sampling for Processor and Cache SimulationPerformance Evaluation and Benchmarking10.1201/9781420037425.ch6(87-115)Online publication date: 9-Nov-2009
https://doi.org/10.1201/9781420037425.ch6
Mutlu OMoscibroda T(2007)Stall-Time Fair Memory Access Scheduling for Chip MultiprocessorsProceedings of the 40th Annual IEEE/ACM International Symposium on Microarchitecture10.1109/MICRO.2007.40(146-160)Online publication date: 1-Dec-2007
https://dl.acm.org/doi/10.1109/MICRO.2007.40
Berg EZeffer HHagersten E(2006)A statistical multiprocessor cache model2006 IEEE International Symposium on Performance Analysis of Systems and Software10.1109/ISPASS.2006.1620793(89-99)Online publication date: 2006
https://doi.org/10.1109/ISPASS.2006.1620793
Lu XFu YTang T(2005)Reducing leakage power in instruction cache using WDC for embedded processorsProceedings of the 2005 Asia and South Pacific Design Automation Conference10.1145/1120725.1121046(1292-1295)Online publication date: 18-Jan-2005
https://dl.acm.org/doi/10.1145/1120725.1121046
Berg EHagersten E(2005)Fast data-locality profiling of native executionACM SIGMETRICS Performance Evaluation Review10.1145/1071690.106423233:1(169-180)Online publication date: 6-Jun-2005
https://dl.acm.org/doi/10.1145/1071690.1064232
Berg EHagersten EEager DWilliamson CBorst SLui J(2005)Fast data-locality profiling of native executionProceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems10.1145/1064212.1064232(169-180)Online publication date: 6-Jun-2005
https://dl.acm.org/doi/10.1145/1064212.1064232
Kattner REger MMüller-Schloer C(2005)Modeling cache coherence overhead with geometric objectsParallel Processing: CONPAR 94 — VAPP VI10.1007/3-540-58430-7_39(438-448)Online publication date: 3-Jun-2005
https://doi.org/10.1007/3-540-58430-7_39
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations