Partitioning and scheduling for parallel image processing operations

Abstract

Many computer vision and image processing (CVIP) operations can be represented as a sequence of tasks with nested loops, specified by the visual programming language Khoros. This paper addresses the automatic partitioning and scheduling of such operations on distributed memory multiprocessors. The major difficulties in determining the optimal image data distribution for each task are that the number of processors available and the size of the input image may vary at the run time, and the cost of some image processing operations may be data-dependent. This paper proposes a compile-time processor assignment and data partitioning scheme that optimizes the average run-time performance of task chains with nested loops by considering the data redistribution overheads and possible run-time parameter variations. This paper presents the theoretical analysis and experimental results on a Meiko CS-2 distributed memory machine.