ABSTRACT
Deterministic-by-construction parallel programming models offer the advantages of parallel speedup while avoiding the nondeterministic, hard-to-reproduce bugs that plague fully concurrent code. A principled approach to deterministic-by-construction parallel programming with shared state is offered by LVars: shared memory locations whose semantics are defined in terms of an application-specific lattice. Writes to an LVar take the least upper bound of the old and new values with respect to the lattice, while reads from an LVar can observe only that its contents have crossed a specified threshold in the lattice. Although it guarantees determinism, this interface is quite limited.
We extend LVars in two ways. First, we add the ability to "freeze" and then read the contents of an LVar directly. Second, we add the ability to attach event handlers to an LVar, triggering a callback when the LVar's value changes. Together, handlers and freezing enable an expressive and useful style of parallel programming. We prove that in a language where communication takes place through these extended LVars, programs are at worst quasi-deterministic: on every run, they either produce the same answer or raise an error. We demonstrate the viability of our approach by implementing a library for Haskell supporting a variety of LVar-based data structures, together with a case study that illustrates the programming model and yields promising parallel speedup.
Supplemental Material
- Arvind, R. S. Nikhil, and K. K. Pingali. I-structures: data structures for parallel computing. ACM Trans. Program. Lang. Syst., 11, October 1989. Google ScholarDigital Library
- H. Attiya, R. Guerraoui, D. Hendler, P. Kuznetsov, M. M. Michael, and M. Vechev. Laws of order: expensive synchronization in concurrent algorithms cannot be eliminated. In POPL, 2011. Google ScholarDigital Library
- D. A. Bader and K. Madduri. Designing multithreaded algorithms for breadth-first search and st-connectivity on the Cray MTA-2. In ICPP, 2006. Google ScholarDigital Library
- R. L. Bocchino, Jr., V. S. Adve, S. V. Adve, and M. Snir. Parallel programming must be deterministic by default. In HotPar, 2009. Google ScholarDigital Library
- R. L. Bocchino, Jr., V. S. Adve, D. Dig, S. V. Adve, S. Heumann, R. Komuravelli, J. Overbey, P. Simmons, H. Sung, and M. Vakilian. A type and effect system for deterministic parallel Java. In OOPSLA, 2009. Google ScholarDigital Library
- R. L. Bocchino, Jr. et al. Safe nondeterminism in a deterministic-bydefault parallel language. In POPL, 2011. Google ScholarDigital Library
- Z. Budimlić, M. Burke, V. Cavé, K. Knobe, G. Lowney, R. Newton, J. Palsberg, D. Peixotto, V. Sarkar, F. Schlimbach, and S. Taşirlar. Concurrent Collections. Sci. Program., 18, August 2010. Google ScholarDigital Library
- S. Burckhardt and D. Leijen. Semantics of concurrent revisions. In ESOP, 2011. Google ScholarDigital Library
- B. L. Chamberlain, D. Callahan, and H. P. Zima. Parallel programmability and the Chapel language. International Journal of High Performance Computing Applications, 21(3), 2007. Google ScholarDigital Library
- D. Chase and Y. Lev. Dynamic circular work-stealing deque. In SPAA, 2005. Google ScholarDigital Library
- N. Conway, W. Marczak, P. Alvaro, J. M. Hellerstein, and D. Maier. Logic and lattices for distributed programming. In SOCC, 2012. Google ScholarDigital Library
- C. Earl, I. Sergey, M. Might, and D. Van Horn. Introspective pushdown analysis of higher-order programs. In ICFP, 2012. Google ScholarDigital Library
- F. Ellen, Y. Lev, V. Luchangco, and M. Moir. SNZI: Scalable NonZero Indicators. In PODC, 2007. Google ScholarDigital Library
- M. Felleisen, R. B. Findler, and M. Flatt. Semantics Engineering with PLT Redex. The MIT Press, 1st edition, 2009. Google ScholarDigital Library
- K. Fraser. Practical lock-freedom. PhD thesis, 2004.Google Scholar
- M. I. Gordon, W. Thies, M. Karczmarek, J. Lin, A. S. Meli, C. Leger, A. A. Lamb, J. Wong, H. Hoffman, D. Z. Maze, and S. Amarasinghe. A stream compiler for communication-exposed architectures. In ASPLOS, 2002. Google ScholarDigital Library
- M. Herlihy and N. Shavit. The Art of Multiprocessor Programming. Morgan Kaufmann, 2008. Google ScholarDigital Library
- G. Kahn. The semantics of a simple language for parallel programming. In J. L. Rosenfeld, editor, Information processing. North Holland, Amsterdam, Aug 1974.Google Scholar
- L. Kuper and R. R. Newton. LVars: lattice-based data structures for deterministic parallelism. In FHPC, 2013. Google ScholarDigital Library
- L. Kuper, A. Turon, N. R. Krishnaswami, and R. R. Newton. Freeze after writing: Quasi-deterministic parallel programming with LVars. Technical Report TR710, Indiana University, November 2013. URL http://www.cs.indiana.edu/cgi-bin/techreports/TRNNN.cgi?trnum=TR710.Google Scholar
- E. Lee and D. Messerschmitt. Synchronous data flow. Proceedings of the IEEE, 75(9):1235--1245, 1987.Google ScholarCross Ref
- D. Leijen, M. Fahndrich, and S. Burckhardt. Prettier concurrency: purely functional concurrent revisions. In Haskell, 2011. Google ScholarDigital Library
- S. Marlow, P. Maier, H.-W. Loidl, M. K. Aswad, and P. Trinder. Seq no more: better strategies for parallel Haskell. In Haskell, 2010. Google ScholarDigital Library
- S. Marlow, R. Newton, and S. Peyton Jones. Amonad for deterministic parallelism. In Haskell, 2011. Google ScholarDigital Library
- M. M. Michael, M. T. Vechev, and V. A. Saraswat. Idempotent work stealing. In PPoPP, 2009. Google ScholarDigital Library
- M. Might. k-CFA: Determining types and/or controlflow in languages like Python, Java and Scheme. http://matt.might.net/articles/implementation-of-kcfa-and-0cfa/.Google Scholar
- R. S. Nikhil. Id language reference manual, 1991.Google Scholar
- S. L. Peyton Jones, R. Leshchinskiy, G. Keller, and M. M. T. Chakravarty. Harnessing the multicores: Nested data parallelism in Haskell. In FSTTCS, 2008. Google ScholarDigital Library
- A. Prokopec, H. Miller, T. Schlatter, P. Haller, and M. Odersky. Flow-Pools: a lock-free deterministic concurrent dataflow abstraction. In LCPC, 2012.Google Scholar
- J. H. Reppy. Concurrent Programming in ML. Cambridge University Press, Cambridge, England, 1999. Google ScholarDigital Library
- M. Shapiro, N. Preguiça, C. Baquero, and M. Zawirski. Conflict-free replicated data types. In SSS, 2011. Google ScholarDigital Library
- L. G. Tesler and H. J. Enea. A language design for concurrent processes. In AFIPS, 1968 (Spring). Google ScholarDigital Library
- K. B. Wheeler, R. C. Murphy, and D. Thain. Qthreads: An API for programming with millions of lightweight threads, 2008.Google Scholar
Index Terms
- Freeze after writing: quasi-deterministic parallel programming with LVars
Recommendations
Taming the parallel effect zoo: extensible deterministic parallelism with LVish
PLDI '14: Proceedings of the 35th ACM SIGPLAN Conference on Programming Language Design and ImplementationA fundamental challenge of parallel programming is to ensure that the observable outcome of a program remains deterministic in spite of parallel execution. Language-level enforcement of determinism is possible, but existing deterministic-by-construction ...
Freeze after writing: quasi-deterministic parallel programming with LVars
POPL '14Deterministic-by-construction parallel programming models offer the advantages of parallel speedup while avoiding the nondeterministic, hard-to-reproduce bugs that plague fully concurrent code. A principled approach to deterministic-by-construction ...
LVars: lattice-based data structures for deterministic parallelism
FHPC '13: Proceedings of the 2nd ACM SIGPLAN workshop on Functional high-performance computingPrograms written using a deterministic-by-construction model of parallel computation are guaranteed to always produce the same observable results, offering programmers freedom from subtle, hard-to-reproduce nondeterministic bugs that are the scourge of ...
Comments