Constant Time Graph Algorithms on the Reconfigurable Multiple Bus Machine

✍ Scribed by Jerry L. Trahan; Ramachandran Vaidyanathan; Chittur P. Subbaraman

• Publisher: Elsevier Science
• Year: 1997
• Tongue: English
• Weight: 413 KB
• Volume: 46
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1997.1385

✦ Synopsis

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 ) increase in the number of processors and buses, where > 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.