ALLEVIATING THE INCREMENTAL GROWTH PROBLEM OF THE HYPERCUBE INTERCONNECTION
NETWORK FOR MASSIVELY PARALLEL COMPUTERS
Sotirios G. Ziavras
Several interconnection networks have been employed in the design of distributed-memory
parallel computers. The (direct binary) hypercube has been one of the most
widely used interconnection networks because it provides small diameter,
and is so robust that it can simulate very efficiently a wide variety of
other structures frequently used in the development of parallel algorithms.
Nevertheless, the hypercube interconnection network cannot be expanded
in practice; the number of communication ports and channels per processor
increases with any increase in the total number of processors in the system.
Thus, not only does the overall wiring complexity increase dramatically
with any increase in the system size, but the VLSI complexity of processors
also increases. Solutions are required to alleviate this incremental growth
problem of the hypercube interconnection network.
I have proposed a methodology that modifies hypercube interconnection
networks in order to support incremental growth techniques. The proposed
methodology accomplishes this goal with minimal modifications of individual
hypercubes and, contrary to other existing techniques, without any need
for additional resources (i.e., without any additional communication ports,
communication channels, or processors). The effectiveness of the proposed
methodology in alleviating the incremental growth problem of the hypercube
is a great asset.
Other impressive properties of the modified networks are their
reduced diameter and reduced average inter-processor distance when compared
to the original hypercubes. These modified hypercube networks, which have
available communication channels for the establishment of external connections,
serve as building blocks for the construction of larger systems.
Return to the "summary of recent research contributions" page
Return to my home page
Last updated 11/02/98, SGZ