easily determined prior to execution; heterogeneous environments, in which parallel computers are embedded into networks, with variable and unpredictable latencies; and the integration of parallel computers into client-server applications. Multithreading has proven useful for overlapping computation and communication or I/O [7,22], for load balancing [14], and for implementing process abstractions in parallel languages [10,12,26,29,35,45].
A difficult issue that must be addressed if multithreading is to be used successfully in distributed-memory environments is the integration of threads and communication. In single-threaded send/receive communication models, a send operation in one process is matched by a receive in another, and serves both to transfer data and to enable execution in the other process. What should happen in a multithreaded environment, where many threads may be executing in a remote address space? Should a message be directed to a thread, or should threads and communication operations be decoupled? Should the code executed in response to an incoming message be specified by the sender or the receiver of the message? In this paper, we propose answers to these and other related questions. We advocate an approach in which global pointers are used to represent communication structures and remote service requests are used to effect data transfer and remote execution. We explain how these two mechanisms interact with each other and with threads, and how they can be used to implement a wide variety of parallel program structures.
Our proposed global pointer and remote service request mechanisms have been incorporated into a multithreaded communication library called Nexus [27], which we and others have used to build a variety of higher-level communication libraries [32,28,18] and to implement several parallel languages [10,41,26]. We use a Nexus implementation to perform detailed performance studies of our proposed communication mechanisms on several parallel platforms. The results of these studies provide insights into the costs associated with their implementation in different environments.
In brief, the principal contributions of this paper are threefold:
- The design of a simple set of mechanisms for constructing multithreaded computations on distributed-memory computers.