Hierarchical fat hypercube architecture for parallel processing systems

DETAILED DESCRIPTION The present invention is directed toward a hierarchical fat hypercube topology that provides a novel and unique approach to implementing multiprocessor systems in a scalable and cost-effective manner.
According to this hierarchical topology, two or more levels of hierarchy are provided.
The first level utilizes conventional n-dimensional hypercube topologies for implementing a multi-processor infrastructure.
Each of these n-dimensional hypercubes are interconnected at a second level which can be one of p dimensions.
Note that p can, but does not have to, equal n.
Thus, according to the hierarchical fat hypercube topology, additional processing nodes can be added to the infrastructure without increasing the dimension of the infrastructure as was done with the conventional hypercubes.
The hierarchical hypercube topology can be implemented such that the bisection bandwidth scales linearly with the number of nodes in the topology.
In other words, the bisection bandwidth per node remains constant regardless of the number of nodes in the network.
Although this feature is found in the conventional basic hypercube, it is not present in many of the proposed variations thereto.
A further advantage of the invention is that by using the second level to interconnect additional n-dimensional hypercubes, significant increases in the number of processing nodes can be realized without having to increase the number of ports required on each router.
As is described below, the network can be expanded by adding additional first-level n-dimensional hypercubes to available router ports on existing metalevel nodes (metanodes) or by adding additional metanodes at the metalevel and adding n-dimensional hypercubes to these additional metanodes.
An additional advantage is that, spare router ports at the second level can remain free for future expansion of the network to include additional nodes.
Because the routers can be implemented using a fewer number of ports per node than was possible with conventional topologies, the routers are more cost effective and more efficient to implement