An analysis of multiprocessing speedup with emphasis on the effect of scheduling methods

The speedup issue is reexamined for message-passing multiprocessors and computer networks in which interprocessor communication overhead is considered undesirable but significant. A unified model of speedup ] is developed for analyzing the system in terms of communication overhead, scheduling, and the application algorithm. The model can be used to assess quantitatively the impact on overall system performance of the interprocessor communication overhead and its interaction with different scheduling methods. Whereas most authors treat speedup as a measure of improved algorithms or improved systems, the presented model integrates the effects of these factors and of scheduling. Two concepts, hidden overhead and efficiency loss, are introduced to clarify the effect of the scheduling factor. The concepts are illustrated using two scheduling methods designed for use in systems with significant communication overhead