Hardware Reference
In-Depth Information
east or go west, the network is one dimensional. If there are two axes, so a packet
can go east or west, or alternatively, go north or south, the network is two dimen-
sional, and so on.
Several topologies are shown in Fig. 8-37. Only the links (lines) and switches
(dots) are shown here. The memories and CPUs (not shown) would typically be
attached to the switches by interfaces. In Fig. 8-37(a), we have a zero-dimensional
star
configuration, in which the CPUs and memories would be attached to the
outer nodes, with the central one just doing switching. Although a simple design,
for a large system, the central switch is likely to be a major bottleneck. Also, from
a fault-tolerance perspective, this is a poor design since a single failure at the cent-
ral switch completely destroys the system.
In Fig. 8-37(b), we have another zero-dimensional design that is at the other
end of the spectrum, a
full interconnect
. Here every node has a direct connection
to every other node. This design maximizes the bisection bandwidth, minimizes
the diameter, and is exceedingly fault tolerant (it can lose any six links and still be
fully connected). Unfortunately, the number of links required for
k
nodes is
k
(
k
1)/2, which quickly gets out of hand for large
k
.
Another topology is the
tree
, illustrated in Fig. 8-37(c). A problem with this
design is that the bisection bandwidth is equal to the link capacity. Since there will
normally be a lot of traffic near the top of the tree, the top few nodes will become
bottlenecks. One way around this problem is to increase the bisection bandwidth
by giving the upper links more bandwidth. For example, the lowest-level links
might have a capacity
b
, those at the next level might have a capacity 2
b
and the
top-level links might each have 4
b
. Such a design is called a
fat tree
and has been
used in commercial multicomputers, such as the (now-defunct) Thinking Ma-
chines' CM-5.
The
ring
of Fig. 8-37(d) is a one-dimensional topology by our definition be-
cause every packet sent has a choice of going left or going right. The
grid
or
mesh
of Fig. 8-37(e) is a two-dimensional design that has been used in many commercial
systems. It is highly regular, easy to scale up to large sizes, and has a diameter that
increases only as the square root of the number of nodes. A variant on the grid is
the
double torus
of Fig. 8-37(f), which is a grid with the edges connected. Not
only is it more fault tolerant than the grid, but the diameter is also less because the
opposite corners can now communicate in only two hops.
Yet another popular topology is the three-dimensional torus. It consists of a
3D-structure with nodes at the points (
i
,
j
,
k
) where all coordinates are integers in
the range from (1, 1, 1) to (
l
,
m
,
n
). Each node has six neighbors, two along each
axis. The nodes at the edges have links that wrap around to the opposite edge, just
as with the 2D torus.
The
cube
of Fig. 8-37(g) is a regular three-dimensional topology. We have il-
lustrated a 2
−
k
cube. In
Fig. 8-37(h) we have a four-dimensional cube constructed from two three-dimen-
sional cubes with the corresponding nodes connected. We could make a five-
×
2
×
2 cube, but in the general case it could be a
k
×
k
×
