Supporting dynamic data structures on distributed-memory machines

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 pointer-based dyn...

Full description

Saved in:
Bibliographic Details
Published in:ACM transactions on programming languages and systems 1995-03, Vol.17 (2), p.233-263
Main Authors: Rogers, Anne, Carlisle, Martin C., Reppy, John H., Hendren, Laurie J.
Format: Article
Language:English
Subjects:
Applied sciences
Compilers
Computer science
control theory
systems
Computing methodologies
Contextual software domains
Data types and structures
Dynamic compilers
Exact sciences and technology
General programming languages
Language features
Language types
Memory management
Operating systems
Parallel computing methodologies
Parallel programming languages
Programming languages
Runtime environments
Software
Software and its engineering
Software engineering
Software notations and tools
Software organization and properties
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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 pointer-based 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. Recursive data structures do not have these properties, so new techniques must be developed. In this article, we describe an execution model for supporting programs that use pointer-based dynamic data structures. This model uses a simple mechanism for migrating a thread of control based on the layout of heap-allocated data and introduces parallelism using a technique based on futures and lazy task creation. We intend to exploit this execution model using compiler analyses and automatic parallelization techniques. We have implemented a prototype system, which we call Olden, that runs on the Intel iPSC/860 and the Thinking Machines CM-5. We discuss our implementation and report on experiments with five benchmarks.
ISSN:0164-0925
1558-4593
DOI:10.1145/201059.201065