Hierarchical star: a new two level interconnection network

We propose a new two level interconnection network topology, hierarchical star networks, HSn, that uses the star graphs as building blocks. Two level networks have been previously proposed that use hypercube and its variants as building blocks; it has been shown that these two level networks are superior to the networks, that are used as building blocks, in terms of various performance metrics including diameter, cost, fault tolerance, fault diameter etc. Our results show that the proposed family of hierarchical star networks perform very competitively in comparison to star graphs; in addition, the proposed network outperforms all of the two level hierarchical networks proposed earlier that uses hypercubes (or its variations) as building blocks. Thus, our results further reinforce the notion that the star graphs are strong competitors of hypercubes for large multiprocessor design. We also investigate various topological properties of the network including embedding, mapping of parallel algorithms, fault tolerance and broadcasting algorithms.