Hierarchical Interconnection Networks Based on (3, 3)-Graphs for Massively Parallel Processors

Gene Eu JAN  Yuan-Shin HWANG  

Publication
IEICE TRANSACTIONS on Information and Systems   Vol.E87-D   No.7   pp.1649-1656
Publication Date: 2004/07/01
Online ISSN: 
DOI: 
Print ISSN: 0916-8532
Type of Manuscript: Special Section PAPER (Special Section on Hardware/Software Support for High Performance Scientific and Engineering Computing)
Category: Networking and System Architectures
Keyword: 
broadcasting algorithms,  interconnection networks,  routing algorithms,  (3, 3)-graph,  folded (3, 3)-networks,  root-folded (3, 3)-networks,  recursively expanded (3, 3)-networks,  flooded (3, 3)-networks,  

Full Text: PDF>>
Buy this Article




Summary: 
This paper proposes several novel hierarchical interconnection networks based on the (3, 3)-graphs, namely folded (3, 3)-networks, root-folded (3, 3)-networks, recursively expanded (3, 3)-networks, and flooded (3, 3)-networks. Just as the hypercubes, CCC, Peterson-based networks, and Heawood-based networks, these hierarchical networks have the following nice properties: regular topology, high scalability, and small diameters. Due to these important properties, these hierarchical networks seem to have the potential as alternatives for the future interconnection structures of multicomputer systems, especially massively parallel processors (MPPs). Furthermore, this paper will present the routing and broadcasting algorithms for these proposed networks to demonstrate that these algorithms are as elegant as the algorithms for hypercubes, CCC, and Petersen- or Heawood-based networks.