Tight analysis of the performance potential of thread speculation using spec CPU 2006

ABSTRACT

Multi-cores such as the Intel®1 Core™2 Duo processor, facilitate efficient thread-level parallel execution of ordinary programs, wherein the different threads-of-execution are mapped onto different physical processors. In this context, several techniques have been proposed for auto-parallelization of programs. Recently, thread-level speculation (TLS) has been proposed as a means to parallelize difficult-to-analyze serial codes. In general, more than one technique can be employed for parallelizing a given program. The overlapping nature of the applicability of the various techniques makes it hard to assess the intrinsic performance potential of each. In this paper, we present a tight analysis of the (unique) performance potential of both: (a) TLS in general and (b) specific types of thread-level speculation, viz., control speculation, data dependence speculation and data value speculation, for the SPEC² CPU2006 benchmark suite in light of the various limiting factors such as the threading overhead and misspeculation penalty. To the best of our knowledge, this is the first evaluation of TLS based on SPEC CPU2006 and accounts for the aforementioned real-life con-straints. Our analysis shows that, at the innermost loop level, the upper bound on the speedup uniquely achievable via TLS with the state-of-the-art thread implementations for both SPEC CINT2006 and CFP2006 is of the order of 1%.

REFERENCES

• 1: A. Kejariwal and A. Nicolau. Reading list of performance analysis, speculative execution. http://www.ics.uci.edu~akejariw/SpeculativeExecutionReadingList.pdf.
• 2: S. F. Lundstrom and G. H. Barnes. A controllable MIMD architectures. In Proceedings of the 1980 International Conference on Parallel Processing, pages 19--27, St. Charles, IL, August 1980.
• 3: Arun Kejariwal , Xinmin Tian , Wei Li , Milind Girkar , Sergey Kozhukhov , Hideki Saito , Utpal Banerjee , Alexandru Nicolau , Alexander V. Veidenbaum , Constantine D. Polychronopoulos, On the performance potential of different types of speculative thread-level parallelism: The DL version of this paper includes corrections that were not made available in the printed proceedings, Proceedings of the 20th annual international conference on Supercomputing, June 28-July 01, 2006, Cairns, Queensland, Australia [doi>10.1145/1183401.1183407]
• 4: SPEC CPU2006. http://www.spec.org/cpu2006.
• 5: G. M. Amdahl. Validity of the single processor approachtoachieving large scale computing capabilities. In AFIPS Conference Proceedings, pages 483--485, 1967.
• 6: Open Research Compiler for Itanium TM Processor Family. http://ipf-orc.sourceforge.net/.
• 7: GCC, the GNU Compiler Collection. http://gcc.gnu.org/.
• 8: P. Jouvelot, Semantic parallelization: a practical exercise in abstract interpretation, Proceedings of the 14th ACM SIGACT-SIGPLAN symposium on Principles of programming languages, p.39-48, January 21-23, 1987, Munich, West Germany [doi>10.1145/41625.41629]
• 9: Pierre Jouvelot , Babak Dehbonei, A unified semantic approach for the vectorization and parallelization of generalized reductions, Proceedings of the 3rd international conference on Supercomputing, p.186-194, June 05-09, 1989, Crete, Greece [doi>10.1145/318789.318810]
• 10: D. J. Quinlan, M. Schordan, Q. Yi, and B. R. de Supinski. Semantic-driven parallelization of loops operating on user-defined containers. pages 524--538, College Station, TX, October 2003.
• 11: U. Banerjee, R. Eigenmann, A. Nicolau, and D. Padua. Automatic program parallelization. Proceedings of the IEEE, 81(2):211--243, February 1993.
• 12: Nicholas Mitchell , Larry Carter , Jeanne Ferrante , Dean Tullsen, ILP versus TLP on SMT, Proceedings of the 1999 ACM/IEEE conference on Supercomputing (CDROM), p.37-es, November 14-19, 1999, Portland, Oregon, United States [doi>10.1145/331532.331569]
• 13: B. R. Rau , C. D. Glaeser, Some scheduling techniques and an easily schedulable horizontal architecture for high performance scientific computing, Proceedings of the 14th annual workshop on Microprogramming, p.183-198, December 01-01, 1981, Chatham, Massachusetts, United States
• 14: A. Nicolau. Percolation scheduling. In Proceedings of the 1985 International Conference on Parallel Processing, August 1985.
• 15: Konstantinos Kyriakopoulos , Kleanthis Psarris, Efficient Techniques for Advanced Data Dependence Analysis, Proceedings of the 14th International Conference on Parallel Architectures and Compilation Techniques, p.143-156, September 17-21, 2005 [doi>10.1109/PACT.2005.19]
• 16: A. Aiken and A. Nicolau. Perfect pipelining: A new loop parallelization technique. Technical Report 87--873, Dept. of Computer Science, Cornell University, 1987.
• 17: Jeffrey T. Oplinger , David L. Heine , Monica S. Lam, In Search of Speculative Thread-Level Parallelism, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.303, October 12-16, 1999
• 18: A Quantitative Assessment of Thread-Level Speculation Techniques, Proceedings of the 14th International Symposium on Parallel and Distributed Processing, p.595, May 01-05, 2000
• 19: Jose Renau , James Tuck , Wei Liu , Luis Ceze , Karin Strauss , Josep Torrellas, Tasking with out-of-order spawn in TLS chip multiprocessors: microarchitecture and compilation, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088173]
• 20: Alexandru Nicolau, Run-time disambiguation: coping with statically unpredictable dependencies, IEEE Transactions on Computers, v.38 n.5, p.633-678, May 1989
• 21: R. Gerber, A. J. C. Bik, K. B. Smith, and X. Tian. The Software Optimization Cookbook, Second Edition. Intel Press, 2006.
• 22: Ian Piumarta , Fabio Riccardi, Optimizing direct threaded code by selective inlining, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.291-300, June 17-19, 1998, Montreal, Quebec, Canada
• 23: Jin Lin , Tong Chen , Wei-Chung Hsu , Pen-Chung Yew , Roy Dz-Ching Ju , Tin-Fook Ngai , Sun Chan, A compiler framework for speculative analysis and optimizations, Proceedings of the ACM SIGPLAN 2003 conference on Programming language design and implementation, June 09-11, 2003, San Diego, California, USA
• 24: Xiaoru Dai , Antonia Zhai , Wei-Chung Hsu , Pen-Chung Yew, A General Compiler Framework for Speculative Optimizations Using Data Speculative Code Motion, Proceedings of the international symposium on Code generation and optimization, p.280-290, March 20-23, 2005 [doi>10.1109/CGO.2005.1]
• 25: Pedro Marcuello , Antonio González, Thread-Spawning Schemes for Speculative Multithreading, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.55, February 02-06, 2002
• 26: Intel R VTune TM Performance Analyzer 8.0 for Windows. http://www.intel.com/cd/software/products/asmo-na/eng/vtune/219898.htm.
• 27: U. Drepper. The Native POSIX Thread Library for Linux. http://people.redhat.com/drepper/nptl-design.pdf, February 2005.
• 28: EPCC OpenMP Microbenchmarks. http://www.epcc.ed.ac.uk/research/openmpbench/openmp index.html.
• 29: Clyde P. Kruskal , Alan Weiss, Allocating independent subtasks on parallel processors, IEEE Transactions on Software Engineering, v.11 n.10, p.1001-1016, Oct. 1985 [doi>10.1109/TSE.1985.231547]
• 30: Utpal K. Banerjee, Dependence Analysis, Kluwer Academic Publishers, Norwell, MA, 1996
• 31: Ding-Kai Chen , Pen-Chung Yew, Redundant Synchronization Elimination for DOACROSS Loops, Proceedings of the 8th International Symposium on Parallel Processing, p.477-481, April 01, 1994
• 32: M. Philippsen , E. A. Heinz, Automatic synchronisation elimination in synchronous FORALLs, Proceedings of the Fifth Symposium on the Frontiers of Massively Parallel Computation (Frontiers'95), p.350, February 06-09, 1995
• 33: Michael Joseph Wolfe , Carter Shanklin , Leda Ortega, High Performance Compilers for Parallel Computing, Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1995
• 34: Haitham Akkary , Srikanth T. Srinivasan , Konrad Lai, Recycling waste: exploiting wrong-path execution to improve branch prediction, Proceedings of the 17th annual international conference on Supercomputing, June 23-26, 2003, San Francisco, CA, USA [doi>10.1145/782814.782819]
• 35: Thomas Ball , James R. Larus, Branch prediction for free, Proceedings of the ACM SIGPLAN 1993 conference on Programming language design and implementation, p.300-313, June 21-25, 1993, Albuquerque, New Mexico, United States

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Measurement techniques

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Measurement, Performance

Keywords:
conflict probability, misspeculation penalty, performance evaluation, speculative execution, threading overhead