Arbiters are electronic devices that allocate access to shared resources.
Bus arbiter A bus arbiter is a device used in a
multi-master bus system to decide which bus master will be allowed to control
the bus for each bus cycle. The most common kind of bus arbiter is the memory
arbiter in a system bus system. A memory arbiter is a device used in a
shared memory system to decide, for each memory cycle, which CPU will be allowed
to access that shared memory. Some atomic instructions depend on the
arbiter to prevent other CPUs from reading memory "halfway through" atomic
read-modify-write instructions. A memory arbiter is typically integrated
into the memory controller/DMA controller.
Some systems, such as Conventional PCI, have a single centralized bus
arbitration device that one can point to as "the" bus arbiter. Other systems use
decentralized bus arbitration, where all the devices cooperate to decide who goes
next. When every CPU connected to the memory
arbiter has synchronized memory access cycles, the memory arbiter can be
designed as a synchronous arbiter. Otherwise the memory arbiter must be
designed as an asynchronous arbiter. 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. For example, in a computer that has multiple CPUs or other devices accessing
computer memory, and has more than one clock, 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 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 circuit, an arbiter has two stable
states corresponding to the two choices. If two requests arrive at an arbiter
within a few picoseconds of each other, the circuit may become meta-stable
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 makes a decision in a fixed time is not possible, one that sometimes
takes a little longer in the hard case can be made to work. It is necessary to
use a multistage synchronization 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, as multiprocessor computers
would 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 arbiter is an example of a synchronous
arbiter that is present in one type of large network switch.
References D.J. Kinniment and J.V. Woods.
"Synchronization and arbitration circuits in digital systems" Proceedings
IEEE. October 1976. Carver Mead and Lynn Conway.
Introduction to VLSI Systems Addison-Wesley. 1979.
Sutherland, Ivan; Ebergen, Jo, "Computers without Clocks", Scientific
American 287: 62–69, doi:10.1038/scientificamerican0802-62
Ran Ginosar. "Fourteen Ways to Fool Your Synchronizer" ASYNC 2003.
J. Anderson and M. Gouda, "A New Explanation of the Glitch Phenomenon ",
Acta Informatica, Vol. 28, No. 4, pp. 297–309, April 1991.
External links Digital Logic Metastability
Metastability Performance of Clocked FIFOs
The 'Asynchronous' Bibliography Efficient Self-Timed Interfaces for
Crossing Clock Domains