June 1996
Abstract The goal of the {\em Olden\/} project is to build a system that provides parallelism for general-purpose C programs with minimal programmer annotations. We focus on programs using dynamic structures such as trees, lists, and DAGs. We describe a programming and execution model for supporting programs that use pointer-based dynamic data structures. The major differences between our model and the standard sequential model are that the programmer explicitly chooses a particular strategy to map the dynamic data structures over a distributed heap, and annotates work that can be done in parallel using futures. Remote data access is handled automatically using a combination of software caching and computation migration. We provide a compile-time heuristic that selects between them for each pointer dereference based on programmer hints regarding the data layout. Also, we provide a new local-knowledge coherence mechanism for the cache that outperforms traditional invalidation methods on our benchmarks. The Olden profiler allows the programmer to verify the data layout hints and to determine which operations in the program are expensive. We have implemented a prototype of Olden on the Thinking Machines CM-5. We describe our implementation and report on experiments with eleven benchmarks.
PhD Thesis, Princeton University. This file is available in compressed postscript.