Supporting Dynamic Data Structures on Distributed Memory Machines

Abstract:

Compiling for distributed memory machines has been a very active
research area in recent years. Much of this work has concentrated on
programs that use arrays as their primary data structures. To date,
little work has been done to address the problem of supporting
programs that use dynamic data structures. The techniques developed
for supporting SPMD execution of array-based programs rely on the fact
that arrays are statically defined and directly addressable. These
techniques do not apply to recursive data structures, which are
neither statically defined nor directly addressable. In this paper,
we describe a three part approach to supporting programs that use
dynamic data structures. First, we use a simple mechanism for
migrating a thread of control based on the layout of heap-allocated
data. Second, we introduce parallelism into the model using a
technique based on futures and lazy task creation. Third, we exploit
this execution model using compiler analyses and parallelization
techniques. We have implemented a prototype system, which we call
Olden, that runs on the Intel iPSC/860 and the Thinking Machines
CM5. We discuss our implementation and report on experiments with
four benchmarks.

This technical paper has been published as

Supporting Dynamic Data Structures on Distributed Memory
Machines. Laurie J. Hendren, John H. Reppy, Martin
C. Carlisle and Anne Rogers,
ACM Transactions
on Programming Languages and Systems
7(2), March 1995.