484 EVOLUTION OF COMPUTER BUILDING BLOCKS
tours that satisfies all the flight legs (one and only one crew makes a flight leg). We are looking for the solution with the lowest cost.
As in the previous applications, the master processor initializes the computation, creates the array according to user's specification, and puts enough initial possible search-path solutions in a global stack from which all the processors pick their work. We arbitrarily choose to put more than 10 X P path solutions into the stack where P equals the number of processors so the work is more evenly distributed between the processors, and all are occupied for a large percentage of the time.
To enhance pruning in the search, a global variable contains the cost of the best solution found so far by any of the processors, and all compare their current cost value to it and begin to backtrack in the search when that global cost is lower.
ALGOL 68 System
A semantically rich subset of the programming language ALGOL 68 was implemented on Cm* [Hibbard, et al., 1978]. In order to take advantage of the parallel architecture of Cm*, the language has been extended by including several methods of specifying concurrent execution and synchronization of subtasks.
The run-time system measured runs upon a small, special purpose kernel which provides basic support for interrupt and I/O handling, segment allocation and swapping, bootstrapping, and the collection of performance statistics. To facilitate locality of memory references, the run-time system is loaded into the local memory of each processor.
Modifications are being studied to provide automatic decomposition of tasks into small-grain subtasks. These modifications comprise a software implementation of multiple parallel-instruction pipelines, in which the instructions are the primitive actions of the ALGOL 68 run-time system, e.g., floating-point operations, array indexing and other vector operations, and assignments of large values. These actions are executed by slave processors on behalf of the master processors which are placing the actions in the pipelines.
The Cm* project has greatly benefited from interaction with other research projects and individuals at the Computer Science Department at CMU; experiences gained from the C.mmp project [Harbison and Wulf, 1977] have been particularly useful. Among those who have made direct contributions to the design and implementation of Cm* are Andy Bechtolsheim, Paolo Coraluppi, Kwok-Woon Lai, Pradeep Reddy, and Daniel Siewiorek.
. KI10-based DECsystem-10.
Bottom, left to right:
. KL10-based DECSYSTEM-20.