Supporting Dynamic Data Structures on Distributed Memory Machines
Report ID: TR-447-94Author: Carlisle, Martin C. / Hendren, Laurie J. / Reppy, John H. / Rogers, Anne
Date: 1994-02-00
Pages: 33
Download Formats: |Postscript|
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.