Linda on distributed memory multiprocessors

The coordination language Linda (Gel85) is a convenient and powerful model for parallel and distributed computing. By permitting the expression of parallel algorithms in an architecture-independent manner, it supports truly portable programming (BCGL88). In order to be practical, Linda must be efficient. Previous work (Car87), (Lei89) demonstrated that Linda can be made efficient on shared memory multiprocessors, bus-based distributed-memory multiprocessors, and local area networks. In this dissertation, we show that Linda can be made efficient on scalable distributed-memory multiprocessors. We present a design for implementing Linda's Tuple Space on such machines, and claim that the design results in an efficient implementation. As an existence proof, we characterize the performance of the design as implemented on an Intel iPSC/2 hyper-cube. We go on to describe a number of runtime optimizations, and investigate their effect on the performance of several synthetic programs that stress communication, as well as eight non-trivial applications. Finally, we discuss the extensibility of the design to massively parallel machines.