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

Abrizio was a fabless semiconductor company which made switching fabric chip sets . Their chip set, the TT1, was used by several large system development companies as the core switch fabric in their high value communication systems.-Founding:It was founded in 1997 by Professor Nick McKeown as a...

 and sold by PMC-Sierra

PMC-Sierra

PMC-Sierra is a fabless semiconductor company which develops and sells devices into the communications, storage, printing, and embedded computing marketplaces.-Corporate history:...

.

Context

A crossbar is the central portion of a crossbar switch

Crossbar switch

In electronics, a crossbar switch is a switch connecting multiple inputs to multiple outputs in a matrix manner....

 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

Packet switching

Packet switching is a digital networking communications method that groups all transmitted data – regardless of content, type, or structure – into suitably sized blocks, called packets. Packet switching features delivery of variable-bit-rate data streams over a shared network...

 applications, the arbitration period is very short. There are often millions or billion

1000000000 (number)

1,000,000,000 is the natural number following 999,999,999 and preceding 1,000,000,001.In scientific notation, it is written as 109....

s of arbitration periods per second.

An arbiter

Arbiter (electronics)

-Asynchronous arbiters:An important form of arbiter is used in asynchronous circuits, to select the order of access to a shared resource among asynchronous requests. Its function is to prevent two operations from occurring at once when they should not...

 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 aribiter is a particular type of arbiter that is optimized for high-speed operation. For a unicast switch, the algorithm is as follows:

1. The decision starts at a single point in the x-y matrix which represents the physical switches, for example the upper left hand corner.
2. Based on the requests, a decision is made whether to close that switch, connecting the corresponding input and output.
3. 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.
4. 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.
5. 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.
6. These results are again fed to the right and below.
7. 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.
8. 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
  Hardware register
  In digital electronics, especially computing, a hardware register stores bits of information, in a way that all the bits can be written to or read out simultaneously.The hardware registers inside a central processing unit are called processor registers....
  
  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
  Computation is defined as any type of calculation. Also defined as use of computer technology in Information processing.Computation is a process following a well-defined model understood and expressed in an algorithm, protocol, network topology, etc...
  
  . Regular structures can sometimes lead to compact semiconductor
  Semiconductor
  A semiconductor is a material with electrical conductivity due to electron flow intermediate in magnitude between that of a conductor and an insulator. This means a conductivity roughly in the range of 103 to 10−8 siemens per centimeter...
  
   implementations.

Variants

There are numerous variants of this method including:

• Randomizing
  Randomization
  Randomization is the process of making something random; this means:* Generating a random permutation of a sequence .* Selecting a random sample of a population ....
  
   or shuffling the order in the which the rows and columns are considered. Some sort of shuffling is generally necessary to achieve fairness.
• Multicast
  Multicast
  In computer networking, multicast is the delivery of a message or information to a group of destination computers simultaneously in a single transmission from the source creating copies automatically in other network elements, such as routers, only when the topology of the network requires...
  
  variants of this method where one input can be connected to multiple outputs in either one or multiple passes.