Arbiter (electronics)

Arbiters are electronic devices that allocate access to shared resources.

Bus arbiter

There are multiple ways to perform a computer bus arbitration, with the most popular varieties being:

1. dynamic centralized parallel where one central arbiter is used for all masters as discussed in this article;
2. centralized serial (or "daisy chain") where, upon accessing the bus, the active master passes the opportunity to the next one. In essence, each connected master contains its own arbiter;
3. distributed arbitration by self-selection (distributed bus arbitration) where the access is self-granted based on the decision made locally by using information from other masters;
4. distributed arbitration by collision detection where each master tries to access the bus on its own, but detects conflicts and retries the failed operations.

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].

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 (today, femtoseconds) 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 having reached 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 (close calls) 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 (see Buridan's principle), 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.

Sources

• D.J. Kinniment and J.V. Woods. Synchronization and arbitration circuits in digital systems. Proceedings IEE. October 1976.
• Carver Mead and Lynn Conway. Introduction to VLSI Systems Addison-Wesley. 1979.
• Sutherland, Ivan; Ebergen, Jo (August 2002), "Computers without Clocks" (PDF), Scientific American, 287 (2): 62–69, Bibcode:2002SciAm.287b..62S, doi:10.1038/scientificamerican0802-62, PMID 12140955, archived from the original (PDF) on 2004-12-14
• 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.
• Noergaard, T. (2012). Embedded Systems Architecture: A Comprehensive Guide for Engineers and Programmers. Embedded technology series. Elsevier Science. ISBN 978-0-12-382197-3. Retrieved 2023-07-25.
• Gottlieb, Allan (1999). "Class Notes for Computer Architecture". cs.nyu.edu. New York University. Retrieved 25 July 2023.

External links

• Digital Logic Metastability
• Metastability Performance of Clocked FIFOs
• The 'Asynchronous' Bibliography Archived 2020-08-08 at the Wayback Machine
• Efficient Self-Timed Interfaces for Crossing Clock Domains