64 bit priority encoder

[suchitra]

Hello I wish to implement a synthesisable code for 64 bit priority
encoder which should work on 500 Mhz. The normal if else statements
will infer a combinatoral which will fail in timing. Can any one
suggest an alternative method.
I tried to look for something called lookahead priority encoder but
didnot get any nice article on it.
looking fordward for your replies
Regards
Suchitra

 

[glen herrmannsfeldt]

John_H wrote:
(snip)

If you have 8 priority encoders 8-bits each, the outputs would be fed to
another 8-bit priority encoder where the enables are the OR of the 8 enables
that fed each stage. You get the rough equivalent of the lookahead carry
without some of the hassle.

Yes, just like other recursive algorithms.

But 500 MHz?

As above, but add pipeline registers between each one, but
500MHz is pretty fast. It might be that six levels of two bit
priority encoders and appropriate pipeline registers could do
it. How fast is your logic, and how wide are the gates?

You can't get faster than one level of logic between latches,
though if you are doing this in an ASIC consider the Earle latch.

-- glen

 

[John_H]

"suchitra" <ssbhide@rediffmail.com> wrote in message
news:110cc2fe.0502020843.35f9bba@posting.google.com...

Hello I wish to implement a synthesisable code for 64 bit priority
encoder which should work on 500 Mhz. The normal if else statements
will infer a combinatoral which will fail in timing. Can any one
suggest an alternative method.
I tried to look for something called lookahead priority encoder but
didnot get any nice article on it.
looking fordward for your replies
Regards
Suchitra

Consider fast carry chains. Can you get a 64-bit adder working in your
target architecture at 500 MHz? The same issues of pipelining apply: if
you can spare an extra clock cycle, it's a lot easier to get that adder - or
priority encoder - running at speed.

A priority encoder and an adder share many characteristics. If you can
understand how the carry chain in a Xilinx FPGA works, you can see how the
priority encoder drops easily into a carry chain structure. Rather than
passing a carry bit unchanged if the A+B value is 1 and generating the carry
if this 2-bit sum is 0 or 2, the lower priority level is passed unchanged if
the current priority enable is 0 and generated if the priority enable is 1
at that stage.

The carry-lookahead has a "propagate/generate" characteristic for each
block. If the block size is 4 bits, the propagate would be asserted for a
sum of 15. The generate would force a carry out if the sum were 16 or
higher or force no carry for 14 or lower. This allows the partial sums to
be computed before the carries are available from the lower stages.

The lookahead priority encoder would do the same thing. If any of the
priority enables are active in a block, that block generates a "carry out"
to the higher priority stages. If there are no active enables, the "carry
out" from the previous priority encoder stages is propagated to the next
stage.

If you have 8 priority encoders 8-bits each, the outputs would be fed to
another 8-bit priority encoder where the enables are the OR of the 8 enables
that fed each stage. You get the rough equivalent of the lookahead carry
without some of the hassle.

But 500 MHz?