Wavefront arbiter

Last updated

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.

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.

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.

Contents

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.

In electronics, a crossbar 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 interconnecting lines between which a connection may be established by closing a switch located at each intersection, the elements of the matrix. Originally, a crossbar switch consisted literally of crossing metal bars that provided the input and output paths. Later implementations achieved the same switching topology in solid state semiconductor chips. The cross-point switch is one of the principal switch architectures, together with a rotary switch, memory switch, and a crossover switch.

Packet switching a method of grouping data which is transmitted over a digital network into packets

Packet switching is a method of grouping data that is transmitted over a digital network into packets. Packets are made of a header and a payload. Data in the header are used by networking hardware to direct the packet to its destination where the payload is extracted and used by application software. Packet switching is the primary basis for data communications in computer networks worldwide.

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.

Arbiters are electronic devices that allocate access to shared resources.

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:

  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:

In digital electronics, especially computing, hardware registers are circuits typically composed of flip flops, often with many characteristics similar to memory, such as:

Computation is any type of calculation that includes both arithmetical and non-arithmetical steps and follows a well-defined model, for example an algorithm.

A semiconductor material has an electrical conductivity value falling between that of a metal, like copper, gold, etc. and an insulator, such as glass. Its resistance decreases as its temperature increases, which is behaviour opposite to that of a metal. Its conducting properties may be altered in useful ways by the deliberate, controlled introduction of impurities ("doping") into the crystal structure. Where two differently-doped regions exist in the same crystal, a semiconductor junction is created. The behavior of charge carriers which include electrons, ions and electron holes at these junctions is the basis of diodes, transistors and all modern electronics. Some examples of semiconductors are silicon, germanium, and gallium arsenide. After silicon, gallium arsenide is the second most common semiconductor and is used in laser diodes, solar cells, microwave-frequency integrated circuits and others. Silicon is a critical element for fabricating most electronic circuits.

Variants

There are numerous variants of this method including:

Randomization is the process of making something random; in various contexts this involves, for example:

Multicast a computer networking technique for forwarding transmissions from one sender to multiple receivers

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 physical layer point-to-multipoint communication.

Related Research Articles

Control theory in control systems engineering is a subfield of mathematics that deals with the control of continuously operating dynamical systems in engineered processes and machines. The objective is to develop a control model for controlling such systems using a control action in an optimum manner without delay or overshoot and ensuring control stability.

Fast Fourier transform O(n logn) divide and conquer algorithm to calculate the discrete Fourier transforms

A fast Fourier transform (FFT) is an algorithm that computes the discrete Fourier transform (DFT) of a sequence, or its inverse (IDFT). Fourier analysis converts a signal from its original domain to a representation in the frequency domain and vice versa. The DFT is obtained by decomposing a sequence of values into components of different frequencies. This operation is useful in many fields, but computing it directly from the definition is often too slow to be practical. An FFT rapidly computes such transformations by factorizing the DFT matrix into a product of sparse factors. As a result, it manages to reduce the complexity of computing the DFT from , which arises if one simply applies the definition of DFT, to , where is the data size. The difference in speed can be enormous, especially for long data sets where N may be in the thousands or millions. In the presence of round-off error, many FFT algorithms are much more accurate than evaluating the DFT definition directly. There are many different FFT algorithms based on a wide range of published theories, from simple complex-number arithmetic to group theory and number theory.

Computational geometry is a branch of computer science devoted to the study of algorithms which can be stated in terms of geometry. Some purely geometrical problems arise out of the study of computational geometric algorithms, and such problems are also considered to be part of computational geometry. While modern computational geometry is a recent development, it is one of the oldest fields of computing with history stretching back to antiquity.

Nonblocking minimal spanning switch

A nonblocking minimal spanning switch is a device that can connect N inputs to N outputs in any combination. The most familiar use of switches of this type is in a telephone exchange. The term "non-blocking" means that if it is not defective, it can always make the connection. The term "minimal" means that it has the fewest possible components, and therefore the minimal expense.

In parallel computer architectures, a systolic array is a homogeneous network of tightly coupled data processing units (DPUs) called cells or nodes. Each node or DPU independently computes a partial result as a function of the data received from its upstream neighbors, stores the result within itself and passes it downstream. Systolic arrays were invented by H. T. Kung and Charles Leiserson who described arrays for many dense linear algebra computations for banded matrices. Early applications include computing greatest common divisors of integers and polynomials. They are sometimes classified as multiple-instruction single-data (MISD) architectures under Flynn's taxonomy, but this classification is questionable because a strong argument can be made to distinguish systolic arrays from any of Flynn's four categories: SISD, SIMD, MISD, MIMD, as discussed later in this article.

In electronics, a crossover switch or matrix switch is a switch connecting multiple inputs to multiple outputs using complex array matrices designed to switch any one input path to any one output path(s). There are blocking and non-blocking types of cross-over switches.

A load-balanced switch is a switch architecture which guarantees 100% throughput with no central arbitration at all, at the cost of sending each packet across the crossbar twice. Load-balanced switches are a subject of research for large routers scaled past the point of practical central arbitration.

Z-order curve function which maps multidimensional data to one dimension while preserving locality of the data points

In mathematical analysis and computer science, functions which are Z-order, Lebesgue curve, Morton space filling curve, Morton order or Morton code map multidimensional data to one dimension while preserving locality of the data points. It is named after Guy Macdonald Morton, who first applied the order to file sequencing in 1966. The z-value of a point in multidimensions is simply calculated by interleaving the binary representations of its coordinate values. Once the data are sorted into this ordering, any one-dimensional data structure can be used such as binary search trees, B-trees, skip lists or hash tables. The resulting ordering can equivalently be described as the order one would get from a depth-first traversal of a quadtree.

Omega network

An Omega network is a network configuration often used in parallel computing architectures. It is an indirect topology that relies on the perfect shuffle interconnection algorithm.

Computer-generated holography (CGH) is the method of digitally generating holographic interference patterns. A holographic image can be generated e.g. by digitally computing a holographic interference pattern and printing it onto a mask or film for subsequent illumination by suitable coherent light source.

Algorithms that construct convex hulls of various objects have a broad range of applications in mathematics and computer science.

Virtual output queueing (VOQ) is a technique used in certain network switch architectures where, rather than keeping all traffic in a single queue, separate queues are maintained for each possible output location. It addresses a common problem known as head-of-line blocking.

In computational geometry, the Bentley–Ottmann algorithm is a sweep line algorithm for listing all crossings in a set of line segments, i.e. it finds the intersection points of line segments. It extends the Shamos–Hoey algorithm, a similar previous algorithm for testing whether or not a set of line segments has any crossings. For an input consisting of line segments with crossings, the Bentley–Ottmann algorithm takes time . In cases where , this is an improvement on a naïve algorithm that tests every pair of segments, which takes .

Multistage interconnection networks (MINs) are a class of high-speed computer networks usually composed of processing elements (PEs) on one end of the network and memory elements (MEs) on the other end, connected by switching elements (SEs). The switching elements themselves are usually connected to each other in stages, hence the name.

In physics, a wavefront is the locus of points having the same phase.

A time-slot interchange (TSI) switch is a network switch that stores data in RAM in one sequence, and reads it out in a different sequence. It uses RAM, a small routing memory and a counter. Like any switch, it has input and output ports. The RAM stores the packets or other data that arrive via its input terminal.

There are many types of artificial neural networks (ANN).

Feature learning a set of techniques that learn a feature: a transformation of raw data input to a representation that can be effectively exploited in machine learning tasks

In machine learning, feature learning or representation learning is a set of techniques that allows a system to automatically discover the representations needed for feature detection or classification from raw data. This replaces manual feature engineering and allows a machine to both learn the features and use them to perform a specific task.

In computing, a logic block or configurable logic block (CLB) is a fundamental building block of field-programmable gate array (FPGA) technology. Logic blocks can be configured by the engineer to provide reconfigurable logic gates.

References

  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.