Sebastian Burckhardt
Abstract
Parallel or incremental versions of an algorithm can significantly outperform their counterparts, but are often difficult to develop. Programming models that provide appropriate abstractions to decompose data and tasks can simplify parallelization. We show in this work that the same abstractions can enable both parallel and incremental execution. We present a novel algorithm for parallel self-adjusting computation. This algorithm extends a deterministic parallel programming model (concurrent revisions) with support for recording and repeating computations. On record, we construct a dynamic dependence graph of the parallel computation. On repeat, we reexecute only parts whose dependencies have changed.
We implement and evaluate our idea by studying five example programs, including a realistic multi-pass CSS layout algorithm. We describe programming techniques that proved particularly useful to improve the performance of self-adjustment in practice. Our final results show significant speedups on all examples (up to 37x on an 8-core machine). These speedups are well beyond what can be achieved by parallelization alone, while requiring a comparable effort by the programmer.
- M. Abadi, B. W. Lampson, and J.-J. Lévy. Analysis and caching of dependencies. In International Conference on Functional Programming (ICFP), 1996. Google Scholar
Digital Library
- U. Acar, G. Blelloch, M. Blume, R. Harper, and K. Tangwongsan. A library for self-adjusting computation. Electronic Notes in Theoretical Computer Science, 148:127--154, 2006. Google ScholarDigital Library
- U. A. Acar. Self-adjusting computation (an overview). In Workshop on Partial Evaluation and Program Manipulation (PEPM), 2009. Google ScholarDigital Library
- U. A. Acar, G. Blelloch, R. Ley-Wild, K. Tangwongsan, and D. Türkouglu. Traceable data types for self-adjusting computation. In Programming Language Design and Implementation (PLDI), 2010. Google ScholarDigital Library
- U. A. Acar, G. E. Blelloch, M. Blume, R. Harper, and K. Tangwongsan. An experimental analysis of self-adjusting computation. Transactions on Programming Languages and Systems (TOPLAS), 32:3:1--3:53, November 2009. Google ScholarDigital Library
- U. A. Acar, G. E. Blelloch, and R. Harper. Selective memoization. In Principles of Programming Languages (POPL), 2003. Google ScholarDigital Library
- U. A. Acar, A. Cotter, B. Hudson, and D. Türkouglu. Parallelism in dynamic well-spaced point sets. In Proceedings of the 23rd ACM Symposium on Parallelism in Algorithms and Architectures, 2011. Symposium on Parallelism in Algorithms and Architectures. Google ScholarDigital Library
- J. Ansel, C. Chan, Y. Wong, M. Olszewski, Q. Zhao, A. Edelman, and S. Amarasinghe. PetaBricks: A language and compiler for algorithmic choice. In Programming Language Design and Implementation (PLDI), 2009. Google ScholarDigital Library
- T. Bergan, O. Anderson, J. Devietti, L. Ceze, and D. Grossman. CoreDet: A compiler and runtime system for deterministic multithreaded execution. In Architectural Support for Programming Languages and Operating Systems (ASPLOS), 2010. Google ScholarDigital Library
- E. Berger, T. Yang, T. Liu, and G. Novark. Grace: Safe multithreaded programming for C/C+. In Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2009. Google ScholarDigital Library
- P. Bhatotia, A. Wieder, I. E. Akkus, R. Rodrigues, and U. A. Acar. Large-scale incremental data processing with change propagation. In USENIX Workshop on Hot Topics in Cloud Computing (HotCloud), 2011. Google ScholarDigital Library
- P. Bhatotia, A. Wieder, R. Rodrigues, U. A. Acar, and R. Pasquini. Incoop: Mapreduce for incremental computations. In ACM Symposium on Cloud Computing, 2011. Google ScholarDigital Library
- R. Bocchino, V. Adve, D. Dig., S. Adve, S. Heumann, R. Komuravelli, J. Overbey, P. Simmons, H. Sung, and M. Vakilian. A type and effect system for Deterministic Parallel Java. In Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2009. Google ScholarDigital Library
- S. Burckhardt, A. Baldassin, and D. Leijen. Concurrent programming with revisions and isolation types. In Object-Oriented Programming, Systems, Languages, and Applications (OOPSLA), 2010. Google ScholarDigital Library
- S. Burckhardt and D. Leijen. Semantics of concurrent revisions (full version). Technical Report MSR-TR-2010--94, Microsoft, 2010.Google Scholar
- S. Burckhardt and D. Leijen. Semantics of concurrent revisions. In European Symposium on Programming (ESOP), 2011. Google ScholarDigital Library
- M. Carlsson. Monads for incremental computing. In International Conference on Functional Programming (ICFP), 2002. Google ScholarDigital Library
- A. Demers, T. Reps, and T. Teitelbaum. Incremental evaluation for attribute grammars with application to syntax-directed editors. In Principles of Programming Languages (POPL), 1981. Google ScholarDigital Library
- J. Devietti, B. Lucia, L. Ceze, and M. Oskin. DMP: Deterministic shared-memory multiprocessing. Micro, IEEE, 30(1):40 --49, 2010. Google ScholarDigital Library
- J. Field and T. Teitelbaum. Incremental reduction in the lambda calculus. In Conference on LISP and Functional Programming, 1990. Google ScholarDigital Library
- C. Flanagan and S. Freund. Efficient and precise dynamic race detection. In Programming Language Design and Impl. (PLDI), 2009. Google ScholarDigital Library
- M. Frigo, P. Halpern, C. E. Leiserson, and S. Lewin-Berlin. Reducers and other Cilk hyperobjects. In Symposium on Parallel Algorithms and Architectures (SPAA), 2009. Google ScholarDigital Library
- P. J. Guo and D. Engler. Towards practical incremental recomputation for scientists: An implementation for the Python language. In Workshop on the Theory and Practice of Provenance (TAPP), 2010. Google ScholarDigital Library
- M. Hammer, U. A. Acar, M. Rajagopalan, and A. Ghuloum. A proposal for parallel self-adjusting computation. In Workshop on Declarative Aspects of Multicore Programming (DAMP), 2007. Google ScholarDigital Library
- A. Heydon, R. Levin, and Y. Yu. Caching function calls using precise dependencies. In Programming Language Design and Implementation (PLDI), 2000. Google ScholarDigital Library
- R. Hoover. Incremental graph evaluation. PhD thesis, Cornell University, 1987. Google ScholarDigital Library
- E. Koskinen, M. Parkinson, and M. Herlihy. Coarse-grained transactions. In Principles of Programming Languages (POPL), 2010. Google ScholarDigital Library
- M. Kulkarni, K. Pingali, B. Walter, G. Ramanarayanan, K. Bala, and L. Chew. Optimistic parallelism requires abstractions. In Programming Language Design and Implementation (PLDI), 2007. Google ScholarDigital Library
- Y. A. Liu, S. D. Stoller, and T. Teitelbaum. Static caching for incremental computation. Transactions on Programming Languages and Systems (TOPLAS), 20:546--585, 1998. Google ScholarDigital Library
- Microsoft. Parallel programming samples, .NET framework 4. http://code.msdn.microsoft.com/ParExtSamples, May 2010.Google Scholar
- G. Navarro. A guided tour to approximate string matching. ACM Computing Surveys, 33:31--88, 2001. Google ScholarDigital Library
- M. Olszewski, J. Ansel, and S. Amarasinghe. Kendo: efficient deterministic multithreading in software. SIGPLAN Notices, 44:97--108, 2009. Google ScholarDigital Library
- W. Pugh and T. Teitelbaum. Incremental computation via function caching. In Principles of Programming Languages (POPL), 1989. Google ScholarDigital Library
- G. Ramalingam and T. Reps. A categorized bibliography on incremental computation. In Principles of Programming Languages (POPL), 1993. Google ScholarDigital Library
- O. Sumer, U. A. Acar, A. Ihler, and R. Mettu. Fast parallel and adaptive updates for dual-decomposition solvers. In Conference on Artificial Intelligence (AAAI), 2011.Google Scholar
- R. S. Sundaresh and P. Hudak. Incremental computation via partial evaluation. In Principles of Programming Languages (POPL), 1991.Google Scholar
- D. M. Yellin and R. E. Strom. INC: a language for incremental computations. In Transactions on Programming Languages and Systems (TOPLAS), volume 13, pages 211 -- 236, 1991. Google ScholarDigital Library
Index Terms
- Two for the price of one: a model for parallel and incremental computation
Recommendations
Two for the price of one: a model for parallel and incremental computation
OOPSLA '11: Proceedings of the 2011 ACM international conference on Object oriented programming systems languages and applicationsParallel or incremental versions of an algorithm can significantly outperform their counterparts, but are often difficult to develop. Programming models that provide appropriate abstractions to decompose data and tasks can simplify parallelization. We ...
A Comparison of 12 Parallel FORTRAN Dialects
A simple program that approximates pi by numerical quadrature is rewritten to run on nine commercially available processors to illustrate the compilations that arise in parallel programming in FORTRAN. The machines used are the Alliant FX/8, BBN ...
Tools-supported HPF and MPI parallelization of the NAS parallel benchmarks
FRONTIERS '96: Proceedings of the 6th Symposium on the Frontiers of Massively Parallel ComputationHigh Performance Fortran (HPF) compilers and communication libraries with the standardized Message Passing Interface (MPI) are becoming widely available, easing the development of portable parallel applications. The Annai tool environment supports ...
Comments