Runtime Systems for Fine-Grain Multicomputers

Abstract

During the past decade, our research group has been engaged in experiments in the architecture and programming of multicomputers. This research has progressed steadily toward the ideal of small granularity, both of the computing nodes within a multicomputer, and of the execution units within concurrent programs. The context for the runtime-system and program-behavior experiments reported in this thesis are: (1) the reactive-process, message passing computational model, (2) C+-, a C++- based, concurrent-programming notation, and (3) the Mosaic C, an experimental, fine-grain multicomputer. We present first, a long-sought solution to the formulation of an unbonded queue of elements within the reactive-process model. This result is applied to allow messages to be received selectively using purely reactive semantics. The primary contributions of this thesis are distributed algorithms and a design method for runtime systems for fine-grain multicomputers. To evaluate the algorithms and design, a prototype runtime system called MADRE was developed, C+- programs whose behaviors are typical of a variety of applications were whritten, these programs were executed on the Mosaic C under MADRE, and the program behavior was instrumental. In addition to conventional operating and runtime-system functions such as local memory management and quiescence detection, MADRE automatically manages user-process placement and naming. MADRE can also be configured to include capabilities for distributing resource demands across the nodes of the multicomuter. Buffered messages can be exported from congested nodes so that incoming messages can continue to be received. The code of user programs can be distributed across the ensemble, and accessed automatically. Each of these capabilities depends upon the formulation of selective receive demonstrated in the solution to the unbounded queue. Our experiments evaluate various automatic process-placement strategies. We show that one algorithm, called k-biased placement, distributes loads nearly as well as random placement, while providing a tunable degree of locality between parent and child processes. Other experiments demonstrate that the message-exportation capability is crucial to fine grain multicomputers; unless messages can be exported, computations fail due to receive queue overflow when only a fraction of the multicomputer's memory resources is being used.

Files

Additional details