Supporting dynamic data structures on distributed-memory machines
Supporting dynamic data structures on distributed-memory machines
复制标题
DOI：
10.1145/201059.201065
复制
发表时间：
1995-03
期刊：
影响因子：
--
通讯作者：
Anne Rogers;M. Carlisle;John H. Reppy;L. Hendren
中科院分区：
文献类型：
--
作者：
Anne Rogers;M. Carlisle;John H. Reppy;L. Hendren
近年来，编译分布式内存机器一直是一个非常活跃的研究领域。这项工作的大部分集中在使用阵列作为其主要数据结构的程序上。迄今为止，几乎没有完成支持使用基于指针的动态数据结构的支持程序的问题。为支持基于数组的程序的SPMD执行而开发的技术取决于数组在静态定义和直接寻址的事实。递归数据结构没有这些属性，因此必须开发新技术。在本文中，我们描述了一个用于支持基于指针的动态数据结构的程序的执行模型。该模型使用一种简单的机制来基于堆积数据的布局来迁移控制线，并使用基于期货和懒惰任务创建的技术引入并行性。我们打算使用编译器分析和自动并行化技术利用此执行模型。我们已经实施了一个原型系统，该原型系统称为Olden，该系统在Intel IPSC/860和Thinking Machines CM-5上运行。我们讨论了我们的实施和有关具有五个基准测试的实验的报告。
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.