Arbiter (electronics)
Encyclopedia
Asynchronous arbiters
An important form of arbiter is used in asynchronous circuitAsynchronous circuit
An asynchronous circuit is a circuit in which the parts are largely autonomous. They are not governed by a clock circuit or global clock signal, but instead need only wait for the signals that indicate completion of instructions and operations. These signals are specified by simple data transfer...
s, 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. For example, in a computer that has multiple CPUs or other devices accessing computer memory
Computer memory
In computing, memory refers to the physical devices used to store programs or data on a temporary or permanent basis for use in a computer or other digital electronic device. The term primary memory is used for the information in physical systems which are fast In computing, memory refers to the...
, and has more than one clock
Clock
A clock is an instrument used to indicate, keep, and co-ordinate time. The word clock is derived ultimately from the Celtic words clagan and clocca meaning "bell". A silent instrument missing such a mechanism has traditionally been known as a timepiece...
, the possibility exists that requests from two unsynchronized sources could come in at nearly the same time. "Nearly" can be very close in time, in the sub-femtosecond range. The memory arbiter must then decide which request to service first. Unfortunately, it is not possible to do this in a fixed time [Anderson 1991].
Ivan Sutherland
Ivan Sutherland
Ivan Edward Sutherland is an American computer scientist and Internet pioneer. He received the Turing Award from the Association for Computing Machinery in 1988 for the invention of Sketchpad, an early predecessor to the sort of graphical user interface that has become ubiquitous in personal...
and Jo Ebergen, in their article "Computers without Clocks", describe Arbiters as follows:
- An Arbiter is like a traffic officer at an intersection who decides which car may pass through next. Given only one request, an Arbiter promptly permits the corresponding action, delaying any second request until the first action is completed. When an Arbiter gets two requests at once, it must decide which request to grant first. For example, when two processors request access to a shared memory at approximately the same time, the Arbiter puts the requests into one order or the other, granting access to only one processor at a time. The Arbiter guarantees that there are never two actions under way at once, just as the traffic officer prevents accidents by ensuring that there are never two cars passing through the intersection on a collision course.
- Although Arbiter circuits never grant more than one request at a time, there is no way to build an Arbiter that will always reach a decision within a fixed time limit. Present-day Arbiters reach decisions very quickly on average, usually within about a few hundred picoseconds. When faced with close calls, however, the circuits may occasionally take twice as long, and in very rare cases the time needed to make a decision may be 10 times as long as normal.
Asynchronous arbiters and metastability
Arbiters break ties. Like a flip-flop circuitFlip-flop (electronics)
In electronics, a flip-flop or latch is a circuit that has two stable states and can be used to store state information. The circuit can be made to change state by signals applied to one or more control inputs and will have one or two outputs. It is the basic storage element in sequential logic...
, an arbiter has two stable states corresponding to the two choices. If two requests arrive at an arbiter within a few picoseconds (today, femtoseconds) of each other, the circuit may become meta-stable
Metastability in electronics
Metastability in electronics is the ability of a digital electronic system to persist for an unbounded time in an unstable equilibrium or metastable state....
before reaching one of its stable states to break the tie. Classical arbiters are specially designed not to oscillate wildly when meta-stable and to decay from a meta-stability as rapidly as possible, typically by using extra power. The probability of not reaching a stable state decreases exponentially with time after inputs have been provided.
A reliable solution to this problem was found in the mid 1970s. Although an arbiter that works reliably in a fixed time is not possible, one that sometimes takes a little longer for the hard case can be made to work. It is necessary to use a multistage synchronization
Metastability in electronics
Metastability in electronics is the ability of a digital electronic system to persist for an unbounded time in an unstable equilibrium or metastable state....
circuit that detects that the arbiter has not yet settled into a stable state. The arbiter then delays processing until a stable state has been achieved. In theory, the arbiter can take an arbitrarily long time to settle, but in practice, it seldom takes more than a few gate delay times. The classic paper is [Kinniment and Woods 1976], which describes how to build a "3 state flip flop" to solve this problem, and [Ginosar 2003], a caution to engineers on common mistakes in arbiter design.
This result is of considerable practical importance. Multiprocessor computers will not work reliably without it. The first multiprocessor computers date from the late 1960s, predating the development of reliable arbiters. Some early multiprocessors with independent clocks for each processor suffered from arbiter race conditions, and thus unreliability. Today, this is no longer a problem.
Synchronous arbiters
Arbiters are used in synchronous contexts as well in order to allocate access to a shared resource. A wavefront arbiterWavefront arbiter
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 and sold by PMC-Sierra.-Context:...
is an example of a synchronous arbiter that is present in one type of large network switch
Network switch
A network switch or switching hub is a computer networking device that connects network segments.The term commonly refers to a multi-port network bridge that processes and routes data at the data link layer of the OSI model...
.