A BRICS Mini-Course
June 28 and 29, 1999
Lectures by
Y. Annie Liu, liu@cs.indiana.edu
Computer Science Department, Indiana University, Bloomington, Indiana 47405
Incremental computation takes advantage of repeated computations on inputs that differ slightly from one another, computing each new output incrementally by making use of the previous output rather than from scratch. This course describes a general systematic approach to efficiency improvement based on incrementalization.
Given a program f and an operation oplus, incrementalization yields an incremental program that computes f(xoplus y) efficiently by using the result of f(x), the intermediate results computed in computing f(x), and auxiliary information about f(x) that can be inexpensively maintained. It unifies existing approaches to incremental computation and is generally applicable; it exploits many existing program analysis and transformation techniques and can be systematically applied.
Since every non-trivial computation proceeds by iteration or recursion, incrementalization may be used for achieving efficient computation in general, by computing loops and recursions incrementally using appropriate incremental programs. Incrementalizing aggregate array computations over loops yields new powerful optimizations that are fully automatable; incrementalizing recursive equations allows dynamic programming programs to be automatically derived. These optimizations yield drastic performance improvements.
This method had been applied to problems in interactive systems, optimizing compilers, transformational program development, etc. Examples include problems in list processing, graph algorithms, VLSI design, and image processing, which were previously solved in ad hoc and often error-prone ways. The design and implementation of a prototype system, CACHET, for deriving incremental programs is also described.
Annie Liu is an assistant professor in the Computer Science Department at Indiana University. Her primary research interests are programming languages, compilers, and software systems. She is particularly interested in general and systematic approaches to improving the efficiency of computations.
Liu received a PhD in computer science from Cornell University in 1996. Liu is a member of IFIP WG2.1. She has served on the program committees of several international conferences, and she co-chairs the ACM SIGPLAN 1999 Workshop on Languages, Compilers, and Tools for Embedded Systems.