previous | contents | next

Chapter 37 A survey of problems and preliminary results concerning parallel processing and parallel processors 457

performance and fast turn around time. Surplus resources can be applied to other jobs, so that the system is potentially efficient, displaying a peak-load averaging effect and hence high utilization of hardware [Corbato and Vyssotsky, 1965]. The concept of sharing in parallel processing systems and its related cost reduction is not, however, limited to hardware. Perhaps even more significant is the common use of data-sets maintained in a system library or file, and even concurrent access during execution from a high-speed store. This may represent considerable economy in storage space and in processing time for I/O and internal memory-hierarchy transfers. But above all [Corbato and Vyssotsky, 1965] it facilitates the sharing of ideas, experience, and results and a cross fertilization among users, a prospect which from a long term point of view represents perhaps the most significant potential of large, library-oriented, multiprocessing systems. Finally, in this brief summary of the basic advantages of parallel processing systems, we refer to their intrinsic modularity, which may yield an expandable system in which the only effect of expansion on the user is improved performance.

Adequate performance of parallel processing systems is, however, predicated on an appropriately low level of overhead. Allocation, scheduling, and supervisory1 strategies, in particular, must be simplified and the related procedures minimized to comprise a small proportion of the total activity in the system. The system design must be based on performance objectives that permit a user to specify a time period and a tolerance within which he requires and expects to receive results, and the cost for which these will be obtained. In general the entire system must yield minimum throughput time for the large job, adequate response time to the terminal requests in conversational mode, guaranteed throughput time for real-time tasks, and minimum cost processing for the batch-processed small job. These needs require the development of an executive and supervisory system integrated with the hardware into a single, unified computing system. Finally, the techniques and algorithms of classical computation, of problem analysis, and of programming, must be modified and new, intrinsically parallel procedures developed if full advantage is to be gained from exploitation of these parallel systems.

Our studies to date represent but a small fraction of the ground that will have to be covered if effective parallel processing systems are to come into their own. It is, however, abundantly clear that such systems will yield their potential only if the design is approached on a broad but unified front ranging from problem analysis and usage techniques, through executive strategies and operating systems, to logic design and technology. We therefore present concepts and results from each of these areas, as obtained during our preliminary investigation into the design and use of parallel processing systems.

3. Language

3.1 Parallelism in high level languages

The analysis of high level language requirements for parallel processing has received considerable attention in the literature. We may refer in particular to the paper by Conway [1963] which discussed the concepts of Fork, Join, and Quit, and the recent review by Dennis and Van Horn [1966].

Recognizing that programming languages should possess capabilities that express the structure of the computational algorithm, Schlaeppi [19??] has proposed augmentations to PL/I-like languages that portray the macro-parallelism in numerical algorithms. These in turn have been reflected in proposals for machine-language implementation. As examples we discuss Split, Terminate, Assemble, Test and Set or Wait (interlock), Resume, Store-Test and Branch, and External Execute instructions. We describe here only the basic functional elements, from which machine instructions for actual realization will be composed as suggested by practical programming experience.

3.2 Machine level instructions for tasking

Split provides the basic task-generating capability. It indicates that in addition to continuing the execution of the present instruction string in normal fashion a new task, or set of tasks, may be initiated, execution starting at a specified address or set of addresses. Such potential tasks will be queued to await pick-up by an appropriate processing unit.

Terminate causes cessation of activity on a task. The terminating unit will, of its own volition, access an appropriate queue to obtain its next task. Alternatively, it may execute an executive allocation-task to determine which of a number of task-queues is to be accessed next according to the current urgency status of work in the system.

Assemble permits the merging of several tasks. The first (n - 1) tasks in an n-way parallel set belonging to a single job, reaching the assemble instruction terminate. The nth task, however, will proceed to execute the program string which constitutes the continuation of all n tasks.

1We differentiate intuitively between executive and supervisory activities. The former are those whose costs should be chargeable to the individual user directly, whereas the latter are absorbed in the system running costs.

previous | contents | next