A proposal for parallel self-adjusting computation

ABSTRACT

We present an overview of our ongoing work on parallelizing self-adjusting-computation techniques. In self-adjusting computation, programs can respond to changes to their data (e.g., inputs, outcomes of comparisons) automatically by running a change-propagation algorithm. This ability is important in applications where inputs change slowly over time. All previously proposed self-adjusting computation techniques assume a sequential execution model. We describe techniques for writing parallel self-adjusting programs and a change propagation algorithm that can update computations in parallel. We describe a prototype implementation and present preliminary experimental results.

REFERENCES

• 1: Umut A. Acar , Guy Blelloch , Robert Harper, Self-adjusting computation, Carnegie Mellon University, Pittsburgh, PA, 2005
• 2: Umut A. Acar , Guy E. Blelloch , Matthias Blume , Kanat Tangwongsan, An experimental analysis of self-adjusting computation, Proceedings of the 2006 ACM SIGPLAN conference on Programming language design and implementation, June 11-14, 2006, Ottawa, Ontario, Canada
• 3: Umut A. Acar , Guy E. Blelloch , Robert Harper, Adaptive functional programming, Proceedings of the 29th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.247-259, January 16-18, 2002, Portland, Oregon
• 4: Umut A. Acar , Guy E. Blelloch , Robert Harper , Jorge L. Vittes , Shan Leung Maverick Woo, Dynamizing static algorithms, with applications to dynamic trees and history independence, Proceedings of the fifteenth annual ACM-SIAM symposium on Discrete algorithms, January 11-14, 2004, New Orleans, Louisiana
• 5: Umut A. Acar, Guy E. Blelloch, Kanat Tangwongsan, and Jorge L. Vittes. Kinetic algorithms via self-adjusting computation. Technical Report CMU-CS-06-115, Department of Computer Science, Carnegie Mellon University, March 2006.
• 6: Michael A. Bender , Jeremy T. Fineman , Seth Gilbert , Charles E. Leiserson, On-the-fly maintenance of series-parallel relationships in fork-join multithreaded programs, Proceedings of the sixteenth annual ACM symposium on Parallelism in algorithms and architectures, June 27-30, 2004, Barcelona, Spain [doi>10.1145/1007912.1007933]
• 7: Guy E. Blelloch, Vector models for data-parallel computing, MIT Press, Cambridge, MA, 1990
• 8: Guy Blelloch , John Greiner, Parallelism in sequential functional languages, Proceedings of the seventh international conference on Functional programming languages and computer architecture, p.226-237, June 26-28, 1995, La Jolla, California, United States [doi>10.1145/224164.224210]
• 9: Richard Cole , Ramesh Hariharan, Dynamic LCA Queries on Trees, SIAM Journal on Computing, v.34 n.4, p.894-923, 2005 [doi>10.1137/S0097539700370539]
• 10: Karl Crary , David Walker , Greg Morrisett, Typed memory management in a calculus of capabilities, Proceedings of the 26th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.262-275, January 20-22, 1999, San Antonio, Texas, United States [doi>10.1145/292540.292564]
• 11: P. Dietz , D. Sleator, Two algorithms for maintaining order in a list, Proceedings of the nineteenth annual ACM conference on Theory of computing, p.365-372, January 1987, New York, New York, United States [doi>10.1145/28395.28434]
• 12: Greg Morrisett, Amal Ahmed, and Matthew Fluet. L³: A linear language with locations. In TLCA'04: Proceedings of the Seventh International Conference on Typed Lambda Calculi and Applications, pages 293--307. Springer-Verlag, April 2005.
• 13: Raimund Seidel and Cecilia R. Aragon. Randomized search trees. Algorithmica, 16(4-5):464--497, 1996.
• 14: David Walker , J. Gregory Morrisett, Alias Types for Recursive Data Structures, Selected papers from the Third International Workshop on Types in Compilation, p.177-206, September 21, 2000

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.0 General

Additional Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Algorithms, Languages, Performance

Keywords:
change propagation, dynamic dependency graphs, fork-join programs, parallel change propagation, parallelism, self-adjusting computation, series-parallel programs