4 ms·

Kinniment expands on the idea at length in [1]. Chaney is another good source on the history of arbiters [2]. Specialists in asynchronous circuit design think a

Kinniment expands on the idea at length in [1]. Chaney is another good source on the history of arbiters [2]. Specialists in asynchronous circuit design think about arbiters a lot. Alex Yakovlev and Alain Martin have published some papers about them. [1] http://www.async.org.uk/David.Kinniment/DJKinniment-He-Who-Hesitates-is-Lost.pdf http://www.async.org.uk/David.Kinniment/DJKinniment-He-Who-H... [2] https://arl.wustl.edu/~jst/cse/260/glitchChaney.pdf https://arl.wustl.edu/~jst/cse/260/glitchChaney.pdf edit: typo

Animats 4y ago
And, finally, here's a data sheet for a 74F786 4-bit asynchronous bus arbiter IC.[1] Here's the answer to the paradox of Buridan's ass[2], in a 16-pin dual inline package. It doesn't take free will. "The 74F786 is designed so that contention between two or more request signals will not glitch or display a metastable condition. In this situation an increase in the BRn to BGn tPHL may be observed. A typical 74F786 has an h = 6.6ns, t = 0.41ns and To = 5µsec." "If two or more BRn inputs are asserted at precisely the same time, one of them will be selected at random, and all BGn outputs will be held in the high state until the selection is made. This guarantees that an erroneous BGn will not be generated even though a metastable condition may occur internal to the device." So, usually, you get a win within a specified time, but sometimes it takes longer. The limit on the longest time is probabilistic, but the odds of settling increase rapidly with time, by orders of magnitude per nanosecond. In this part, we get to see a simple standalone arbiter with its own data sheet. A logic diagram is given, so you can see how this is built out of simple gates. Note that diagram can't be read as abstract logic; propagation delay matters. While the arbiter is in a metastable state, an inhibit signal is generated which prevents any output from appearing. Once the arbiter has settled, the winning output is allowed out. The gate thresholds matter. The inhibit signal doesn't turn off until there's only one clear winner. It's an old part, from 1991, because today this function is usually part of a larger function such as a CPU chip or a DRAM interface. [1] https://www.digikey.com/en/htmldatasheets/production/96092/0/0/1/74f786.html https://www.digikey.com/en/htmldatasheets/production/96092/0... [2] https://en.wikipedia.org/wiki/Buridan%27s_ass https://en.wikipedia.org/wiki/Buridan%27s_ass

Animats 4y ago

And, finally, here's a data sheet for a 74F786 4-bit asynchronous bus arbiter IC.[1] Here's the answer to the paradox of Buridan's ass[2], in a 16-pin dual inline package. It doesn't take free will. "The 74F786 is designed so that contention between two or more request signals will not glitch or display a metastable condition. In this situation an increase in the BRn to BGn tPHL may be observed. A typical 74F786 has an h = 6.6ns, t = 0.41ns and To = 5µsec." "If two or more BRn inputs are asserted at precisely the same time, one of them will be selected at random, and all BGn outputs will be held in the high state until the selection is made. This guarantees that an erroneous BGn will not be generated even though a metastable condition may occur internal to the device." So, usually, you get a win within a specified time, but sometimes it takes longer. The limit on the longest time is probabilistic, but the odds of settling increase rapidly with time, by orders of magnitude per nanosecond. In this part, we get to see a simple standalone arbiter with its own data sheet. A logic diagram is given, so you can see how this is built out of simple gates. Note that diagram can't be read as abstract logic; propagation delay matters. While the arbiter is in a metastable state, an inhibit signal is generated which prevents any output from appearing. Once the arbiter has settled, the winning output is allowed out. The gate thresholds matter. The inhibit signal doesn't turn off until there's only one clear winner. It's an old part, from 1991, because today this function is usually part of a larger function such as a CPU chip or a DRAM interface. [1] https://www.digikey.com/en/htmldatasheets/production/96092/0/0/1/74f786.html https://www.digikey.com/en/htmldatasheets/production/96092/0... [2] https://en.wikipedia.org/wiki/Buridan%27s_ass https://en.wikipedia.org/wiki/Buridan%27s_ass