Campus Event Calendar

Event Entry

What and Who

Self - Ajusting Computation

Umut A. Acar
Toyota Technological Institute at Chicago
SWS Colloquium

Umut Acar is an Assistant Professor at Toyota Technological Institute.
He received his Ph.D. from Carnegie Mellon University (2005), his
M.A. from University of Texas at Austin (1999), and his B.S. from
Bilkent University, Turkey (1997). His research interests include
language design and implementation, particularly for dynamic systems
that interact with changing data from various sources such as users
and the physical environment.
AG 1, AG 3, AG 4, AG 5, SWS, RG1, MMCI  
Expert Audience

Date, Time and Location

Thursday, 16 April 2009
60 Minutes
E1 4


Many application domains require computations to interact with data
sets that change slowly or incrementally over time. For example,
software systems that interact with the physically changing world,
e.g., databases, graphical systems, robotic software systems,
program-development environments, scientific-computing applications,
must respond efficiently and correctly to changes as they occur in the
world. Since incremental modifications to data are often small, they
can be processed asymptotically faster than re-computing from scratch,
often generating orders of magnitude speedups in practice. Realizing
this potential using traditional techniques, however, often requires
complex algorithmic and software design and implementation, ultimately
limiting the range of problems that can effectively be addressed in

In this talk, I present an overview of advances on self-adjusting
computation: an approach to developing software systems that interact
with changing data. I start by presenting the principle ideas behind a
mechanism for propagating a change through a computation, and then
describe the design of programming-language constructs for enabling
computations to respond automatically and efficiently to modifications
to their data. I show that these language constructs are realistic by
describing how to extend existing languages with them and how to
compile the extended languages into provably efficient executables,
whose performance properties can be analyzed via cost semantics. To
evaluate the effectiveness of the approach, I consider a number of
benchmarks as well as more sophisticated applications from diverse
areas such as computational geometry, scientific computing, machine
learning, and computational biology. Our results show that
self-adjusting computation can be broadly effective in achieving
efficient implementations, solving open problems, and pointing to new
research directions. In practice, our measurements show that
self-adjusting programs often respond to incremental modifications by
a linear factor faster than recomputing from scratch, resulting in
orders of magnitude speedups.


Bettina Bennett
--email hidden

Video Broadcast

passcode not visible
logged in users only

Bettina Peden-Bennett, 04/08/2009 12:01 -- Created document.