Self-adjusting computation: (an overview)

ABSTRACT

Many applications need to respond to incremental modifications to data. Being incremental, such modification often require incremental modifications to the output, making it possible to respond to them asymptotically faster than recomputing from scratch. In many cases, taking advantage of incrementality therefore dramatically improves performance, especially as the input size increases. As a frame of reference, note that in parallel computing speedups are bounded by the number of processors, often a (small) constant.

Designing and developing applications that respond to incremental modifications, however, is challenging: it often involves developing highly specific, complex algorithms. Self-adjusting computation offers a linguistic approach to this problem. In self-adjusting computation, programs respond automatically and efficiently to modifications to their data by tracking the dynamic data dependences of the computation and incrementally updating their output as needed. In this invited talk, I present an overview of self-adjusting computation and briefly discuss the progress in developing the approach and present some recent advances.

REFERENCES

• 1: MLton. http://mlton.org/.
• 2: Umut A. Acar , Guy Blelloch , Robert Harper, Self-adjusting computation, Carnegie Mellon University, Pittsburgh, PA, 2005
• 3: Umut A. Acar , Amal Ahmed , Matthias Blume, Imperative self-adjusting computation, Proceedings of the 35th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 07-12, 2008, San Francisco, California, USA
• 4: 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
• 5: 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
• 6: 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
• 7: Umut A. Acar , Guy E. Blelloch , Kanat Tangwongsan , Duru Türkoğlu, Robust Kinetic Convex Hulls in 3D, Proceedings of the 16th annual European symposium on Algorithms, September 15-17, 2008, Karlsruhe, Germany [doi>10.1007/978-3-540-87744-8_3]
• 8: Umut A. Acar , Guy E. Blelloch , Kanat Tangwongsan , Jorge L. Vittes, Kinetic algorithms via self-adjusting computation, Proceedings of the 14th conference on Annual European Symposium, p.636-647, September 11-13, 2006, Zurich, Switzerland [doi>10.1007/11841036_57]
• 9: Umut A. Acar, Guy E. Blelloch, and Jorge L. Vittes. An experimental analysis of change propagation in dynamic trees. In Workshop on Algorithm Engineering and Experimentation (ALENEX), 2005.
• 10: Umut A. Acar, Matthias Blume, and Jacob Donham. A consistent semantics of self-adjusting computation. In Proceedings of the 16th Annual European Symposium on Programming (ESOP), 2007.
• 11: Umut A. Acar, Benoit Hudson, Kanat Tangwongsan, and Duru Turkoglu. Maintaining well-spaced point sets under dynamic changes, November 2008. In preparation.
• 12: Umut A. Acar, Alexander Ihler, Ramgopal Mettu, and Ozgur Sumer. Adaptive Bayesian Inference. In Neural Information Processing Systems (NIPS), 2007.
• 13: Umut A. Acar, Alexander Ihler, Ramgopal Mettu, and Ozgur Sumer. Adaptive Inference on General Graphical Models. In Uncertainty in Artificial Intelligence (UAI), 2008.
• 14: Pankaj K. Agarwal , Leonidas J. Guibas , Herbert Edelsbrunner , Jeff Erickson , Michael Isard , Sariel Har-Peled , John Hershberger , Christian Jensen , Lydia Kavraki , Patrice Koehl , Ming Lin , Dinesh Manocha , Dimitris Metaxas , Brian Mirtich , David Mount , S. Muthukrishnan , Dinesh Pai , Elisha Sacks , Jack Snoeyink , Subhash Suri , Ouri Wolefson, Algorithmic issues in modeling motion, ACM Computing Surveys (CSUR), v.34 n.4, p.550-572, December 2002 [doi>10.1145/592642.592647]
• 15: David Eppstein, Zvi Galil, and Giuseppe F. Italiano. Dynamic graph algorithms. In Mikhail J. Atallah, editor, Algorithms and Theory of Computation Handbook, chapter 8. CRC Press, 1999.
• 16: Matthew Hammer , Umut A. Acar , Mohan Rajagopalan , Anwar Ghuloum, A proposal for parallel self-adjusting computation, Proceedings of the 2007 workshop on Declarative aspects of multicore programming, p.3-9, January 16-16, 2007, Nice, France [doi>10.1145/1248648.1248651]
• 17: Matthew A. Hammer , Umut A. Acar, Memory management for self-adjusting computation, Proceedings of the 7th international symposium on Memory management, June 07-08, 2008, Tucson, AZ, USA [doi>10.1145/1375634.1375642]
• 18: Matthew A. Hammer, Umut A. Acar, and Yan Chen. CEAL: A C-based language for self-adjusting computation. Technical report, Toyota Technological Institute, November 2008.
• 19: Benoit Hudson , Gary L. Miller, Dynamic mesh refinement, Carnegie Mellon University, Pittsburgh, PA, 2007
• 20: Ruy Ley-Wild , Umut A. Acar , Matthew Fluet, A cost semantics for self-adjusting computation, Proceedings of the 36th annual ACM SIGPLAN-SIGACT symposium on Principles of programming languages, January 21-23, 2009, Savannah, GA, USA
• 21: Ruy Ley-Wild , Matthew Fluet , Umut A. Acar, Compiling self-adjusting programs with continuations, Proceeding of the 13th ACM SIGPLAN international conference on Functional programming, September 20-28, 2008, Victoria, BC, Canada
• 22: Gary L. Miller , John H. Reif, Parallel tree contraction and its application, Proceedings of the 26th Annual Symposium on Foundations of Computer Science, p.478-489, October 21-23, 1985 [doi>10.1109/SFCS.1985.43]
• 23: George C. Necula , Scott McPeak , Shree Prakash Rahul , Westley Weimer, CIL: Intermediate Language and Tools for Analysis and Transformation of C Programs, Proceedings of the 11th International Conference on Compiler Construction, p.213-228, April 08-12, 2002
• 24: G. Ramalingam , Thomas Reps, A categorized bibliography on incremental computation, Proceedings of the 20th ACM SIGPLAN-SIGACT symposium on Principles of programming languages, p.502-510, March 1993, Charleston, South Carolina, United States [doi>10.1145/158511.158710]
• 25: Daniel D. Sleator , Robert Endre Tarjan, A data structure for dynamic trees, Journal of Computer and System Sciences, v.26 n.3, p.362-391, June 1983 [doi>10.1016/0022-0000(83)90006-5]

INDEX TERMS

Primary Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.1 Formal Definitions and Theory
          Subjects: Semantics

General Terms:
Algorithms, Design, Experimentation, Languages, Performance

Keywords:
asymptotic complexity, change propagation, compilers, continuations, dependence graphs, incremental modification, language design, performance, self-adjusting computation