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).