More Web Proxy on the site http://driver.im/

Article

Free access

Hardware identification of cache conflict misses

Authors:

Jamison D. Collins,

Dean M. TullsenAuthors Info & Claims

MICRO 32: Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture

Pages 126 - 135

Published: 16 November 1999 Publication History

PDF eReader Publisher Site

Abstract

This paper describes the Miss Classification Table, a simple mechanism that enables the processor or memory controller to identify each cache miss as either a conflict miss or a capacity (non-conflict) miss. The miss classification table works by storing part of the tag of the most recently evicted line of a cache set. If the next miss to that cache set has a matching tag, it is identified as a conflict miss. This technique correctly identifies 87% of misses in the worst case.

Several applications of this information are demonstrated, including improvements to victim caching, next-line prefetching, cache exclusion, and a pseudo-associative cache. This paper also presents the Adaptive Miss Buffer (AMB), which combines several of these techniques, targeting each miss with the most appropriate optimization, all within a single small miss buffer. The AMB's combination of techniques achieves 16% better performance than any single technique alone.

References

[1]

A. Agarwal and S. D. Pudar. Column-associative caches: a technique for reducing the miss rate of direct-mapped caches. In 20th Annual International Symposium on Computer Architecture, pages 179-190, San Diego, CA, May 1993. ACM.

Digital Library

[2]

B. N. Bershad, D. Lee, T. H. Romer, and J. B. Chen. Avoiding conflict misses dynamically in large direct-mapped caches. In Six International Conference on Architectural Support for Programming Languages and Operating Systems, pages 158-170, Oct. 1994.

Digital Library

[3]

T-F. Chen and J.-L. Baer. Effective hardware-based data prefetching for high-performance processors. IEEE Transactions on Computers, 44(5):609--623, May 1995.

Digital Library

[4]

A. L. Cox and R. J. Fowler. Adaptive cache coherency for detecting migratory shared data. In 20th Annual International Symposium on Computer Architecture, pages 98-108, San Diego, CA, May 1993. ACM.

Digital Library

[5]

A. Gonzalez, C. Aliagas, and M. Valero. A data cache with multiple caching strategies tuned to different types of locality. In International Conference on Supercomputing, pages 338-347, June 1995.

Digital Library

[6]

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

Digital Library

[7]

H. Hirata, K. Kimura, S. Nagamine, Y. Mochizuki, A. Nishimura, Y. Nakase, and T. Nishizawa. An elementary processor architecture with simultaneous instruction issuing from multiple threads. In 19th Annual International Symposium on Computer Architecture, pages 136-145, May 1992.

Digital Library

[8]

T. L. Johnson and W. W. Hwu. Run-time adaptive cache hierarchy management via reference analysis, in 24th Annual International Symposium on Computer Architecture, pages 364-373, May 1997.

Digital Library

[9]

D. Joseph and D. Grunwald. Prefetching using markov predictors. IEEE Transactions on Computers, 48(2):121-133, Feb. 1999.

Digital Library

[10]

N. P. Jouppi. Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers. In 17th Annual International Symposium on Computer Architecture, pages 364-373, May 1995.

Digital Library

[11]

V. Milutinovic, M. Tomasevic, B. Markovi, and M. Tremblay. A new cache architecture concept: the split temporal/spatial cache. In Proceedings of 8th Mediterranean Electrotechnical Conference, pages 1108-1111, May 1996.

[12]

B. A. Nayfeh, L. Hammond, and K. Olukotun. Evaluation of design altematives for a multiprocessor microprocessor. In 23rd Annual International Symposium on Computer Architecture, pages 67-77, May 1996.

Digital Library

[13]

T H. Romer, D. Lee, B. N. Bershad, and J. B. Chert. Dynamic page mapping policies for cache conflict resolution on standard hardware. In First Annual Symposium on Operating Systems Design and Implementation, pages 255-266, Nov. 1994.

[14]

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

Digital Library

[15]

G.S. Sohi, S. E. Breach, and T N. Vijaykumar. Multiscalar processors. In 22rid Annual International Symposium on Computer Architecture, pages 414--425, June 1995.

Digital Library

[16]

P. Stenstrom, M. Brorsson, and L. Sandberg. An adaptive cache coherence protocol optimized for migratory sharing. In 20th Annual International Symposium on Computer Architecture, pages 109-118, San Diego, CA, May 1993. ACM.

Digital Library

[17]

H.S. Stone. High-Performance Computer Architecture. Addison Wesley, 1987.

Digital Library

[18]

D. M. Tullsen. Simulation and modeling of a simultaneous multithreading processor. In 22nd Annual Computer Measurement Group Conference, Dec. 1996.

Digital Library

[19]

D. M. Tullsen, S. J. Eggers, J. S. Emer, H. M. Levy, J. L. Lo, and R. L. Stamm. Exploiting choice: Instruction fetch and issue on an implementable simultaneous multithreading processor. In 23rd Annual International Symposium on Computer Architecture, May 1996.

Digital Library

[20]

G. Tyson, M. Farrens, J. Matthews, and A. R. Pleszkun. A modified approach to data cache management. In 28th Annual International Symposium on Microarchitecture, pages 93-103, Dec. 1995.

Digital Library

Cited By

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
Xu CRajamani KFerreira AFelter WRubio JLi YOliveira RFelber PHu Y(2018)dCatProceedings of the Thirteenth EuroSys Conference10.1145/3190508.3190555(1-13)Online publication date: 23-Apr-2018
https://dl.acm.org/doi/10.1145/3190508.3190555
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
Show More Cited By

Index Terms

Hardware identification of cache conflict misses
1. Hardware
  1. Hardware validation
  2. Integrated circuits
    1. Semiconductor memory

Recommendations

Runtime identification of cache conflict misses: The adaptive miss buffer

This paper describes the miss classification table, a simple mechanism that enables the processor or memory controller to identify each cache miss as either a conflict miss or a capacity (non-conflict) miss. The miss classification table works by ...
Reducing cache misses through programmable decoders

Level-one caches normally reside on a processor's critical path, which determines clock frequency. Therefore, fast access to level-one cache is important. Direct-mapped caches exhibit faster access time, but poor hit rates, compared with same sized set-...
Effective padding of multidimensional arrays to avoid cache conflict misses
PLDI '16: Proceedings of the 37th ACM SIGPLAN Conference on Programming Language Design and Implementation

Caches are used to significantly improve performance. Even with high degrees of set associativity, the number of accessed data elements mapping to the same set in a cache can easily exceed the degree of associativity. This can cause conflict misses and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM Conferences

MICRO 32: Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture

November 1999

299 pages

ISBN:076950437X

Chairmen:
Ronny Ronen
Intel Israel
,
Matthew Farrens
Univ. of California, Davis
,
Ilan Spillinger
Intel Israel

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

Sponsors

IEEE TC - MICRO: IEEE TC - MICRO
SIGMICRO: ACM Special Interest Group on Microarchitectural Research and Processing

Publisher

IEEE Computer Society

United States

Publication History

Published: 16 November 1999

Check for updates

Qualifiers

Article

Conference

MICRO99

Sponsor:

IEEE TC - MICRO
SIGMICRO

MICRO99: 32nd Annual ACM/IEEE International Symposium on Microarchitecture

November 16 - 18, 1999

Haifa, Israel

Acceptance Rates

MICRO 32 Paper Acceptance Rate 27 of 131 submissions, 21%;

Overall Acceptance Rate 484 of 2,242 submissions, 22%

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

13
Total Citations
View Citations
424
Total Downloads

Downloads (Last 12 months)54
Downloads (Last 6 weeks)4

Reflects downloads up to 20 Dec 2024

Other Metrics

View Author Metrics

Citations

Cited By

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
Xu CRajamani KFerreira AFelter WRubio JLi YOliveira RFelber PHu Y(2018)dCatProceedings of the Thirteenth EuroSys Conference10.1145/3190508.3190555(1-13)Online publication date: 23-Apr-2018
https://dl.acm.org/doi/10.1145/3190508.3190555
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
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
Seshadri VBhowmick AMutlu OGibbons PKozuch MMowry TYew PZhai AKeckler S(2014)The dirty-block indexProceeding of the 41st annual international symposium on Computer architecuture10.5555/2665671.2665697(157-168)Online publication date: 14-Jun-2014
https://dl.acm.org/doi/10.5555/2665671.2665697
Seshadri VBhowmick AMutlu OGibbons PKozuch MMowry T(2014)The dirty-block indexACM SIGARCH Computer Architecture News10.1145/2678373.266569742:3(157-168)Online publication date: 14-Jun-2014
https://dl.acm.org/doi/10.1145/2678373.2665697
Seshadri VMutlu OKozuch MMowry TYew PCho SDeRose LLilja D(2012)The evicted-address filterProceedings of the 21st international conference on Parallel architectures and compilation techniques10.1145/2370816.2370868(355-366)Online publication date: 19-Sep-2012
https://dl.acm.org/doi/10.1145/2370816.2370868
Gaur JChaudhuri MSubramoney S(2011)Bypass and insertion algorithms for exclusive last-level cachesACM SIGARCH Computer Architecture News10.1145/2024723.200007539:3(81-92)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/2024723.2000075
Gaur JChaudhuri MSubramoney SIyer RYang QGonzález A(2011)Bypass and insertion algorithms for exclusive last-level cachesProceedings of the 38th annual international symposium on Computer architecture10.1145/2000064.2000075(81-92)Online publication date: 4-Jun-2011
https://dl.acm.org/doi/10.1145/2000064.2000075
Jeong JStenström PDubois MAlderighi MSalapura VMcKee S(2006)Simple penalty-sensitive replacement policies for cachesProceedings of the 3rd conference on Computing frontiers10.1145/1128022.1128068(341-352)Online publication date: 3-May-2006
https://dl.acm.org/doi/10.1145/1128022.1128068
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 Table of Contents