research-article

Evaluation of Hardware-Based Stride and Sequential Prefetching in Shared-Memory Multiprocessors

Authors:

Fredrik Dahlgren,

Per StenströmAuthors Info & Claims

IEEE Transactions on Parallel and Distributed Systems, Volume 7, Issue 4

Pages 385 - 398

https://doi.org/10.1109/71.494633

Published: 01 April 1996 Publication History

Abstract

We study the efficiency of previously proposed stride and sequential prefetching two promising hardware-based prefetching schemes to reduce read-miss penalties in shared-memory multiprocessors. Although stride accesses dominate in four out of six of the applications we study, we find that sequential prefetching does as well as and in same cases even better than stride prefetching for five applications. This is because 1) most strides are shorter than the block size (we assume 32 byte blocks), which means that sequential prefetching is as effective for these stride accesses, and 2) sequential prefetching also exploits the locality of read misses with nonstride accesses. However, since stride prefetching in general results in fewer useless prefetches, it offers the extra advantage of consuming less memory-system bandwidth.

References

[1]

J.-L. Baer and T.-F. Chen, "An Effective On-Chip Preloading Scheme To Reduce Data Access Penalty," Proc. Supercomputing '91, pp. 176-186, 1991,.]]

Digital Library

[2]

R. Bianchini and T.J. LeBlanc, "A Preliminary Evaluation of Cache-Miss-Initiated Prefetching Techniques in Scalable Multiprocessors," Tech. Report 515, Computer Science Dept., Univ. of Rochester, May 1994.]]

[3]

M. Brorsson F. Dahlgren H. Nilsson and P. Stenström, "The CacheMire Test Bench_A Flexible and Effective Approach for Simulation of Multiprocessors," Proc. 26th Ann. Simulation Symp., pp. 41-49, 1993.]]

[4]

L.M. Censier and P. Feautrier, "A New Solution to Coherence Problems in Multicache Systems," IEEE Trans. Computers, vol. 27, pp. 1,112-1,118, Dec. 1978.]]

[5]

T.-F. Chen and J.-L. Baer, "A Performance Study of Software and Hardware Data Prefetching Schemes," Proc. 21st Int'l Symp. Computer Architecture, pp. 223-232, 1994.]]

Digital Library

[6]

F. Dahlgren M. Dubois and P. Stenström, "Fixed and Adaptive Sequential Prefetching in Shared-Memory Multiprocessors," Proc. Int'l Conf. Parallel Processing, vol. I, pp. 56-63, 1993.]]

Digital Library

[7]

F. Dahlgren M. Dubois and P. Stenström, "Combined Performance Gains of Simple Cache Protocol Extensions," Proc. 21st Int'l Symp. Computer Architecture, pp.187-197, 1994,.]]

Digital Library

[8]

F. Dahlgren and P. Stenström, "Effectiveness of Hardware-Based Stride and Sequential Prefetching in Shared-Memory Multiprocessors," Proc. First Int'l Symp. High-Performance Computer Architecture, pp. 68-77, 1995.]]

Digital Library

[9]

J. Fu and J.H. Patel, "Data Prefetching in Multiprocessor Vector Cache Memories," Proc. 18th Int'l Symp. Computer Architecture, pp. 54-63, 1991.]]

Digital Library

[10]

J. Fu J.H. Patel and B.L. Janssens, "Stride Directed Prefetching in Scalar Processors," Proc. 25th Ann. Int'l Symp. Microarchitecture, pp. 102-110, 1992,.]]

Digital Library

[11]

K. Gharachorloo A. Gupta and J. Hennessy, "Performance Evaluation of Memory Consistency Models for Shared-Memory Multiprocessors," Proc. ASPLOS IV, pp. 245-257, 1991.]]

Digital Library

[12]

A. Gupta, et al., "Comparative Evaluation of Latency Reducing and Toleratin Techniques," Proc. 18th Int'l Symp. Computer Architecture, pp. 254-263, 1991.]]

Digital Library

[13]

E. Hagersten, "Towards Scalable Cache Only Memory Architectures," PhD thesis, SICS Dissertation Series 08, Swedish Inst. of Computer Science, Oct. 1992.]]

[14]

D. Kroft, "Lockup-Free Instruction Fetch/Prefetch Cache Organization," Proc. Eighth Int'l Symp. Computer Architecture, pp. 81-87, 1981.]]

Digital Library

[15]

R. Lee P-C. Yew and D. Lawrie, "Data Prefetching in Shared-Memory Multiprocessors," Proc. Int'l Conf. Parallel Processing, pp. 28-31, 1987.]]

[16]

T. Mowry and A. Gupta, "Tolerating Latency through Software-Controlled Prefetching in Scalable Shared- Memory Multiprocessors," J. Parallel and Distributed. Computing, vol. 12, pp. 87-106, June 1991.]]

Digital Library

[17]

T. Mowry, "Tolerating Latency Through Software Controlled Data Prefetching," PhD Thesis, Dept. of Computer Science, Stanford Univ., Palo, Alto, Calif., Mar. 1994.]]

Digital Library

[18]

J.P. Singh W.-D. Weber and A. Gupta, "SPLASH: Stanford Parallel Applications for Shared-Memory," Computer Architecture News, vol. 20, pp. 5-44, Mar. 1992.]]

Digital Library

[19]

I. Sklenar, "Prefetch Unit for Vector Operations on Scalar Computers," Computer Architecture News, vol. 20, pp. 31-37, Sept. 1992.]]

Digital Library

[20]

A.J. Smith, "Sequential Program Prefetching in Memory Hierarchies," Computer, vol. 11, no. 12, pp. 7-21, Dec. 1978.]]

Digital Library

[21]

P. Stenström, "A Survey of Cache Coherence Scheme for Multiprocessors," Computer, vol. 23, no. 6, pp. 12-24, Jun.e 1990.]]

Digital Library

[22]

P. Stenström F. Dahlgren and L. Lundberg, "A Lockup-Free Multiprocessor Cache Design," Proc. Int'l Conf. Parallel Processing, vol. I, pp. 246-250, 1991.]]

Cited By

Wang JPanda RJohn L(2018)SelSMaPACM Transactions on Architecture and Code Optimization10.1145/327465015:4(1-21)Online publication date: 10-Oct-2018
https://dl.acm.org/doi/10.1145/3274650
Nori AGaur JRai SSubramoney SWang H(2018)Criticality aware tiered cache hierarchyProceedings of the 45th Annual International Symposium on Computer Architecture10.1109/ISCA.2018.00019(96-109)Online publication date: 2-Jun-2018
https://dl.acm.org/doi/10.1109/ISCA.2018.00019
Shevgoor MKoladiya SBalasubramonian RWilkerson CPugsley SChishti ZPrvulovic M(2015)Efficiently prefetching complex address patternsProceedings of the 48th International Symposium on Microarchitecture10.1145/2830772.2830793(141-152)Online publication date: 5-Dec-2015
https://dl.acm.org/doi/10.1145/2830772.2830793
Show More Cited By

Index Terms

Evaluation of Hardware-Based Stride and Sequential Prefetching in Shared-Memory Multiprocessors
1. Computer systems organization
  1. Architectures
    1. Parallel architectures
      1. Multiple instruction, multiple data
2. Hardware
  1. Hardware validation
    1. Post-manufacture validation and debug
      1. Bug detection, localization and diagnosis

Recommendations

Sequential Hardware Prefetching in Shared-Memory Multiprocessors

To offset the effect of read miss penalties on processor utilization in shared-memory multiprocessors, several software- and hardware-based data prefetching schemes have been proposed. A major advantage of hardware techniques is that they need no ...
Effectiveness of hardware-based stride and sequential prefetching in shared-memory multiprocessors
HPCA '95: Proceedings of the 1st IEEE Symposium on High-Performance Computer Architecture

We study the relative efficiency of previously proposed stride and sequential prefetching-two promising hardware-based prefetching schemes to reduce read-miss penalties in shared-memory multiprocessors. Although stride accesses dominate in four out of ...
Effective cache prefetching on bus-based multiprocessors

Compiler-directed cache prefetching has the potential to hide much of the high memory latency seen by current and future high-performance processors. However, prefetching is not without costs, particularly on a shared-memory multiprocessor. Prefetching ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image IEEE Transactions on Parallel and Distributed Systems

IEEE Transactions on Parallel and Distributed Systems Volume 7, Issue 4

April 1996

128 pages

ISSN:1045-9219

Editor:
Duncan H. Lawrie
Univ. of Illinois at Urbana-Champaign, Urbana

Issue’s Table of Contents

Copyright © Copyright © 1996 IEEE. All Rights Reserved.

Publisher

IEEE Press

Publication History

Published: 01 April 1996

Author Tags

Qualifiers

Research-article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

29
Total Citations
View Citations
0
Total Downloads

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

Reflects downloads up to 04 Oct 2024

Other Metrics

View Author Metrics

Citations

Cited By

Wang JPanda RJohn L(2018)SelSMaPACM Transactions on Architecture and Code Optimization10.1145/327465015:4(1-21)Online publication date: 10-Oct-2018
https://dl.acm.org/doi/10.1145/3274650
Nori AGaur JRai SSubramoney SWang H(2018)Criticality aware tiered cache hierarchyProceedings of the 45th Annual International Symposium on Computer Architecture10.1109/ISCA.2018.00019(96-109)Online publication date: 2-Jun-2018
https://dl.acm.org/doi/10.1109/ISCA.2018.00019
Shevgoor MKoladiya SBalasubramonian RWilkerson CPugsley SChishti ZPrvulovic M(2015)Efficiently prefetching complex address patternsProceedings of the 48th International Symposium on Microarchitecture10.1145/2830772.2830793(141-152)Online publication date: 5-Dec-2015
https://dl.acm.org/doi/10.1145/2830772.2830793
Chen YLiu YMacii E(2013)Dual-addressing memory architecture for two-dimensional memory access patternsProceedings of the Conference on Design, Automation and Test in Europe10.5555/2485288.2485308(71-76)Online publication date: 18-Mar-2013
https://dl.acm.org/doi/10.5555/2485288.2485308
Grannaes MJahre MNatvig L(2010)Multi-level hardware prefetching using low complexity delta correlating prediction tables with partial matchingProceedings of the 5th international conference on High Performance Embedded Architectures and Compilers10.1007/978-3-642-11515-8_19(247-261)Online publication date: 25-Jan-2010
https://dl.acm.org/doi/10.1007/978-3-642-11515-8_19
Zhang ZKulkarni AMa XZhou YSchröder-Preikschat WWilkes JIsaacs R(2009)Memory resource allocation for file system prefetchingProceedings of the 4th ACM European conference on Computer systems10.1145/1519065.1519075(75-88)Online publication date: 1-Apr-2009
https://dl.acm.org/doi/10.1145/1519065.1519075
Ramos LBriz JIbáñez PViñals V(2008)Low-Cost Adaptive Data PrefetchingProceedings of the 14th international Euro-Par conference on Parallel Processing10.1007/978-3-540-85451-7_36(327-336)Online publication date: 26-Aug-2008
https://dl.acm.org/doi/10.1007/978-3-540-85451-7_36
Gill BBathen L(2007)Optimal multistream sequential prefetching in a shared cacheACM Transactions on Storage10.1145/1288783.12887893:3(10-es)Online publication date: 1-Oct-2007
https://dl.acm.org/doi/10.1145/1288783.1288789
Malkowski KLee IRaghavan PIrwin M(2006)Conjugate gradient sparse solversProceedings of the 20th international conference on Parallel and distributed processing10.5555/1898699.1898822(297-297)Online publication date: 25-Apr-2006
https://dl.acm.org/doi/10.5555/1898699.1898822
Dubois MVassiliadis SGaudiot JPiuri V(2004)Fighting the memory wall with assisted executionProceedings of the 1st conference on Computing frontiers10.1145/977091.977116(168-180)Online publication date: 14-Apr-2004
https://dl.acm.org/doi/10.1145/977091.977116
Show More Cited By

View Options

View options

Media

Figures

Other

Tables

View Issue’s Table of Contents