(2) It balances the loads by identifying groups of nodes ('flows') that can be moved to adjacent processors without creating new pieces. Our initial results are promising, giving us good load balancing and a reasonably low number of inter-processor edges."

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

Programming nonshared memory systems is more difficult than programming shared memory systems, since there is no support for shared data structures. Current programming languages for distributed memory architectures force the user to decompose all data structures into separate pieces, with each owned by one of the processors in the machine, and with all communication explicitly specified by low-level message-passing primitives. This paper presents a new programming environment for distributed memory architectures, providing a global name space and allowing direct access to remote parts of data values. We describe the analysis and program transformations required to implement this environment, and present the efficiency of the resulting code on the NCUBE/7 and IPSC/2 hypercubes. (kr).