Coping with sparse inputs on enhanced meshes-semigroup computation with COMMON CRCW buses

Consider an √n×√n processor mesh where, in addition to the local links, each row and column is enhanced by a COMMON CRCW bus. Assume that each processor stores an element of a commutative semigroup, and only k<n entries (in arbitrary positions) are nonzero. We wish to compute the sum of all entries. For this problem we easily obtain a lower time bound of Ω(k^¼) if k⩽n ^2/3. Our main result is an O(k^¼log² k) time algorithm. It requires a composition of several data movement and compaction techniques which seem to be of general use for solving problems with sparse inputs scattered on the mesh, as it is typical e.g. for primal sketches in digital image processing