Optimization of data prefetch helper threads with path-expression based statistical modeling

ABSTRACT

This paper investigates helper threads that improve performance by prefetching data on behalf of an application's main thread. The focus is data prefetch helper threads that lack branch instructions and which generate prefetches for one dynamic instance of a delinquent load instruction per spawned helper thread. This form of helper thread, some-times called a simple p-thread, has been studied previously by Roth et al. [29, 26] who proposed a framework for optimizing their impact. A key step in that framework is predicting the performance impact of a helper thread. In this paper we propose and evaluate a novel performance prediction technique that achieves comparable results yet requires less detailed information about dynamic program behavior. This technique extends a path expression based statistical modeling framework [2] by incorporating information about branch correlation (which we show is important) and by considering data flow information in a statistical manner. Significantly, the profile information we use is similar to that provided within current optimizing compilers. This paper also provides the first comprehensive assessment of the sources of modeling error relevant to predicting the performance impact of simple p-threads.

REFERENCES

• 1: T. M. Aamodt. Modeling and Optimization of Speculative Threads. PhD thesis, Department of Electrical and Computer Engineering, University of Toronto, 2006.
• 2: Tor M. Aamodt , Pedro Marcuello , Paul Chow , Antonio González , Per Hammarlund , Hong Wang , John P. Shen, A framework for modeling and optimization of prescient instruction prefetch, Proceedings of the 2003 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 11-14, 2003, San Diego, CA, USA
• 3: Hiralal Agrawal , Joseph R. Horgan, Dynamic program slicing, Proceedings of the ACM SIGPLAN 1990 conference on Programming language design and implementation, p.246-256, June 1990, White Plains, New York, United States
• 4: Thomas Ball , James R. Larus, Efficient path profiling, Proceedings of the 29th annual ACM/IEEE international symposium on Microarchitecture, p.46-57, December 02-04, 1996, Paris, France
• 5: Rastislav Bodík , Rajiv Gupta , Mary Lou Soffa, Interprocedural conditional branch elimination, Proceedings of the ACM SIGPLAN 1997 conference on Programming language design and implementation, p.146-158, June 16-18, 1997, Las Vegas, Nevada, United States
• 6: D. Burger and T. M. Austin. The SimpleScalar Tool Set, Version 2.0. http://www.simplescalar.com, 1997.
• 7: Martin Christopher Carlisle, Olden: parallelizing programs with dynamic data structures on distributed-memory machines, Princeton University, Princeton, NJ, 1996
• 8: Pohua P. Chang , Scott A. Mahlke , Wen-mei W. Hwu, Using profile information to assist classic code optimizations, Software—Practice & Experience, v.21 n.12, p.1301-1321, Dec. 1991 [doi>10.1002/spe.4380211204]
• 9: Robert S. Chappell , Francis Tseng , Adi Yoaz , Yale N. Patt, Difficult-path branch prediction using subordinate microthreads, Proceedings of the 29th annual international symposium on Computer architecture, May 25-29, 2002, Anchorage, Alaska
• 10: Peng-Sheng Chen , Yuan-Shin Hwang , Roy Dz-Ching Ju , Jenq Kuen Lee, Interprocedural Probabilistic Pointer Analysis, IEEE Transactions on Parallel and Distributed Systems, v.15 n.10, p.893-907, October 2004 [doi>10.1109/TPDS.2004.56]
• 11: Jamison D. Collins , Hong Wang , Dean M. Tullsen , Christopher Hughes , Yong-Fong Lee , Dan Lavery , John P. Shen, Speculative precomputation: long-range prefetching of delinquent loads, Proceedings of the 28th annual international symposium on Computer architecture, p.14-25, June 30-July 04, 2001, Göteborg, Sweden
• 12: M. Dubois and Y. Song. Assisted execution. Technical Report CENG 98--25, Department of EE-Systems, University of Southern California, October 1998.
• 13: J. A. Fisher. Trace Scheduling: A Technique for Global Microcode Compaction. IEEE Trans. Computers, 30(7):478--490, 1981.
• 14: Gramma Tech. Codesurfer. http://www.grammatech.com, 2007.
• 15: Mary W. Hall , Jennifer M. Anderson , Saman P. Amarasinghe , Brian R. Murphy , Shih-Wei Liao , Edouard Bugnion , Monica S. Lam, Maximizing Multiprocessor Performance with the SUIF Compiler, Computer, v.29 n.12, p.84-89, December 1996 [doi>10.1109/2.546613]
• 16: Intel Corporation. Intel®VTune#8482; Performance Analyzer. http://www.intel.com, 2007.
• 17: Dongkeun Kim , Steve Shih-wei Liao , Perry H. Wang , Juan del Cuvillo , Xinmin Tian , Xiang Zou , Hong Wang , Donald Yeung , Milind Girkar , John P. Shen, Physical Experimentation with Prefetching Helper Threads on Intel's Hyper-Threaded Processors, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.27, March 20-24, 2004, Palo Alto, California
• 18: Dongkeun Kim , Donald Yeung, Design and evaluation of compiler algorithms for pre-execution, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 19: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 20: Steve S.W. Liao , Perry H. Wang , Hong Wang , Gerolf Hoflehner , Daniel Lavery , John P. Shen, Post-pass binary adaptation for software-based speculative precomputation, Proceedings of the ACM SIGPLAN 2002 Conference on Programming language design and implementation, June 17-19, 2002, Berlin, Germany
• 21: Chi-Keung Luk , Todd C. Mowry, Optimizing the cache performance of non-numeric applications, University of Toronto, Toronto, Ont., Canada, 2000
• 22: Eduard Mehofer , Bernhard Scholz, Probabilistic data flow system with two-edge profiling, Proceedings of the ACM SIGPLAN workshop on Dynamic and adaptive compilation and optimization, p.65-72, January 2000
• 23: 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]
• 24: Todd C. Mowry , Chi-Keung Luk, Predicting data cache misses in non-numeric applications through correlation profiling, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.314-320, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 25: Steven S. Muchnick, Advanced compiler design and implementation, Morgan Kaufmann Publishers Inc., San Francisco, CA, 1998
• 26: Vlad Petric , Amir Roth, Energy-Effectiveness of Pre-Execution and Energy-Aware P-Thread Selection, Proceedings of the 32nd annual international symposium on Computer Architecture, p.322-333, June 04-08, 2005
• 27: G. Ramalingam, Data flow frequency analysis, Proceedings of the ACM SIGPLAN 1996 conference on Programming language design and implementation, p.267-277, May 21-24, 1996, Philadelphia, Pennsylvania, United States
• 28: 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
• 29: Amir Roth , Gurindar S. Sohi, A quantitative framework for automated pre-execution thread selection, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey
• 30: Bernhard Scholz , Eduard Mehofer, Dataflow Frequency Analysis Based on Whole Program Paths, Proceedings of the 2002 International Conference on Parallel Architectures and Compilation Techniques, p.95-103, September 22-25, 2002
• 31: Timothy Sherwood , Erez Perelman , Greg Hamerly , Brad Calder, Automatically characterizing large scale program behavior, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 32: Srikanth T. Srinivasan , Alvin R. Lebeck, Load latency tolerance in dynamically scheduled processors, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.148-159, November 1998, Dallas, Texas, United States
• 33: Standard Performance Evaluation Corporation. SPEC 2000 CPU benchmarks. http://www.spec.org/.
• 34: Robert Endre Tarjan, A Unified Approach to Path Problems, Journal of the ACM (JACM), v.28 n.3, p.577-593, July 1981 [doi>10.1145/322261.322272]
• 35: Robert Endre Tarjan, Fast Algorithms for Solving Path Problems, Journal of the ACM (JACM), v.28 n.3, p.594-614, July 1981 [doi>10.1145/322261.322273]
• 36: 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 on an experimental itanium^® 2 processor-based platform, Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 37: Craig Zilles , Gurindar Sohi, Execution-based prediction using speculative slices, Proceedings of the 28th annual international symposium on Computer architecture, p.2-13, June 30-July 04, 2001, Göteborg, Sweden
• 38: Craig B. Zilles , Gurindar S. Sohi, Understanding the backward slices of performance degrading instructions, Proceedings of the 27th annual international symposium on Computer architecture, p.172-181, June 2000, Vancouver, British Columbia, Canada

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.0 GENERAL

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

  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.4 Processors
          Subjects: Optimization

General Terms:
Algorithms, Design, Measurement, Performance, Theory

Keywords:
analytical modeling, data prefetch, helper threads, multithreading, optimization, path expressions