Efficient Load Balancing Techniques for Image Analysis on an M-SIMD Machine
Yunhui Zheng, Darren J. Kerbyson, G.R. Nudd · Warwick Research Archive Portal (University of Warwick) · 1992
The computational requirements for the real time processing of image sequences is sufficiently high that some form of parallel hardware is essential. In the analysis of a sequence of images the areas of interest are moving objects which usually occupy only small distinct areas within the full field of view. A single instruction multiple data (SIMD) machine has considerable advantages for these types of operations where there is a high requirement for data parallel processing. However, on conventional SIMD machines, only the processors to which the moving objects are mapped onto have significant work-load. The remaining processors are idle during most of the processing period resulting in significant load imbalance and poor utilisation. We describe here load balancing techniques for a Multiple-SIMD (M-SIMD) machine, consisting of a number of small conventional SIMD arrays (patches) connected together to form a larger M-SIMD array. Each SIMD patch can perform independent computations. Using the M-SIMD configuration idle processors can be re-allocated to process active regions of other images from an image sequence or from multiple sensors, significantly increasing the throughput and flexibility of the system. A TvotingU algorithm is presented for the calculation of the minimum number of patches the object is mapped onto along with a heuristic (near optimum) patch allocation process.