Campus Event Calendar
Event Entry
What and Who
Programmable Self-Adjusting Computation
Ruy Ley-Wild
Carnegie Mellon University
SWS Colloquium
Ruy Ley-Wild studied math and computing at Carnegie Mellon University, and
then continued to pursue a Ph.D. in computer science.
SWS, RG1
Expert Audience
English
Note: We use this to send email in the morning.
Date, Time and Location
Tuesday, 27 April 2010
14:00
60 Minutes
E1 5
5th floor
Saarbrücken
Abstract
In the self-adjusting computation model, programs can respond
automatically and efficiently to input changes by tracking the dynamic
data dependencies of the computation and incrementally updating the output
as needed. After a run from scratch, the input can be changed and the
output can be updated via change-propagation, a mechanism for re-executing
the portions of the computation affected by the changes while reusing the
unaffected parts. Previous research shows that self-adjusting computation
can be effective at achieving near-optimal update bounds for various
applications. We address the question of how to write and reason about
self-adjusting programs.
We propose a language-based technique for annotating ordinary programs and
compiling them into equivalent self-adjusting versions. We also provide a
cost semantics and a concept of trace distance that enables reasoning
about the effectiveness of self-adjusting computation at the source level.
To facilitate asymptotic analysis, we propose techniques for composing and
generalizing concrete distances via trace contexts (traces with holes).
The translation preserves the extensional semantics of the source
programs, the intensional cost of from-scratch runs, and ensures that
change-propagation between two evaluations takes time bounded by their
relative distance.
Contact
Brigitta Hansen
0681 - 9325691
--email hidden
Video Broadcast
Yes
Kaiserslautern
G26
206
passcode not visible
logged in users only
Carina Schmitt, 04/26/2010 14:22
Brigitta Hansen, 04/20/2010 13:38 -- Created document.
Brigitta Hansen, 04/20/2010 13:38 -- Created document.