Economics is the principle driver of current trends to
use commodity components in the construction of parallel systems
for a range of sizes.
One objective is to enable the user to purchase a small
system initially, and then extend it through a range of
sizes as needs dictate.
A desirable feature is to have good system performance through
the range of sizes; an undesirable feature is to require the user
to purchase excess hardware that will not be used until the
system is grown to its maximum allowable size.
In this paper, we give a new construction
which reconciles these two conflicting factors by introducing a way
to interconnect several components of a given small network using
only the routers for the small network, with
one additional port per router.
This construction, which we call a shift-product, does not
unduly raise the communication diameter of the resulting large network.
Keywords:
interconnection networks, parallel computer, scalable networks,
shuffle-exchange networks, Cayley graphs, product graphs, de Bruijn network,
commodity components, computer architecture, computer science
