article

Free access

Cache replacement with dynamic exclusion

Author:

Scott McFarlingAuthors Info & Claims

ACM SIGARCH Computer Architecture News, Volume 20, Issue 2

Pages 191 - 200

https://doi.org/10.1145/146628.139727

Published: 01 April 1992 Publication History

Abstract

Most recent cache designs use direct-mapped caches to provide the fast access time required by modern high speed CPU's. Unfortunately, direct-mapped caches have higher miss rates than set-associative caches, largely because direct-mapped caches are more sensitive to conflicts between items needed frequently in the same phase of program execution.

This paper presents a new technique for reducing direct-mapped cache misses caused by conflicts for a particular cache line. A small finite state machine recognizes the common instruction reference patterns where storing an instruction in the cache actually harms performance. Such instructions are dynamically excluded, that is they are passed directly through the cache without being stored. This reduces misses to the instructions that would have been replaced.

The effectiveness of dynamic exclusion is dependent on the severity of cache conflicts and thus on the particular program and cache size of interest. However, across the SPEC benchmarks, simulation results show an average reduction in miss rate of 33% for a 32KB instruction cache with 16B lines. In addition, applying dynamic exclusion to one level of a cache hierarchy can improve the performance of the next level since instructions do not need to be stored on both levels. Finally, dynamic exclusion also improves combined instruction and data cache miss rates.

References

[1]

L.A. Belady. A study of replacement algorithms for a virtual-storage computer. IBM Systems J., 5(2):78-101, 1966.

Digital Library

[2]

W.W. Hwu and P. H. Chang. Achieving high instruction cache performance with an optimizing compiler. In Proc. 16th Sym. on Computer Architecture, Israel, May 1989.

Digital Library

[3]

M.D. Hill. Aspects of Cache Memory and Instruction Buffer Performance. PhD thesis, University of California, Berkeley, November 1987.

Digital Library

[4]

N.P. Jouppi. Improving direct-mapped cache performance by the addition of a small fullyassociative cache and prefetch buffers. In Proc. 17th Sym. on Computer Architecture, Seattle, May 1990.

Digital Library

[5]

E.A. Killian. In RISCompiler and C Programmer's Guide. MIPS Computer Systems, 930 Arques Ave., Sunnyvale, CA 94086, 1986.

[6]

S. McFarling. Program optimization for instruction caches. In Proceedings of ASPLOS tli, Boston, MA, April 1989.

Digital Library

[7]

S. McFarling. Cache replacement with dynamic exclusion. WRL Technical Note TN-22, Digital Western Research Laboratory, November 1991.

[8]

S. McFarling. Program Analysis and Optimization for Machines with Instruction Cache. PhD thesis, Stanford University, September 1991. Available as CSL-TR-91-493.

Digital Library

[9]

K. Pettis and R. C. Hansen. Profile guided code positioning. In Proceedings of the ACM SIGPLAN'90 Conference on Programming Language Design and Implementation, pages 16-27, 1990.

Digital Library

[10]

S. Przybylski, M. Horowitz, and J.L. Hennessy. Performance tradeoffs in cache design. In Proc. 15th Sym. on Computer Architecture, Honolulu, Hawaii, June 1988.

Digital Library

[11]

S. Przybylski, M. Horowitz, and J. Hennessy. Characteristics of performance-optimal multilevel cache heirarchy. In Proc. 16th Sym. on Computer Architecture, israel, May 1989.

Digital Library

[12]

S.A. Przybylski. Performance-Directed Memory Heirarchy Design. PhD thesis, Stanford University, September 1988.

Digital Library

[13]

J.E. Smith and J. R. Goodman. Instruction cache replacement policies and organizations. IEEE Transactions on Computers, C-34(3):234-241, March 1985.

Digital Library

[14]

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

Digital Library

[15]

M.D. Smith. Tracing with pixie. Technical Report CSL-TR-91-497, Computer Systems Laboratory, Stanford University, November 1991,

[16]

SPEC. The SPEC Benchmark Report. Waterside Associates, Fremont, CA, January 1990.

[17]

M.E. Wolf and M. S. Lain. A clam locality optimizing algorithm. In Proceedings of the ACM SIGPLAN '91 Conference on Programming Language Design and Implementation, pages 30--44, 1991.

Digital Library

Cited By

González AAliagas C(2014)Author retrospective for the dual data cacheACM International Conference on Supercomputing 25th Anniversary Volume10.1145/2591635.2591652(32-34)Online publication date: 10-Jun-2014
https://dl.acm.org/doi/10.1145/2591635.2591652
Mendlson APinter SShtokhamer R(2005)Compile time instruction cache optimizationsCompiler Construction10.1007/3-540-57877-3_27(404-418)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-57877-3_27
Karlsson MHagersten E(2004)Timestamp-Based Selective Cache AllocationHigh Performance Memory Systems10.1007/978-1-4419-8987-1_4(43-59)Online publication date: 2004
https://doi.org/10.1007/978-1-4419-8987-1_4
Show More Cited By

Recommendations

High performance cache replacement using re-reference interval prediction (RRIP)
ISCA '10

Practical cache replacement policies attempt to emulate optimal replacement by predicting the re-reference interval of a cache block. The commonly used LRU replacement policy always predicts a near-immediate re-reference interval on cache hits and ...
A Case for MLP-Aware Cache Replacement

Performance loss due to long-latency memory accesses can be reduced by servicing multiple memory accesses concurrently. The notion of generating and servicing long-latency cache misses in parallel is called Memory Level Parallelism (MLP). MLP is not ...
Cache replacement with dynamic exclusion
ISCA '92: Proceedings of the 19th annual international symposium on Computer architecture

Most recent cache designs use direct-mapped caches to provide the fast access time required by modern high speed CPU's. Unfortunately, direct-mapped caches have higher miss rates than set-associative caches, largely because direct-mapped caches are more ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGARCH Computer Architecture News

ACM SIGARCH Computer Architecture News Volume 20, Issue 2

Special Issue: Proceedings of the 19th annual international symposium on Computer architecture (ISCA '92)

May 1992

429 pages

ISSN:0163-5964

DOI:10.1145/146628

Editor:
Allan Gotlieb
New York Univ., New York, NY

Issue’s Table of Contents

ISCA '92: Proceedings of the 19th annual international symposium on Computer architecture
May 1992
439 pages
ISBN:0897915097
DOI:10.1145/139669
Chairman:
Allan Gottlieb
New York Unvi., New York, NY

Copyright © 1992 Author.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1992

Published in SIGARCH Volume 20, Issue 2

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

50
Total Citations
View Citations
909
Total Downloads

Downloads (Last 12 months)163
Downloads (Last 6 weeks)18

Reflects downloads up to 07 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

González AAliagas C(2014)Author retrospective for the dual data cacheACM International Conference on Supercomputing 25th Anniversary Volume10.1145/2591635.2591652(32-34)Online publication date: 10-Jun-2014
https://dl.acm.org/doi/10.1145/2591635.2591652
Mendlson APinter SShtokhamer R(2005)Compile time instruction cache optimizationsCompiler Construction10.1007/3-540-57877-3_27(404-418)Online publication date: 30-May-2005
https://doi.org/10.1007/3-540-57877-3_27
Karlsson MHagersten E(2004)Timestamp-Based Selective Cache AllocationHigh Performance Memory Systems10.1007/978-1-4419-8987-1_4(43-59)Online publication date: 2004
https://doi.org/10.1007/978-1-4419-8987-1_4
John LLi TSubramanian A(1999)Annex cache: a cache assist to implement selective cachingMicroprocessors and Microsystems10.1016/S0141-9331(99)00048-423:8-9(537-551)Online publication date: Dec-1999
https://doi.org/10.1016/S0141-9331(99)00048-4
Wong DDavis EYoung J(1998)A Software Approach to Avoiding Spatial Cache Collisions in Parallel Processor SystemsIEEE Transactions on Parallel and Distributed Systems10.1109/71.6894479:6(601-608)Online publication date: 1-Jun-1998
https://dl.acm.org/doi/10.1109/71.689447
Beal JUsbeck KLoyall JRowe MMetzler J(2018)Adaptive Opportunistic Airborne Sensor SharingACM Transactions on Autonomous and Adaptive Systems10.1145/317999413:1(1-29)Online publication date: 16-Apr-2018
https://dl.acm.org/doi/10.1145/3179994
Iannucci SAbdelwahed S(2018)Model-Based Response Planning Strategies for Autonomic Intrusion ProtectionACM Transactions on Autonomous and Adaptive Systems10.1145/316844613:1(1-23)Online publication date: 16-Apr-2018
https://dl.acm.org/doi/10.1145/3168446
Young VChou CJaleel AQureshi M(2018)ACCORDProceedings of the 45th Annual International Symposium on Computer Architecture10.1109/ISCA.2018.00036(328-339)Online publication date: 2-Jun-2018
https://dl.acm.org/doi/10.1109/ISCA.2018.00036
Sridharan ASeznec A(2017)Dynamic and discrete cache insertion policies for managing shared last level caches in large multicoresJournal of Parallel and Distributed Computing10.1016/j.jpdc.2017.02.004106:C(215-226)Online publication date: 1-Aug-2017
https://dl.acm.org/doi/10.1016/j.jpdc.2017.02.004
Das SAamodt TDally W(2015)Reuse Distance-Based Probabilistic Cache ReplacementACM Transactions on Architecture and Code Optimization10.1145/281837412:4(1-22)Online publication date: 19-Oct-2015
https://dl.acm.org/doi/10.1145/2818374
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

Figures

Tables

Media

View Issue’s Table of Contents