Software Caching and Computation Migration in Olden

Software caching and computation migration are mechanisms that satisfy remote references by either bringing a copy of the data to the computation or moving the computation to the data. We evaluate these mechanisms usingOlden, a system that, with minimal programmer annotations, provides parallelism for C programs that use recursively defined structures, such as trees, lists, and DAGs. We demonstrate that providing both software caching and computation migration can improve the performance of these programs, and provide a compile-time heuristic that selects between them for each pointer dereference. We have implemented the heuristic in Olden on the Thinking Machines CM-5. We describe our implementation and report on experiments with eleven benchmarks.