Dynamic performance tuning for speculative threads

ABSTRACT

In response to the emergence of multicore processors, various novel and sophisticated execution models have been introduced to fully utilize these processors. One such execution model is Thread-Level Speculation (TLS), which allows potentially dependent threads to execute speculatively in parallel. While TLS offers significant performance potential for applications that are otherwise non-parallel, extracting efficient speculative threads in the presence of complex control flow and ambiguous data dependences is a real challenge. This task is further complicated by the fact that the performance of speculative threads is often architecture-dependent, input-sensitive, and exhibits phase behaviors. Thus we propose dynamic performance tuning mechanisms that determine where and how to create speculative threads at runtime.

This paper describes the design, implementation, and evaluation of hardware and software support that takes advantage of runtime performance profiles to extract efficient speculative threads. In our proposed framework, speculative threads are monitored by hardware-based performance counters and their performance impact is estimated. The creation of speculative threads is adjusted based on the estimation. This paper proposes speculative threads performance estimation techniques, that are capable of correctly determining whether speculation can improve performance for loops that corresponds to 83.8% of total loop execution time across all benchmarks. This paper also examines several dynamic performance tuning policies and finds that the best tuning policy achieves an overall speedup of 36.8%on a set of benchmarks from SPEC2000 suite, which outperforms static thread management by 9.5%.

REFERENCES

• 1: Haitham Akkary , Michael A. Driscoll, A dynamic multithreading processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.226-236, November 1998, Dallas, Texas, United States
• 2: Derek Bruening , Timothy Garnett , Saman Amarasinghe, An infrastructure for adaptive dynamic optimization, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, March 23-26, 2003, San Francisco, California
• 3: BURCEA, M. stOMP: A Specializing Thread Library for OpenMP. PhD thesis, University of Toronto, 2005.
• 4: Doug Burger , Todd M. Austin, The SimpleScalar tool set, version 2.0, ACM SIGARCH Computer Architecture News, v.25 n.3, p.13-25, June 1997 [doi>10.1145/268806.268810]
• 5: Marcelo Cintra , Josep Torrellas, Eliminating Squashes Through Learning Cross-Thread Violations in Speculative Parallelization for Multiprocessors, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.43, February 02-06, 2002
• 6: 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
• 7: Leonardo Dagum , Ramesh Menon, OpenMP: An Industry-Standard API for Shared-Memory Programming, IEEE Computational Science & Engineering, v.5 n.1, p.46-55, January 1998 [doi>10.1109/99.660313]
• 8: Pradeep K. Dubey , Kevin O'Brien , Kathryn M. O'Brien , Charles Barton, Single-program speculative multithreading (SPSM) architecture: compiler-assisted fine-grained multithreading, Proceedings of the IFIP WG10.3 working conference on Parallel architectures and compilation techniques, p.109-121, June 27-29, 1995, Limassol, Cyprus
• 9: Stijn Eyerman , Lieven Eeckhout , Tejas Karkhanis , James E. Smith, A performance counter architecture for computing accurate CPI components, Proceedings of the 12th international conference on Architectural support for programming languages and operating systems, October 21-25, 2006, San Jose, California, USA
• 10: Manoj Franklin , Gurindar S. Sohi, The expandable split window paradigm for exploiting fine-grain parallelsim, Proceedings of the 19th annual international symposium on Computer architecture, p.58-67, May 19-21, 1992, Queensland, Australia
• 11: Manish Gupta , Rahul Nim, Techniques for speculative run-time parallelization of loops, Proceedings of the 1998 ACM/IEEE conference on Supercomputing (CDROM), p.1-12, November 07-13, 1998, San Jose, CA
• 12: Lance Hammond , Brian D. Carlstrom , Vicky Wong , Ben Hertzberg , Mike Chen , Christos Kozyrakis , Kunle Olukotun, Programming with transactional coherence and consistency (TCC), Proceedings of the 11th international conference on Architectural support for programming languages and operating systems, October 07-13, 2004, Boston, MA, USA
• 13: Lance Hammond , Mark Willey , Kunle Olukotun, Data speculation support for a chip multiprocessor, Proceedings of the eighth international conference on Architectural support for programming languages and operating systems, p.58-69, October 02-07, 1998, San Jose, California, United States
• 14: Lance Hammond , Vicky Wong , Mike Chen , Brian D. Carlstrom , John D. Davis , Ben Hertzberg , Manohar K. Prabhu , Honggo Wijaya , Christos Kozyrakis , Kunle Olukotun, Transactional Memory Coherence and Consistency, Proceedings of the 31st annual international symposium on Computer architecture, p.102, June 19-23, 2004, München, Germany
• 15: Maurice Herlihy , J. Eliot B. Moss, Transactional memory: architectural support for lock-free data structures, Proceedings of the 20th annual international symposium on Computer architecture, p.289-300, May 16-19, 1993, San Diego, California, United States
• 16: Troy A. Johnson , Rudolf Eigenmann , T. N. Vijaykumar, Min-cut program decomposition for thread-level speculation, Proceedings of the ACM SIGPLAN 2004 conference on Programming language design and implementation, June 09-11, 2004, Washington DC, USA
• 17: Troy A. Johnson , Rudolf Eigenmann , T. N. Vijaykumar, Speculative thread decomposition through empirical optimization, Proceedings of the 12th ACM SIGPLAN symposium on Principles and practice of parallel programming, March 14-17, 2007, San Jose, California, USA [doi>10.1145/1229428.1229474]
• 18: Karthik Sundaramoorthy , Zach Purser , Eric Rotenburg, Slipstream processors: improving both performance and fault tolerance, Proceedings of the ninth international conference on Architectural support for programming languages and operating systems, p.257-268, November 2000, Cambridge, Massachusetts, United States
• 19: 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
• 20: Tom Knight, An architecture for mostly functional languages, Proceedings of the 1986 ACM conference on LISP and functional programming, p.105-112, August 1986, Cambridge, Massachusetts, United States [doi>10.1145/319838.319854]
• 21: Venkata Krishnan , Josep Torrellas, The Need for Fast Communication in Hardware-Based Speculative Chip Multiprocessors, Proceedings of the 1999 International Conference on Parallel Architectures and Compilation Techniques, p.24, October 12-16, 1999
• 22: Jae W. Lee , Man Cheuk Ng , Krste Asanovic, Globally-Synchronized Frames for Guaranteed Quality-of-Service in On-Chip Networks, Proceedings of the 35th International Symposium on Computer Architecture, p.89-100, June 21-25, 2008
• 23: Wei Liu , James Tuck , Luis Ceze , Wonsun Ahn , Karin Strauss , Jose Renau , Josep Torrellas, POSH: a TLS compiler that exploits program structure, Proceedings of the eleventh ACM SIGPLAN symposium on Principles and practice of parallel programming, March 29-31, 2006, New York, New York, USA [doi>10.1145/1122971.1122997]
• 24: Jiwei Lu , Howard Chen , Rao Fu , Wei-Chung Hsu , Bobbie Othmer , Pen-Chung Yew , Dong-Yuan Chen, The Performance of Runtime Data Cache Prefetching in a Dynamic Optimization System, Proceedings of the 36th annual IEEE/ACM International Symposium on Microarchitecture, p.180, December 03-05, 2003
• 25: LU, J., CHEN, H., YEW, P. C., AND HSU, W. C. Design and implementation of a lightweight dynamic optimization system. Journal of Instruction Level Parallelism 6 (2004).
• 26: Jiwei Lu , Abhinav Das , Wei-Chung Hsu , Khoa Nguyen , Santosh G. Abraham, Dynamic Helper Threaded Prefetching on the Sun UltraSPARC CMP Processor, Proceedings of the 38th annual IEEE/ACM International Symposium on Microarchitecture, p.93-104, November 12-16, 2005, Barcelona, Spain [doi>10.1109/MICRO.2005.18]
• 27: 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
• 28: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 29: Pedro Marcuello , Antonio González, Clustered speculative multithreaded processors, Proceedings of the 13th international conference on Supercomputing, p.365-372, June 20-25, 1999, Rhodes, Greece [doi>10.1145/305138.305214]
• 30: 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
• 31: Pedro Marcuello , Antonio González , Jordi Tubella, Speculative multithreaded processors, Proceedings of the 12th international conference on Supercomputing, p.77-84, July 1998, Melbourne, Australia [doi>10.1145/277830.277850]
• 32: MERICAS, A. Performance monitoring on the POWER5 microprocessor. In Performance Evaluation and Benchmarking, L. K. John and L. Eeckhout, Eds. CRC Press, 2006, pp. 247--266.
• 33: Priya Nagpurkar , Chandra Krintz , Michael Hind , Peter F. Sweeney , V. T. Rajan, Online Phase Detection Algorithms, Proceedings of the International Symposium on Code Generation and Optimization, p.111-123, March 26-29, 2006 [doi>10.1109/CGO.2006.26]
• 34: OPEN64 DEVELOPERS. Open64 compiler and tools, 2001.
• 35: 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
• 36: PERELMAN, E., POLITO, M., YVES BOUGUET, J., SAMPSON, J., CALDER, B., AND DULONG, C. Detecting phases in parallel applications on shared memory architectures. In Proc. of the International Parallel and Distributed Processing Symposium. 2006.
• 37: Zach Purser , Karthik Sundaramoorthy , Eric Rotenberg, A study of slipstream processors, Proceedings of the 33rd annual ACM/IEEE international symposium on Microarchitecture, p.269-280, December 2000, Monterey, California, United States [doi>10.1145/360128.360155]
• 38: Ravi Rajwar , James R. Goodman, Transactional lock-free execution of lock-based programs, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 39: Jose Renau , Karin Strauss , Luis Ceze , Wei Liu , Smruti Sarangi , James Tuck , Josep Torrellas, Thread-Level Speculation on a CMP can be energy efficient, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088178]
• 40: Gurindar S. Sohi , Scott E. Breach , T. N. Vijaykumar, Multiscalar processors, Proceedings of the 22nd annual international symposium on Computer architecture, p.414-425, June 22-24, 1995, S. Margherita Ligure, Italy
• 41: J. Greggory Steffan , Christopher B. Colohan , Antonia Zhai , Todd C. Mowry, A scalable approach to thread-level speculation, Proceedings of the 27th annual international symposium on Computer architecture, p.1-12, June 2000, Vancouver, British Columbia, Canada
• 42: M. Aater Suleman , Moinuddin K. Qureshi , Yale N. Patt, Feedback-driven threading: power-efficient and high-performance execution of multi-threaded workloads on CMPs, Proceedings of the 13th international conference on Architectural support for programming languages and operating systems, March 01-05, 2008, Seattle, WA, USA
• 43: Gregory T. Sullivan , Derek L. Bruening , Iris Baron , Timothy Garnett , Saman Amarasinghe, Dynamic native optimization of interpreters, Proceedings of the 2003 workshop on Interpreters, virtual machines and emulators, p.50-57, June 12-12, 2003, San Diego, California [doi>10.1145/858570.858576]
• 44: Jenn-Yaun Tsai , Jian Huang , Christoffer Amlo , David J. Lilja , Pen-Chung Yew, The Superthreaded Processor Architecture, IEEE Transactions on Computers, v.48 n.9, p.881-902, September 1999 [doi>10.1109/12.795219]
• 45: J. Tubella , A. González, Control Speculation in Multithreaded Processors through Dynamic Loop Detection, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.14, January 31-February 04, 1998
• 46: T. N. Vijaykumar , Gurindar S. Sohi, Task selection for a multiscalar processor, Proceedings of the 31st annual ACM/IEEE international symposium on Microarchitecture, p.81-92, November 1998, Dallas, Texas, United States
• 47: WANG, S., DAI, X., YELLAJYOSULA, K. S., ZHAI, A., AND YEW, P.-C. Loop selection for thread-level speculation. In Proc. of the Workshops on Languages and Compilers for Parallel Computing. Oct 2005.
• 48: Antonia Zhai , Christopher B. Colohan , J. Gregory Steffan , Todd C. Mowry, Compiler optimization of scalar value communication between speculative threads, Proceedings of the 10th international conference on Architectural support for programming languages and operating systems, October 05-09, 2002, San Jose, California
• 49: Antonia Zhai , Christopher B. Colohan , J. Gregory Steffan , Todd C. Mowry, Compiler Optimization of Memory-Resident Value Communication Between Speculative Threads, Proceedings of the international symposium on Code generation and optimization: feedback-directed and runtime optimization, p.39, March 20-24, 2004, Palo Alto, California
• 50: 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:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.2 Multiple Data Stream Architectures (Multiprocessors)
          Subjects: Multiple-instruction-stream, multiple-data-stream processors (MIMD)

General Terms:
Experimentation, Performance

Keywords:
dynamic optimization, multicore, parallelism, thread-level speculation