Computing on reconfigurable buses

The authors demonstrate novel uses for buses in a multiprocessor reconfigurable architecture both as topological descriptors and as powerful computational devices. This paradigm results in fast algorithms to solve a number of problems in computer arithmetic, image processing, and computer vision. An O(1) time algorithm is proposed to compute the sum and difference of two N-bit numbers using N processors only. Two fast algorithms are presented for image segmentation and parallel visibility. The algorithm for image segmentation uses a novel technique involving building a bus around each region of interest in the image. Once such a bus is established it can be successfully used as a topological descriptor for the corresponding region. With a binary image pretiled in the natural way on a reconfigurable mesh of size N×N the segmentation algorithm runs in O(log N) time, improving by a factor of O(log N) over the state of the art. A very simple algorithm is introduced to solve the parallel visibility problem on an image of size N×N. The algorithm runs in O(log N) time and is conceptually very simple