clockless arbiters on fpgas?

I've been having a really hard time coming up with a design for a robust clockless arbiter in an FPGA, and was wondering if anybody here can provide input. By robust, I mean that it works correctly with probability=1 and its output never glitches, but may take an unbounded amount of time to resolve.

Charles Seitz describes a solution in custom VLSI on page 260 of Mead and Conway's _Introduction to VLSI Systems_, but this assumes you have control over gate threshholds and can make some of them substantially higher than others.

The basic component that causes problems is the "interlock", a module with two inputs A,B and two outputs X,Y.

+---------------+ A -----> | | -----> X | Interlock | B -----> | | -----> Y +---------------+

All signals start low. If A+ (A rises) before B+, then X+. If B+ before A+, then Y+. Once one of the outputs rises, the other one will not rise until the device is reset (assume some sort of reset signal). The important part here is that the interlock can take as long as it likes to raise one of the outputs, but it must raise exactly one of them, and cannot lower it once raised (ie no glitching).

I'm working with Atmel FPGAs, but advice based on other devices would be just as helpful. I thought of using the "internal feedback line" to feed one of the 3-LUT's outputs back into one of its inputs as half of an interlock -- the state of the feedback line being used to determine if signal A+ has already arrived. But the problem is that you might have A+ arrive, which causes the output of the 3-LUT to transition, but then B+ might arrive *before* the LUT's output transition arrives back at the third input to the LUT.

Any pointers? I've come across a rather depressing paper concluding that this isn't possible on the (extremely old) XC4000, but I'm sort of hoping against hope that things may have changed:

formatting link

This paper claims to have a solution, but doesn't go into detail, so I suspect that they may be overlooking something.

formatting link

Thanks for any pointers...

- a

--
PGP/GPG: 5C9F F366 C9CF 2145 E770  B1B8 EFB1 462D A146 C380
Reply to
Adam Megacz
Loading thread data ...

I think your problem inherently cannot be solved if you assume that A and B can start rising at any time, and that input thresholds and through-delays can vary by small amounts, as thy inevitably will.

If you reduce your requirements to an unambiguous output, even if it is the "wrong" one (whatever wrong means when things happen essentially simultaneously) then the problem reminds me of metastability resolution, which will usually occur in a short time (although theoretically -but only theoretically- unbounded).

The faster the circuitry, the smaller your "no-man's land" of uncertainty, and the faster the resolutio. I would, therefore, go with the fastest LUT-based FPGA. You can imagine which one I have in mind.

So: theoretically it's unsolvable, but you can get very close with modern circuits... Peter Alfke, speculat> I've been having a really hard time coming up with a design for a

Reply to
Peter Alfke

Peter Alfke schrieb:

22V10 ??

SCNR ;-)

Regards Falk

Reply to
Falk Brunner

They haven't. Adding a clock and using standard synchronization techniques will be ten times easier that any alternative.

-- Mike Treseler

Reply to
Mike Treseler

When Peter wrote that, my imagination jumped to the new (claimed ) 2GHz Async FPGAs , still comming... ;)

-jg

Reply to
Jim Granville

Adam Megacz wrote

Googling for "self-timed arbiter fpga" throws up several hits. At a very quick glance, this paper

formatting link
seems relevant. In essence it's externally self-timed, but generates an internal clock when needed.

Here is a quote from the paper, supporting other remarks in this thread: "Designing an arbiter on an FPGA is even more dificult. In order to minimise metastability effects the built in flip-flops must be used. typically D-latches. since they will have the highest gain and lowest feedback times."

Reply to
Tim

Reply to
Peter Alfke

I think in the case where the two inputs rise almost simultaneously, then it may be more important that the arbiter resolves one and only one output, than it correctly identify which one was first.

Jon

Reply to
Jon Elson

Un bel giorno Adam Megacz digitò:

I think Heisenberg would have something to argue about this.

--
asd
Reply to
dalai lamah

That's what I addressd in my first response: "If you reduce your requirements to an unambiguous output, even if it is the "wrong" one (whatever wrong means when things happen essentially simultaneously) then the problem reminds me of metastability resolution, which will usually occur in a short time (although theoretically -but only theoretically- unbounded)."

Given any specific test condition, every additional nanosecond of tolerable output delay increases the MTBF by ten decimal orders of magnitude (every extra 100 ps increases the MTBF a factor of ten). This was taken from XAPP094, which describes metastable recovery, essentially the same problem... And Heisenberg is in agreement, I checked with him ;-) Peter Alfke, Xilinx

Reply to
Peter Alfke

Rats! I've been counting the ones dancing on the head of the pin. :-)

Marc

Reply to
Marc Guardiani

I googled and found this: "Let's get a couple things straight. First, you're misquoting the saying in question. According to unimpeachable sources, it's not how many angels can dance on the head of a pin, it's how many can do it on the point of a needle--which, of course, makes more sense. Second, the earliest citation I can find is from a book by Ralph Cudworth in the

17th century, which is a suspiciously late in the day." from "The Straight Dope"

"Head of a needle" never seemed to convey the intended meaning... Peter Alfke

Reply to
Peter Alfke

Thanks, Tim; that was actually the same paper I posted in my question.

- a

--
PGP/GPG: 5C9F F366 C9CF 2145 E770  B1B8 EFB1 462D A146 C380
Reply to
Adam Megacz

Thanks, Mike.

One more question: is there any serious disadvantage to using a clocked DFF directly as an "arbiter" rather than generating some artificial ring-oscillator-clock?

The scenario I'm thinking of is to have both the D and CLK lines into the FF low, and then both of them rise. If CLK rises first, then Q=0; if D rises first then Q=1. This acts as a very crude arbitration primitive -- not the entire solution [*].

The only disadvantage I can think of is that the oscillator-clock arbiter's MTBF is unrelated to the timing of the inputs you hand it (the clock signal is effectively "random" compared to the async input, so the probability of a setup/hold failure is a nicely distributed random variable). Using my scheme, the MTBF depends on how often you have "close" arbitrations -- if you have lots of them it has a worse MTBF (than an oscillator-clock), if you have fewer of them it has a better MTBF (than an oscillator-clock). - a

[*] Beyond this I would have to OR each input signal with a delayed fanout of the other signal, so that one of them could "win" even if the other one never showed up. Additionally, I'd probably want at least two layers of DFFs -- so that the second layer can mask any fluctuations on the output of the first DFF. But racing CLK against D is really the only part I have doubts about.
--
PGP/GPG: 5C9F F366 C9CF 2145 E770  B1B8 EFB1 462D A146 C380
Reply to
Adam Megacz

Adam, as I explained earlier: You are trying to detect something that is inherently meaningless. Since unknown delay differences "in front of" your circuit are much larger than the inherent ambiguity of the detector, it is meaningless to fight the small metastability window, when you have perhaps nanoseconds, and definitely pioseconds of funcertainty elswhere.

You can get a clear and def> Mike Treseler writes:

Reply to
Peter Alfke

Hi, Peter,

I think I may not have stated my request precisely enough. The device does not need to determine which signal "wins the race"; it just needs to unambiguously award the trophy to one of the runners.

An arbiter is still an arbiter when you add a delay line to one of its inputs: it still performs the essential function of choosing an unambiguous winner, even if it favors one side over the other.

- a

Reply to
Adam Megacz

Here's how you would do this in an ASIC (see page 6, top left slide)

formatting link

The four transistors on the right basically measure the voltage difference between the two NAND outputs, watching for them to be separated by at least Vth. There's another version where you use high-threshhold gates instead.

Obviously you can't reproduce exactly this circuit in an FPGA. I'm just posting this to show the thing I'm trying to imitate.

- a

Reply to
Adam Megacz

Reply to
Peter Alfke

Adam> > Here's how you would do this in an ASIC (see page 6, top left slide) Adam> >

formatting link

Peter> Adam, if you read the second posting in this thread, that's exactly Peter> what I described there. We could have saved ourselves a lot of Peter> postings...

Hrm, do you mean this posting [below]? This is very, very different from a Seitz Arbiter... without the voltage-differencing, the arbiter can fail (glitch, "change its mind", etc).

Peter> If you reduce your requirements to an unambiguous output, even if it is Peter> the "wrong" one (whatever wrong means when things happen essentially Peter> simultaneously) then the problem reminds me of metastability Peter> resolution, which will usually occur in a short time (although Peter> theoretically -but only theoretically- unbounded).

Peter> The faster the circuitry, the smaller your "no-man's land" of Peter> uncertainty, and the faster the resolutio. I would, therefore, go with Peter> the fastest LUT-based FPGA. You can imagine which one I have in mind.

Peter> So: theoretically it's unsolvable, but you can get very close with Peter> modern circuits...

--
PGP/GPG: 5C9F F366 C9CF 2145 E770  B1B8 EFB1 462D A146 C380
Reply to
Adam Megacz

If I may ask, what's your application for this ? That reminds me of something I saw recently : PUFs

Sylvain

Reply to
Sylvain Munaut

ElectronDepot website is not affiliated with any of the manufacturers or service providers discussed here. All logos and trade names are the property of their respective owners.