A lightweight in-place implementation for software thread-level speculation

ABSTRACT

Thread-level speculation (TLS) is a technique that allows parts of a sequential program to be executed in parallel. TLS ensures the parallel program's behaviour remains true to the language's original sequential semantics; for example, allowing multiple iterations of a loop to run in parallel if there are no conflicts between them.

Conventional software-TLS algorithms detect conflicts dynamically. They suffer from a number of problems. TLS implementations can impose large storage overheads caused by buffering speculative work. TLS implementations can offer disappointing scalability, if threads can only commit speculative work back to the "real" heap sequentially. TLS implementations can be slow because speculative reads must consult look-aside tables to see earlier speculative writes, or because speculative operations replace normal reads and writes with expensive synchronisation primitives (e.g. CAS or memory fences).

We present a streamlined software-TLS algorithm for mostly-parallel loops that aims to avoid these problems. We allow speculative work to be performed in place, so we avoid buffering, and so that reads naturally see earlier writes. We avoid needing a serial-commit protocol. We avoid the need for CAS or memory fences in common operations. We strive to reduce the size of TLS-related conflict-detection state, and to interact well with typical data-cache implementations. We evaluate our implementation on off-the-shelf hardware using seven applications from SciMark2, BYTEmark and JOlden. We achieve an average 77% of the speed-up of manually-parallelized versions of the benchmarks for fully parallel loops. We achieve a maximum of a 5.8x speed-up on an 8-core machine.

REFERENCES

• 1: Vikram S. Adve , John Mellor-Crummey , Mark Anderson , Jhy-Chun Wang , Daniel A. Reed , Ken Kennedy, An integrated compilation and performance analysis environment for data parallel programs, Proceedings of the 1995 ACM/IEEE conference on Supercomputing (CDROM), p.50-es, December 04-08, 1995, San Diego, California, United States [doi>10.1145/224170.224340]
• 2: Luis Ceze , James Tuck , Josep Torrellas , Calin Cascaval, Bulk Disambiguation of Speculative Threads in Multiprocessors, Proceedings of the 33rd annual international symposium on Computer Architecture, p.227-238, June 17-21, 2006
• 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: Michael K. Chen , Kunle Olukotun, The Jrpm system for dynamically parallelizing Java programs, Proceedings of the 30th annual international symposium on Computer architecture, June 09-11, 2003, San Diego, California
• 5: Marcelo Cintra , Diego R. Llanos, Toward efficient and robust software speculative parallelization on multiprocessors, Proceedings of the ninth ACM SIGPLAN symposium on Principles and practice of parallel programming, June 11-13, 2003, San Diego, California, USA
• 6: Francis Dang , Hao Yu , Lawrence Rauchwerger, The R-LRPD Test: Speculative Parallelization of Partially Parallel Loops, Proceedings of the 16th International Symposium on Parallel and Distributed Processing, p.20, April 15-19, 2002
• 7: 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
• 8: Tim Harris , Mark Plesko , Avraham Shinnar , David Tarditi, Optimizing memory transactions, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 9: Intel. Intel 64 and IA-32 Architectures Software Developer's Manual, Volume 3A: System Programming Guide, chapter 7. In http://download.intel.com/design/processor/manuals/253668.pdf, Sep 2008.
• 10: Iffat H. Kazi , David J. Lilja, Coarse-Grained Thread Pipelining: A Speculative Parallel Execution Model for Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.12 n.9, p.952-966, September 2001 [doi>10.1109/71.954629]
• 11: Seon Wook Kim , Chong-liang Ooi , Rudolf Eigenmann , Babak Falsafi , T. N. Vijaykumar, Reference idempotency analysis: a framework for optimizing speculative execution, Proceedings of the eighth ACM SIGPLAN symposium on Principles and practices of parallel programming, p.2-11, June 2001, Snowbird, Utah, United States
• 12: François Masdupuy, Array abstractions using semantic analysis of trapezoid congruences, Proceedings of the 6th international conference on Supercomputing, p.226-235, July 19-24, 1992, Washington, D. C., United States [doi>10.1145/143369.143414]
• 13: C. E. Oancea and A. Mycroft. Set-Congruence Dynamic Analysis for Software TLS. In Lang. Comp. Par. Comp. (LCPC), Aug 2008.
• 14: Cosmin E. Oancea , Alan Mycroft, Software thread-level speculation: an optimistic library implementation, Proceedings of the 1st international workshop on Multicore software engineering, May 11-11, 2008, Leipzig, Germany [doi>10.1145/1370082.1370090]
• 15: C. J. F. Pickett and C. Verbrugge. Software Thread Level Speculation for the Java Language and Virtual Machine Environment. In Lang. Comp. Par. Comp. (LCPC), Oct 2005.
• 16: L. Rauchwerger, and N. M. Amato, and D. A. Padua. A Scalable Method for Run-Time Loop Parallelization. In Int. Conf. Supercomputing (ICS), Jul 1995.
• 17: Lawrence Rauchwerger , David A. Padua, The LRPD Test: Speculative Run-Time Parallelization of Loops with Privatization and Reduction Parallelization, IEEE Transactions on Parallel and Distributed Systems, v.10 n.2, p.160-180, February 1999 [doi>10.1109/71.752782]
• 18: P. Rundberg and P. Stenström. An All-Software Thread-Level Data Dependence Speculation System for Multiprocessors. The Journal of Instr.-Level Par., 1999.
• 19: Silvius Rus , Maikel Pennings , Lawrence Rauchwerger, Sensitivity analysis for automatic parallelization on multi-cores, Proceedings of the 21st annual international conference on Supercomputing, June 17-21, 2007, Seattle, Washington [doi>10.1145/1274971.1275008]
• 20: Silvius Rus , Lawrence Rauchwerger , Jay Hoeflinger, Hybrid analysis: static & dynamic memory reference analysis, International Journal of Parallel Programming, v.31 n.4, p.251-283, August 2003 [doi>10.1023/A:1024597010150]
• 21: Bratin Saha , Ali-Reza Adl-Tabatabai , Richard L. Hudson , Chi Cao Minh , Benjamin Hertzberg, McRT-STM: a high performance software transactional memory system for a multi-core runtime, 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.1123001]
• 22: Susmit Sarkar , Peter Sewell , Francesco Zappa Nardelli , Scott Owens , Tom Ridge , Thomas Braibant , Magnus O. Myreen , Jade Alglave, The semantics of x86-CC multiprocessor machine code, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
• 23: 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
• 24: 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
• 25: M. Tremblay, J. Chan, S. Chaudhry, A. W. Conigliaro, and S. S. Tse The MAJC Architecture: A Synthesis of Parallelism and Scalability. In Symp. Microarch. (MICRO), Dec 2000.
• 26: Adam Welc , Suresh Jagannathan , Antony Hosking, Safe futures for Java, Proceedings of the 20th annual ACM SIGPLAN conference on Object-oriented programming, systems, languages, and applications, October 16-20, 2005, San Diego, CA, USA
• 27: 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
• 28: 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:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Design, Performance

Keywords:
roll-back, thread-level speculation (tls)