A fast algorithm for computing a histogram on reconfigurable mesh

Abstract

The reconfigurable mesh captures salient features from a variety of sources, including the content addressable array parallel processor, the CHiP, the polymorphic-torus network and the bus automaton. It consists of an array of processors interconnected by a reconfigurable bus system. The bus system can be used to dynamically obtain various interconnection patterns between the processors. In this paper, we present a fast algorithm for computing the histogram of an N/spl times/N image with h grey levels in O(min{/spl radic/h+log*(N/h),N}) time on an N/spl times/N reconfigurable mesh assuming each PE has a constant amount of local memory. This algorithm runs on the PARBUS and MRN/LRN models. In addition, histogram modification can be performed in O(/spl radic/h) time on the same model. A variant of out algorithm runs in O(min{/spl radic/h+log log(N/h),N}) time on an N/spl times/N RMESH in which each PE has constant storage. This result improves the known time and memory bounds for histogramming on the RMESH model.< <ETX xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">&gt;</ETX>