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

We investigate the data partitioning, distribution, and scheduling problem for minimizing the total processing time of computer vision and image proce ssing (CVIP) data on bus networks. Using the recently evolved divisible loa d paradigm (DLT) [V. Bharadwaj, D. Chose, V. Mani, T.G. Robertazzi, Schedul ing divisible loads in parallel and distributed systems, IEEE Computer Soci ety Press, Los Almitos, California, 1996] for processing loads that are com putationally intensive, we design and analyze a scheduler that optimally pa rtitions the CVIP data and assigns it to the processors in the network in s uch a way that the total processing time is a minimum. In addition to the t ransmission delay in the network, we consider all the overhead components t hat penalize the time performance in the problem formulation. With this for mulation, we derive closed-form solutions for the optimal processing time w hen the CVIP data distribution follows a fixed sequence. We then derive a n ecessary and sufficient condition for the existence of an optimal processin g time. We then prove an optimal sequence theorem that identifies a sequenc e that gives rise to an optimal processing time among all possible load dis tribution sequences, whenever such a sequence of load distribution exists. The performance of the strategy proposed is also analyzed with respect to s peed-up and processor utilization or efficiency metrics. Several illustrati ve examples are shown for the ease of understanding. (C) 2000 Elsevier Scie nce B.V. All rights reserved.