A loop structured technique for the control of a multiprocessing system

Abstract

A method for routing control information to and from the processors in a multiprocessing system is presented and analyzed. The technique requires the construction of two sets of data registers connected in the form of closed loops. Every processor is interfaced to one register on each loop through which data is propagated in a parallel manner and at a constant rate (as controlled by a system clock). A system controller introduces data words called "packets" onto the "input" loop for distribution to available processors. The packets contain information sufficient for the initiation of concurrent tasks. The processors input these packets, execute tasks as directed, and generate similar packets which signify task completion. The latter packets are deposited on the "output" loop by the processors for return to the system controller. The analysis reveals that under appropriate restrictions (namely, a large supply of tasks, a fixed task execution time, and the efficient handling of packets by the system controller), the scheme makes effective use of processing resources. The throughput of tasks increases linearly with the addition of processors until the number of processors, n, is equal to the ratio of task execution time to system clock time, p, after which it remains fixed as more processors are added. The overhead required to route control information through the system decreases as 1/n until n equals p, whereupon it increases linearly for larger n. A simulator, used to verify the analysis and extend same to more general systems, is also described. It shows that as restrictions are lifted, the loop structured technique continues to be a viable scheme for the control of a multiprocessor, especially in applications in which its simplicity and modularity are advantageous.