Document Open Access Logo

The Eureka Programming Model for Speculative Task Parallelism

Authors Shams Imam, Vivek Sarkar

PDF
Thumbnail PDF

File

LIPIcs.ECOOP.2015.421.pdf
  • Filesize: 0.7 MB
  • 24 pages

Document Identifiers

Author Details

Shams Imam
Vivek Sarkar

Cite AsGet BibTex

Shams Imam and Vivek Sarkar. The Eureka Programming Model for Speculative Task Parallelism. In 29th European Conference on Object-Oriented Programming (ECOOP 2015). Leibniz International Proceedings in Informatics (LIPIcs), Volume 37, pp. 421-444, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2015)
https://doi.org/10.4230/LIPIcs.ECOOP.2015.421

Abstract

In this paper, we describe the Eureka Programming Model (EuPM) that simplifies the expression of speculative parallel tasks, and is especially well suited for parallel search and optimization applications. The focus of this work is to provide a clean semantics for, and efficiently support, such "eureka-style" computations (EuSCs) in general structured task parallel programming models. In EuSCs, a eureka event is a point in a program that announces that a result has been found. A eureka triggered by a speculative task can cause a group of related speculative tasks to become redundant, and enable them to be terminated at well-defined program points. Our approach provides a bound on the additional work done in redundant speculative tasks after such a eureka event occurs. We identify various patterns that are supported by our eureka construct, which include search, optimization, convergence, and soft real-time deadlines. These different patterns of computations can also be safely combined or nested in the EuPM, along with regular task-parallel constructs, thereby enabling high degrees of composability and reusability. As demonstrated by our implementation, the EuPM can also be implemented efficiently. We use a cooperative runtime that uses delimited continuations to manage the termination of redundant tasks and their synchronization at join points. In contrast to current approaches, EuPM obviates the need for cumbersome manual refactoring by the programmer that may (for example) require the insertion of if checks and early return statements in every method in the call chain. Experimental results show that solutions using the EuPM simplify programmability, achieve performance comparable to hand-coded speculative task-based solutions and out-perform non-speculative task-based solutions.
Keywords
  • Async-Finish Model
  • Delimited Continuations
  • Eureka Model
  • Parallel Programming
  • Speculative Parallelism
  • Task Cancellation
  • Task Termination

Metrics

  • Access Statistics
  • Total Accesses (updated on a weekly basis)
    0
    PDF Downloads
    0
    Metadata Views

Supplementary Materials

References

  1. S. F. Altschul, W. Gish, W. Miller, E. W. Myers, and D. J. Lipman. Basic Local Alignment Search Tool. Journal of molecular biology, 215(3):403-410, October 1990. Google Scholar
  2. Walter Binder. Design and Implementation of the J-SEAL2 Mobile Agent Kernel. In SAINT'01, pages 35-, 2001. Google Scholar
  3. Bradford Nichols and Dick Buttlar and Jacqueline Proulx Farrell. Pthreads Programming: Chapter 4 - Managing Pthreads. O'Reilly & Associates, Inc., Sebastopol, CA, USA, 1996. Google Scholar
  4. F. Warren Burton. Speculative computation, parallelism, and functional programming. IEEE Trans. Computers, 34(12):1190-1193, 1985. Google Scholar
  5. Giorgio Buttazzo, Giuseppe Lipari, Luca Abeni, and Marco Caccamo. Soft Real-Time Systems: Predictability vs. Efficiency. Plenum Publishing Co., 2005. Google Scholar
  6. Philippe Charles and et al. X10: An Object-Oriented Approach to Non-uniform Cluster Computing. SIGPLAN Not., 40:519-538, October 2005. Google Scholar
  7. Liming Chen and A. Avizienis. N-Version Programming: A Fault-Tolerance Approach to Reliability of Software Operation. In FTCS-25, Jun 1995. Google Scholar
  8. Jens Clausen. Branch and Bound Algorithms - Principles and Examples. Parallel Computing in Optimization, pages 239-267, 1997. Google Scholar
  9. Grzegorz Czajkowski and Laurent Daynés. Multitasking Without Comprimise: A Virtual Machine Evolution. In OOPSLA'01, pages 125-138, 2001. Google Scholar
  10. Olivier Danvy and Andrzej Filinski. Abstracting Control. In LFP'90, pages 151-160, 1990. Google Scholar
  11. Iulian Drago and et al. Continuations in the Java Virtual Machine. In ICOOOLPS'2007, 2007. Google Scholar
  12. Alejandro Duran, Xavier Teruel, Roger Ferrer, Xavier Martorell, and Eduard Ayguade. Barcelona OpenMP Tasks Suite. In ICPP'09, 2009. Google Scholar
  13. Marc Feeley. Polling Efficiently on Stock Hardware. In FPCA'93, pages 179-187. ACM, 1993. Google Scholar
  14. Mattias Felleisen. The Theory and Practice of First-Class Prompts. In POPL'88, 1988. Google Scholar
  15. Matteo Frigo, Charles E. Leiserson, and Keith H. Randall. The Implementation of the Cilk-5 Multithreaded Language. In PLDI'98, pages 212-223, 1998. Google Scholar
  16. J. Goldenberg and G. Levine. Ada’s Abort Statement: License to Kill. Ada Letters, IX(6):97-103, September 1989. Google Scholar
  17. Anne Greenbaum. Iterative Methods for Solving Linear Systems. Society for Industrial and Applied Mathematics, Philadelphia, PA, USA, 1997. Google Scholar
  18. Yi Guo, Rajkishore Barik, Raghavan Raman, and Vivek Sarkar. Work-First and Help-First Scheduling Policies for Async-Finish Task Parallelism. In IPDPS'09, pages 1-12, 2009. Google Scholar
  19. Maurice H. Halstead. Elements of Software Science. Elsevier Science Inc., New York, NY, USA, 1977. Google Scholar
  20. Christopher T. Haynes and Daniel P. Friedman. Engines Build Process Abstractions. In LFP'84, 1984. Google Scholar
  21. Ilya Grigorik. Untangling Evented Code with Ruby Fibers. https://www.igvita.com/2010/03/22/untangling-evented-code-with-ruby-fibers/, 2010.
  22. Shams Imam and Vivek Sarkar. Cooperative Scheduling of Parallel Tasks with General Synchronization Patterns. In ECOOP'14, 2014. Google Scholar
  23. Shams Imam and Vivek Sarkar. Habanero-Java Library: a Java 8 Framework for Multicore Programming. In PPPJ'14. ACM, 2014. Google Scholar
  24. Alexey Kolesnichenko, Sebastian Nanz, and Bertrand Meyer. How to Cancel a Task. In Proceedings of MUSEPAT'13, pages 61-72. Springer, 2013. Google Scholar
  25. Daan Leijen, Wolfram Schulte, and Sebastian Burckhardt. The Design of a Task Parallel Library. In OOPSLA'09, pages 227-242, 2009. Google Scholar
  26. Wei-Ming Lin, Wei Xie, and Bo Yang. Performance Analysis for Parallel Solutions to Generic Search Problems. In SAC'97, pages 422-430, 1997. Google Scholar
  27. Andrey Marochko. Exception Handling and Cancellation in TBB - Part II, May 2008. Google Scholar
  28. T. J. McCabe. A Complexity Measure. IEEE Trans. on Soft. Engineering, 2(4), July 1976. Google Scholar
  29. Oliver Kowalke. Introduction (Boost Coroutines). http://www.boost.org/doc/libs/1_53_0/libs/coroutine/doc/html/coroutine/intro.html, 2009.
  30. Stephen Olivier, Jun Huan, Jinze Liu, Jan Prins, James Dinan, P. Sadayappan, and Chau-Wen Tseng. UTS: An Unbalanced Tree Search Benchmark. In LCPC'06, pages 235-250, 2007. Google Scholar
  31. OpenMP API, Version 4.0. http://www.openmp.org/mp-documents/OpenMP4.0.0.pdf, July 2013.
  32. Randy B. Osborne. Speculative computation in multilisp. In LFP'90, pages 198-208, 1990. Google Scholar
  33. W. R. Pearson and D. J. Lipman. Improved tools for biological sequence comparison. National Academy of Sciences of the United States of America, 85(8):2444-2448, April 1988. Google Scholar
  34. Tim Peierls, Brian Goetz, Joshua Bloch, Joseph Bowbeer, Doug Lea, and David Holmes. Java Concurrency in Practice. Addison-Wesley Professional, 2005. Google Scholar
  35. Ruben Perez and Gregory Malecha. Speculative Parallelism in Cilk++, 2012. Google Scholar
  36. Prakash Prabhu, Ganesan Ramalingam, and Kapil Vaswani. Safe Programmable Speculative Parallelism. In PLDI'10, pages 50-61, 2010. Google Scholar
  37. Python Software Foundation. concurrent.futures — Launching parallel tasks, August 2014. Google Scholar
  38. Raghavan Raman, Jisheng Zhao, Vivek Sarkar, Martin Vechev, and Eran Yahav. Efficient Data Race Detection for Async-Finish Parallelism. In RV'10, pages 368-383, 2010. Google Scholar
  39. Tiark Rompf, Ingo Maier, and Martin Odersky. Implementing First-class Polymorphic Delimited Continuations by a Type-directed Selective CPS-transform. In ICFP'09, 2009. Google Scholar
  40. Jun Shirako, David M. Peixotto, Vivek Sarkar, and William N. Scherer. Phasers: a Unified Deadlock-Free Construct for Collective and Point-to-Point Synchronization. In ICS'08, pages 277-288, 2008. Google Scholar
  41. Sriram Srinivasan and Alan Mycroft. Kilim: Isolation-Typed Actors for Java. In ECOOP'08, 2008. Google Scholar
  42. Lukas Stadler, Christian Wimmer, Thomas Würthinger, Hanspeter Mössenböck, and John Rose. Lazy Continuations for Java Virtual Machines. In PPPJ'09, 2009. Google Scholar
  43. Oussama Tahan, Mats Brorsson, and Mohamed Shawky. Introducing Task Cancellation to OpenMP. In 8th Int'l Workshop on OpenMP, IWOMP 2012, pages 73-87, June 2012. Google Scholar
  44. The Jikes RVM Project. Threading and Yieldpoints. http://jikesrvm.org/Threading+and+Yieldpoints, 2007.
  45. The Open MPI Project. MPI_Abort. https://www.open-mpi.org/doc/v1.8/man3/MPI_Abort.3.php, 2014.
  46. Richard Wiener. Branch and Bound Implementations for the Traveling Salesperson Problem. Journal of Object Technology, 2(2), 2003. Google Scholar
  47. Wolfram. Solve Optimization Problems with Speculative Parallelism, November 2008. Google Scholar
Questions / Remarks / Feedback
X

Feedback for Dagstuhl Publishing


Thanks for your feedback!

Feedback submitted

Could not send message

Please try again later or send an E-mail
© 2023-2024 Schloss Dagstuhl – LZI GmbH Imprint Privacy Contact