Reconfigurable mesh algorithms for summing up binary values and its applications

The authors present an asymptotically efficient parallel algorithm for summing up n binary values on reconfigurable meshes. They show that, given n binary values on an n^1/2×n^1/2 reconfigurable mesh with each processor containing one value initially, the summation of the n binary values can be performed in O(log log n) time. Several applications of the algorithm are presented. It is shown that summing up n b-bit numbers can be performed in O(b log log n) time on an n ^1/2×n^1/2 reconfigurable mesh. Next, the histogram computation, of an n×n image can be completed in O(L× log log n) time on an n×n reconfigurable mesh, where L is the number of gray-level values. A parallel algorithm for computing the area and perimeter of image components in an n×n image is developed on an n× n reconfigurable mesh. The resulting time complexity is O (C log log n) time, where C is the number of image components. The implementation of enumeration sort on an n×n^1/2×n^1/2 reconfigurable mesh is shown. O(log log n) time is required for the sorting algorithm