ON THE DESIGN OF DISTRIBUTED-MEMORY SISAL

The design of task management and distribution, virtual shared address ing, and multithreading in a distributed memory implementation of the functional programming language Sisal is described. Flat task distribu tion, where independent tasks are distributed to slave processes by a single master process, and multilevel task distribution. Where tasks a re distributed to slave processes in parallel by a number of sub-maste r processes are studied. The trade-offs for these two distribution met hods are measured. A flexible loop distribution scheme that allows loo p distribution to be tied to data distribution is described and the ef fectiveness of this approach is studied. The virtual shared addressing (VISA) system that provides a shared memory abstraction for distribut ed memory machines is described. Several block cyclic data structure a llocation schemes are studied for one-dimensional arrays, and a variet y of distribution functions for two-dimensional arrays and their effec tiveness in reducing remote references are presented. An optimization that eliminates the need for translating VISA addresses that result in local references, and is introduced it is shown that this is extremel y effective in reducing the execution time of programs that exhibit a high degree of locality. Distributing one-dimensional arrays and tying the loop distribution to the data distribution is effective, but mult i-dimensional array distribution currently causes too much message pas sing overhead. Finally, the effectiveness of multithreading in hiding latency is studied. Machine-independent multithreading design is evalu ated and it is shown that, in the presence of very few remote referenc es, multithreading does not improve efficiency. However, in programs w ith an abundance of remote reference multithreading does pay off. The runtime system is currently implemented on the nCUBE/2 multiprocessor, but has been carefully designed to be portable to other distributed m emory architectures.