The Butterfly switch
The Butterfly switch provides a mechanism for passing messages between
the Node Controllers of different processing elements. These messages
normally take the form of memory cycle requests and acknowledgements,
and since the assembly and dissassembly of message packets is
performed by the PNC, the microprocessors perceive transparent access
to both local and non-local memory. The PNCs are also capable of
performing block transfer operations to facilitate the movement of
blocks of memory from the local memory of one processing node to
another.
The 'black box' specification of the Butterfly switch is a
relatively simple one. As far as the processing nodes are concerned,
it consists of an equal number of input and output ports, which need
not be a power of two, although normally they would be. The ports are
uniquely labelled and, to enable routing to be performed 'on the fly'
as messages pass through the switch, each message incorporates a
header containing the label of its destination port. The insertion of
messages into the switch from different sources occurs asynchronously,
and the time taken for a message to propagate from its source to its
destination depends on the number of inputs to the switch and the
loading on the switch during routing. The asynchronous nature of the
M68000 bus enables variable round-trip delays to be hidden from the
processor, although they do have an effect on system performance as we
shall see shortly.
The network messages, containing non-local memory addresses, a data
field and some control bits, are approximately 80-bits long and, to
keep the complexity (measured here in terms of inter-stage wiring) of
the switch nodes within manageable limits, the switch nodes serialise
the packets into 8-bit chunks. These 8-bit chunks are piped through
the switch at a rate of one chunk every 100 ns, resulting in a minimum
switch latency of approximately 10 cycles per packet.
Switch topology
The Butterfly switch is a multi-stage network which uses a variant of
the shuffle permutation to connect 4-input and 4-output exchange
boxes. These exchange boxes are effectively 4 x 4 cross-bar switches,
and to illustrate this a Butterfly switch with 16 ports is depicted in
the figure. Routing within a single node is performed by labelling the
four output ports uniquely in the range {0 ... 3}, then assigning a
route from each input port to the output port selected by the two
least significant digits of the destination label associated with each
incoming packet, as shown in the figure. As the destination label for
a packet passes through each switching node the two least signinficant
digits are 'removed', thus exposing the next two digits to the routing
function in the subsequent stage of the network. If at any time during
the setting up of a route through the switch, a routing conflict
occurs, one of the conflicting messages will proceed unaffected
whereas the other must retrace its path out of the switch, to be
re-transmitted after a short delay. The importance of clearing down a
partially routed, but blocked, link from the point in the network
where the conflict occurred back to the source node, will become
apparent when we discuss the performance of the switch.
The routing function
The actual routing function used by the Butterfly switch can be
expressed formally by defining it as a composite sequence of
permutations, Bni, which is applied to an input
packet of the following form. Let the input packet consist of a
header containing an n-bit destination label D =
{dn, ..., d1}. Let us also assume that
during the routing of the packet through the switch the packet header
is located at the kth stage, with an intermediate label given by P
= {pn, ..., p1}. The switch network is
characterised in terms of i, the radix of the switch
nodes. The radix determines how many channels are switched within a
single switch node, and this is given by c = 2i. Hence, the
total number of active stages in the network is given by
s = log2i N = n/i for an N-port
Butterfly switch. We can hence define
Eni, the exchange permutation performed
in each switching node on a packet with destination label D
when at an intermediate label P, to be
|
Eni (<P, D>) |
= |
<{pn, pn-1, ..., pi+1, di, di-1, ..., d1}, |
| | {di,, di-1, ..., d1, dn, dn-1, ..., di+1}> |
and the shuffle permutation applied to the
connections from stage k to stage k+1 is then
Sn,ik (<P, D>) = <σn-(n-ik) (P), D>
where σn-x(P) is the xth
inverse sub-shuffle applied to P. This permutation is defined
formally as
σ-(n-ik)n(P) = {pn,
pn-1, ..., pik+1, pi,
pi-1, ..., p1, pik, pik-1,
..., pi+1}
Informally, this defines a right-circular rotation of the binary
representation of the least significant ik bits of P, by
i places. Effectively, Eni and Sn,ik map
from <P, D> to <P', D'>, where
P and
P' are the entry and exit labels of the packet through the kth
stage in the network, and D and D' are the target (destination)
labels before and after the routing takes place at the kth stage in
the network.
The Butterfly switch as a whole can now be defined as the composition of
Eni and Sn,ik over n/i stages, thus
Bni = (Eni Sn,ik)n/ik=l
This permutation is illustrated in the figure, for 16 processing nodes
and i=2 (4 x 4 switch nodes). Note, there is no shuffle
permutation at the output of the switch, since the last shuffle
permutation is Sin,n/i which is equal to
I, the identity permutation.