Article

Predictive sequential associative cache

Authors:

J. EmerAuthors Info & Claims

HPCA '96: Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture

Page 244

Published: 03 February 1996 Publication History

Abstract

In this paper we propose a cache design that provides the same miss rate as a two-way set associative cache, but with an access time closer to a direct-mapped cache. As with other designs, a traditional direct-mapped cache is conceptually partitioned into multiple banks, and the blocks in each set are probed, or examined, sequentially. Other designs either probe the set in a fixed order or add extra delay in the access path for all accesses. We use prediction sources to guide the cache examination, reducing the amount of searching and thus the average access latency. A variety of accurate prediction sources are considered, with some being available in early pipeline stages. We feel that our design offers the same or better performance and is easier to implement than previous designs.

References

[1]

Anant Agarwal, John Hennesy, and Mark Horowitz. Cache performance of operating systems and multiprogramming. ACM Transactions on Computer Systems, 6:393-431, November 1988.

Digital Library

[2]

Anant Agarwal and Steven D. Pudar. Column-associative caches: A technique for reducing the miss rate of direct mapped caches. In 20th Annual International Symposium on Computer Architecture, SIGARCH Newsletter, pages 179-190. IEEE, 1993.

Digital Library

[3]

Todd M. Austin, Dionisios N. Pnevmatikatos, and Gurindar S. Sohi. Skewed associativity enhances performance predictability. In 22nd Annual International Symposium on Computer Architecture, SIGARCH Newsletter, pages 369-380. IEEE, 1995.

Digital Library

[4]

M. Berry. The Perfect Club Benchmarks: Effective performance evaluation of supercomputers. The International Journal of Supercomputer Applications, 3(3):5-40, Fall 1989.

Digital Library

[5]

Francois Bodin and André Seznec. Skewed associativity enhances performance predictability. In 22nd Annual International Symposium on Computer Architecture, SIGARCH Newsletter, pages 265- 275. IEEE, 1995.

Digital Library

[6]

J. H. Chang, H. Chao, and K. So. Cache design of a submicron CMOS System/370. In 14th Annual International Symposium on Computer Architecture, SIGARCH Newsletter, pages 208-213. IEEE, June 1987.

Digital Library

[7]

Mark Hill. A case for direct-mapped caches. IEEE Computer, 21(12):25-40, December 1988.

Digital Library

[8]

Norm Jouppi. Cache write policies and performance. In 20th Annual International Symposium on Computer Architecture, SIGARCH Newsletter, pages 191-201. IEEE, May 1993.

Digital Library

[9]

David R. Kaeli and Philip G. Emma. Branch history table prediction of moving target branches due to subroutine returns. In 18th Annual International Symposium on Computer Architecture, SIGARCH Newsletter, pages 34-42. ACM, May 1991.

Digital Library

[10]

R. R. Kessler, Richard Jooss, Alvin Lebeck, and Mark D. Hill. Inexpensive implementations of set-associativity. In 16th Annual International Symposium on Computer Architecture, SIGARCH Newsletter. IEEE, May 1989.

Digital Library

[11]

Scott McFarling. Program optimization for instruction caches. In Proceedings of the 3rd Symposium on Architectural Support for Programming Languagess and Operating Systems, pages 183-191. ACM, 1988.

Digital Library

[12]

Wen mei W. Hwu and Pohua P. Chang. Achieving high instruction cache performance with an optimizing compiler. In 16th Annual International Symposium on Computer Architecture, SIGARCH Newsletter, pages 242-251. ACM, 1989.

Digital Library

[13]

André Seznec. A case for two-way skewed-associative caches. In 20th Annual International Symposium on Computer Architecture, SIGARCH Newsletter, pages 169-168. IEEE, 1993.

Digital Library

[14]

Kimming So and Rudolph N. Rechtschaffen. Cache operations by MRU change. IEEE Transactions on Computers, 37(6):700-709, June 1988.

Digital Library

[15]

Amitabh Srivastava and Alan Eustace. ATOM A system for building customized program analysis tools. In Proceedings of the SIGPLAN'94 Conference on Programming Language Design and Implementation. ACM, 1994.

Digital Library

[16]

Steven J. E. Wilton and Norman P. Jouppi. An enhanced access and cycle time model for on-chip caches. Report 93/5, DEC Western Research Lab, 1993.

Cited By

Alves RRos ABlack-Schaffer DKaxiras SManne SHunter HAltman E(2019)Filter caching for freeProceedings of the 46th International Symposium on Computer Architecture10.1145/3307650.3322269(436-448)Online publication date: 22-Jun-2019
https://dl.acm.org/doi/10.1145/3307650.3322269
Teran EChishti ZWang ZWilkerson CJiménez DKaeli DPericàs M(2018)Flexible associativity for DRAM cachesProceedings of the 15th ACM International Conference on Computing Frontiers10.1145/3203217.3203283(88-96)Online publication date: 8-May-2018
https://dl.acm.org/doi/10.1145/3203217.3203283
Naderan-Tahan MSarbazi-Azad H(2018)Domino CacheACM Transactions on Design Automation of Electronic Systems10.1145/317484823:3(1-23)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1145/3174848
Show More Cited By

Index Terms

Predictive sequential associative cache
1. Hardware
  1. Integrated circuits
    1. Semiconductor memory
      1. Dynamic memory

Index terms have been assigned to the content through auto-classification.

Recommendations

Two Fast and High-Associativity Cache Schemes

A traditional implementation of the set-associative cache has the disadvantage of longer access cycle times than that of a direct-mapped cache. Several methods have been proposed for implementing associativity in non-traditional ways. However, most of ...
Cache Operations by MRU Change

The performance of set associative caches is analyzed. The method used is to group the cache lines into regions according to their positions in the replacement stacks of a cache, and then to observe how the memory access of a CPU is distributed over ...
Selective Victim Caching: A Method to Improve the Performance of Direct-Mapped Caches

Although direct-mapped caches suffer from higher miss ratios as compared to set-associative caches, they are attractive for today's high-speed pipelined processors that require very low access times. Victim caching was proposed by Jouppi [1] as an ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image Guide Proceedings

HPCA '96: Proceedings of the 2nd IEEE Symposium on High-Performance Computer Architecture

February 1996

ISBN:0818672374

Copyright © Copyright (c) 1996 Institute of Electrical and Electronics Engineers, Inc. All rights reserved.

Publisher

IEEE Computer Society

United States

Publication History

Published: 03 February 1996

Author Tags

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

69
Total Citations
View Citations
0
Total Downloads

Downloads (Last 12 months)0
Downloads (Last 6 weeks)0

Reflects downloads up to 02 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Alves RRos ABlack-Schaffer DKaxiras SManne SHunter HAltman E(2019)Filter caching for freeProceedings of the 46th International Symposium on Computer Architecture10.1145/3307650.3322269(436-448)Online publication date: 22-Jun-2019
https://dl.acm.org/doi/10.1145/3307650.3322269
Teran EChishti ZWang ZWilkerson CJiménez DKaeli DPericàs M(2018)Flexible associativity for DRAM cachesProceedings of the 15th ACM International Conference on Computing Frontiers10.1145/3203217.3203283(88-96)Online publication date: 8-May-2018
https://dl.acm.org/doi/10.1145/3203217.3203283
Naderan-Tahan MSarbazi-Azad H(2018)Domino CacheACM Transactions on Design Automation of Electronic Systems10.1145/317484823:3(1-23)Online publication date: 1-Feb-2018
https://dl.acm.org/doi/10.1145/3174848
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
Sembrant ACarlson THagersten EBlack-Shaffer DPerais ASeznec AMichaud PPrvulovic M(2015)Long term parking (LTP)Proceedings of the 48th International Symposium on Microarchitecture10.1145/2830772.2830815(334-346)Online publication date: 5-Dec-2015
https://dl.acm.org/doi/10.1145/2830772.2830815
Seongil OSanghyuk Kwon Young Hoon Son Yujin Park Jung Ho Ahn (2015)CIDR: A Cache Inspired Area-Efficient DRAM Resilience Architecture against Permanent FaultsIEEE Computer Architecture Letters10.1109/LCA.2014.232489414:1(17-20)Online publication date: 1-Jan-2015
https://dl.acm.org/doi/10.1109/LCA.2014.2324894
Sembrant AHagersten EBlack-Schaffer DYew PZhai AKeckler S(2014)The Direct-to-Data (D2D) cacheProceeding of the 41st annual international symposium on Computer architecuture10.5555/2665671.2665694(133-144)Online publication date: 14-Jun-2014
https://dl.acm.org/doi/10.5555/2665671.2665694
Sembrant AHagersten EBlack-Schaffer D(2014)The Direct-to-Data (D2D) cacheACM SIGARCH Computer Architecture News10.1145/2678373.266569442:3(133-144)Online publication date: 14-Jun-2014
https://dl.acm.org/doi/10.1145/2678373.2665694
Zheng ZWang ZLipasti MXie YKarnik TKhellah MMehra R(2014)Tag check elisionProceedings of the 2014 international symposium on Low power electronics and design10.1145/2627369.2627606(351-356)Online publication date: 11-Aug-2014
https://dl.acm.org/doi/10.1145/2627369.2627606
Peir JLai SLu SStark JLai K(2014)Bloom filtering cache misses for accurate data speculation and prefetchingACM International Conference on Supercomputing 25th Anniversary Volume10.1145/2591635.2667183(347-356)Online publication date: 10-Jun-2014
https://dl.acm.org/doi/10.1145/2591635.2667183
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Table of Contents