Compiler and hardware support for reducing the synchronization of speculative threads

ABSTRACT

Thread-level speculation (TLS) allows us to automatically parallelize general-purpose programs by supporting parallel execution of threads that might not actually be independent. In this article, we focus on one important limitation of program performance under TLS, which stalls as a result of synchronizing and forwarding scalar values between speculative threads that would otherwise cause frequent data dependences and, hence, failed speculation. Using SPECint benchmarks that have been automatically transformed by our compiler to exploit TLS, we present, evaluate in detail, and compare both compiler and hardware techniques for improving the communication of scalar values. We find that through our dataflow algorithms for three increasingly aggressive instruction scheduling techniques, the compiler can drastically reduce the critical forwarding path introduced by the synchronization and forwarding of scalar values. We also show that hardware techniques for reducing synchronization can be complementary to compiler scheduling, but that the additional performance benefits are minimal and are generally not worth the cost.

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: AMD Corporation. 2005. Leading the industry: Multi-core technology & dual-core processors from AMD. http://multicore.amd.com/en/Technology/.
• 3: Glenn Ammons , James R. Larus, Improving data-flow analysis with path profiles, Proceedings of the ACM SIGPLAN 1998 conference on Programming language design and implementation, p.72-84, June 17-19, 1998, Montreal, Quebec, Canada
• 4: William Blume , Ramon Doallo , Rudolf Eigenmann , John Grout , Jay Hoeflinger , Thomas Lawrence , Jaejin Lee , David Padua , Yunheung Paek , Bill Pottenger , Lawrence Rauchwerger , Peng Tu, Parallel Programming with Polaris, Computer, v.29 n.12, p.78-82, December 1996 [doi>10.1109/2.546612]
• 5: Chang, P. P., Warter, N. J., Mahlke, S. A., Chen, W. Y., and Hwu, W. W. 1991. Three superblock scheduling models for superscalar and superpipelined processors. Tech. Rept. CRHC-91-29, Center for Reliable and High-Performance Computing, University of Illinois.
• 6: 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
• 7: 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
• 8: Christopher B. Colohan , Anastassia Ailamaki , J. Gregory Steffan , Todd C. Mowry, Optimistic intra-transaction parallelism on chip multiprocessors, Proceedings of the 31st international conference on Very large data bases, August 30-September 02, 2005, Trondheim, Norway
• 9: Colohan, C. B., Ailamaki, A., Steffan, J. G., and Mowry, T. C. 2006. Hardware support for large speculative threads. In 33rd Annual International Symposium on Computer Architecture (ISCA '06).
• 10: Cytron, R. 1986. Doacross: Beyond vectorization for multiprocessors. In International Conference on Parallel Processing.
• 11: 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
• 12: Brian Fields , Shai Rubin , Rastislav Bodík, Focusing processor policies via critical-path prediction, Proceedings of the 28th annual international symposium on Computer architecture, p.74-85, June 30-July 04, 2001, Göteborg, Sweden
• 13: J. A. Fisher, Trace Scheduling: A Technique for Global Microcode Compaction, IEEE Transactions on Computers, v.30 n.7, p.478-490, July 1981 [doi>10.1109/TC.1981.1675827]
• 14: 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
• 15: Gabbay, F. and Mendelson, A. 1996. Speculative execution based on value prediction. Tech. Rept. EE Department TR #1080, Technion--Israel Institute of Technology.
• 16: David M. Gallagher , William Y. Chen , Scott A. Mahlke , John C. Gyllenhaal , Wen-mei W. Hwu, Dynamic memory disambiguation using the memory conflict buffer, Proceedings of the sixth international conference on Architectural support for programming languages and operating systems, p.183-193, October 05-07, 1994, San Jose, California, United States
• 17: S. Gopal , T. Vijaykumar , J. Smith , G. Sohi, Speculative Versioning Cache, Proceedings of the 4th International Symposium on High-Performance Computer Architecture, p.195, January 31-February 04, 1998
• 18: 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
• 19: 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
• 20: C.-W. Tseng , S. Hiranandani , K. Kennedy, Preliminary experiences with the Fortran D compiler, Proceedings of the 1993 ACM/IEEE conference on Supercomputing, p.338-350, December 1993, Portland, Oregon, United States [doi>10.1145/169627.169747]
• 21: IBM Corporation. 2007. IBM unleashes world's fastest chip in powerful new computer. http://www-03.ibm.com/press/us/en/pressrelease/21580.wss.
• 22: Intel Corporation. 2005. Intel's Dual-Core Processor for Desktop PCs. http://www.intel.com/personal/desktopcomputer/dual_core/index.htm.
• 23: 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]
• 24: Jens Knoop , Oliver Rüthing , Bernhard Steffen, Lazy code motion, Proceedings of the ACM SIGPLAN 1992 conference on Programming language design and implementation, p.224-234, June 15-19, 1992, San Francisco, California, United States
• 25: 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
• 26: 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
• 27: 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]
• 28: Pedro Marcuello , Jordi Tubella , Antonio González, Value prediction for speculative multithreaded architectures, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.230-236, November 16-18, 1999, Haifa, Israel
• 29: Pedro Marcuello , Jordi Tubella , Antonio González, Value prediction for speculative multithreaded architectures, Proceedings of the 32nd annual ACM/IEEE international symposium on Microarchitecture, p.230-236, November 16-18, 1999, Haifa, Israel
• 30: Andreas Moshovos , Scott E. Breach , T. N. Vijaykumar , Gurindar S. Sohi, Dynamic speculation and synchronization of data dependences, Proceedings of the 24th annual international symposium on Computer architecture, p.181-193, June 01-04, 1997, Denver, Colorado, United States
• 31: A. Nicolau, Run-Time Disambiguation: Coping with Statically Unpredictable Dependencies, IEEE Transactions on Computers, v.38 n.5, p.663-678, May 1989 [doi>10.1109/12.24269]
• 32: 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
• 33: D. A. Padua , D. J. Kuck , D. H. Lawrie, High-Speed Multiprocessors and Compilation Techniques, IEEE Transactions on Computers, v.29 n.9, p.763-776, September 1980 [doi>10.1109/TC.1980.1675676]
• 34: Manohar K. Prabhu , Kunle Olukotun, Using thread-level speculation to simplify manual parallelization, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 35: Manohar K. Prabhu , Kunle Olukotun, Exposing speculative thread parallelism in SPEC2000, Proceedings of the tenth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 15-17, 2005, Chicago, IL, USA [doi>10.1145/1065944.1065964]
• 36: Eric Rotenberg , Quinn Jacobson , Yiannakis Sazeides , Jim Smith, Trace processors, Proceedings of the 30th annual ACM/IEEE international symposium on Microarchitecture, p.138-148, December 01-03, 1997, Research Triangle Park, North Carolina, United States
• 37: 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
• 38: 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
• 39: 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
• 40: J. Gregory Steffan , Christopher B. Colohan , Antonia Zhai , Todd C. Mowry, Improving Value Communication for Thread-Level Speculation, Proceedings of the 8th International Symposium on High-Performance Computer Architecture, p.65, February 02-06, 2002
• 41: J. Gregory Steffan , Christopher Colohan , Antonia Zhai , Todd C. Mowry, The STAMPede approach to thread-level speculation, ACM Transactions on Computer Systems (TOCS), v.23 n.3, p.253-300, August 2005 [doi>10.1145/1082469.1082471]
• 42: Sun Corporation. 2005. Throughput computing—Niagara. http://www.sun.com/processors/throughput/.
• 43: 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]
• 44: T. N. Vijaykumar , Gurindar S. Sohi, Compiling for the multiscalar architecture, The University of Wisconsin - Madison, 1998
• 45: 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
• 46: Robert P. Wilson , Robert S. French , Christopher S. Wilson , Saman P. Amarasinghe , Jennifer M. Anderson , Steve W. K. Tjiang , Shih-Wei Liao , Chau-Wen Tseng , Mary W. Hall , Monica S. Lam , John L. Hennessy, SUIF: an infrastructure for research on parallelizing and optimizing compilers, ACM SIGPLAN Notices, v.29 n.12, p.31-37, Dec. 1994 [doi>10.1145/193209.193217]
• 47: Kenneth C. Yeager, The MIPS R10000 Superscalar Microprocessor, IEEE Micro, v.16 n.2, p.28-40, April 1996 [doi>10.1109/40.491460]
• 48: Antonia Zhai , Todd C. Mowry, Compiler optimization of value communication for thread-level speculation, Carnegie Mellon University, Pittsburgh, PA, 2005
• 49: Zhai, A., Colohan, C. B., Steffan, J. G., and Mowry, T. C. 2002. Compiler optimizations to accelerate scalar value communication between speculative threads. Tech. Rept. CMU-CS-02-162, School of Computer Science, Carnegie Mellon University. August.
• 50: 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
• 51: Craig Buchanan Zilles , Gurindar S. Sohi, Master/slave speculative parallelization and approximate code, The University of Wisconsin - Madison, 2002
• 52: Craig Zilles , Gurindar Sohi, Master/slave speculative parallelization, Proceedings of the 35th annual ACM/IEEE international symposium on Microarchitecture, November 18-22, 2002, Istanbul, Turkey

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)

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

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

General Terms:
Design, Experimentation, Performance

Keywords:
Thread-level speculation, automatic parallelization, chip-multiprocessing, instruction scheduling