Hardware Reference
In-Depth Information
passing. Even on a single-CPU machine, when the processor wants to read or
write a word, what it typically does is assert certain lines on the bus and wait for a
reply. This action is fundamentally like message passing: the initiator sends a re-
quest and waits for a response. In large multiprocessors, communication between
CPUs and remote memory almost always consists of the CPU sending an explicit
message, called a
packet
, to memory requesting some data, and the memory send-
ing back a reply packet.
Topology
The topology of an interconnection network describes how the links and
switches are arranged, for example, as a ring or as a grid. Topological designs can
be modeled as graphs, with the links as arcs and the switches as nodes, as shown in
Fig. 8-37. Each node in an interconnection network (or its graph) has some num-
ber of links connected to it. Mathematicians call the number of links the
degree
of
the node; engineers call it the
fanout
. In general, the greater the fanout, the more
routing choices there are and the greater the fault tolerance, that is, the ability to
continue functioning even if a link fails by routing around it. If every node has
k
arcs and the wiring is done right, it is possible to design the network so that it
remains fully connected even if
k
1 links fail.
Another property of an interconnection network (or its graph) is its
diameter
.
If we measure the distance between two nodes by the number of arcs that have to
be traversed to get from one to the other, then the diameter of a graph is the dis-
tance between the two nodes that are the farthest apart (i.e., have the greatest dis-
tance between them). The diameter of an interconnection network is related to the
worst-case delay when sending packets from CPU to CPU or from CPU to memo-
ry because each hop across a link takes a finite amount of time. The smaller the
diameter, the better the worst-case performance. Also important is the average dis-
tance between two nodes, since this relates to the average packet transit time.
Yet another important property of an interconnection network is its transmis-
sion capacity, that is, how much data it can move per second. One useful measure
of this capacity is the
bisection bandwidth
. To compute this quantity, we first
have to (conceptually) partition the network into two equal (in terms of number of
nodes) but unconnected parts by removing a set of arcs from its graph. Then we
compute the total bandwidth of the arcs that have been removed. There may be
many different ways to partition the network into two equal parts. The bisection
bandwidth is the minimum of all the possible partitions. The significance of this
number is that if the bisection bandwidth is, say, 800 bits/sec, then if there is a lot
of communication between the two halves, the total throughput may be limited to
only 800 bits/sec, in the worst case. Many designers believe bisection bandwidth
is the most important metric of an interconnection network. Many interconnection
networks are designed with the goal of maximizing the bisection bandwidth.
−
