A Wavefront arbiter is a circuit used to make decisions which control the crossbar of a high capacity switch fabric in parallel. It was commercialized in the TT1 and TTx chip sets designed by
Abrizio
Abrizio was a fabless semiconductor company which made switching fabric chip sets ( integrated circuits for computer network switches). Their chip set, the TT1, was used by several large system development companies as the core switch fabric in t ...
and sold by
PMC-Sierra
PMC-Sierra was a global fabless semiconductor company with offices worldwide that developed and sold semiconductor devices into the storage, communications, optical networking, printing, and embedded computing marketplaces.
On January 15, 2016, ...
.
Context
A crossbar is the central portion of a
crossbar switch
In electronics and telecommunications, a crossbar switch (cross-point switch, matrix switch) is a collection of switches arranged in a matrix configuration. A crossbar switch has multiple input and output lines that form a crossed pattern of int ...
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
In telecommunications, packet switching is a method of grouping Data (computing), data into ''network packet, packets'' that are transmitted over a digital Telecommunications network, network. Packets are made of a header (computing), header and ...
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 register
In digital electronics, especially computing, hardware registers are circuits typically composed of flip flops, often with many characteristics similar to memory, such as:
* The ability to read or write multiple bits at a time, and
* Using an a ...
s), 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
Computation is any type of arithmetic or non-arithmetic calculation that follows a well-defined model (e.g., an algorithm).
Mechanical or electronic devices (or, historically, people) that perform computations are known as ''computers''. An es ...
. Regular structures can sometimes lead to compact
semiconductor
A semiconductor is a material which has an electrical resistivity and conductivity, electrical conductivity value falling between that of a electrical conductor, conductor, such as copper, and an insulator (electricity), insulator, such as glas ...
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
In computer networking, multicast is group communication where data transmission is addressed to a group of destination computers simultaneously. Multicast can be one-to-many or many-to-many distribution. Multicast should not be confused with ...
variants of this method where one input can be connected to multiple outputs in either one or multiple passes.
References
{{reflist, refs=
[{{cite book
, last = Gelenbe
, first = E.
, last2 = Bagchi
, first2 = K.
, last3 = Zobrist
, first3 = G.
, title = Network Systems Design
, publisher = Taylor & Francis
, year = 1999
, isbn = 978-90-5699-635-2
, url = https://books.google.com/books?id=DUBsMZsAnCMC&pg=PA6
, access-date = 13 September 2018
, page = 6
]
Stanford class notes description of the algorithm
Switches