Difference between revisions of "Arbiter"
(Add an important point) |
(Mention close to perfection) |
||
| Line 10: | Line 10: | ||
If the incoming signals are aligned 'just right' (in other words, 'just wrong'), this process can be subject to [[meta-stability]] issues, if the circuitry is constructed of standard digital components ([[flip-flop]]s, etc). | If the incoming signals are aligned 'just right' (in other words, 'just wrong'), this process can be subject to [[meta-stability]] issues, if the circuitry is constructed of standard digital components ([[flip-flop]]s, etc). | ||
| − | One common solution is to use a special-purpose component called a 'three- | + | One common solution is to use a special-purpose component called a 'three-output flip-flop', which has a 'not done yet' output in addition to the normal '0' and '1' outputs. The third output is produced by the addition of two analog comparators, which look at the output, and check to see if it is above a low margin, and below a high margin (i.e. the output has not yet settled into one state or another). |
| − | Even this kind of arbiter is not ''guaranteed'' to produce an answer within a fixed, bounded time (it is currently believed that this is theoretically impossible), but at least the user is aware that such an arbiter is still dithering. | + | Even this kind of arbiter is not ''guaranteed'' to produce an answer within a fixed, bounded time (it is currently believed that this is theoretically impossible), but at least the user is aware that such an arbiter is still dithering. By suitable engineering, it is however possible to create arbiters that do meet a modest timing limit an extremely high percentage of the time (with failure rates on the order of centuries). |
== Further reading== | == Further reading== | ||
Revision as of 16:44, 2 December 2016
A arbiter is a device which examines two or more signals which are either:
- synchronous, but using clocks which are not fixed relative to one another; or
- at least one is asynchronous
and decides which of them arrived first.
For signals that arrive more or less simultaneously, it is usually more important that the arbiter pick one relatively quickly, without dithering too long over the choice. That is because the chief function of an arbiter is usually to provide mutual exclusion; i.e. to prevent two different clients from trying to use a single resource at the same time.
If the incoming signals are aligned 'just right' (in other words, 'just wrong'), this process can be subject to meta-stability issues, if the circuitry is constructed of standard digital components (flip-flops, etc).
One common solution is to use a special-purpose component called a 'three-output flip-flop', which has a 'not done yet' output in addition to the normal '0' and '1' outputs. The third output is produced by the addition of two analog comparators, which look at the output, and check to see if it is above a low margin, and below a high margin (i.e. the output has not yet settled into one state or another).
Even this kind of arbiter is not guaranteed to produce an answer within a fixed, bounded time (it is currently believed that this is theoretically impossible), but at least the user is aware that such an arbiter is still dithering. By suitable engineering, it is however possible to create arbiters that do meet a modest timing limit an extremely high percentage of the time (with failure rates on the order of centuries).
Further reading
- Warren Mackie Littlefield, Thomas J. Chaney, "The Glitch Phenomenon", Technical Memo No. 10, Washington University in St. Louis, 1966 - An extensive look at early WUSTL work on meta-stability, it includes an amusing analogy to describe the arbiter meta-stability problem
- David J. Kinniment, John V. Woods, "Synchronization and Arbitration Circuits in Digital Systems", Proceedings of the IEEE, Vol. 123, pp. 961-966, 1976 - A crisp description of the three-output flip-flop solution
