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:

  http://www.iccd-conference.org/proceedings/1998/90990360.pdf

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

  http://citeseer.ist.psu.edu/maheswaran94hazardfree.html

Thanks for any pointers...

  - a

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

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, speculating at home.

=================================
Adam Megacz wrote:
> 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:
>
>   http://www.iccd-conference.org/proceedings/1998/90990360.pdf
>
> This paper claims to have a solution, but doesn't go into detail, so I
> suspect that they may be overlooking something.
>
>   http://citeseer.ist.psu.edu/maheswaran94hazardfree.html
>
> Thanks for any pointers...
>
>   - a
> 
> -- 
> PGP/GPG: 5C9F F366 C9CF 2145 E770  B1B8 EFB1 462D A146 C380

Peter Alfke schrieb:

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

22V10 ??

SCNR ;-)

Regards
Falk

Adam Megacz wrote:

> 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

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

          -- Mike Treseler

Falk Brunner wrote:

> Peter Alfke schrieb:
> 
>> 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.
> 
> 
> 22V10 ??
> 
> SCNR ;-)

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

Adam Megacz  wrote
>
> 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.

Googling for "self-timed arbiter fpga" throws up several hits. At a very 
quick glance, this paper 
http://www.cl.cam.ac.uk/~swm11/research/papers/iccd1998.pdf 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." 

Since signals A and B are each driven through interconnects with
unavoidable delay differences, any attempt to find out which of the two
signals arrived first has an unavoidable error. That error is much
larger than the width of the metastability capture window, which is
only fractional femtoseconds in a modern FPGA flip-flop.
The stated problem is not only unsolvable, but inherently meaningless.
How many angels can dance on the tip of a pin?
Peter Alfke, Xilinx

==================
Adam Megacz wrote:
> 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:
>
>   http://www.iccd-conference.org/proceedings/1998/90990360.pdf
>
> This paper claims to have a solution, but doesn't go into detail, so I
> suspect that they may be overlooking something.
>
>   http://citeseer.ist.psu.edu/maheswaran94hazardfree.html
>
> Thanks for any pointers...
>
>   - a
> 
> -- 
> PGP/GPG: 5C9F F366 C9CF 2145 E770  B1B8 EFB1 462D A146 C380

Peter Alfke wrote:

>Since signals A and B are each driven through interconnects with
>unavoidable delay differences, any attempt to find out which of the two
>signals arrived first has an unavoidable error. That error is much
>larger than the width of the metastability capture window, which is
>only fractional femtoseconds in a modern FPGA flip-flop.
>  
>
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

Un bel giorno Adam Megacz digit�:

> By robust, I mean that it works correctly with
> probability=1

I think Heisenberg would have something to argue about this.

-- 
asd

Jon Elson wrote:
> > 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
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