Wavefront arbiter

A Wavefront arbiter is a circuit used to make decisions which control the crossbar of a high capacity switch fabric in parallel.^[1] It was commercialized in the TT1 and TTx chip sets designed by Abrizio and sold by PMC-Sierra.

Context

A crossbar is the central portion of a crossbar switch fabric which connects the inputs to the outputs. A set of decisions of which inputs are connected to which outputs must be made each arbitration period. In high speed cell switching or packet switching applications, the arbitration period is very short. There are often millions or billions of arbitration periods per second.

An arbiter is the circuit that makes the decision as to which of the crossbar's many switches should be closed. Speed is a key design criterion of an arbiter in some applications.

Algorithm description

A wavefront arbiter is a particular type of arbiter that is optimized for high-speed operation. For a unicast switch, the algorithm is as follows:

The decision starts at a single point in the x-y matrix which represents the physical switches, for example the upper left hand corner.
Based on the requests, a decision is made whether to close that switch, connecting the corresponding input and output.
The result of this decision is then fed to the right along the matrix axis representing the input, and down along the matrix axis representing the output.
The results of the first computation then enable the next computation at the point to the right and at the point below and switch closing decision is made at each of those two points.
The results of these subsequent two calculations then are then fed to the points below and to the right of them. These results then enable the decisions at the next three points which are to the right and below.
These results are again fed to the right and below.
In the case where the calculation did not start in the upper left hand corner, the results wrap around the right back to the first left column and around the bottom to the top row.
The calculation continues until all of the decisions have been made.

Benefit of use

The benefits of this type of calculation include:

Speed – the algorithm can be implemented in a combinatorial manner (without hardware registers), allowing the wavefront to propagate across much or all of the matrix in one or a few clock periods.
Regularity – the nodes of the physical structure used to compute this are all identical. This is often called a systolic computation. Regular structures can sometimes lead to compact semiconductor implementations.

Variants

There are numerous variants of this method including:

Randomizing or shuffling the order in which the rows and columns are considered. Some sort of shuffling is generally necessary to achieve fairness.
Multicast variants of this method where one input can be connected to multiple outputs in either one or multiple passes.

References

^ Gelenbe, E.; Bagchi, K.; Zobrist, G. (1999). Network Systems Design. Taylor & Francis. p. 6. ISBN 978-90-5699-635-2. Retrieved 13 September 2018.

Stanford class notes description of the algorithm

[Gelenbe_Bagchi_Zobrist_1999_p._6-1] Gelenbe, E.; Bagchi, K.; Zobrist, G. (1999). Network Systems Design. Taylor & Francis. p. 6. ISBN 978-90-5699-635-2. Retrieved 13 September 2018.

[1]