Predictor virtualization

ABSTRACT

Many hardware optimizations rely on collecting information about program behavior at runtime. This information is stored in lookup tables. To be accurate and effective, these optimizations usually require large dedicated on-chip tables. Although technology advances offer an increased amount of on-chip resources, these resources are allocated to increase the size of on-chip conventional cache hierarchies.

This work proposes Predictor Virtualization, a technique that uses the existing memory hierarchy to emulate large predictor tables. We demonstrate the benefits of this technique by virtualizing a state-of-the-art data prefetcher. Full-system, cycle-accurate simulations demonstrate that the virtualized prefetcher preserves the performance benefits of the original design, while reducing the on-chip storage dedicated to the predictor table from 60KB down to less than one kilobyte.

REFERENCES

• 1: Yoav Almog , Roni Rosner , Naftali Schwartz , Ari Schmorak, Specialized Dynamic Optimizations for High-Performance Energy-Efficient Microarchitecture, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.137, March 20-24, 2004, Palo Alto, California
• 2: Paul Barham , Boris Dragovic , Keir Fraser , Steven Hand , Tim Harris , Alex Ho , Rolf Neugebauer , Ian Pratt , Andrew Warfield, Xen and the art of virtualization, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 3: Luiz André Barroso , Kourosh Gharachorloo , Robert McNamara , Andreas Nowatzyk , Shaz Qadeer , Barton Sano , Scott Smith , Robert Stets , Ben Verghese, Piranha: a scalable architecture based on single-chip multiprocessing, Proceedings of the 27th annual international symposium on Computer architecture, p.282-293, June 2000, Vancouver, British Columbia, Canada
• 4: Jason F. Cantin , Mikko H. Lipasti , James E. Smith, Stealth prefetching, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 5: David Chaiken , John Kubiatowicz , Anant Agarwal, LimitLESS directories: A scalable cache coherence scheme, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.224-234, April 08-11, 1991, Santa Clara, California, United States
• 6: Christopher Clark , Keir Fraser , Steven Hand , Jacob Gorm Hansen , Eric Jul , Christian Limpach , Ian Pratt , Andrew Warfield, Live migration of virtual machines, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.273-286, May 02-04, 2005
• 7: 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
• 8: Jamison Collins , Suleyman Sair , Brad Calder , Dean M. Tullsen, Pointer cache assisted prefetching, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 9: M. Ekman , P. Stenstrom, Enhancing Multiprocessor Architecture Simulation Speed Using Matched-Pair Comparison, Proceedings of the IEEE International Symposium on Performance Analysis of Systems and Software, 2005, p.89-99, March 20-22, 2005 [doi>10.1109/ISPASS.2005.1430562]
• 10: Ferdman, M., and Falsafi, B. Last-Touch Correlated Data Streaming. In Proc. of the Intl' Symposium on Performance Analysis of Systems and Software, 2007.
• 11: Chris Gniady , Babak Falsafi, Speculative Sequential Consistency with Little Custom Storage, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.179-188, September 22-25, 2002
• 12: Nikolaos Hardavellas , Stephen Somogyi , Thomas F. Wenisch , Roland E. Wunderlich , Shelley Chen , Jangwoo Kim , Babak Falsafi , James C. Hoe , Andreas G. Nowatzyk, SimFlex: a fast, accurate, flexible full-system simulation framework for performance evaluation of server architecture, ACM SIGMETRICS Performance Evaluation Review, v.31 n.4, p.31-34, March 2004 [doi>10.1145/1054907.1054914]
• 13: Zhigang Hu , Stefanos Kaxiras , Margaret Martonosi, Timekeeping in the memory system: predicting and optimizing memory behavior, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 14: Jerger, N., Hill, E., and Lipasti, M. Friendly Fire: Understanding the Effects of Multiprocessor Prefetching. In Proc. of the International Symposium on Performance Analysis of Systems and Software, 2006.
• 15: Chetana N. Keltcher , Kevin J. McGrath , Ardsher Ahmed , Pat Conway, The AMD Opteron Processor for Multiprocessor Servers, IEEE Micro, v.23 n.2, p.66-76, March 2003 [doi>10.1109/MM.2003.1196116]
• 16: Mikko H. Lipasti , John Paul Shen, Exceeding the dataflow limit via value prediction, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.226-237, December 02-04, 1996, Paris, France
• 17: 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
• 18: 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]
• 19: Sanjay J. Patel , Steven S. Lumetta, rePLay: A Hardware Framework for Dynamic Optimization, IEEE Transactions on Computers, v.50 n.6, p.590-608, June 2001 [doi>10.1109/12.931895]
• 20: Moinuddin K. Qureshi , Daniel N. Lynch , Onur Mutlu , Yale N. Patt, A Case for MLP-Aware Cache Replacement, Proceedings of the 33rd annual international symposium on Computer Architecture, p.167-178, June 17-21, 2006
• 21: Ravi Rajwar , Maurice Herlihy , Konrad Lai, Virtualizing Transactional Memory, Proceedings of the 32nd annual international symposium on Computer Architecture, p.494-505, June 04-08, 2005
• 22: Parthasarathy Ranganathan , Sarita Adve , Norman P. Jouppi, Reconfigurable caches and their application to media processing, Proceedings of the 27th annual international symposium on Computer architecture, p.214-224, June 2000, Vancouver, British Columbia, Canada
• 23: Roni Rosner , Yoav Almog , Micha Moffie , Naftali Schwartz , Avi Mendelson, Power Awareness through Selective Dynamically Optimized Traces, Proceedings of the 31st annual international symposium on Computer architecture, p.162, June 19-23, 2004, München, Germany
• 24: 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
• 25: Timothy Sherwood , Suleyman Sair , Brad Calder, Predictor-directed stream buffers, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.42-53, December 2000, Monterey, California, United States [doi>10.1145/360128.360135]
• 26: Avinash Sodani , Gurindar S. Sohi, Dynamic instruction reuse, Proceedings of the 24th annual international symposium on Computer architecture, p.194-205, June 01-04, 1997, Denver, Colorado, United States
• 27: Stephen Somogyi , Thomas F. Wenisch , Anastassia Ailamaki , Babak Falsafi , Andreas Moshovos, Spatial Memory Streaming, Proceedings of the 33rd annual international symposium on Computer Architecture, p.252-263, June 17-21, 2006
• 28: Tendler, J., Dodson, S., and Fields, S. IBM eServer Power4 System Microarchitecture, Technical White Paper, IBM Server Group, 2001
• 29: VMWare -- http://www.vmware.com
• 30: Kai Wang , Manoj Franklin, Highly accurate data value prediction using hybrid predictors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.281-290, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 31: Zhenlin Wang , Doug Burger , Kathryn S. McKinley , Steven K. Reinhardt , Charles C. Weems, Guided region prefetching: a cooperative hardware/software approach, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 32: Thomas F. Wenisch , Stephen Somogyi , Nikolaos Hardavellas , Jangwoo Kim , Anastassia Ailamaki , Babak Falsafi, Temporal Streaming of Shared Memory, Proceedings of the 32nd annual international symposium on Computer Architecture, p.222-233, June 04-08, 2005
• 33: Thomas F. Wenisch , Roland E. Wunderlich , Michael Ferdman , Anastassia Ailamaki , Babak Falsafi , James C. Hoe, SimFlex: Statistical Sampling of Computer System Simulation, IEEE Micro, v.26 n.4, p.18-31, July 2006 [doi>10.1109/MM.2006.79]
• 34: Roland E. Wunderlich , Thomas F. Wenisch , Babak Falsafi , James C. Hoe, SMARTS: accelerating microarchitecture simulation via rigorous statistical sampling, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 35: Weifeng Zhang , Brad Calder , Dean M. Tullsen, An Event-Driven Multithreaded Dynamic Optimization Framework, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.87-98, September 17-21, 2005 [doi>10.1109/PACT.2005.7]

INDEX TERMS

Primary Classification:
  B. Hardware
  B.3 MEMORY STRUCTURES
      B.3.2 Design Styles
          Subjects: Cache memories

General Terms:
Design, Performance

Keywords:
caches, memory hierarchy, metadata, predictor virtualization