Efficient emulation of hardware prefetchers via event-driven helper threading

ABSTRACT

The advance of multi-core architectures provides significant benefits for parallel and throughput-oriented computing, but the performance of individual computation threads does not improve and may even suffer a penalty because of the increased contention for shared resources. This paper explores the idea of using available general-purpose cores in a CMP as helper engines for individual threads running on the active cores. We propose a lightweight architectural framework for efficient event-driven software emulation of complex hardware accelerators and describe how this framework can be applied to implement a variety of prefetching techniques. We demonstrate the viability and effectiveness of our framework on a wide range of applications from the SPEC CPU2000 and Olden benchmark suites. On average, our mechanism provides performance benefits within 5% of pure hardware implementations. Furthermore, we demonstrate that running event-driven prefetching threads on top of a baseline with a hardware stride prefetcher yields significant speedups for many programs. Finally, we show that our approach provides competitive performance improvements over other hardware approaches for multi-core execution while executing fewer instructions and requiring considerably less hardware support.

REFERENCES

• 1: Jamison D. Collins , Dean M. Tullsen , Hong Wang , John P. Shen, Dynamic speculative precomputation, Proceedings of the 34th annual ACM/IEEE international symposium on Microarchitecture, December 01-05, 2001, Austin, Texas
• 2: Robert Cooksey , Stephan Jourdan , Dirk Grunwald, A stateless, content-directed data prefetching mechanism, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 3: John W. C. Fu , Janak H. Patel , Bob L. Janssens, Stride directed prefetching in scalar processors, Proceedings of the 25th annual international symposium on Microarchitecture, p.102-110, December 01-04, 1992, Portland, Oregon, United States
• 4: Ilya Ganusov , Martin Burtscher, Future Execution: A Hardware Prefetching Technique for Chip Multiprocessors, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.350-360, September 17-21, 2005 [doi>10.1109/PACT.2005.23]
• 5: Bart Goeman , Hans Vandierendonck , Koen de Bosschere, Differential FCM: Increasing Value Prediction Accuracy by Improving Table Usage Efficiency, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.207, January 20-24, 2001
• 6: http://www.spec.org/osg/cpu2000/.
• 7: Doug Joseph , Dirk Grunwald, Prefetching using Markov predictors, Proceedings of the 24th annual international symposium on Computer architecture, p.252-263, June 01-04, 1997, Denver, Colorado, United States
• 8: Norman P. Jouppi, Improving direct-mapped cache performance by the addition of a small fully-associative cache and prefetch buffers, Proceedings of the 17th annual international symposium on Computer Architecture, p.364-373, May 28-31, 1990, Seattle, Washington, United States
• 9: Gokul B. Kandiraju , Anand Sivasubramaniam, Going the distance for TLB prefetching: an application-driven study, Proceedings of the 29th annual international symposium on Computer architecture, p.195, May 25-29, 2002, Anchorage, Alaska
• 10: E. Larson, S. Chatterjee, and T. Austin. Mase: a novel infrastructure for detailed microarchitectural modeling. In Proc. Second Intl. Symp. on Performance Analysis of Systems and Software, 2001.
• 11: Mikko H. Lipasti , Christopher B. Wilkerson , John Paul Shen, Value locality and load value prediction, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.138-147, October 01-04, 1996, Cambridge, Massachusetts, United States
• 12: Chi-Keung Luk, Tolerating memory latency through software-controlled pre-execution in simultaneous multithreading processors, Proceedings of the 28th annual international symposium on Computer architecture, p.40-51, June 30-July 04, 2001, Göteborg, Sweden
• 13: Chi-Keung Luk , Todd C. Mowry, Compiler-based prefetching for recursive data structures, Proceedings of the seventh international conference on Architectural support for programming languages and operating systems, p.222-233, October 01-04, 1996, Cambridge, Massachusetts, United States
• 14: Andreas Moshovos , Dionisios N. Pnevmatikatos , Amirali Baniasadi, Slice-processors: an implementation of operation-based prediction, Proceedings of the 15th international conference on Supercomputing, p.321-334, June 2001, Sorrento, Italy [doi>10.1145/377792.377856]
• 15: Onur Mutlu , Jared Stark , Chris Wilkerson , Yale N. Patt, Runahead Execution: An Alternative to Very Large Instruction Windows for Out-of-Order Processors, Proceedings of the 9th International Symposium on High-Performance Computer Architecture, p.129, February 08-12, 2003
• 16: Kyle J. Nesbit , James E. Smith, Data Cache Prefetching Using a Global History Buffer, Proceedings of the 10th International Symposium on High Performance Computer Architecture, p.96, February 14-18, 2004 [doi>10.1109/HPCA.2004.10030]
• 17: S. Palacharla , R. E. Kessler, Evaluating stream buffers as a secondary cache replacement, Proceedings of the 21ST annual international symposium on Computer architecture, p.24-33, April 18-21, 1994, Chicago, Illinois, United States
• 18: Justin Rattner, Multi-Core to the Masses, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.3, September 17-21, 2005 [doi>10.1109/PACT.2005.31]
• 19: Amir Roth , Gurindar S. Sohi, Speculative Data-Driven Multithreading, Proceedings of the 7th International Symposium on High-Performance Computer Architecture, p.37, January 20-24, 2001
• 20: Yiannakis Sazeides , James E. Smith, The predictability of data values, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.248-258, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 21: P. Shivakumar and N. P. Jouppi. Cacti 3.0: An integrated cache timing, power, and area model. Tech. report WRL-2001-2, Compaq Western Research Laboratory, December 2001.
• 22: Yan Solihin , Jaejin Lee , Josep Torrellas, Using a user-level memory thread for correlation prefetching, Proceedings of the 29th annual international symposium on Computer architecture, p.171, May 25-29, 2002, Anchorage, Alaska
• 23: Srikanth T. Srinivasan , Haitham Akkary , Tom Holman , Konrad Lai, A Minimal Dual-Core Speculative Multi-Threading Architecture, Proceedings of the IEEE International Conference on Computer Design (ICCD'04), p.360-367, October 11-13, 2004
• 24: Perry H. Wang , Jamison D. Collins , Hong Wang , Dongkeun Kim , Bill Greene , Kai-Ming Chan , Aamir B. Yunus , Terry Sych , Stephen F. Moore , John P. Shen, Helper Threads via Virtual Multithreading, IEEE Micro, v.24 n.6, p.74-82, November 2004 [doi>10.1109/MM.2004.75]
• 25: Chengqiang Zhang , Sally A. McKee, Hardware-only stream prefetching and dynamic access ordering, Proceedings of the 14th international conference on Supercomputing, p.167-175, May 08-11, 2000, Santa Fe, New Mexico, United States [doi>10.1145/335231.335247]
• 26: Huiyang Zhou, Dual-Core Execution: Building a Highly Scalable Single-Thread Instruction Window, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.231-242, September 17-21, 2005 [doi>10.1109/PACT.2005.18]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.8 Performance and Reliability

General Terms:
Performance

Keywords:
helper threading, multi-core architectures, prefetching