''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
Abstract:
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.