Tasking with out-of-order spawn in TLS chip multiprocessors: microarchitecture and compilation

ABSTRACT

Chip Multiprocessors (CMPs) are flexible, high-frequency platforms on which to support Thread-Level Speculation (TLS). However, for TLS to deliver on its promise, CMPs must exploit multiple sources of speculative task-level parallelism, including any nesting levels of both subroutines and loop iterations. Unfortunately, these environments are hard to support in decentralized CMP hardware: since tasks are spawned out-of-order and unpredictably, maintaining key TLS basics such as task ordering and efficient resource allocation is challenging.While the concept of out-of-order spawning is not new, this paper is the first to propose a set of microarchitectural mechanisms that, altogether, fundamentally enable fast TLS with out-of-order spawn in a CMP. Moreover, we develop a fully-automated TLS compiler for aggressive out-of-order spawn. With our mechanisms, a TLS CMP with four 4-issue cores achieves an average speedup of 1.30 for full SPECint 2000 applications; the corresponding speedup for in-order only spawn is 1.04. Overall, our mechanisms unlock the potential of TLS for the toughest applications.

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: Anasua Bhowmik , Manoj Franklin, A general compiler framework for speculative multithreading, Proceedings of the fourteenth annual ACM symposium on Parallel algorithms and architectures, August 10-13, 2002, Winnipeg, Manitoba, Canada [doi>10.1145/564870.564885]
• 3: M. K. Chen , K. Olukotun, Exploiting Method-Level Parallelism in Single-Threaded Java Programs, Proceedings of the 1998 International Conference on Parallel Architectures and Compilation Techniques, p.176, October 12-18, 1998
• 4: Peng-Sheng Chen , Ming-Yu Hung , Yuan-Shin Hwang , Roy Dz-Ching Ju , Jenq Kuen Lee, Compiler support for speculative multithreading architecture with probabilistic points-to analysis, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 5: Marcelo Cintra , José F. Martínez , Josep Torrellas, Architectural support for scalable speculative parallelization in shared-memory multiprocessors, Proceedings of the 27th annual international symposium on Computer architecture, p.13-24, June 2000, Vancouver, British Columbia, Canada
• 6: John G. Cleary , J. A. David McWha , Murray Pearson, Timestamp representations for virtual sequences, Proceedings of the eleventh workshop on Parallel and distributed simulation, p.98-105, June 10-13, 1997, Lockenhaus, Austria
• 7: 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
• 8: SSA for Trees - GNU Project, May 2003. http://www.gccsummit.org/2003/view_abstract.php?talk=2.
• 9: 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
• 10: Venkata Krishnan , Josep Torrellas, A Chip-Multiprocessor Architecture with Speculative Multithreading, IEEE Transactions on Computers, v.48 n.9, p.866-880, September 1999 [doi>10.1109/12.795218]
• 11: X. F. Li, Z. H. Dui, Q. Y. Zhao, and T. F. Ngai. Software Value Prediction for Speculative Parallel Threaded Computations. In Value Prediction Workshop, pages 18--25, June 2003.
• 12: R. H. Littin, J. A. D. McWha, M. W. Pearson, and J. G. Cleary. Block Based Execution and Task Level Parallelism. In Australian Computer Science Communications, pages 57--66, 1998.
• 13: 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]
• 14: 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
• 15: 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
• 16: Jose Renau , Josep Torrellas, Chip multiprocessors with speculative multithreading: design for performance and energy efficiency, University of Illinois at Urbana-Champaign, Champaign, IL, 2004
• 17: 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
• 18: 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
• 19: M. Tremblay. MAJC; Microprocessor Architecture for Java Computing. Hot Chips, August 1999.
• 20: 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]
• 21: Jenn-Yuan Tsai , Zhenzhen Jiang , Pen-Chung Yew, Compiler Techniques for the Superthreaded Architectures, International Journal of Parallel Programming, v.27 n.1, p.1-19, Feb. 1999 [doi>10.1023/A:1018730501763]
• 22: 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
• 23: Fredrik Warg , Per Stenström, Limits on Speculative Module-Level Parallelism in Imperative and Object-Oriented Programs on CMP Platforms, Proceedings of the 2001 International Conference on Parallel Architectures and Compilation Techniques, p.221-230, September 08-12, 2001
• 24: 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