SUPPORTING DYNAMIC DATA-STRUCTURES ON DISTRIBUTED-MEMORY MACHINES

Compiling for distributed-memory machines has been a very active resea rch area in recent years. Much of this work has concentrated on progra ms that use arrays as their primary data structures. To date, little w ork has been done to address the problem of supporting programs that u se pointer-based dynamic data structures. The techniques developed for supporting SPMD execution of array-based programs rely on the fact th at arrays are statically defined and directly addressable. Recursive d ata structures do not have these properties, so new techniques must be developed. In this article, we describe an execution model for suppor ting programs that use pointer-based dynamic data structures. This mod el uses a simple mechanism for migrating a thread of control based on the layout of heap-allocated data and introduces parallelism using a t echnique based on futures and lazy task creation. We intend to exploit this execution model using compiler analyses and automatic paralleliz ation techniques. We have implemented a prototype system, which we cal l Olden, that runs on the Intel iPSC/860 and the Thinking Machines CM- 5. We discuss our implementation and report on experiments with five b enchmarks.