|
Umut Acar Toyota Technological Institute |
|
Self-Adjusting Computation 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 relatively broad range 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. ********** 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. |
|
4:15pm B17 Upson Hall Tuesday, March 24, 2009 Refreshments at 3:45pm in the Upson 4th Floor Atrium |
|
Computer Science Colloquium Spring 2009 |
|
www.cs.cornell.edu/events/colloquium |