Bounds on multiprocessing anomalies and related packing algorithms

Abstract

It has been known for some time that certain rather general models of multiprocessing systems frequently exhibit behavior which could be termed "anomalous," e.g., an increase in the number of processors of the system can cause an increase in the time used to complete a job. In order to fully realize the potential benefits afforded by parallel processing, it becomes important to understand the underlying causes of this behavior and the extent to which the resulting system performance may be degraded.