MIME-Version: 1.0
Server: CERN/3.0
Date: Monday, 16-Dec-96 21:39:08 GMT
Content-Type: text/html
Content-Length: 7002
Last-Modified: Saturday, 29-Jun-96 22:41:27 GMT
Incrementalization
Incrementalization-
A General Systematic Approach to Efficiency Improvement
Objectives
- We are engaged in an ambitious effort to derive
incremental programs automatically (or semi-automatically) from
non-incremental programs written in standard programming languages.
This approach contrasts with earlier approaches that aimed to
incrementally evaluate non-incremental programs.
- In essence, every program computes by fixed-point iteration,
expressed as recursive functions or loops. This is why loop
optimizations are so important. A loop body can be regarded as a
program f parameterized by an induction variable x that
is incremented on each iteration by a change operation +.
Efficient iterative computation relies on effective use of state,
i.e., computing the result of each iteration using stored results of
previous iterations. This is why strength reduction and related
techniques are crucial for performance.
- Given a program f and an input change operation
+, a program f' that computes f(x+y) efficiently
by using the result of the previous computation of f(x) is
called an incremental version of f under +.
Sometimes, information other than the result of f(x) needs to
be maintained and used for efficient incremental computation of
f(x+y). We call a function that computes such information an
extended version of f. Thus, the goal of computing
loops efficiently corresponds to constructing an extended version of a
program f and deriving an incremental version of the extended
version under an input change operation +.
- In general, incremental computation aims to solve a problem
on a sequence of inputs that differ only slightly from one another,
making use of the previously computed output in computing a new
output, instead of computing the new output from scratch. Incremental
computation is a fundamental issue relevant throughout computer
software, e.g., optimizing compilers, transformational program
development, and interactive systems.
Results
Y. Annie Liu yanhong@cs.cornell.edu
Last updated 6/29/96