Concurrent image processing on hypercube multicomputers
Joydeep Ghosh · Proceedings of SPIE, the International Society for Optical Engineering/Proceedings of SPIE · 1990
This paper presents a simple and effective method for the concurrent manipulation of linearly ordered data structures on hypercube systems, and extends it to cater to multidimensional images. The method is based on the existence of a binomial search tree rooted at any arbitrary processor node of the hypercube such that (i) every edge of the tree corresponds to a direct link between a pair of hypercube nodes, and (ii) it spans any arbitrary sequence of n consecutive nodes as specified by a gray code ordering, using a fan-out of at most [log2n] and a depth of ([log2n] + 1) . The search trees spanning different processor lists are vertex disjoint and are formed dynamically and concurrently, They can be specified using information local to each node. Thus, they can be used for performing operations such as broadcast and merge simultaneously on image components with non-uniform sizes. The concurrent search reduces the complexity of several low and intermediate-level image processing algorithms to depend on the size of the largest image segment rather than the size of the entire image.