Efficient partitioning and scheduling of computer vision and image processing data on bus networks using divisible load analysis

Abstract

We investigate the data partitioning, distribution, and scheduling problem for minimizing the total processing time of computer vision and image processing (CVIP) data on bus networks. Using the recently evolved divisible load paradigm (DLT) [V. Bharadwaj, D. Ghose, V. Mani, T.G. Robertazzi, Scheduling divisible loads in parallel and distributed systems, IEEE Computer Society Press, Los Almitos, California, 1996] for processing loads that are computationally intensive, we design and analyze a scheduler that optimally partitions the CVIP data and assigns it to the processors in the network in such a way that the total processing time is a minimum. In addition to the transmission delay in the network, we consider all the overhead components that penalize the time performance in the problem formulation. With this formulation, we derive closed-form solutions for the optimal processing time when the CVIP data distribution follows a fixed sequence. We then derive a necessary and sufficient condition for the existence of an optimal processing time. We then prove an optimal sequence theorem that identifies a sequence that gives rise to an optimal processing time among all possible load distribution sequences, whenever such a sequence of load distribution exists. The performance of the strategy proposed is also analyzed with respect to speed-up and processor utilization or efficiency metrics. Several illustrative examples are shown for the ease of understanding.