research-article

Analytical cache models with applications to cache partitioning

Authors:

Srinivas Devadas,

Larry RudolphAuthors Info & Claims

ACM International Conference on Supercomputing 25th Anniversary Volume

Pages 323 - 334

https://doi.org/10.1145/2591635.2667181

Published: 17 June 2001 Publication History

Abstract

An accurate, tractable, analytic cache model for time-shared systems is presented, which estimates the overall cache miss-rate of a multiprocessing system with any cache size and time quanta. The input to the model consists of the isolated miss-rate curves for each process, the time quanta for each of the executing processes, and the total cache size. The output is the overall miss-rate. Trace-driven simulations demonstrate that the estimated miss-rate is very accurate. Since the model provides a fast and accurate way to estimate the effect of context switching, it is useful for both understanding the effect of context switching on caches and optimizing cache performance for time-shared systems. A cache partitioning mechanism is also presented and is shown to improve the cache miss-rate up to 25% over the normal LRU replacement policy.

References

[1]

A. AgarwM, M. Huruwitz, and J. Hennessy. An analytica/ cache mudel. A CM Transactions on Computer Systems, 7(2), May 1989.

[2]

Cumpaq. Cumpaq A1phaStatiun family.

[3]

T. M. Cuver and J. A. Thumas. Elements of Information Theory. Wiley, Juhn & Suns, Incurpurated, Mar. 1991.

[4]

S. J. Eggers, J. S. Enter, H. M. Levy, J. L. Lu, R. L. Stamm, and D. M. Tullsen. Simultaneous multithreading: A platfurm fur next-generatiun prucessurs. IEEE Micro, 17(5), 1997.

Digital Library

[5]

C. Freeburit. The hewlett packard PA-RISC 8500 processor. TechiticM report, Itewlett Packard Laboratories, Oct. 1998.

[6]

A. Goitzglez, M. VMero, N. Topham, aitd J. M. Parcerisa. Elimiitatiitg cache coitflict misses through XOR-based placemeitt functions. IIt the 1997 international conference on Supercomputing, 1997.

Digital Library

[7]

J. L. Heititiitg. SPEC CPU2000: Measuriitg CPU performaitce iit the Itew Itfilleititium. IEEE Computer, July 2000.

[8]

N. Jouppi. Improviitg direct-mapped cache performaitce by the additioit of a small fully-associative cache aitd prefetch buffers. IIt the 17th Annual International Symposium on Computer Architecture, 1990.

Digital Library

[9]

D. B. Kirk. Process depeitdeitt static cache partitioitiitg for reM-time systems. IIt Real-Time Systems Symposium, 1988.

[10]

H. Kwak, B. Lee, A. R. Hursoit, S.-H. Yooit, aitd W.-J. Hahn. Effects of multithreadiitg oft cache performaitce. IEEE Transactions on Computers, 48(2), Feb. 1999.

Digital Library

[11]

J. L. Lo, J. S. Emer, H. M. Levy, R. L. Stamm, D. M. Tullseit, aitd S. J. Eggers. Coitvertiitg thread-level parallelism to iitstructioit-level parallelism via simultaiteous multithreadiitg. ACM Transactions on Computer Systems, 15, 1997.

Digital Library

[12]

P. Magitussoit aitd B. Weriter. Efficieitt memory simulatioit iit SimICS. lit 28th Annual Simulation Symposium, 1995.

[13]

MIPS Techitologies, IItc. MIPS RIO000 Microprocessor" User's Manual, 1996.

[14]

J. C. Mogul aitd A. Borg. The effect of coittext switches oft cache performaitce. IIt the fourth international conference on Architectural support for programming languages and operating systems, 1991.

Digital Library

[15]

J. Muoz. Data-Intensive Systems Benchmark Suite Analysis and Specification. http://www.aec.com/projectweb/dis, Juite 1999.

[16]

M. Roseitblum, S. A. Herrod, E. Witchel, aitd A. Gupta. Complete computer system simulatioit: The SimOS approach. IEEE Parallel U Distributed Technology, 1995.

Digital Library

[17]

M. S. Squillaitte aitd E. D. Lazowska. Usiitg processor-cache Mtiitity iitformatioit lit shared-momory Itmltiprocessor scheduliitg. IEEE Transactions on Parallel and Distributed Systems, 4(2), Feb. 1993.

Digital Library

[18]

H. S. Stoite, J. Turek, aitd J. L. Wolf. Optimal partitioitiitg of cache memory. IEEE Transactions on Computers, 41(9), Sept. 1992.

Digital Library

[19]

G. E. Suh aitd L. Rudolph. Set-associative cache models for time-shared systems. Techitical Report CSG Memo 433, Massachusetts IItstitute of Techitology, 2001.

[20]

D. Thi6baut aitd H. S. Stoite. Footpriitts lit the cache. ACM Transactions on Computer Systems, 5(4), Nov. 1987.

[21]

D. Thi6baut, H. S. Stoite, aitd J. L. Wolf. Improviitg disk cache hit-ratios through cache partitioitiitg. IEEE Transactions on Computers, 41(6), Juite 1992.

Digital Library

[22]

N. Topham aitd A. Goitzf1ez. Raitdomized cache placemeitt for elemiitatiitg coitflicts. IEEE Transactions on Computers, 48(2), Feb. 1999.

Digital Library

[23]

J. Torrellas, A. Tucker, aitd A. Gupta. Beitefits of cache-Mtiitity scheduliitg lit shared-itmmory Itmltiprocessors: A summary, lit the 1993 ACM SIGMETRICS conference on Measurement and modeling of computer systems, 1993.

Digital Library

[24]

D. M. Tullseit, S. J. Eggers, aitd H. M. Levy. Simultaiteous multithreadiitg: Maximiziitg oft-chip parallelism. Iit 22nd Annual International Symposium on Computer" Architecture, 1995.

Digital Library

[25]

R. A. Uhlig aitd T. N. Mudge. Trace-driveit memory simulatioit: A survey. ACM Computing Surveys, 29(2), Juite 1997.

Digital Library

[26]

M. Zagha, B. Larsoit, S. Turner, aitd M. Itzkowitz. Performaitce analysis usiitg the MIPS R1000. IIt Supercomputing'96, 1996.

Digital Library

Cited By

Xiao JXiang YWang XLuo YPimentel AWang ZGallivan KNikolopoulos DBeivide RGallopoulos E(2023)FLORIA: A Fast and Featherlight Approach for Predicting Cache PerformanceProceedings of the 37th International Conference on Supercomputing10.1145/3577193.3593740(25-36)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1145/3577193.3593740
Xiang YWang XHuang ZWang ZLuo YWang ZOliveira RFelber PHu Y(2018)DCAPSProceedings of the Thirteenth EuroSys Conference10.1145/3190508.3190511(1-15)Online publication date: 23-Apr-2018
https://dl.acm.org/doi/10.1145/3190508.3190511
Hu XWang XZhou LLuo YWang ZDing CYe C(2018)Fast Miss Ratio Curve Modeling for Storage CacheACM Transactions on Storage10.1145/318575114:2(1-34)Online publication date: 12-Apr-2018
https://dl.acm.org/doi/10.1145/3185751

Index Terms

Analytical cache models with applications to cache partitioning

Recommendations

Analytical cache models with applications to cache partitioning
ICS '01: Proceedings of the 15th international conference on Supercomputing

An accurate, tractable, analytic cache model for time-shared systems is presented, which estimates the overall cache miss-rate of a multiprocessing system with any cache size and time quanta. The input to the model consists of the isolated miss-rate ...
Location cache: a low-power L2 cache system
ISLPED '04: Proceedings of the 2004 international symposium on Low power electronics and design

While set-associative caches incur fewer misses than direct-mapped caches, they typically have slower hit times and higher power consumption, when multiple tag and data banks are probed in parallel. This paper presents the location cache structure which ...
Improving cache performance with adaptive cache topologies and deferred coherence models

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

ACM International Conference on Supercomputing 25th Anniversary Volume

June 2014

94 pages

ISBN:9781450328401

DOI:10.1145/2591635

Editor:
Utpal Banerjee

Copyright © 2001 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

SIGARCH: ACM Special Interest Group on Computer Architecture

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 17 June 2001

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Research-article

Acceptance Rates

Overall Acceptance Rate 629 of 2,180 submissions, 29%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

3
Total Citations
View Citations
374
Total Downloads

Downloads (Last 12 months)19
Downloads (Last 6 weeks)1

Reflects downloads up to 24 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Xiao JXiang YWang XLuo YPimentel AWang ZGallivan KNikolopoulos DBeivide RGallopoulos E(2023)FLORIA: A Fast and Featherlight Approach for Predicting Cache PerformanceProceedings of the 37th International Conference on Supercomputing10.1145/3577193.3593740(25-36)Online publication date: 21-Jun-2023
https://dl.acm.org/doi/10.1145/3577193.3593740
Xiang YWang XHuang ZWang ZLuo YWang ZOliveira RFelber PHu Y(2018)DCAPSProceedings of the Thirteenth EuroSys Conference10.1145/3190508.3190511(1-15)Online publication date: 23-Apr-2018
https://dl.acm.org/doi/10.1145/3190508.3190511
Hu XWang XZhou LLuo YWang ZDing CYe C(2018)Fast Miss Ratio Curve Modeling for Storage CacheACM Transactions on Storage10.1145/318575114:2(1-34)Online publication date: 12-Apr-2018
https://dl.acm.org/doi/10.1145/3185751

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