research-article

Optimal bypass monitor for high performance last-level caches

Authors:

Xu ChengAuthors Info & Claims

PACT '12: Proceedings of the 21st international conference on Parallel architectures and compilation techniques

Pages 315 - 324

https://doi.org/10.1145/2370816.2370862

Published: 19 September 2012 Publication History

Abstract

In the last-level cache, large amounts of blocks have reuse distances greater than the available cache capacity. Cache performance and efficiency can be improved if some subset of these distant reuse blocks can reside in the cache longer. The bypass technique is an effective and attractive solution that prevents the insertion of harmful blocks.

Our analysis shows that bypass can contribute significant performance improvement, and the optimal bypass can achieve similar performance compared to OPT+B, which is the theoretical optimal replacement policy. Thus, we propose a bypass technique called Optimal Bypass Monitor (OBM), which makes bypass decisions by learning and predicting the behavior of the optimal bypass. OBM keeps a short global track of the incoming-victim block pairs. By detecting the first reuse block in each pair, the behavior of the optimal bypass on the track can be asserted to guide the bypass choice.

Any existing replacement policy can be extended with OBM while requiring negligible design modification. Our experimental results show that using less than 1.5KB extra memory, OBM with the NRU replacement policy outperforms LRU by 9.7% and 8.9% for single-thread and multi-programmed workloads respectively. Compared with other state-of-the-art proposals such as DRRIP and SDBP, it achieves superior performance with less storage overhead.

References

[1]

S. Bansal and D. S. Modha. Car: Clock with adaptive replacement. In FAST-3, 2004.

Digital Library

[2]

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

Digital Library

[3]

S. Borkar and A. A. Chien. The future of microprocessors. Commun. ACM, 54:67--77, 2011.

Digital Library

[4]

M. Chaudhuri. Pseudo-lifo: the foundation of a new family of replacement policies for last-level caches. In MICRO-42, 2009.

Digital Library

[5]

C.-H. Chi and H. Dietz. Improving cache performance by selective cache bypass. In HICSS-22, 1989.

[6]

H. Gao and C. Wilkerson. A dueling segmented lru replacement algorithm with adaptive bypassing. In JWAC-1, 2010.

[7]

J. Gaur, M. Chaudhuri, and S. Subramoney. Bypass and insertion algorithms for exclusive last-level caches. In ISCA-38, 2011.

Digital Library

[8]

A. González, C. Aliagas, and M. Valero. A data cache with multiple caching strategies tuned to different types of locality. In ICS-9, 1995.

[9]

J. L. Henning. Spec cpu2006 benchmark descriptions. SIGARCH Comput. Archit. News, 34:1--17, 2006.

Digital Library

[10]

Z. Hu, S. Kaxiras, and M. Martonosi. Timekeeping in the memory system: predicting and optimizing memory behavior. In ISCA-29, 2002.

Digital Library

[11]

Intel. Intel core i7 processor. http://www.intel.com/products/processor/corei7/.

[12]

A. Jaleel, K. B. Theobald, S. C. Steely, Jr., and J. Emer. High performance cache replacement using re-reference interval prediction (rrip). In ISCA-37, 2010.

Digital Library

[13]

J. Jalminger and P. Stenstrom. A novel approach to cache block reuse predictions. In ICPP '03, 2003.

[14]

L. John and A. Subramanian. Design and performance evaluation of a cache assist to implement selective caching. In ICCD '97, 1997.

[15]

T. Johnson, D. Connors, M. Merten, and W.-M. Hwu. Run-time cache bypassing. Computers, IEEE Transactions on, 48(12):1338--1354, 1999.

Digital Library

[16]

N. P. Jouppi. Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. In ISCA-17, 1990.

Digital Library

[17]

G. Keramidas, P. Petoumenos, and S. Kaxiras. Cache replacement based on reuse-distance prediction. In ICCD-25, 2007.

[18]

S. M. Khan, D. A. Jiménez, D. Burger, and B. Falsafi. Using dead blocks as a virtual victim cache. In PACT-19, 2010.

Digital Library

[19]

S. M. Khan, Y. Tian, and D. A. Jimenez. Sampling dead block prediction for last-level caches. In MICRO-43, 2010.

Digital Library

[20]

M. Kharbutli and Y. Solihin. Counter-based cache replacement and bypassing algorithms. Computers, IEEE Transactions on, 57(4):433--447, 2008.

Digital Library

[21]

A.-C. Lai, C. Fide, and B. Falsafi. Dead-block prediction & dead-block correlating prefetchers. In ISCA-28, 2001.

Digital Library

[22]

H. Liu, M. Ferdman, J. Huh, and D. Burger. Cache bursts: A new approach for eliminating dead blocks and increasing cache efficiency. In MICRO-41, 2008.

Digital Library

[23]

R. Manikantan, K. Rajan, and R. Govindarajan. Nucache: An efficient multicore cache organization based on next-use distance. In HPCA-17, 2011.

Digital Library

[24]

N. Megiddo and D. S. Modha. Arc: A self-tuning, low overhead replacement cache. In FAST-2, 2003.

Digital Library

[25]

N. Muralimanohar, R. Balasubramonian, and N. Jouppi. Cacti 6.0: A tool to understand large caches. HP Research Report, 2007.

[26]

H. Patil, R. Cohn, M. Charney, R. Kapoor, A. Sun, and A. Karunanidhi. Pinpointing representative portions of large intel itanium programs with dynamic instrumentation. In MICRO-37, 2004.

Digital Library

[27]

M. K. Qureshi, A. Jaleel, Y. N. Patt, S. C. Steely, and J. Emer. Adaptive insertion policies for high performance caching. In ISCA-34, 2007.

Digital Library

[28]

M. K. Qureshi, D. N. Lynch, O. Mutlu, and Y. N. Patt. A case for mlp-aware cache replacement. In ISCA-33, 2006.

Digital Library

[29]

K. Rajan and G. Ramaswamy. Emulating optimal replacement with a shepherd cache. In MICRO-40, 2007.

Digital Library

[30]

J. Rivers and E. Davidson. Reducing conflicts in direct-mapped caches with a temporality-based design. In ICPP '96, 1996.

[31]

J. A. Rivers, E. S. Tam, G. S. Tyson, E. S. Davidson, and M. Farrens. Utilizing reuse information in data cache management. In ICS-12, 1998.

Digital Library

[32]

R. Subramanian, Y. Smaragdakis, and G. H. Loh. Adaptive caches: Effective shaping of cache behavior to workloads. In MICRO-39, 2006.

Digital Library

[33]

G. Tyson, M. Farrens, J. Matthews, and A. R. Pleszkun. A modified approach to data cache management. In MICRO-28, 1995.

Digital Library

[34]

S. Walsh and J. Board. Pollution control caching. In ICCD '95, 1995.

Digital Library

[35]

C. Wu, A. Jaleel, W. Hasenplaugh, M. Martonosi, S. Steely Jr, and J. Emer. Ship: Signature-based hit predictor for high performance caching. In MICRO-44, 2011.

Digital Library

[36]

C. Wu, A. Jaleel, M. Martonosi, S. Steely Jr, and J. Emer. Pacman: Prefetch-aware cache management for high performance caching. In MICRO-44, 2011.

Digital Library

[37]

L. Xiang, T. Chen, Q. Shi, and W. Hu. Less reused filter: improving l2 cache performance via filtering less reused lines. In ICS-23, 2009.

Digital Library

[38]

Y. Xie and G. H. Loh. Pipp: Promotion/insertion pseudo-partitioning of multi-core shared caches. In ISCA-36, 2009.

Digital Library

Cited By

Bagchi ADharamjeet Rishabh OSuri MPanda P(2024)POEM: Performance Optimization and Endurance Management for Non-volatile CachesACM Transactions on Design Automation of Electronic Systems10.1145/365345229:5(1-36)Online publication date: 27-Mar-2024
https://dl.acm.org/doi/10.1145/3653452
Bagchi AJoshi DPanda P(2023)COBRRA: COntention-aware cache Bypass with Request-Response ArbitrationACM Transactions on Embedded Computing Systems10.1145/363274823:1(1-30)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3632748
Wang YChang CSivasubramaniam ASoundararajan N(2023)ACIC: Admission-Controlled Instruction Cache2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA56546.2023.10071033(165-178)Online publication date: Feb-2023
https://doi.org/10.1109/HPCA56546.2023.10071033
Show More Cited By

Index Terms

Optimal bypass monitor for high performance last-level caches
1. Hardware
  1. Integrated circuits
    1. Semiconductor memory
      1. Dynamic memory

Recommendations

Introducing hierarchy-awareness in replacement and bypass algorithms for last-level caches
PACT '12: Proceedings of the 21st international conference on Parallel architectures and compilation techniques

The replacement policies for the last-level caches (LLCs) are usually designed based on the access information available locally at the LLC. These policies are inherently sub-optimal due to lack of information about the activities in the inner-levels of ...
Bypass and insertion algorithms for exclusive last-level caches
ISCA '11: Proceedings of the 38th annual international symposium on Computer architecture

Inclusive last-level caches (LLCs) waste precious silicon estate due to cross-level replication of cache blocks. As the industry moves toward cache hierarchies with larger inner levels, this wasted cache space leads to bigger performance losses compared ...
High performance cache replacement using re-reference interval prediction (RRIP)
ISCA '10: Proceedings of the 37th annual international symposium on Computer architecture

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 ...

Comments

Information & Contributors

Information

Published In

cover image ACM Conferences

PACT '12: Proceedings of the 21st international conference on Parallel architectures and compilation techniques

September 2012

512 pages

ISBN:9781450311823

DOI:10.1145/2370816

General Chairs:
Pen-Chung Yew
University of Minnesota
,
Sangyeun Cho
University of Pittsburgh
,
Program Chairs:
Luiz DeRose
Cray, Inc.
,
David J. Lilja
University of Minnesota

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

IFIP WG 10.3: IFIP WG 10.3
SIGARCH: ACM Special Interest Group on Computer Architecture
IEEE CS TCPP: IEEE Computer Society Technical Committee on Parallel Processing
IEEE CS TCAA: IEEE CS technical committee on architectural acoustics

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 19 September 2012

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Author Tags

Qualifiers

Research-article

Conference

PACT '12

Sponsor:

IFIP WG 10.3
SIGARCH
IEEE CS TCPP
IEEE CS TCAA

PACT '12: International Conference on Parallel Architectures and Compilation Techniques

September 19 - 23, 2012

Minnesota, Minneapolis, USA

Acceptance Rates

Overall Acceptance Rate 121 of 471 submissions, 26%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

31
Total Citations
View Citations
477
Total Downloads

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

Reflects downloads up to 08 Mar 2025

Other Metrics

View Author Metrics

Citations

Cited By

Bagchi ADharamjeet Rishabh OSuri MPanda P(2024)POEM: Performance Optimization and Endurance Management for Non-volatile CachesACM Transactions on Design Automation of Electronic Systems10.1145/365345229:5(1-36)Online publication date: 27-Mar-2024
https://dl.acm.org/doi/10.1145/3653452
Bagchi AJoshi DPanda P(2023)COBRRA: COntention-aware cache Bypass with Request-Response ArbitrationACM Transactions on Embedded Computing Systems10.1145/363274823:1(1-30)Online publication date: 17-Nov-2023
https://dl.acm.org/doi/10.1145/3632748
Wang YChang CSivasubramaniam ASoundararajan N(2023)ACIC: Admission-Controlled Instruction Cache2023 IEEE International Symposium on High-Performance Computer Architecture (HPCA)10.1109/HPCA56546.2023.10071033(165-178)Online publication date: Feb-2023
https://doi.org/10.1109/HPCA56546.2023.10071033
Kim BKim YNair PHong S(2022)Exploiting Data Compression for Adaptive Block Placement in Hybrid CachesElectronics10.3390/electronics1102024011:2(240)Online publication date: 12-Jan-2022
https://doi.org/10.3390/electronics11020240
Oliveira GGomez-Luna JOrosa LGhose SVijaykumar NFernandez ISadrosadati MMutlu O(2021)DAMOV: A New Methodology and Benchmark Suite for Evaluating Data Movement BottlenecksIEEE Access10.1109/ACCESS.2021.31109939(134457-134502)Online publication date: 2021
https://doi.org/10.1109/ACCESS.2021.3110993
Li LChapman BTaufer MBalaji PPeña A(2019)Compiler assisted hybrid implicit and explicit GPU memory management under unified address spaceProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3295500.3356141(1-16)Online publication date: 17-Nov-2019
https://dl.acm.org/doi/10.1145/3295500.3356141
Wang JRamrakhyani PElsasser WJohn L(2019)Reducing Data Movement and Energy in Multilevel Cache Hierarchies without Losing Performance: Can you have it all?Proceedings of the International Conference on Parallel Architectures and Compilation Techniques10.1109/PACT.2019.00037(382-393)Online publication date: 23-Sep-2019
https://dl.acm.org/doi/10.1109/PACT.2019.00037
Díaz JMonreal TIbáñez PLlabería JViñals V(2019)ReD: A reuse detector for content selection in exclusive shared last-level cachesJournal of Parallel and Distributed Computing10.1016/j.jpdc.2018.11.005125(106-120)Online publication date: Mar-2019
https://doi.org/10.1016/j.jpdc.2018.11.005
Li LFinkel HKong MChapman B(2018)Manage OpenMP GPU Data Environment Under Unified Address SpaceEvolving OpenMP for Evolving Architectures10.1007/978-3-319-98521-3_5(69-81)Online publication date: 29-Aug-2018
https://doi.org/10.1007/978-3-319-98521-3_5
Feng LSinha SZhang WLiang YParameswaran S(2017)A hybrid approach to cache management in heterogeneous CPU-FPGA platformsProceedings of the 36th International Conference on Computer-Aided Design10.5555/3199700.3199829(937-944)Online publication date: 13-Nov-2017
https://dl.acm.org/doi/10.5555/3199700.3199829
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.

Figures

Tables

Media

View Table of Conten