8. CASE STUDIES
fixed, any port can correspond to any of the six directions. The non-coherent HyperTransport (HT)
protocol provides a low latency, point-to-point channel used to drive the Seastar network interface.
Four virtual channels are used to provide point-to-point flow control and deadlock avoidance.
Using virtual channels avoids unnecessary head-of-line (HoL) blocking for different network traffic
flows, however, the extent to which virtual channels improve network utilization depends on the
distribution of packets among the virtual channels.
The routing rules for the Cray XT are subject to several constraints. Foremost, the network must
provide error-free transmission of each packet from the source node identifier (NID) to the destination .
To accomplish this, the distributed table-driven routing algorithm is implemented with a dedicated
routing table at each input port that is used to lookup the destination port and virtual channel of the
incoming packet. The lookup table at each input port is not sized to cover the maximum 32k node
network since most systems will be much smaller, only a few thousand nodes. Instead, a hierarchical
routing scheme divides the node name space into global and local regions. The upper three bits of the
destination field (given by the destination[14:12] in the packet header) of the incoming packet
are compared to the global partition of the current SeaStar router. If the global partition does not
match, then the packet is routed to the output port specified in the global lookup table (GLUT).
The GLUT is indexed by destination[14:12] to choose one of eight global partitions.
Once the packet arrives at the correct global region, it will precisely route within a local
partition of 4096 nodes given by the destination[11:0] field in the packet header. The tables
must be constructed to avoid deadlocks. Glass and Ni [ 25 ] describe turn cycles that can occur
in k -ary n -cube networks. However, torus networks are also susceptible to deadlock that results
from overlapping virtual channel dependencies (this only applies to k -ary n -cubes, where k> 4) as
described by Dally and Seitz [ 19 ]. Additionally, the SeaStar router does not allow 180 degree turns
within the network. The routing algorithm must both provide deadlock-freedom and achieve good
performance on benign traffic. In a fault-free network, a straightforward dimension-ordered routing
(DOR) algorithm will provide balanced traffic across the network links. Although, in practice,
faulty links will occur and the routing algorithm must route around the bad link in a way that
preserves deadlock freedom and attempts to balance the load across the physical links. Furthermore,
it is important to optimize the buffer space within the SeaStar router by balancing the number of
packets within each virtual channel.
184.108.40.206 Avoiding deadlock in the presence of faults and turn constraints
The routing algorithm rests upon a set of rules to prevent deadlock. In the turn model, a positive first
(x+, y+, z+ then x-, y-, z-) rule prevents deadlock and allows some routing options to avoid faulty
links or nodes. The global/local routing table adds an additional constraint for valid turns. Packets
must be able to travel to their local area of the destination without the deadlock rule preventing free
movement within the local area. In the Cray XT network the localities are split with yz planes. To