Static Global Scheduling for Optimal Computer Vision and ImageProcessing Operations on Distributed-Memory Multiprocessor

In this paper, we develop a static global scheduling scheme for mappingcomputer vision and image processing (CVIP) operations on distributed-memorymultiprocessors. Unlike most current parallel image processing research whichfocuses on parallelizing individual processing algorithms on a particularparallel architecture, our scheduler is for optimizing processor assignment anddata partition for an entire image processing pipeline.The scheduler operates on task graphs specified by conventional visuallanguages such as Khoros and Explorer. A task graph is assumed to be a linearchain of operations with any number of nested loops. The task chain is firstdecomposed into simpler subchains; each a linear sequence of tasks withoutloops. The communication and computation costs of the component tasks in thesubchains are determined by a taxonomy of CVIP operations. Data redistributionoverheads in between tasks can also be tabulated in advance for many populardata partitioning schemes. The scheduler then employs a shortest pathalgorithm to optimize the parallel time, taking into consideration possiblevariation in the task and resource parameters (such as the image size andnumber of processors used), and both the intra-operation and theinter-operation computation and communication times. In this paper, we presentthe scheduling scheme, and provide analyses and experimental results to verifyour approach.