The hierarchical cliques interconnection network

The fully connected network possesses extremely good topological, fault-tolerant, and embedding properties. However, due to its high degree, the fully connected network has not been an attractive candidate for building parallel computers. On the other hand, tree-based networks are popular as parallel computer networks, even though they suffer from poor fault-tolerance and embedding properties. The hierarchical cliques interconnection network described in this paper incorporates positive features of the fully connected network and the tree network. In other words, the hierarchical cliques possess such desirable properties as low diameter, low degree, self routing, versatile embedding, good fault-tolerance and strong resilience. Hierarchical cliques can efficiently embed most important networks and possess a scalable, modular structure. Further, by combining hierarchical cliques with fat trees congestion in the upper levels can be alleviated. (C) 2003 Elsevier Inc. All rights reserved.