More Web Proxy on the site http://driver.im/

Article

Cache miss behavior: is it √2?

Authors:

P. G. EmmaAuthors Info & Claims

CF '06: Proceedings of the 3rd conference on Computing frontiers

Pages 313 - 320

https://doi.org/10.1145/1128022.1128064

Published: 03 May 2006 Publication History

Abstract

It has long been empirically observed that the cache miss rate decreased as a power law of cache size, where the power was approximately -1/2. In this paper, we examine the dependence of the cache miss rate on cache size both theoretically and through simulation. By combining the observed time dependence of the cache reference pattern with a statistical treatment of cache entry replacement, we predict that the cache miss rate should vary with cache size as an inverse power law for a first level cache. The exponent in the power law is directly related to the time dependence of cache references, and lies between -0.3 to -0.7. Results are presented for both direct mapped and set associative caches, and for various levels of the cache hierarchy. Our results demonstrate that the dependence of cache miss rate on cache size arises from the temporal dependence of the cache access pattern.

References

[1]

R. Kalla, B.Sinharoy, and J. Tendler. "IBM Power5 Chip: A dual-core multi-threaded processor", IEEE Micro 24(2), 40-47, 2004.

Digital Library

[2]

D. Boggs et al. "The microarchitecture of the Intel Pentium 4 processor on 90 nm technology", Intel Technology Journal 8, Issue 1, 1997.

[3]

http://www.amd.com, Technical Documentation. "AMD Opteron Product Data Sheet", Publication number 23932, 2004.

[4]

http://www.sun.com/processors/manuals/USIV_v1.0.pdf. "UltraSPARC IV Processor", User's Manual Supplement, Version 1.0, 2004.

[5]

C. K. Chow. "On Optimization of Storage Hierarchies", IBM Journal of R & D 18, 194--203, 1974.

Digital Library

[6]

C. K. Chow. "Determination of Cache's Capacity and its Matching Storage Hierarchy", IEEE Transactions on Computers, c-25, 157--164, 1976.

Digital Library

[7]

J. S. Harper, D. J. Kerbyson and G. R. Nudd. "Efficient Analytical Modelling of Multi-Level Set-Associative Caches", Proceedings of the International Conference HPCN Europe '99' 1593, pp. 473--482, 1999.

Digital Library

[8]

S. Przybylski, M. Horowitz and J. Hennessy. "Performance Tradeoffs in Cache Design", Proceedings of the 15th Annual International Symposium on Computer Architecture, pp. 290--298, 1988.

Digital Library

[9]

S. Przybylski, M. Horowitz and J. Hennessy. "Characteristics of Performance-Optimal Multi-Level Cache Hierarchies", Proceedings of the 16th Annual International Symposium on Computer Architecture, pp. 114--121, 1989.

Digital Library

[10]

G. S. Rao. "Performance Analysis of Cache Memories", JACM 25, 378--395, 1978.

Digital Library

[11]

J. H. Saltzer. "A Simple Linear Model of Demand Paging Performance", CACM 17, 181--186, 1974.

Digital Library

[12]

A. J. Smith. "Cache Memories", Computing Surveys 14, 473--528, 1982.

Digital Library

[13]

M. H. Macdougall. "Instruction-level Program and Processor Modeling", Computer 7, 14--24, 1984.

Digital Library

[14]

J. P. Singh, H. S. Stone and D. F. Thiebaut. "A Model of Workloads and Its Use in Miss-Rate Prediction for Fully Associative Caches", IEEE Transactions on Computers 41, 811--825, 1992.

Digital Library

[15]

A. Hartstein and T. R. Puzak. "Optimum Power/Performance Pipeline Depth", Proc. of the 36th Annual IEEE/ACM International Symposium on Microarchitecture, pp. 117--125, 2003.

Digital Library

[16]

D. Thiebaut, J. L. Wolf and H. S. Stone. "Synthetic Traces for Trace-Driven Simulation of Cache Memories", IEEE Transactions on Computers 41, 388--410, 1992.

Digital Library

Cited By

Cherezov AVasiliev AFerroukhi H(2023)Acceleration of Nuclear Reactor Simulation and Uncertainty Quantification Using Low-Precision ArithmeticApplied Sciences10.3390/app1302089613:2(896)Online publication date: 9-Jan-2023
https://doi.org/10.3390/app13020896
Ajrian AEbadi MDelijani EKoroteev D(2023)SERIAL AND DIFFERENT PARALLEL IMPLEMENTATIONS OF LATTICE BOLTZMANN METHOD IN PYTHON: A COMPARATIVE ANALYSISComputational Thermal Sciences: An International Journal10.1615/ComputThermalScien.202304560015:5(55-70)Online publication date: 2023
https://doi.org/10.1615/ComputThermalScien.2023045600
Lai PFan RZhang XZhang WLiu FZhou J(2022)Utility Optimal Thread Assignment and Resource Allocation in Multi-Server SystemsIEEE/ACM Transactions on Networking10.1109/TNET.2021.312381730:2(735-748)Online publication date: Apr-2022
https://doi.org/10.1109/TNET.2021.3123817
Show More Cited By

Index Terms

Cache miss behavior: is it √2?
1. Hardware
  1. Communication hardware, interfaces and storage
    1. External storage
  2. Integrated circuits
    1. Semiconductor memory
      1. Dynamic memory
      2. Non-volatile memory

Recommendations

Tag-Split Cache for Efficient GPGPU Cache Utilization
ICS '16: Proceedings of the 2016 International Conference on Supercomputing

Modern GPUs employ cache to improve memory system efficiency. However, large amount of cache space is underutilized due to irregular memory accesses and poor spatial locality which exhibited commonly in GPU applications. Our experiments show that using ...
Increasing hardware data prefetching performance using the second-level cache

Techniques to reduce or tolerate large memory latencies are critical for achieving high processor performance. Hardware data prefetching is one of the most heavily studied solutions, but it is essentially applied to first-level caches where it can ...
Increasing cache capacity through word filtering
ICS '07: Proceedings of the 21st annual international conference on Supercomputing

With the increasing performance gap between processor and memory, it is essential that caches are utilized efficiently. However, caches are very inefficiently utilized because not all the excess data fetched into the cache, to exploit spatial locality, ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

CF '06: Proceedings of the 3rd conference on Computing frontiers

May 2006

430 pages

ISBN:1595933026

DOI:10.1145/1128022

General Chairs:
Monica Alderighi
IASF - INAF
,
Valentina Salapura
IBM
,
Program Chair:
Sally A. McKee
Cornell University

Copyright © 2006 ACM.

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]

Sponsors

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 03 May 2006

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Article

Conference

CF06

Sponsor:

CF06: Computing Frontiers Conference

May 3 - 5, 2006

Ischia, Italy

Acceptance Rates

Overall Acceptance Rate 273 of 785 submissions, 35%

Upcoming Conference

CF '25

Sponsor:
sigmicro

22nd ACM International Conference on Computing Frontiers

May 28 - 30, 2025

Cagliari , Italy

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

27
Total Citations
View Citations
871
Total Downloads

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

Reflects downloads up to 06 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Cherezov AVasiliev AFerroukhi H(2023)Acceleration of Nuclear Reactor Simulation and Uncertainty Quantification Using Low-Precision ArithmeticApplied Sciences10.3390/app1302089613:2(896)Online publication date: 9-Jan-2023
https://doi.org/10.3390/app13020896
Ajrian AEbadi MDelijani EKoroteev D(2023)SERIAL AND DIFFERENT PARALLEL IMPLEMENTATIONS OF LATTICE BOLTZMANN METHOD IN PYTHON: A COMPARATIVE ANALYSISComputational Thermal Sciences: An International Journal10.1615/ComputThermalScien.202304560015:5(55-70)Online publication date: 2023
https://doi.org/10.1615/ComputThermalScien.2023045600
Lai PFan RZhang XZhang WLiu FZhou J(2022)Utility Optimal Thread Assignment and Resource Allocation in Multi-Server SystemsIEEE/ACM Transactions on Networking10.1109/TNET.2021.312381730:2(735-748)Online publication date: Apr-2022
https://doi.org/10.1109/TNET.2021.3123817
Zhang FSakr MHwang KKhan S(2019)Empirical Discovery of Power-Law Distribution in MapReduce ScalabilityIEEE Transactions on Cloud Computing10.1109/TCC.2017.26693207:3(744-755)Online publication date: 1-Jul-2019
https://doi.org/10.1109/TCC.2017.2669320
Asad ADorostkar AMohammadi F(2018)A novel power model for future heterogeneous 3D chip-multiprocessors in the dark silicon ageEURASIP Journal on Embedded Systems10.1186/s13639-018-0086-12018:1Online publication date: 27-Jul-2018
https://doi.org/10.1186/s13639-018-0086-1
Li ALiu WKristensen MVinter BWang HHou KMarquez ASong SMohr BRaghavan P(2017)Exploring and analyzing the real impact of modern on-package memory on HPC scientific kernelsProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3126908.3126931(1-14)Online publication date: 12-Nov-2017
https://dl.acm.org/doi/10.1145/3126908.3126931
Dai HLi CZhou HGupta SKartsaklis CMantor M(2016)A model-driven approach to warp/thread-block level GPU cache bypassingProceedings of the 53rd Annual Design Automation Conference10.1145/2897937.2897966(1-6)Online publication date: 5-Jun-2016
https://dl.acm.org/doi/10.1145/2897937.2897966
Venkatesan VTay YWei Q(2016)Sizing Cleancache Allocation for Virtual Machines’ Transcendent MemoryIEEE Transactions on Computers10.1109/TC.2015.245602565:6(1949-1963)Online publication date: 1-Jun-2016
https://doi.org/10.1109/TC.2015.2456025
Yatao Zhu Shuai Zhang Xiaochun Ye Da Wang Xu Tan Dongrui Fan Zhimin Zhang Hongliang Li (2016)An energy-efficient bandwidth allocation method for single-chip heterogeneous processor2016 Seventh International Green and Sustainable Computing Conference (IGSC)10.1109/IGCC.2016.7892617(1-7)Online publication date: 2016
https://doi.org/10.1109/IGCC.2016.7892617
Garcia-Guirado AFernandez-Pascual RGarcia J(2015)ICCI: In-Cache Coherence InformationIEEE Transactions on Computers10.1109/TC.2014.230818564:4(995-1014)Online publication date: 1-Apr-2015
https://dl.acm.org/doi/10.1109/TC.2014.2308185
Show More Cited By

View Options

Login options

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

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Table of Contents