8. CASE STUDIES
18.104.22.168 Key parameters associated with age-based arbitration
The Cray XT network provides age-based arbitration to mitigate the affects of this traffic merging
as shown in Figure 8.9 , thus reducing the variation in packet delivery time. However, age-based
arbitration can introduce a starvation scenario whereby younger packets are starved at the output
port and cannot make forward progress toward the destination. The details of the algorithm along
with performance results are given by Abts and Weisser [ 4 ]. There are three key parameters for
controlling the aging algorithm.
AGE_CLOCK_PERIOD - a chip-wide 32-bit countdown timer that controls the rate at which
packets age. If the age rate is too slow, it will appear as though packets are not accruing any
queueing delay, their ages will not change, and all packets will appear to have the same age. On
the other hand, if the age rate is too fast, packets ages will saturate very quickly — perhaps after
only a few hops — at the maximum age of 255, and packets will not generally be distinguishable
by age. The resolution of AGE_CLOCK_PERIOD allows anywhere from 2 nanoseconds to more
than 8 seconds of queueing delay to be accrued before the age value is incremented.
REQ_AGE_BIAS and RSP_AGE_BIAS - each hop that a packet takes increments the packet age
by the REQ_AGE_BIAS if the packet arrived on VC0/VC1 or by RSP_AGE_BIAS if the packet
arrived on VC2/VC3. The age bias fields are configurable on a per-port basis, with the default
bias of 1.
AGE_RR_SELECT - a 64-bit array specifying the output arbitration policy. A value of all 0s
will select round-robin arbitration, and a value of all 1s will select age-based arbitration. A
combination of 0s and 1s will control the ratio of round-robin to age-based. For example, a
value of 0101
0101 will use half round-robin and half age-based.
When a packet arrives at the head of the input queue, it undergoes routing by indexing into the
LUT with destination[11:0] to choose the target port and virtual channel. Since each input port and
VC has a dedicated buffer at the output staging buffer, there is no arbitration necessary to allocate
the staging buffer — only flow control. At the output port, arbitration is performed on a per-packet
basis (not per flit, as wormhole flow control would). Each output port is allocated by performing a
4-to-1 VC arbitration along with a 7-to-1 arbitration to select among the input ports. Each output
port maintains two independent arbitration pointers — one for round-robin and one for age-based.
A 6-bit counter is incremented on each grant cycle and indexes into the AGE_RR_SELECT bit array
to choose the per-packet arbitration policy.
The Cray BlackWidow is a scalable shared memory multiprocessor using custom vector processors,
and the Cray XT is a distributed memory multiprocessor built from commodity microprocessors.
The Cray XT uses a 3-D torus (low-radix) network, in contrast to the high-radix folded-Clos of the
BlackWidow. This topology difference is in large part because the 3-D torus is a direct network and