article

Free access

Avoiding conflict misses dynamically in large direct-mapped caches

Authors:

Brian N. Bershad,

Theodore H. Romer,

J. Bradley ChenAuthors Info & Claims

ACM SIGPLAN Notices, Volume 29, Issue 11

Pages 158 - 170

https://doi.org/10.1145/195470.195527

Published: 01 November 1994 Publication History

Abstract

This paper describes a method for improving the performance of a large direct-mapped cache by reducing the number of conflict misses. Our solution consists of two components: an inexpensive hardware device called a Cache Miss Lookaside (CML) buffer that detects conflicts by recording and summarizing a history of cache misses, and a software policy within the operating system's virtual memory system that removes conflicts by dynamically remapping pages whenever large numbers of conflict misses are detected. Using trace-driven simulation of applications and the operating system, we show that a CML buffer enables a large direct-mapped cache to perform nearly as well as a two-way set associative cache of equivalent size and speed, although with lower hardware cost and complexity.

References

[1]

Agarwal, A. and Pudar, S. D. Column-Associative Caches: A Technique for Reducing the Miss Rate of Direct Mapped Caches. In Proc. ~Oth Annual international Symposium On C,omputer Architecture, pages 179-190, May 1993.

Digital Library

[2]

Borg, A., Kessler, R., Lazana, G., and Wall, D. Long Address Traces From RISC Machines: Generation and Analysis. WRL Research Report 89/14, Digital Equipment Corporation Western Research Laboratory, 1989.

[3]

Bray, B. K., Lynch, W. L., and Flynn, M. J. Page Allocation to Reduce Access Time of Physical Caches. Technical Report CSL-TR-90-454, Stanford University, 1990.

Digital Library

[4]

Chambers, C. The Cecil Language: Specification and Rationale. Technical Report 93-03- 05, University of Washington, March 1993.

[5]

Chert, J. B. and Bershad, B. N. The Impact of Operating System Structure on Memory System Performance. in Proceedings of the ldth A C,M Symposium on Operating System Principles, pages 120-133, December 1993.

Digital Library

[6]

Chen, J. B. Software Methods for System Address Tracing. In Proceedings of the,lth Workshop On Workstation Operating Systems, pages 178-185. IEEE Computer Society Press, October 1993.

[7]

Custer, H. Inside W~ndows NT. Microsoft Press, 1993.

Digital Library

[8]

Digital Equipment Corporation. Cord, 1991.

[9]

Digital Equipment Corporation. DEC'chip ~106,~-AA Microprocessor, Hardware Reference Manual, 1992. Order Number: EC-N0079-72.

[10]

Dutton, T., Eiref, D., Kurth, H., Reisert, J., and Stewart, R. The Design of the DEC :t000 AXP Systems, Two High-Performance Workstations. Digital Technical Journal, 4(4):66-81, 1992. Special Issue.

[11]

Hill, M. D. Aspects of Cache Memory and Instruction Buffer Performance. PhD dissertation, University of California at Berkeley, Computer Sciences Division, November 1987. Number UCB/CSD 87/381.

Digital Library

[12]

Hill, M. D. A Case for Direct-Mapped Caches. IEEE Computer, pages 25-40, December 1988.

Digital Library

[13]

Hosking, A. L. and Moss, J. E. B. Protection Traps and Alternatives for Memory Management of an Object Oriented Language. In Procee~ngs of the ldth A CM Symposium on Operating System Principles, pages 106-119, December 1993.

Digital Library

[14]

Hwu, W.-m. and Chang, P. Achieving High Instruction Cache Performance with an Optimizing Compiler. In Proceedings of the 16th Annual International Symposium On Computer Architecture, pages 183-191, June 1989.

Digital Library

[15]

Jouppi, N. P. Improving Direct-Mapped Cache Performance by the Addition of a Small Fully- Associative Cache and Prefetch Buffers. In Proceedings of the 17th Annual Internatzonal Symposzum On Computer Architecture, pages 364- 373, May 1990.

Digital Library

[16]

Kane, G. MIPS RISC Archztecture. Prentice- Hall, Englewood Cliffs, N J, 1988.

Digital Library

[17]

Kessler, R. and Hill, M. D. Page Placement Algorithms for Large ReM-Indexed Caches. A CM Transactions on Computer Systems, 10(4):338-359, November 1992.

Digital Library

[18]

Kurpanek, G., Chan, K., Zheng, J., DeLano, E., and Bryg, W. PA7200: A PA- RISC Processor with Integrated High Performance MP Bus Interface. In Digest of Papers. Spring COMPCON 9~, pages 375-382, 1994.

[19]

McFarling, S. Program Optimization for instruction Caches. In Proceedings of the 3rd International Conference On Architectural Support for Programmzng Languages and Operating Systems, pages 183-191, April 1989.

Digital Library

[20]

Pettis, K. and Itansen, R. Profile Guided Code Positioning. In Procee~ngs of the Conference On Programming Language Design and Implementation, pages 16-26, June 1990.

Digital Library

[21]

Przybylski, S. A., Horowitz, M., and Hennessy, J. L. Performance Tradeoffs in Cache Design. In Proceedzngs of the 15th Annual International Symposzum on Computer Architecture, pages 290-298. IEEE, May 1988.

Digital Library

[22]

Smith, A. J. Cache Memories. A CM Computer Surveys, 14(3):473-530, September 1982.

Digital Library

[23]

Taylor, G., Davies, P., and FarmwaJd, M. The TLB Slice - A Low-cost High-Speed Address Translation Mechanisms. In Proceedings of the 17th Annual International Sympos,um On Computer Architecture, pages 355-363, May 1990.

Digital Library

[24]

ULTRIX Documentation Group, Digital Equipment Corporation. ULTRIX Documentation Overview .for RISC Processors, 1989. Order number AA-NE13A-TE.

[25]

Wahbe, R., Lucco, S., Anderson, T. E., and Graham, S. L. Efficient Software-Based Fault Isolation. In Proceedings of the 1,ith A CM Sympossum on Operating System Principles, pages 203-216, December 1993.

Digital Library

[26]

Wall, D. W. Systems for Late Code Modification, pages 275-293. Springer-Verlag, 1992.

[27]

Wheeler, B. and Bershad, B. N. Consistency Management for Virtually Indexed Caches. In Proceedings of the 5th International Conference on Archatectural Support for Programming Languages and Operating Systems (ASPLOS-V), pages 124-136, October 1992.

Digital Library

[28]

Wood, D. A. An In-Cache Address Translation Mechanism. In Proceedings of the 13th Annual Symposium on Computer Architecture, pages 358-365. IEEE Computer Society Press, June 1986.

Digital Library

Cited By

Roy PSong SKrishnamoorthy SLiu XKnoop JSchordan MJohnson TO'Boyle M(2018)Lightweight detection of cache conflictsProceedings of the 2018 International Symposium on Code Generation and Optimization10.1145/3168819(200-213)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3168819
Shatnawi AAlsaedeen M(2018)Reducing the second-level cache conflict misses using a set folding techniqueThe Journal of Supercomputing10.1007/s11227-017-2174-874:2(970-993)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s11227-017-2174-8
Liu FGe QYarom YMckeen FRozas CHeiser GLee R(2016)CATalyst: Defeating last-level cache side channel attacks in cloud computing2016 IEEE International Symposium on High Performance Computer Architecture (HPCA)10.1109/HPCA.2016.7446082(406-418)Online publication date: Mar-2016
https://doi.org/10.1109/HPCA.2016.7446082
Show More Cited By

Recommendations

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGPLAN Notices

ACM SIGPLAN Notices Volume 29, Issue 11

Nov. 1994

323 pages

ISSN:0362-1340

EISSN:1558-1160

DOI:10.1145/195470

Editor:
Richard L. Wexelblat
Washington D.C.

Issue’s Table of Contents

ASPLOS VI: Proceedings of the sixth international conference on Architectural support for programming languages and operating systems
November 1994
341 pages
ISBN:0897916603
DOI:10.1145/195473
Chairmen:
Forest Baskett
Silicon Graphics
,
Douglas Clark
Princeton Univ.

Copyright © 1994 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]

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 November 1994

Published in SIGPLAN Volume 29, Issue 11

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

131
Total Citations
View Citations
1,132
Total Downloads

Downloads (Last 12 months)215
Downloads (Last 6 weeks)41

Reflects downloads up to 21 Nov 2024

Other Metrics

View Author Metrics

Citations

Cited By

Roy PSong SKrishnamoorthy SLiu XKnoop JSchordan MJohnson TO'Boyle M(2018)Lightweight detection of cache conflictsProceedings of the 2018 International Symposium on Code Generation and Optimization10.1145/3168819(200-213)Online publication date: 24-Feb-2018
https://dl.acm.org/doi/10.1145/3168819
Shatnawi AAlsaedeen M(2018)Reducing the second-level cache conflict misses using a set folding techniqueThe Journal of Supercomputing10.1007/s11227-017-2174-874:2(970-993)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s11227-017-2174-8
Liu FGe QYarom YMckeen FRozas CHeiser GLee R(2016)CATalyst: Defeating last-level cache side channel attacks in cloud computing2016 IEEE International Symposium on High Performance Computer Architecture (HPCA)10.1109/HPCA.2016.7446082(406-418)Online publication date: Mar-2016
https://doi.org/10.1109/HPCA.2016.7446082
Xiaoning Ding Nikolopoulos DSong Jiang Xiaodong Zhang (2006)MESA: reducing cache conflicts by integrating static and run-time methods2006 IEEE International Symposium on Performance Analysis of Systems and Software10.1109/ISPASS.2006.1620803(189-198)Online publication date: 2006
https://doi.org/10.1109/ISPASS.2006.1620803
Wu ZKaushik APatel H(2024)High Performance and Predictable Shared Last-level Cache for Safety-Critical SystemsACM Transactions on Embedded Computing Systems10.1145/368730823:6(1-30)Online publication date: 11-Sep-2024
https://dl.acm.org/doi/10.1145/3687308
Wu ZKaushik APatel H(2023)ZeroCost-LLC: Shared LLCs at No Cost to WCL2023 IEEE 29th Real-Time and Embedded Technology and Applications Symposium (RTAS)10.1109/RTAS58335.2023.00027(249-261)Online publication date: May-2023
https://doi.org/10.1109/RTAS58335.2023.00027
Wan JBi YZhou ZLi Z(2022)MeshUp: Stateless Cache Side-channel Attack on CPU Mesh2022 IEEE Symposium on Security and Privacy (SP)10.1109/SP46214.2022.9833794(1506-1524)Online publication date: May-2022
https://doi.org/10.1109/SP46214.2022.9833794
Ge QYarom YChothia THeiser G(2019)Time ProtectionProceedings of the Fourteenth EuroSys Conference 201910.1145/3302424.3303976(1-17)Online publication date: 25-Mar-2019
https://dl.acm.org/doi/10.1145/3302424.3303976
Hua YLiu XHua YLiu X(2019)Data Similarity-Aware Computation Infrastructure for the CloudSearchable Storage in Cloud Computing10.1007/978-981-13-2721-6_7(153-178)Online publication date: 9-Feb-2019
https://doi.org/10.1007/978-981-13-2721-6_7
Shatnawi AAlsaedeen M(2018)Reducing the second-level cache conflict misses using a set folding techniqueThe Journal of Supercomputing10.1007/s11227-017-2174-874:2(970-993)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1007/s11227-017-2174-8
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

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

Media

Figures

Other

Tables

View Issue’s Table of Contents