<%@ page language="java" contentType="text/html" %> <%-- Include common initialisation code --%> <%@ include file="/arch/common.jsp" %> <%-- The current tab --%> <% String currentTab = "Research"; %> <%-- Content of navigation pane --%> <%@ include file="nav.jsp" %> <% showCurrentLink=true; %> <%-- Current navigation location --%> <% String currentNav = "Reports and Theses"; %> <%-- Include the code for the document header --%> <%@ include file="/arch/header.jsp" %>

Research Report CS-RR-214

<%-- Include the code for the lines and navigation --%> <%@ include file="/arch/middle.jsp" %>

Y. Zheng, Darren J. Kerbyson and Graham R. Nudd, Efficient Load Balancing Techniques for Image Analysis on an M-SIMD Machine (June 1, 1992).

Abstract

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.

<%@ include file="hardcopy.html" %> <%-- Include the code for the document footer --%> <%@ include file="/arch/footer.jsp" %>