© 2001, Myricom, Inc.
-- 22 --
Revision: 27 August 2001
generally have a regular structure that can be used to simplify the calculation. Also, at least for
full-bisection networks, there are some mathematical shortcuts that can be used to verify that the
bisection is full.
A message-passing network is said to be
rearrangeable
if it can route any permutation without
blocking. For example, an 8-host rearrangeable network must be able to route:
from host
0
1
2
3
4
5
6
7
↓
↓
↓
↓
↓
↓
↓
↓
to host
3
5
1
0
7
6
2
4
and every other of the 8! (40,320) possible permutations. Unlike a single crossbar switch, a
special case of a rearrangeable network, the set of routes used from host to host is permitted in a
rearrangeable network to be different for different permutations.
It should be evident that a network that is rearrangeable necessarily has full bisection. The
converse is not true. A network may have full-bisection but not be rearrangeable.
For the distributed computations performed on clusters, it is generally not practical to coordinate
the routing to take advantage of a network being rearrangeable. However, it is often easiest to
demonstrate that a network has full bisection by showing that it is rearrangeable.
Inasmuch as the path-formation latency of Myrinet switches is much smaller than software
latency, the maximal or average
diameter
, measured in switches traversed, is a relatively
unimportant metric of the network topology.
8. Clos Networks
Clos networks are named for Charles Clos, who introduced them in a paper titled “A Study of
Non-Blocking Switching Networks,” published in the
Bell System Technical Journal
in March
1953. Clos networks are rearrangeable: researchers at that time were seeking ways to route
arbitrary permutations of telephone connections. Clos networks thus exhibit full bisection. The
Clos network topology has other excellent properties – scaling to large sizes, modularity, and
multiple-path redundancy – that make it an ideal topology for cluster networks.
Our basic building block, the crossbar switch, is itself a rearrangeable and full-bisection network.
However, technology sets a practical upper limit on the degree of crossbar switches. For
Myrinet this limit is currently 16-port crossbar switches, which are implemented in a single chip,
the XBar16. The Clos topology provides systematic ways of connecting these 16-port crossbar
switches to serve large numbers of hosts, and to do so in a way that achieves full bisection.
As a first step toward understanding these constructions, here is the Clos network of 16-port
switches that connects 128 hosts, a network that we’ll refer to as the Clos128:
