Variable Size Adder Tree

[ShortCircuit]

I have been trying to write a function which could be synthesized that implements the additions of the elements of a varying sized array.

I am trying to add the elements in pairs instead of adding by cascaded adders. I also know the width of the input array at compile time, but I cant work out a way of automatically generating each adder result and using these results in the next level. Has anyone tried to do something similar, or am I just trying to do the impossible?

Thanks,
Jason

 

[joris]

I've done something like that before; What I did was, having a recursive entity just for the adders.

It getting an integer array of length 'n', where n was generic,
The body would fill a new results array of length (n / 2) (rounding upwards for uneven n)

It would embed the same entity again with adjusted n, until n becomes 1 (the final result).

 

[ShortCircuit]

I've done something like that before; What I did was, having a recursive entity just for the adders.

It getting an integer array of length 'n', where n was generic,
The body would fill a new results array of length (n / 2) (rounding upwards for uneven n)

It would embed the same entity again with adjusted n, until n becomes 1 (the final result).

Did you have to use generate statements in order to accomplish this?

 

[joris]

Yes, I used a bunch of generate statements for this - both for generates and if generates.

You can also do the recursion inside the architecture, using a function or a procedure (I'm not sure whether that's allowed with a procedure as well, haven't tried that), which would call itself as described before; That way, the generates change into normal if and for loop statements.

You can also use a two-dimensional array to hold the intermediate results (only filling half of it -- a triangle); That way, you can easily do this inside a process (or function/procedure); The synthesizer should be able to figure out which array locations are never used