XNL Switch and Its Control
Original Publication Date: 1992-Jan-01
Included in the Prior Art Database: 2005-Mar-21
Described is a switch for interprocessor communication in massively parallel computer systems which allows any processor to be connected to any other processor and which is non-blocking.
XNL Switch and Its Control
a switch for interprocessor communication in
massively parallel computer systems which allows any processor to be
connected to any other processor and which is non-blocking.
switch is constructed from a series of small crosspoint
switches. With N being the number of inputs of a crosspoint switch
and X being an expansion factor, there are three types of crosspoint
switches: First, the expansion block which is an N x XN switch, then
the central block which is an XN x XN switch, and finally the
convergence block which is an XN x N switch. Several levels L of
expansion blocks may be cascaded before the central block which is
then followed by an equal number of levels of convergence blocks to
form an M x M XNL switch, with M being the total number of inputs
of the XNL switch.
block has a multiple number of outputs for each
of the N inputs. The multiple is described by the expansion factor
X. For example, an expansion block with N = 4 and X = 3 would
have 12 outputs. Since this block would be a crosspoint switch, any
available output could be connected to any input.
of the expansion block is to provide more paths in
the network than can be connected at any given time. This allows
many alternative routes from an input to any network output, which
are necessary to overcome the possibility that many routes may be
blocked by previous connections.
routes and total network inputs/outputs may be
provided by cascading expansion blocks as many levels L as
implementation restrictions will allow.
A message may
follow any of the possible (XN)L paths from a
single input to the central blocks. It is the task of the central
and convergence blocks to then route the message to the specific
network destination port.
is wired such that every output of an expansion
block is connected to a different central block in order to achieve
the largest network configuration, and each output of a central block
is wired to a different convergence block. See Fig. 1 for an example
of an XNL network with X = 2, N = 2 and L = 1.
Fig. 2 shows what happens when the previous network is expanded by
adding a level (L = 2), and Fig. 3 depicts an XNL network with X
= 3, N = 2 and L = 1. The total number of input ports
in a fully configured XNL network is XN(L + 1) .
It is also
possible to build an XNL switch in less than its
full configuration. This is accomplished by simply connecting an
integer multiple of either X or N outputs from each expansion block
to each central block and doing the same with the convergence blocks.
Fig. 4 shows an example of X = 2, N = 4 and L =
1. Since the reduced XNL switch has the same number of possible
paths from each input to each output, it also has the same
non-blocking characteristics as a fully configured switch with the
same XNL description. Only...