A Caltech Library Service

Runtime systems for fine-grain multicomputers


Boden, Nanette Jackson (1993) Runtime systems for fine-grain multicomputers. Dissertation (Ph.D.), California Institute of Technology. doi:10.7907/2c3a-k589.


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 unbounded 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 written, these programs were executed on the Mosaic C under MADRE, and the program behavior was instrumented. In addition to conventional operating- and runtime-system functions such as local memory management and quiescence detection, MADRE automatically manages userprocess placement and naming. MADRE can also be configured to include capabilities for distributing resource demands across the nodes of the multicomputer. 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 finegrain multicomputers; unless messages can be exported, computations fail due to receive queue overflow when only a fraction of the multicomputer's memory resources are being used.

Item Type:Thesis (Dissertation (Ph.D.))
Subject Keywords:Computer Science
Degree Grantor:California Institute of Technology
Division:Engineering and Applied Science
Major Option:Computer Science
Thesis Availability:Public (worldwide access)
Research Advisor(s):
  • Van de Snepscheut, Jan L. A.
Thesis Committee:
  • Van de Snepscheut, Jan L. A. (chair)
  • Seitz, Charles L.
  • Van de Velde, Eric
  • Keller, Herbert Bishop
  • Taylor, Stephen
Defense Date:20 January 1993
Record Number:CaltechETD:etd-08222007-103344
Persistent URL:
Default Usage Policy:No commercial reproduction, distribution, display or performance rights in this work are provided.
ID Code:3198
Deposited By: Imported from ETD-db
Deposited On:27 Aug 2007
Last Modified:19 Apr 2021 22:32

Thesis Files

PDF (Boden_nj_1993.pdf) - Final Version
See Usage Policy.


Repository Staff Only: item control page