Novel neighborhood search for multiprocessor scheduling with pipelining

Abstract

This paper presents a neighborhood search algorithm for heterogeneous multiprocessor scheduling in which loop pipelining is used to exploit parallelism between iterations. The method adopts a realistic model for interprocessor communication where resource contention is taken into consideration. The schedule representation scheme is flexible so that communication scheduling can be performed in a generic manner. Base on a general time formulation of the schedule performance, the algorithm improves an initial schedule in an efficient way by successive modification to the task processor mapping and task ordering. Simulation results show that significant improvement over existing methods can be obtained. A parallel software video encoder was implemented based on the scheduling result and real time performance was achieved with pipelining of frame encoding. © 2001 Elsevier Science.