CMU-CS-05-129Computer Science Department School of Computer Science, Carnegie Mellon University
CMU-CS-05-129
Umut A. Acar May 2005 Ph.D. Thesis
CMU-CS-05-129.ps
Keywords: Self-adjusting computation, dynamic algorithms,
dynamic data structures, kinetic data structures, dynamic dependence
graphs, memoization, change propagation, trace stability, functional
programming, lambda calculus, type systems, operational semantics,
modifiable references, selective memoization, sorting, convex hulls,
parallel tree contraction, dynamic trees, rake-and-compress trees.
From the algorithmic perspective, we describe novel data structures
for tracking the dependences in a computation and a change-propagation
algorithm for adjusting computations to changes. We show that the
overhead of our dependence tracking techniques is From the languages perspective, we describe language facilities for writing self-adjusting programs in a type-safe and correct manner. The techniques make writing self-adjusting programs nearly as easy as ordinary (non-self-adjusting) programs. A key property of the techniques is that they enable the programmer to control the cost of dependence tracking by applying it selectively. Using language techniques, we also formalize the change-propagation algorithm and prove that it is correct. We demonstrate that our techniques are efficient both in theory and in practice by considering a number of applications. Our applications include a random sampling algorithm on lists, the quick sort and merge sort algorithms, the Graham's Scan and the quick algorithm for planar convex hull, and the tree-contraction algorithm. From the theoretical perspective, we apply trace stability to our applications and show complexity bounds that are within an expected constant factor of the best bounds achieved by special-purpose algorithms. From the practical perspective, we implement a general purpose library for writing self-adjusting programs, and implement and evaluate self-adjusting versions of our applications. Our experiments show that our techniques dramatically simplify writing self-adjusting programs, and can yield very good performance even when compared to special-purpose algorithms, both in theory and in practice. 299 pages
| |

Return to:
SCS Technical Report Collection This page maintained by reports@cs.cmu.edu |