''Constant Time Graph Algorithms on the Reconfigurable Multiple Bus Machine''

Jerry L. Trahan

Ramachandran Vaidyanathan

Chittur P. Subbaraman

Journal of Parallel and Distributed Computing, vol. 46, no. 1, pp. 1-14, October 1997


The Reconfigurable Multiple Bus Machine (RMBM) is a model of parallel computation based on reconfigurable buses. Unlike other reconfigurable bus-based models such as the Reconfigurable Mesh (R-Mesh), the RMBM separates the functions of processors and switches. In this paper, we present constant time RMBM algorithms for a number of fundamental graph problems. These algorithms are more efficient, in terms of processors, than corresponding R-Mesh algorithms. Also presented is a novel range reduction technique for a constant time simulation of each step of a Priority CRCW RMBM on a Common or Collision CRCW RMBM. This simulation incurs only a factor of O(P^ epsilon) increase in the number of processors and buses, where epsilon > 0 is any constant and P is the number of processors in the simulated Priority CRCW RMBM. This method may be of independent interest. The algorithms presented in this paper demonstrate the potential for fast and processor-efficient computation available in the ability of a reconfigurable bus-based model to separate the functions of processors and switches.

This work was supported in part by the Louisiana Board of Regents through the Louisiana Education Quality Support Fund under contract number LEQSF(1994-96)-RD-A-07 and the National Science Foundation under grant number CCR-9503882.