Load balancing and task decomposition techniques for parallel implementation of integrated vision systems algorithms

摘要

Integrated vision systems employ a sequence of image understanding algorithms in which the output of an algorithm is the input of the next algorithm in the sequence. Algorithms that constitute an integrated vision systems exhibit different characteristics, and therefore, require different data decomposition techniques and efficient load balancing techniques for parallel implementation. However, since input data of a task is produced as output of the previous task, this information can be exploited to perform knowledge based data decomposition and load balancing. This paper presents several techniques to perform static and dynamic load balancing schemes for integrated vision systems. These techniques are novel in the sense that they capture the computational requirements of a task by examining the data when it is produced. Furthermore, they can be applied to many integrated vision systems because many algorithms in different systems are either same or have similar computational characteristics. These techniques are evaluated by applying them to the algorithms in a motion estimation system. It is shown that the performance gains when these techniques are used are significant and the overhead of using these techniques is minimal. The performance is evaluated by implementing the algorithms using the presented techniques on a hypercube multiprocessor system.