Dissertation: Abstract

The text on this page has not been brought up to date. Links may be broken, facts may be unusually Vancouver-oriented, and addresses may be incorrect.

If you desperately need the updated information, you can write to me. Otherwise, please hang in there, and I'll get around to updating my site as soon as I have a chance.

Thanks for your interest!

For Version Stamps for Functional Arrays and Determinacy Checking: Two Applications of Ordered Lists for Advanced Programming Languages.

This thesis describes the fat-elements method for providing functional arrays and the LR-tags method for determinacy checking. Although these topics may seem very different, they are actually closely linked: Both methods provide reproducibility in advanced programming languages and share many implementation details, such as tagging data using version stamps taken from an ordered list.

The fat-elements method provides arrays as a true functional analogue of imperative arrays with the properties that functional programmers expect from data structures. It avoids many of the drawbacks of previous approaches to the problem, which typically sacrifice usability for performance or vice versa.

The fat-elements method efficiently supports array algorithms from the imperative world by providing constant-time operations for single-threaded array use. Fully persistent array accesses may also be performed in constant amortized time if the algorithm satisfies a simple requirement for uniformity of access. For algorithms that do not access the array uniformly or single-threadedly, array reads or updates take at most O(log n) amortized time for an array of size n. The method is also space efficient—creating a new array version by updating a single array element requires constant amortized space.

The LR-tags method is a technique for detecting indeterminacy in asynchronous parallel programs—such as those using nested parallelism on shared-memory MIMD machines—by checking Bernstein's conditions, which prevent determinacy races by avoiding write/write and read/write contention between parallel tasks. Enforcing such conditions at compile time is difficult for general parallel programs. Previous attempts to enforce the conditions at runtime have had non--constant-factor overheads, sometimes coupled with serial-execution requirements.

The LR-tags method can check Bernstein's (or Steele's generalized) conditions at runtime while avoiding some of the drawbacks present in previous approaches to this problem. The method has constant-factor space and time overheads when run on a uniprocessor machine and runs in parallel on multiprocessor machines, whereas the best previous solution, CILK's Nondeterminator (a constant-space and nearly constant-time approach), requires serial execution.

Both parts of the thesis include theoretical and practical material. Tests from implementations of both techniques indicate that the methods should be quite usable in practice.

Full text is available as PDF (2.6 MB).