© 1979 by British Computer Society
Allocation algorithms for dynamically microprogrammable multiprocessor systems
1 Lawrence Livermore Laboratory, Livermore, California, USA, 2 Mathematics Department, University of Denver, University Park, Denver, Colorado, USA
Due to advances in integrated circuit technology, multiprocessor systems with more than two Central Processing Units are becoming economically feasible. For this reason, the study of such systems with the aim of developing more efficient hardware and software structures is gaining interest. One type of multiprocessor structure which has recently received some attention is the dynamically microprogrammable multiprocessor system. This paper investigates the problems of efficiently allocating the processors of such a system among the system's workload.
A collection of algorithms and scheduling procedures is developed which may be used for processor allocation in dynamically microprogrammable multiprocessor systems with an arbitrary number of processors. Proofs that these algorithms produce configurations which optimise certain measures are given. The algorithms are practical in the sense that the computation required increases linearly with respect to the number of processors to be allocated. Finally, a simulation study has shown that in many circumstances the use of these algorithms can be expected to yield a significant improvement in system performance over an allocation scheme previously proposed.
Received August 1977.
* Lawrence Livermore Laboratory, Livermore, California 94550, USA
Mathematics Department, University of Denver, University Park, Denver, Colorado 80208, USA