Speculative N-Way barriers

ABSTRACT

Speculative execution is an important technique that has historically been used to extract concurrency from sequential programs. While techniques to support speculation work well when computations perform relatively simple actions (e.g., reads and writes to known locations), understanding speculation for multi-threaded programs in which threads may communicate and synchronize through multiple shared references is significantly more challenging, and is the focus of this paper.

We use as our reference point a simple higher-order concurrent language extended with an n-way barrier and a fork/join execution model. Our technique permits the expression guarded by the barrier to speculatively proceed before the barrier has been satisfied (i.e., before all threads that synchronize on that barrier have done so) and to have participating threads that would normally block on the barrier to speculatively proceed as well. Our solution formulates safety properties under which speculation is correct in a fork/join model, and per-synchronization basis.

References

1. M. Abadi, A. Birrell, T. Harris, and M. Isard. Semantics of Transactional Memory and Automatic Mutual Exclusion. In POPL, pages 63--74, 2008.
2. U. A. Acar, A. Ahmed, and M. Blume. Imperative Self-Adjusting Computation. In POPL, pages 309--322, 2008.
3. A.-R. Adl-Tabatabai, B. T. Lewis, V. Menon, B. R. Murphy, B. Saha, and T. Shpeisman. Compiler and Runtime Support for Efficient Software Transactional Memory. In PLDI, pages 26--37, 2006.
4. J.-P. Banâtre and D. L. Métayer. Programming by Multiset Transformation. Commun. ACM, 36(1), 1993.
5. N. Benton, L. Cardelli, and C. Fournet. Modern Concurrency Abstractions for C#. ACM Trans. Program. Lang. Syst., 26(5):769--804, 2004.
6. R. D. Blumofe, C. F. Joerg, B. C. Kuszmaul, C. E. Leiserson, K. H. Randall, and Y. Zhou. Cilk: An efficient multithreaded runtime system. In Journal of Parallel and Distributed Computing, pages 207--216, 1995.
7. S. Conchon and F. L. Fessant. Jocaml: Mobile Agents for Objective-Caml. In First International Symposium on Agent Systems and Applications, 1999.
8. K. Donnelly and M. Fluet. Transactional events. In ICFP, pages 124--135, 2006.
9. R. W. Floyd. Algorithm 97: Shortest path. Commun. ACM, 5(6), 1962.
10. C. Fournet, F. L. Fessant, L. Maranget, and A. Schmidt. JoCaml: A Langauge for Concurrent Distributed and Mobile Programming. In Advanced Functional Programming, pages 129--158. 2002.
11. C. Fournet and G. Gonthier. The reflexive cham and the join-calculus. In POPL, pages 372--385, 1996.
12. C. Fournet and G. Gonthier. The join calculus: a language for distributed mobile programming. In Proceedings of the Applied Semantics Summer School (APPSEM), 2000. Draft available from http://research.microsoft.com/ fournet.
13. L. Hammond, M. Willey, and K. Olukotun. Data speculation support for a chip multiprocessor. In ASPLOS, pages 58--69, 1998.
14. T. Harris and K. Fraser. Language support for lightweight transactions. In OOPSLA, pages 388--402, 2003.
15. G. S. Itzstein and M. Jasiunas. On Implementing High-Level Concurrency in Java. In Advances in Computer Systems Architecture, pages 151--165, 2003. LNCS 2823.
16. T. A. Johnson, R. Eigenmann, and T. N. Vijaykumar. Min-cut program decomposition for thread-level speculation. In PLDI, pages 59--70, 2004.
17. M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. P. Chew. Optimistic Parallelism Requires Abstractions. In PLDI, pages 211--222, 2007.
18. W. Liu, J. Tuck, L. Ceze, W. Ahn, K. Strauss, J. Renau, and J. Torrellas. POSH: A TLS Compiler that Exploits Program Structure. In PPoPP, pages 158--167, 2006.
19. J. F. Martínez and J. Torrellas. Speculative Synchronization: Applying Thread-Level Speculation to Explicitly Parallel Applications. In ASPLOS, pages 18--29, 2002.
20. K. F. Moore and D. Grossman. High-level Small-Step Operational Semantics for Transactions. In POPL, pages 51--62, 2008.
21. A. Navabi, X. Zhang, and S. Jagannathan. Quasi-static Scheduling for Safe Futures. In PPoPP, pages 23--32, 2008.
22. http://www.scala-lang.org.
23. S. Singh. Higher-Order Combinators for Join Patterns Using S™. In ACM Transact Workshop, 2006.
24. G. S. Sohi, S. E. Breach, and T. N. Vijaykumar. Multiscalar processors. In ISCA, pages 414--425, 1995.
25. J. Steffan and T. Mowry. The Potential for Using Thread-Level Data Speculation to Facilitate Automatic Parallelization, booktitle = HPCA. page 2, 1998.
26. J. G. Steffan, C. B. Colohan, A. Zhai, and T. C. Mowry. A Scalable Approach to Thread-Level Speculation. In ISCA, pages 1--12, 2000.

Index Terms

• Software and its engineering

  • Software notations and tools

    • General programming languages

      • Language features