Supporting SPMD Execution for Dynamic Data Structures

Abstract:

In this paper, we address the problem of supporting SPMD execution of
programs that use recursively--defined dynamic data structures on
distributed memory machines. The techniques developed for supporting SPMD
execution of array--based programs rely on the fact that arrays are
statically defined and directly addressable. As a result, these techniques
do not apply to recursive data structures, which are neither statically
defined nor directly addressable. We propose a three--pronged approach.
First, we describe a simple mechanism for migrating a thread of control
based on the layout of heap--allocated data. Second, we explain how to
introduce parallelism into the model using a technique based on futures and
lazy task creation [MKH91]. Third, we present the compiler analyses and
parallelization techniques that are required to exploit the proposed
mechanism.

This technical paper has been published as

"Supporting SPMD Execution for Dynamic Data Structures." Anne
Rogers, John H. Reppy and Laurie J. Hendren, in
Languages and Compilers for Parallel
Computing, edited by U. Banerjee, D. Gelernter,
A. Nicolau, and D. Padua, Springer Verlag LNCS 757
(1994).