2048 input or gate ?

On Mon, 17 Jul 2006 18:04:33 GMT, "John_H" <johnhandwork@mail.com>
wrote:
...
>> Ain't optimization fun?
>
>I thought through this too quickly.  The first stage in the example I was 
>drawing out could do 64-wide ORs with the first carry chain which is 8 
>slices or 7*Tbyp, not 2*Tbyp.  The second stage would be from 32 carry 
>chains for 4 slices of MUXCY-based OR for 3*Tbyp, not 2*Tbyp so the timing 
>would be more like 6.137 ns, still significantly better than the LUT tree.
>
>I missed the 56 elements mentioned initially; this is probably just poor 
>partitioning, relying instead on a "maximum carry width" value.
>
>I'd manually partition the OR into two sets based on the 2 levels of 
>carries.  The generate can be used to shorthand the 32 intermediate values. 
>The KEEP attribute may be what's needed in XST - I use the syn_keep=1 in the 
>synplicity synthesizer.  This synthesized okay but I didn't put a wrapper 
>around it to get into a physiacl part (2k I/O is too much for me).
...

Thanks John and everyone else,
So far I tried all three options. It turns out a LUT4 tree is slightly
faster at 6.26ns  than what XST comes up with (6.613ns) where as the
number of LUT4s go from 515 to 811. John's two level LUT4+muxcy on the
other hand has a delay of 4.94ns at 648 LUT4s.
In terms of generating the LUT4 tree by hand, I used 5 different
generate statements with keeps on the outputs which convinces XST to
give me what I wanted. By the way 32x64 vs 64x32 partition does not
make a difference but 64x32 is very slightly larger.

"mk" <kal*@dspia.*comdelete> wrote in message 
news:rs5lb2ltpdofqci81sr6hnvpjraub3rduc@4ax.com...
> Thanks John and everyone else,
> So far I tried all three options. It turns out a LUT4 tree is slightly
> faster at 6.26ns  than what XST comes up with (6.613ns) where as the
> number of LUT4s go from 515 to 811. John's two level LUT4+muxcy on the
> other hand has a delay of 4.94ns at 648 LUT4s.
> In terms of generating the LUT4 tree by hand, I used 5 different
> generate statements with keeps on the outputs which convinces XST to
> give me what I wanted. By the way 32x64 vs 64x32 partition does not
> make a difference but 64x32 is very slightly larger.

I would have thought the result would be 512+16+1 LUTs -- 2048/4 LUTs 
feeding 64 carry chains, 64/4 LUTs feeding the final carry chain, and 1 to 
register the carry at the top of the chain -- for 539 total, not 648.
_____

For the OR tree, rather than 5 generates you could be creative with one big 
wire and do one generate loop:

(*KEEP*) wire [681:0] ORs;  // 512+128+32+8+2 intermediate OR results
wire [2729:0] XtraWideOR = {ORs,inr};
generate
  genvar i;
  for( i=0; i<682; i=i+1)
  begin : ORtree
    ORs[i] = |XtraWideOR[i*4 +: 4];
  end
endgenerate
assign outw = |XtraWideOR[682*4 +: 2];

Symon wrote:
> "Ben Jones" <ben.jones@xilinx.com> wrote in message
> news:e9gfcl$4mg1@cliff.xsj.xilinx.com...
> >
> > Hope this makes sense... perhaps someone can take it a step further and
> > work
> > out where the 56 levels thing really comes from (and thus deduce what this
> > particular synthesis tool believes the LUT:CY speed ratio is!).
> >
> > Cheers,
> >
> >        -Ben-
> >
> Hi Ben,
> Thanks for that, it made sense to me. I think we might need to know what
> part the design was in because the carry chain length is limited by the
> number of rows in the FPGA. Smaller parts have smaller maximum length
> chains. Also, as a BTW, I see from the datasheet that the ORCY structure
> that was in V2PRO has been dropped from the V4. That made wide gates even
> faster.

It makes some sense, but I think the fastest approach is to use
combinations in layers.  With the large discrepancy in speed, it makes
sense to use a lot of input in a single carry chain.  But the carry
chain is by nature serial and the delays keep adding.  The delays with
LUTs can be done in parallel using a pyramid structure.  I think the
fastest approach would be to combine the two in a pyramid of LUTs and
carry chains like they have been discussing above.

One way to compare the two is to consider building up from a single
LUT.  With four inputs to a LUT, you can combine four single LUTs to
another LUT for 16 inputs with two LUT delays.  Using the 12:1
approximation for the ratio of delays in the two, you can combine 12
LUTs for 48 inputs and get two LUT delays using the carry chain.
Clearly this is faster on the first level.

So let's consider increasing the size by a factor of four by combining
four, 48-input carry chains using a LUT.  This will give 192 inputs
with three LUT delays.  To do that in a longer carry chain, you would
get 5 LUT delays.  So clearly it is better at some point to break the
carry chains and combine their outputs with a LUT.  I am assuming that
you can not run one carry chain into another without using a LUT.  In
fact, I seem to recall that to get an output from a carry chain you
need to use a LUT.  So maybe my delay calculations are flawed since the
12:1 ration does not account for the required end of chain LUT.  In
fact, I am pretty sure that makes the carry chain slower than a pyramid
of LUTs.

Anyone know the details of connecting the output of the carry chain in
V4 parts?

rickman wrote:
> It makes some sense, but I think the fastest approach is to use
> combinations in layers.  With the large discrepancy in speed, it makes
> sense to use a lot of input in a single carry chain.  But the carry
> chain is by nature serial and the delays keep adding.  The delays with
> LUTs can be done in parallel using a pyramid structure.  I think the
> fastest approach would be to combine the two in a pyramid of LUTs and
> carry chains like they have been discussing above.
> 
> One way to compare the two is to consider building up from a single
> LUT.  With four inputs to a LUT, you can combine four single LUTs to
> another LUT for 16 inputs with two LUT delays.  Using the 12:1
> approximation for the ratio of delays in the two, you can combine 12
> LUTs for 48 inputs and get two LUT delays using the carry chain.
> Clearly this is faster on the first level.
> 
> So let's consider increasing the size by a factor of four by combining
> four, 48-input carry chains using a LUT.  This will give 192 inputs
> with three LUT delays.  To do that in a longer carry chain, you would
> get 5 LUT delays.  So clearly it is better at some point to break the
> carry chains and combine their outputs with a LUT.  I am assuming that
> you can not run one carry chain into another without using a LUT.  In
> fact, I seem to recall that to get an output from a carry chain you
> need to use a LUT.  So maybe my delay calculations are flawed since the
> 12:1 ration does not account for the required end of chain LUT.  In
> fact, I am pretty sure that makes the carry chain slower than a pyramid
> of LUTs.
> 
> Anyone know the details of connecting the output of the carry chain in
> V4 parts?

In the Spartan3E parts (things may vary for the Virtex4) the exit from a 
MUXCY (as opposed to an XORCY used in an adder) can be directly onto 
routing.  The timing report will go straight from a Tbyp delay to the net.

For 4^n inputs ORed in a LUT tree (or pyramid) the additive delay will 
be n*Tilo+(n-1)*Tnet.  For one carry chain, the additive delay will be 
Topcyf+((4^n)/8-1)*Tbyp.  For my Spartan3E, -5 speed grade, the carry 
chain is better at n=2-4; I'm surprised the numbers work for n=2 but 
that comes from a history where carry chains were tough to get on and 
off (here we only have to sweat getting on the carry chain, off is free).

If the problem were a 256-wide OR or a 16k-wide OR, an extra level of 
LUTs would work out well with one or two carry chain stages, 
respectively.  The numbers may skew slightly for other families but the 
timing reports will show what the makeup is for the various paths - 
including routing - to make a better determination of what's "best."

"rickman" <spamgoeshere4@yahoo.com> wrote in message
news:1153186786.804902.220530@h48g2000cwc.googlegroups.com...

> Anyone know the details of connecting the output of the carry chain in
> V4 parts?

The quickest way off the carry chain, believe it or not, is to use the XORCY
element (with a 0 input from the fabric, or a 1 if you want inversion). This
is faster than going up to the next LUT and using the dedicated output. This
still takes a few hundred picoseconds though (check the timing files for the
exact number).

<plug> In Virtex 5, the carry chain structure has got *much* faster relative
to the rest of the fabric, both in terms of propagation delay and time to
get on/off the chain... :-) </plug>

Cheers,

        -Ben-

Ben Jones wrote:
> 
> <plug> In Virtex 5, the carry chain structure has got *much* faster relative
> to the rest of the fabric, both in terms of propagation delay and time to
> get on/off the chain... :-) </plug>

Hi Ben,
  Great, so does that mean Webpack will (soon?) allow designers to 
actually use the Virtex 5 family ?

-jg

"Ben Jones" <ben.jones@xilinx.com> wrote in message 
news:e9i89j$63f1@cliff.xsj.xilinx.com...
>
> <plug> In Virtex 5, the carry chain structure has got *much* faster 
> relative
> to the rest of the fabric, both in terms of propagation delay and time to
> get on/off the chain... :-) </plug>
>
Hi Ben,
C'mon, dish the numbers! :-) Is it looking ahead further, or has the chain 
itself got faster?
Cheers, Syms. 

"Symon" <symon_brewer@hotmail.com> wrote in message
news:44bcd307$1_1@x-privat.org...
> "Ben Jones" <ben.jones@xilinx.com> wrote in message
> news:e9i89j$63f1@cliff.xsj.xilinx.com...
> >
> > <plug> In Virtex 5, the carry chain structure has got *much* faster
> > relative
> > to the rest of the fabric, both in terms of propagation delay and time
to
> > get on/off the chain... :-) </plug>
> >
> C'mon, dish the numbers! :-) Is it looking ahead further, or has the chain
> itself got faster?

So, each slice now has four LUTs and four FFs. Consequently, there are four
MUXCY/XORCY pairs in each slice's subchain. The Tbyp (i.e. cin-to-cout
delay) for the slice is on the order of 80ps. So that works out to around
20ps per LUT, or twice as fast as in Virtex-4.

I am not a sub-micron designer, so I don't really know how they achieved it
:) but I'll bet it's a combination of the two factors you mentioned.

Cheers,

    -Ben-

"Jim Granville" <no.spam@designtools.co.nz> wrote in message
news:44bcbff9$1@clear.net.nz...
> Ben Jones wrote:
> >
> > <plug> In Virtex 5, the carry chain structure has got *much* faster
relative
> > to the rest of the fabric, both in terms of propagation delay and time
to
> > get on/off the chain... :-) </plug>
>
> Hi Ben,
>   Great, so does that mean Webpack will (soon?) allow designers to
> actually use the Virtex 5 family ?

I, like you, am surprised that it doesn't (even in the 8.2i release).
Doubtless there is a justification somewhere in terms of reduced burden on
the technical support hotline or some-such... bah!

Then again, the full ISE suite isn't all that expensive... <ducks> :)

Cheers,

    -Ben-

"Ben Jones" <ben.jones@xilinx.com> wrote in message 
news:e9is6s$63f2@cliff.xsj.xilinx.com...
>
> I am not a sub-micron designer,
>
Just as well, you wouldn't be able to reach your keyboard! :-)
>
> so I don't really know how they achieved it
> :) but I'll bet it's a combination of the two factors you mentioned.
>
Yep, sounds like it. Thanks for that heads-up.
Cheers, Syms.