HyperTransPort Imposes A Fairness Algorithm

The Basic Policy2

The fairness policy basically allows a tunnel to insert packets onto the upstream link at a rate equal to the most active device (UnitID) below it. What this means is that it must determine the most active downstream UnitID, then may insert packets one-for-one with that transaction stream. Of course, during idle times on the bus, it may insert packets at will. The goal of the specification is that there will be a continuous reassessment of the insertion rate to match changing conditions. On the subject of dynamic adjustment of the insertion rate, the specification says: "this property must be met over a window in time small enough to be responsive to the dynamic traffic patterns, yet large enough to be statistically convergent".

The Algorithm

There are two parts to the Fairness and Forward progress algorithm: calculating the insertion rate and implementing a hardware mechanism that enforces it. While a single interface is described here, tunnel devices actually must implement independent algorithms for each link. There are no programmable control/status registers associated with the algorithm; it is completely hardware based. Also note that:

1. Information packets (NOP and Sync) are issued on a per-link basis and not subject to the fairness algorithm.

2. All other packets are handled without regard to their type, virtual channel, etc. All ordering and priority issues are handled internally.

First, Calculate The Insertion Rate

This is done through the implementation of hardware registers to monitor incoming packets requiring forwarding for each transaction stream. Because HyperTransport permits a total of 32 UnitIDs per chain, the register set to manage each link consists of:

1. 32 individual 3-bit counters which are used to count the incoming packets from individual transaction streams (using the request and response packet UnitID field)

2. One 8-bit counter used to count the collective number of incoming packets from all transaction streams.

At reset, all 32 individual counters are reset to "0". The 8-bit counter is reset to "1". The sequence of events in the counters as packets arrive to be forwarded is as follows:

1. Each time a packet to be forwarded arrives, its individual 3-bit counter is indexed by 1.

2. The 8-bit counter is also indexed any time a forwarded packet arrives from any UnitID.

3. The first individual 3-bit counter to overflow (roll to "0") represents the most active UnitID.

4. The value in the eight bit counter when the first 3-bit counter overflows is used as the denominator of a fraction which is expressed as 8/denominator. This ratio is the maximum rate at which the tunnel device may insert its own packets onto the upstream link.

5. The specification recommends that the tunnel space out the interleaving of its packets, rather than bursting them all at once.

Insertion Rate Calculation Example

Assume there are three devices below a tunnel: UnitID2, UnitID4, and UnitID5. Packets targeting main memory are being issued by all three devices.

1. Incoming packets from UnitID5 cause its 3-bit counter to roll over first.

2. The 8-bit counter (denominator) was at 12 when the roll over occurred.

3. The tunnel then calculates the insertion rate: 8/denominator = 8/12 = 2/3.

4. The tunnel is allowed to insert, on average, two packets for every three which it forwards for the devices below it.

The HyperTransport specification provides additional guidelines for designers in implementing a simple priority and arbitration scheme, achieving non-integral insertion rates, and avoiding potential starvation problems.