A Caltech Library Service

Runtime Systems for Fine-Grain Multicomputers

Boden, Nanette Jackson (1993) Runtime Systems for Fine-Grain Multicomputers. Computer Science Technical Reports, California Institute of Technology , Pasadena, CA. (Unpublished)

Postscript - Submitted Version
See Usage Policy.

[img] PDF - Submitted Version
See Usage Policy.


Use this Persistent URL to link to this item:


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.

Item Type:Report or Paper (Technical Report)
Additional Information:© 1993 California Institute of Technology.
Group:Computer Science Technical Reports
Series Name:Computer Science Technical Reports
Record Number:CaltechCSTR:1993.cs-tr-92-10
Persistent URL:
Usage Policy:You are granted permission for individual, educational, research and non-commercial reproduction, distribution, display and performance of this work in any format.
ID Code:26896
Deposited By: Imported from CaltechCSTR
Deposited On:17 Jul 2001
Last Modified:03 Oct 2019 03:18

Repository Staff Only: item control page