Guided scheduling schemes for image understanding tasks for shared and distributed memory multiprocessors

This paper presents guided scheduling schemes for image understanding tasks on distributed and shared memory multiprocessors. The techniques are specifically suitable for medium to coarse-grain parallelism for a wide range of image understanding tasks and are largely architecture independent. The principle behind the schemes is to measure the load distribution for a task early when its input data is produced and to use this measure to schedule tasks onto parallel processors. The authors present the performance of these schemes on a distributed as well as a shared memory machine for a motion estimation system involving zero-crossing, stereo match and time match. The results show that the performance gains over simple scheduling are manifold and the overhead is minimal