Application programs written for large-scale multicomputers with interconnection structures known to the programmer (e.g., hypercubes or meshes) use complex communication structures for connecting the applications' parallel tasks. Such structures implement a wide variety of functions, including the exchange of data or control information relevant to the task computations and/or the communications required for task synchronization, message forwarding/filtering under program control, and so on.Topologyis a programming and operating system construct that allows programmers to describe and efficiently implement such functionality as distributed objects with well-defined operational interfaces. As with abstract data types, topologies may be reused by any application desiring their functionality. However, in contrast to other research in parallel or distributed object-based operating systems, internally, a topology may be an entirely distributed implementation of the object's functionality, consisting of a communication graph and type-specific computations, which are triggered by messages traversing the graph. Sample computations may perform additions or minimizations of the values traversing a topology, thereby computing a global sum or minimum. Similarly, computations may concatenate or filter messages in order to implement program monitoring, I/O, file storage, or virtual terminal services. Topologies are implemented as an extension of the Intel iPSC hypercube's operating system kernel and have been used with several, large-scale parallel application programs.

Abstract The static distribution of work among tasks is not possible in many parallel applications. Therefore, it is essential to implement convenient and efficient abstractions for ‘work sharing’ on multicomputers. This paper compares the utility of two operating system facilities for the implementation of such ‘work sharing’: (1) a system for the migration of processes from heavily to less loaded processors and (2) a more general OS construct for the implementation of arbitrary distributed objects. Both were implemented as extensions to the Intel iPSC/1 operating system on a 32‐node hypercube. Their experimental evaluation is based on a parallel implementation of a branch‐and‐bound algorithm. Two sets of results are attained. First, the necessity of the constructs for dynamic work sharing is demonstrated for applications with dynamic data domains, such as parallel branch‐and‐bound algorithms. This is followed by measurements that demonstrate the acceptable cost of process migration for a specific parallel branch‐and‐bound algorithm. These measurements are then compared with results attained with the construct for the implementation of distributed objects. Second, when using branch‐and‐bound to solve the Travelling Salesperson Problem (TSP), evaluation of the resulting parallel TSP program shows that some analytical and simulation results attained in past, published work may not hold.

We describe our experiences with a real-time multiprocessor operating system, called GEM (Generalized Executive for Multiprocessor applications) and with an extension to GEM, called CHAOS (Concurrent Hierarchical Adaptable Object System). CHAOS offers kernel-level primitives that allow high-performance, large-scale, real-time software to be programmed as a system of interacting objects. This significantly improves modularity, reconfigurability, and maintainability.