The Bus-Connected Ringed Tree: A Versatile Interconnection Network

✍ Scribed by Omkar M. Dighe; Ramachandran Vaidyanathan; S.Q. Zheng

• Publisher: Elsevier Science
• Year: 1996
• Tongue: English
• Weight: 336 KB
• Volume: 33
• Category: Article
• ISSN: 0743-7315
• DOI: 10.1006/jpdc.1996.0037

✦ Synopsis

We consider the use of multiple-bus networks (MBNs) in a synchronous parallel processing environment. We propose a class of MBNs called bus-connected ringed trees (BRTs). A 1-dimensional BRT is shown to have an optimal processor fanout of 2 and to be capable of optimally simulating a complete binary tree and a ring. The results for the 1-dimensional BRT extend to higher dimensional BRTs. In particular, the 2-dimensional BRT is shown to have a constant processor fan-out of 4 and to be capable of efficiently simulating a complete binary tree, ring, and fixed-degree 2-dimensional structures that include the torus, mesh, and mesh of trees. The 2-dimensional BRT serves as a uniform platform on which all algorithms for the above topologies can be run efficiently.