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   Info

Expert Audience

English

60 Minutes

Saarbrücken

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
practice.

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

0631-9303-9602

--email hidden

Yes

Kaiserslautern

G26

204/206

passcode not visible

logged in users only