O'Reilly logo

Principles and Practices of Interconnection Networks by Brian Patrick Towles, William James Dally

Stay ahead with the world's most comprehensive technology and business learning platform.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, tutorials, and more.

Start Free Trial

No credit card required

168 CHAPTER 8 Routing Basics
x dimension remains the same, but for the y dimension the preferred direction is
D
y
= 0. How do we route the packet in this case? By moving the destination node
to 32, routing in either the positive or negative direction in the y dimension requires
three hops. So, to balance load, it is important that traffic be evenly distributed in
the two directions. A simple approach for doing this is to abandon a deterministic
algorithm and randomly split the traffic equally between the positive and negative
y directions.
3
It can also be easily verified by intuition or from Equation 8.4 that a
preferred direction of zero can occur only when k is even.
We have focused on the torus up to this point, but dimension-order routing
works similarly in the mesh. The lack of wraparound channels simplifies the choice
of the preferred directions, which in this case are also the only valid directions:
D
M,i
=
+1ifd
i
>s
i
1 otherwise.
Despite its generally poor load balancing properties, dimension-order routing has
been widely used in mesh and torus networks for two reasons. First, it is very simple
to implement. In particular, it allows the router to be dimension-sliced or partitioned
across dimensions. Second, it simplifies the problem of deadlock avoidance by pre-
venting any cycles of channel dependency between dimensions. However, deadlock
can still occur within a dimension. (See Chapter 14.)
8.5 Case Study: Dimension-Order Routing in the Cray T3D
Figure 8.5 shows a Cray T3D [95, 161], which connects up to 2,048 DEC Alpha
processing elements in a 3-D torus. The T3D is a shared-memory multiprocessor.
Each processing element includes a local memory but can access the local memory
of all other processing elements by forwarding load and store operations over the
torus network. Each pair of processing elements shares a single router via a network
interface.
The T3D network uses dimension-order routing and is implemented using a
dimension-sliced (Section 7.2.2) router, as shown in Figure 8.6. The router is re-
alized on three identical ECL gate arrays that route in the x, y, and z dimensions,
respectively. The overall design closely follows the organization of the J-Machine
router (Section 5.5). This partitioning is possible because of the dimension-order
routing. We consider a different partitioning in Exercise 8.6.
When a packet arrives from the network interface, the x router examines the
packet to determine if it must route in the +x dimension, the x dimension, or,
if it is already at the destination x coordinate, proceed to the y router. Suppose the
3. In Exercise 8.9, we explore the cost of not balancing this load and deterministic ways to achieve this
balance.
8.5 Case Study: Dimension-Order Routing in the Cray T3D 169
Figure 8.5 A Cray T3D connects up to 2,048 DEC Alpha processors in a 3-D torus with shared memory.
packet is forwarded in the +x direction (along the xpOut channel). At each subse-
quent x router, the router checks the packet to see if it is at the proper x coordinate.
The packet is forwarded to the y router when it reaches the proper coordinate.
Otherwise, it continues to move in the +x direction.
Each T3D router channel has a bandwidth of 300 Mbytes/s and is carried over
a wire mat between modules. The channels each have 16 data bits and 8 control bits
and operate at 150 MHz, the same frequency as the original Alpha 21064 processors.
The wire mat is a harness of wires that are manually connected to the board edge
connectors to implement the torus topology. It is called a mat because it resembles
an irregularly woven fabric. Each data and control signal is carried as a differential
ECL signal over a twisted pair of wires in the wire mat.

With Safari, you learn the way you learn best. Get unlimited access to videos, live online training, learning paths, books, interactive tutorials, and more.

Start Free Trial

No credit card required