> The particular example I'm thinking of had a 128 in, 128 xor tree that 
> really shouldn't be any harder to synth than a CRC.  It's a linear 
> mapping stage in an SP block cipher (like AES, but not AES (which has a 
> relatively weak mixing function)).
> 
> Vivado gave (IIRC) 11 or 12 levels of logic rather than the expected 3 
> levels of logic.  Hmmm.  The revised source code (expressed as a bunch of 
> xors) produced 4 levels of logic, and routed to speed.
> 
Same here.  I have constant multiplier matrices and each has a column weight of about 160 so I end up with a 160-input XOR for each column.  Ideally that would be log6(160)=2.8 levels.  First I have to use very low-level code and even then Vivado shares subexpressions too much and I end up with 6 levels unless I isolate column groups in different modules.  If I isolate each column in its own module I can get the 3 levels.  Isolating column groups also means they are placed as a group which reduces wirelengths.

> The Xilinx DSP48E2 has a wide xor mode that I think can give a 96 input 
> xor in a single DSP48E2 slice.  I've never tried it.

Yeah, I looked into this at one point but decided against it for a few reasons.  I thought a nice feature would be to be able to turn off the carries in the DSP48 and then you could use them for GF multipliers.  I have used DSP48s as GF(2) accumulators and I've used them as transposers to extract column data from rows stored in RAMs.

On Thu, 04 May 2017 10:56:56 -0700, Kevin Neilson wrote:

>> I use Vivado to do GF multiplications that wide using purely
>> behavioural VHDL.  BTW, A straightforward behavioural implementation
>> will *not* give good results with a wide bus.
>> I believe the problem is that most tools (in particular Vivado) do a
>> poor job of synthesising xor trees with a massive fanin (e.g. >> 100
>> bits). The optimisers have a poor complexity (I guess at least O(N^2),
>> but it might be exponential) wrt the size of the function.
>> 
>> You can use all sorts of mathematical tricks to make it work without
>> need to go "low level".
>> For example, to deal with large fanin, partition your 512 bit input
>> into N slices of 512/N bits each.  Use N multipliers, one for each
>> slice, put a keep (or equivalent) attribute on the outputs, then xor
>> the outputs together.  This gives the same result, uses about the same
>> number of LUTs,
>> but gives the optimiser in the tool a chance to do a good job.
>> 
>> 
>> I use the same GF multiplier code in ISE and Quartus, too (but not on
>> buses that wide).
>> 
>> The entire flow is in VHDL and works in any LRM-compliant tool.  It's
>> parameterised, too, so I don't need to rewrite for a different bus
>> width.
>> 
>> 
>> I've been using similar approaches in VHDL since the turn of the
>> century and have never been burned.
>> 
>> YMMV.
>> 
>> Regards,
>> Allan
> 
> I used to do big GF matrix multiplications in which you could set
> parameters for the field size and field generator poly, etc.  Vivado
> just gets bogged down.  Now I just expand that into a GF(2) matrix in
> Matlab and dump it to a parameter and all Vivado has to know how to do
> is XOR.
> 
> I also have problems with the wide XORs.  Multiplication by a big GF(2)
> matrix means a wide XOR for each column.  Vivado tries to share LUTs
> with common subexpressions across the columns.  Too much sharing.  That
> sounds like a good thing, but it's not smart enough to know how much
> it's impacting timing.  You save LUTs, but you end up with a routing
> mess and too many levels of logic and you don't come close to meeting
> timing at all.  So then I have to make a generate loop and put
> subsections of the matrix in separate modules and use directives to
> prevent optimizing across boundaries.  (KEEPs don't work.)  It's all a
> pain.  But then I end up with something a little bigger but which meets
> timing.


I thought about my historical code some more, and I realised that I did 
have some examples of behavioural GF multipliers that didn't work as well 
as the same function expressed as a bunch of wide xors.

The particular example I'm thinking of had a 128 in, 128 xor tree that 
really shouldn't be any harder to synth than a CRC.  It's a linear 
mapping stage in an SP block cipher (like AES, but not AES (which has a 
relatively weak mixing function)).

Vivado gave (IIRC) 11 or 12 levels of logic rather than the expected 3 
levels of logic.  Hmmm.  The revised source code (expressed as a bunch of 
xors) produced 4 levels of logic, and routed to speed.

BTW, I used my VHDL testbench for the original function to write out the 
VHDL for the xor tree.

 
> I really wish there were a way to use the carry chains for wide XORs.

I think that carry chains (and similar structures) became less important 
for wide functions once six input LUTs became commonplace.

The Xilinx DSP48E2 has a wide xor mode that I think can give a 96 input 
xor in a single DSP48E2 slice.  I've never tried it.

Regards,
Allan

On 04/05/17 18:12, kristoff wrote:
> Hi all,
>
>
> As a follow-up in the RISC-V thread.
>
>
> On 02-05-17 18:11, kristoff wrote:
>> Or, you can "mix-match" licenses. Sifive (the company that sells the
>> E310 CPU and hifive devboards) are an interesting example of this.
>> They open-sourced the RTL design but keep the knowledge of actually
>> implementing a risc-v core as optimised as possible for themselfs, as a
>> service to sell.
>
> This was on eenews Europe today:
> http://www.eenewseurope.com/news/sifive-launches-commercial-risc-v-processor-cores
>
>
>
>
>
> As a small follow-up question:
> Does anybody have any idea how to get the hifive boards in Europe?
>

I got one from the crowdsupply site.  I haven't got round to trying it 
yet :-(

> For the last thing I ordered in the US (a pandaboard), I had to pay VAT
> (ok, that's normal), but also a handling-fee for the shipping-company
> and the customs-service to get the thing shipped in.
> In the end, these additional costs where more then the VAT itself.
>
>
>
> Cheerio! Kr. Bonne.

> I use Vivado to do GF multiplications that wide using purely behavioural=
=20
> VHDL.  BTW, A straightforward behavioural implementation will *not* give=
=20
> good results with a wide bus.
> I believe the problem is that most tools (in particular Vivado) do a poor=
=20
> job of synthesising xor trees with a massive fanin (e.g. >> 100 bits). =
=20
> The optimisers have a poor complexity (I guess at least O(N^2), but it=20
> might be exponential) wrt the size of the function.
>=20
> You can use all sorts of mathematical tricks to make it work without need=
=20
> to go "low level".
> For example, to deal with large fanin, partition your 512 bit input into=
=20
> N slices of 512/N bits each.  Use N multipliers, one for each slice, put=
=20
> a keep (or equivalent) attribute on the outputs, then xor the outputs=20
> together.  This gives the same result, uses about the same number of LUTs=
,=20
> but gives the optimiser in the tool a chance to do a good job.
>=20
>=20
> I use the same GF multiplier code in ISE and Quartus, too (but not on=20
> buses that wide).
>=20
> The entire flow is in VHDL and works in any LRM-compliant tool.  It's=20
> parameterised, too, so I don't need to rewrite for a different bus width.
>=20
>=20
> I've been using similar approaches in VHDL since the turn of the century=
=20
> and have never been burned.
>=20
> YMMV.
>=20
> Regards,
> Allan

I used to do big GF matrix multiplications in which you could set parameter=
s for the field size and field generator poly, etc.  Vivado just gets bogge=
d down.  Now I just expand that into a GF(2) matrix in Matlab and dump it t=
o a parameter and all Vivado has to know how to do is XOR.

I also have problems with the wide XORs.  Multiplication by a big GF(2) mat=
rix means a wide XOR for each column.  Vivado tries to share LUTs with comm=
on subexpressions across the columns.  Too much sharing.  That sounds like =
a good thing, but it's not smart enough to know how much it's impacting tim=
ing.  You save LUTs, but you end up with a routing mess and too many levels=
 of logic and you don't come close to meeting timing at all.  So then I hav=
e to make a generate loop and put subsections of the matrix in separate mod=
ules and use directives to prevent optimizing across boundaries.  (KEEPs do=
n't work.)  It's all a pain.  But then I end up with something a little big=
ger but which meets timing.

I really wish there were a way to use the carry chains for wide XORs.

> We had code that calculated, basically a shift table to calculate the CRC of a long word.
> The RTL code worked fine for ISE.  But when we hit Vivado, it'd pause 10 minutes or so 
> over each instance (we had lots) which significantly hit our build times.
> 
> So, I changed this code to "almost" self-modifying code.  The code would by default
> calculate the shift matrix using our "normal" RTL, which looked something like:
>       assign H_n_o = h_pow_n( H_zero, NUM_ZEROS_MINUS_ONE );
> where H_zero was an "matrix" of constants, and NUM_ZEROS_MINUS_ONE a static
> parameter.  The end result is a matrix of constants as well, but "dynamically"
> calculated. (Here "dynamically" means once at elaboration time, since all inputs
> to the function were static).
> 
> Then we just added code to dump each unknown table entry sort-of like:
>   if( ( POLY_WIDTH == 8 ) && ( NUM_ZEROS_MINUS_ONE == 7 ) && ( POLYNOMIAL == 'h2f ) )
>     assign H_n_o = 'hd4eaf52e175ffba9;
>   ...
>   else // no table entry - use default RTL calc
>     assign H_n_o = h_pow_n( H_zero, NUM_ZEROS_MINUS_ONE );
> 
> We "closed" the loop by hand.  If the "table" entry didn't exist, the tool would use the
> RTL definition, and spit out the pre-calculated entry.  All done in 
> verilog.   We insert that new table entry into our source code by hand, and continue - next
> time the build would be quicker.
> 
> This *workaround* was a bit kludge, but was the rare (only really) exception for us
> in our parameterized code.  Normally the tools just handled things fine.
> And again to be clear the only thing we were working around was long synthesis times.  
> The quality of results was fine in either case.
> 
> Maybe the code you were creating the pendulum swings the other way
> and it was more the norm, rather than the exception to see things like this.
> 
> Interesting topic, I'm glad to hear of your (and others) experiences.
> 
> Regards,
> 
> Mark

I looked up my notes for the LFSR I was referring to and one instance of the more-abstract version took 16 min to synthesize and the less-abstract version took less than a minute.  (And we needed many instances.)  When I try to do something at a higher level it ends up like your experience:  I have to do a lot of experiments to see what works and then tweak things endlessly.  It eats up a lot of time. 

Hi all,


As a follow-up in the RISC-V thread.


On 02-05-17 18:11, kristoff wrote:
> Or, you can "mix-match" licenses. Sifive (the company that sells the
> E310 CPU and hifive devboards) are an interesting example of this.
> They open-sourced the RTL design but keep the knowledge of actually
> implementing a risc-v core as optimised as possible for themselfs, as a
> service to sell.

This was on eenews Europe today:
http://www.eenewseurope.com/news/sifive-launches-commercial-risc-v-processor-cores




As a small follow-up question:
Does anybody have any idea how to get the hifive boards in Europe?

For the last thing I ordered in the US (a pandaboard), I had to pay VAT 
(ok, that's normal), but also a handling-fee for the shipping-company 
and the customs-service to get the thing shipped in.
In the end, these additional costs where more then the VAT itself.



Cheerio! Kr. Bonne.

On Wed, 03 May 2017 13:39:38 -0700, Kevin Neilson wrote:

>> (continuing a bit OT...)
>> 
>> Kevin,
>> 
>> That's unfortunate.  We've been very successful with writing
>> parameterizable code - even before SystemVerilog. Heck even before
>> Verilog-2001.  Things like N-Tap FIRs,
>> Two-D FIRs.  FFTs, Video Blenders, etc...  All with configurable
>> settings -
>> bit widths, rounding/truncation options/etc..  I think in a previous
>> job I had a parametizable Galois Field Multiplier too.
>> 
>> I'm not sure what trouble you had with the tools.  It takes a bit more
>> up front work, but pays off quite a bit in the end.  We really had no
>> choice, given the number of FPGAs we do, along with how many engineers
>> support them.  Lot's of shared code was the only way to go.
>> 
>> If you've got something you like, then I suggest keeping it.  But for
>> others,
>> I think writing parameterizable HDL isn't too much trouble - and is
>> made even easier with SystemVerilog.  And higher level too.
>> 
>> Regards,
>> 
>> Mark
> 
> I've just been burned too many times.  I know better now.  The last time
> I made the mistake I was just making a simple PN generator (LFSR).  The
> only complication was that it was highly parallel--I think I had to
> generate maybe 512 bits per cycle, so it ends up being a big matrix
> multiplication over GF(2).  First I made the high-level version where
> you could set a parameters for the width and taps and so on.  It took
> forever for Vivado to crank on it.  This is just a few lines of code,
> mind you, and is just a bunch of XORs.  Then I had Matlab generate an
> include file with the matrix packed into a long parameter which
> essentially sets up XOR taps.  That was, I think, ~20x faster, which
> translated into hours of synthesis time.  The synthesized circuit was
> also better for various reasons.  This is just one example.  I also
> still have to instantiate primitives frequently for various reasons. 
> The level of abstraction doesn't seem like it's changed much in 15 years
> if you really need performance.  This doesn't really have anything to do
> with the SystemVerilog constructs.  I'm just talking about high-level
> code in general.  If I were allowed, I would still use modports,
> structs, enums, etc.


I use Vivado to do GF multiplications that wide using purely behavioural 
VHDL.  BTW, A straightforward behavioural implementation will *not* give 
good results with a wide bus.
I believe the problem is that most tools (in particular Vivado) do a poor 
job of synthesising xor trees with a massive fanin (e.g. >> 100 bits).  
The optimisers have a poor complexity (I guess at least O(N^2), but it 
might be exponential) wrt the size of the function.

You can use all sorts of mathematical tricks to make it work without need 
to go "low level".
For example, to deal with large fanin, partition your 512 bit input into 
N slices of 512/N bits each.  Use N multipliers, one for each slice, put 
a keep (or equivalent) attribute on the outputs, then xor the outputs 
together.  This gives the same result, uses about the same number of LUTs, 
but gives the optimiser in the tool a chance to do a good job.


I use the same GF multiplier code in ISE and Quartus, too (but not on 
buses that wide).

The entire flow is in VHDL and works in any LRM-compliant tool.  It's 
parameterised, too, so I don't need to rewrite for a different bus width.


I've been using similar approaches in VHDL since the turn of the century 
and have never been burned.

YMMV.

Regards,
Allan

In article <a66c4c17-6f43-4aec-9dd5-c06badf5b11f@googlegroups.com>,
Kevin Neilson  <kevin.neilson@xilinx.com> wrote:
>> (continuing a bit OT...)
>> 
>> Kevin,
>> 
>> That's unfortunate.  We've been very successful with writing parameterizable code - even 
>> before SystemVerilog. Heck even before Verilog-2001.  Things like N-Tap FIRs, 
>> Two-D FIRs.  FFTs, Video Blenders, etc...  All with configurable settings - 
>> bit widths, rounding/truncation options/etc..  I think in a previous job I had a 
>> parametizable Galois Field Multiplier too.
>> 
>> I'm not sure what trouble you had with the tools.  It takes a bit more up front work,
>> but pays off quite a bit in the end.  We really had no choice, given the number of 
>> FPGAs we do, along with how many engineers support them.  Lot's of shared code
>> was the only way to go. 
>> 
>> If you've got something you like, then I suggest keeping it.  But for others,
>> I think writing parameterizable HDL isn't too much trouble - and is made
>> even easier with SystemVerilog.  And higher level too.
>> 
>> Regards,
>> 
>> Mark
>
>I've just been burned too many times.  I know better now.  The last time I made the mistake I was just making a simple PN generator (LFSR).  The
>only complication was that it was highly parallel--I think I had to generate maybe 512 bits per cycle, so it ends up being a big matrix
>multiplication over GF(2).  First I made the high-level version where you could set a parameters for the width and taps and so on.  It took forever
>for Vivado to crank on it.  This is just a few lines of code, mind you, and is just a bunch of XORs.  Then I had Matlab generate an include file
>with the matrix packed into a long parameter which essentially sets up XOR taps.  That was, I think, ~20x faster, which translated into hours of
>synthesis time.  The synthesized circuit was also better for various reasons.  This is just one example.  I also still have to instantiate
>primitives frequently for various reasons.  The level of abstraction doesn't seem like it's changed much in 15 years if you really need performance.
>This doesn't really have anything to do with the SystemVerilog constructs.  I'm just talking about high-level code in general.  If I were allowed, I
>would still use modports, structs, enums, etc.

Ah, we did find something similar in Vivado.  For use is was a large parallel 
CRC - which is pretty much functionally identical to your LFSR (big XOR trees).

We had code that calculated, basically a shift table to calculate the CRC of a long word.
The RTL code worked fine for ISE.  But when we hit Vivado, it'd pause 10 minutes or so 
over each instance (we had lots) which significantly hit our build times.

So, I changed this code to "almost" self-modifying code.  The code would by default
calculate the shift matrix using our "normal" RTL, which looked something like:
      assign H_n_o = h_pow_n( H_zero, NUM_ZEROS_MINUS_ONE );
where H_zero was an "matrix" of constants, and NUM_ZEROS_MINUS_ONE a static
parameter.  The end result is a matrix of constants as well, but "dynamically"
calculated. (Here "dynamically" means once at elaboration time, since all inputs
to the function were static).

Then we just added code to dump each unknown table entry sort-of like:
  if( ( POLY_WIDTH == 8 ) && ( NUM_ZEROS_MINUS_ONE == 7 ) && ( POLYNOMIAL == 'h2f ) )
    assign H_n_o = 'hd4eaf52e175ffba9;
  ...
  else // no table entry - use default RTL calc
    assign H_n_o = h_pow_n( H_zero, NUM_ZEROS_MINUS_ONE );

We "closed" the loop by hand.  If the "table" entry didn't exist, the tool would use the
RTL definition, and spit out the pre-calculated entry.  All done in 
verilog.   We insert that new table entry into our source code by hand, and continue - next
time the build would be quicker.

This *workaround* was a bit kludge, but was the rare (only really) exception for us
in our parameterized code.  Normally the tools just handled things fine.
And again to be clear the only thing we were working around was long synthesis times.  
The quality of results was fine in either case.

Maybe the code you were creating the pendulum swings the other way
and it was more the norm, rather than the exception to see things like this.

Interesting topic, I'm glad to hear of your (and others) experiences.

Regards,

Mark

> (continuing a bit OT...)
> 
> Kevin,
> 
> That's unfortunate.  We've been very successful with writing parameterizable code - even 
> before SystemVerilog. Heck even before Verilog-2001.  Things like N-Tap FIRs, 
> Two-D FIRs.  FFTs, Video Blenders, etc...  All with configurable settings - 
> bit widths, rounding/truncation options/etc..  I think in a previous job I had a 
> parametizable Galois Field Multiplier too.
> 
> I'm not sure what trouble you had with the tools.  It takes a bit more up front work,
> but pays off quite a bit in the end.  We really had no choice, given the number of 
> FPGAs we do, along with how many engineers support them.  Lot's of shared code
> was the only way to go. 
> 
> If you've got something you like, then I suggest keeping it.  But for others,
> I think writing parameterizable HDL isn't too much trouble - and is made
> even easier with SystemVerilog.  And higher level too.
> 
> Regards,
> 
> Mark

I've just been burned too many times.  I know better now.  The last time I made the mistake I was just making a simple PN generator (LFSR).  The only complication was that it was highly parallel--I think I had to generate maybe 512 bits per cycle, so it ends up being a big matrix multiplication over GF(2).  First I made the high-level version where you could set a parameters for the width and taps and so on.  It took forever for Vivado to crank on it.  This is just a few lines of code, mind you, and is just a bunch of XORs.  Then I had Matlab generate an include file with the matrix packed into a long parameter which essentially sets up XOR taps.  That was, I think, ~20x faster, which translated into hours of synthesis time.  The synthesized circuit was also better for various reasons.  This is just one example.  I also still have to instantiate primitives frequently for various reasons.  The level of abstraction doesn't seem like it's changed much in 15 years if you really need performance.  This doesn't really have anything to do with the SystemVerilog constructs.  I'm just talking about high-level code in general.  If I were allowed, I would still use modports, structs, enums, etc.

In article <e4a7957e-c42e-4846-b8ab-ebcf170238dd@googlegroups.com>,
Kevin Neilson  <kevin.neilson@xilinx.com> wrote:
>> Rick - yeah, it's pathetic.  The synthesizable subset of SystemVerilog was 
>> actually fairly concretely defined in the SystemVerilog 3.1 draft, in 2005.  
>> We're just now - 12 years later really finding an acceptable solution for 
>> FPGA designs.  To repeat myself - It's really pathetic.
>
>In my case, I mostly write for Vivado, but I have to write code which will also work for some ASIC synthesis tools which don't like anything too
>modern.  I'm not sure why; I just know I have to keep to a low common denominator.
>
>Anyway, and this is a different topic altogether, I've reverted to writing very low-level code for Vivado.  I've given up the dream of
>parameterizable HDL.  I do a lot of Galois Field arithmetic and I put all my parameterization in Matlab and generate Verilog include files (mostly
>long parameters) from that.  The Verilog then looks about as understandable as assembly and I hate doing it but I have to.  It's the same thing I
>was doing over ten years ago with Perl but now do with Matlab.  Often Vivado will synthesize the high-level version with functions and nested loops,
>but it is an order of magnitude slower (synthesis time) than the very low-level version.  And sometimes it doesn't synthesize how I like.  I've just
>given up on high-level synthesizable code.

(continuing a bit OT...)

Kevin,

That's unfortunate.  We've been very successful with writing parameterizable code - even 
before SystemVerilog. Heck even before Verilog-2001.  Things like N-Tap FIRs, 
Two-D FIRs.  FFTs, Video Blenders, etc...  All with configurable settings - 
bit widths, rounding/truncation options/etc..  I think in a previous job I had a 
parametizable Galois Field Multiplier too.

I'm not sure what trouble you had with the tools.  It takes a bit more up front work,
but pays off quite a bit in the end.  We really had no choice, given the number of 
FPGAs we do, along with how many engineers support them.  Lot's of shared code
was the only way to go. 

If you've got something you like, then I suggest keeping it.  But for others,
I think writing parameterizable HDL isn't too much trouble - and is made
even easier with SystemVerilog.  And higher level too.

Regards,

Mark