Scheduling of low-level image & vision algorithms (SOLLIVA)

This dissertation presents analyses of scheduling computer vision tasks onto networks of heterogeneous machines. The motivation for this research is the computational need of an Automatic Visual Inspection System (AVIS) developed for the NASA Space Engineering and Research Center. The implementation and use of AVIS is limited by compute intensive image processing algorithms. In order to minimize the computation time, the data parallel nature of these algorithms is exploited. The data parallel computations are scheduled on networks of machines containing both execution and communication heterogeneity.; Defining an optimal schedule for an arbitrary algorithm on a network of heterogeneous machines is an NP complete problem. This work focuses on data parallel deterministic neighborhood computer vision algorithms. This focus enables the polynomial time definition of a schedule that minimizes the schedule length by overlapping computation and communication cycles on the network. This scheduling model allows for any speed machine to participate in the concurrent computation but makes the assumption of a master/slave control mechanism using a linear communication network. The model utilizes parameters which describe the communication overhead, communication bandwidth, and execution bandwidth of specific machines.; The analysis of this scheduling problem requires the definition of several master/slave control models. Most current scheduling and load balancing algorithms inadequately represent the communication between the master and slave machines. The work presented in this dissertation constructs models which extend static load balancing techniques to better represent the communication latencies.; The first of these models assumes homogeneous and deterministic communication rates and heterogeneous deterministic execution rates for the slave machines used in the schedule. These assumptions enable a fast algorithm to define the optimal number of slave machines to be used in a given schedule. This scheduling algorithm has complexity of O(n) which is an order of magnitude faster than recently proposed techniques. The second model relaxes the homogenous communication assumption and incorporates heterogeneous deterministic communication rates to and from the slave machines. This model extends recently proposed efforts, all of which assume homogenous (deterministic) communication rates. This model allows slave machines at remote sites to efficiently contributed to a distributed algorithm with a scheduling complexity of O(n{dollar}sp2{dollar}). The last deterministic model relaxes the master/slave control model to allow the master machine to perform a section of the distributed calculations. The theoretical results for these three deterministic models are compared with observed results.; The final model presented in this dissertation is nondeterministic. Based on sampled statistics, a composite statistical model of the schedule length is defined. This novel statistical approach is used to generate theoretical distributions of schedule length. The hypothetical behavior of these models are compared to observed schedule length for several types of computer vision algorithms.