<DX-MON>
alanvgreen: as you're doing that in one assignment, it will cause the tools to generate the full tree of adders required so that the whole thing happens in one clock cycle or timing fails.. if the signals don't have inter-adder dependencies, then this will be O(1).. if there are dependencies, then it depends however it boils down to the worst-case gate+interconnect propergation delay for your chosen FPGA
<DX-MON>
big-O analysis of FPGA things is hard if not somewhat meaningless as operations are always done in parallel
<DX-MON>
gate delay is what we talk about as this is the base unit for determining f(max)
<DX-MON>
I hope that makes sense?
<sorear>
I'm pretty sure the question was whether it will generate a balanced tree of adders or a lopsided chain of adders
<sorear>
which hasn't been directly answered, although some of the answers have assumed it
<DX-MON>
ah.. that answer significantly depends on inter-signal dependencies
<DX-MON>
if there are none, then it will be flat and not a tree
<DX-MON>
iif there are some, then it will be a series of trees
<DX-MON>
if there is a total strict ordering of dependencies, then it will be a cascade
<DX-MON>
it all depends on the dependencies
<mwk>
as for the original question
<mwk>
can't speak for other toolchains, but yosys will recognize it's a big sum and not just a chain of adds
<DX-MON>
what do I mean by a dependency? I mean a series of signals that are being used to represent one numerical value together have an addition dependency on the next lowest bit in the form of the carry chain
<DX-MON>
which also explains why a total strict ordering forms a cascade
<mwk>
and emit a balanced-ish tree of 3:2 compressors with a final single full adder stage
<DX-MON>
ah, that's neat - good to know mwk!
<mwk>
not always optimal area-wise (the optimal type of compressor to use should be chosen based on target's LUT size tbh), but has the right asymptotic delay
<DX-MON>
with the Xilinx tools, many of their FPGAs have dedicated fast carry chain logic so you get a stripe of slices going up the device chained together doing the addition with the carry being fed through slice-to-slice
<mwk>
heh, all reasonable FPGAs have dedicated carry chains, and of course yosys uses those for the final stage
<DX-MON>
:) I wasn't sure if it was Xilinx specific and their parts are what I'm most familiar with atm
<mwk>
for the previous stages, the whole point of using compressors instead of carry adders is to avoid the long dependency chains
<DX-MON>
makes sense.. keeps prop delay down
<mwk>
the details of the carry chain are very vendor-specific; the fact of *some* kind of carry chain existing is near-universal
<mwk>
(though xilinx has been using practically the same mux+xor arrangement for a *long* time, starting from the original virtex, right up to ultrascale)
<DX-MON>
*nod*
<DX-MON>
I know their arrangement allows the tools to generate only a half adder to do the addition itself and the mux+xor forms the other half adder but with some highly optimised gates to make the propergation delays almost not part of the equation
<DX-MON>
which is how you can do a 100MHz 64-bit add on a Spartan 6 without the tools crying at you
<mwk>
pretty much
<mwk>
the mux chain involved can do plenty of other fun tricks too btw, like very wide and-gates, or ultrafast comparisons
<mwk>
though it's underused due to lack of toolchain support
<DX-MON>
I'm somehow not surprised as the structure screams of that kind of thing.. but it's not something I see Xilinx wanting to capitalise on
<mwk>
I am quite proud of the yosys cmp2lcu thing btw, utilizing this for comparisons
<mwk>
would be really nice to have a LUT mapper that could just utilize at least the muxes dynamically for any kind of logic (xors too, preferably, but that would be a stretch)
<DX-MON>
ah, indeed.. that'd be cool
Degi_ has joined #nmigen
Degi has quit [Ping timeout: 265 seconds]
Degi_ is now known as Degi
<alanvgreen>
DX-MON: thanks
<alanvgreen>
mwk: thank you too!
PyroPeter_ has joined #nmigen
PyroPeter has quit [Ping timeout: 245 seconds]
PyroPeter_ is now known as PyroPeter
slan has joined #nmigen
<Evidlo>
what is d1b2 bridging to?
<sorear>
/whois d1b2
<sorear>
Evidlo: if you look at the WHOIS information it will tell you.
<Evidlo>
yeah, I saw thanks
slan has quit [Quit: leaving]
slan has joined #nmigen
Bertl_oO is now known as Bertl_zZ
jeanthom has joined #nmigen
revolve has quit [Read error: Connection reset by peer]
revolve has joined #nmigen
pftbest has joined #nmigen
jeanthom has quit [Ping timeout: 245 seconds]
chipmuenk has joined #nmigen
jfng has quit [Quit: Idle for 30+ days]
bgs has joined #nmigen
revolve has quit [Ping timeout: 246 seconds]
revolve has joined #nmigen
Bertl_zZ is now known as Bertl
revolve_ has joined #nmigen
pepijndevos_ has joined #nmigen
revolve has quit [*.net *.split]
pepijndevos has quit [*.net *.split]
roamingr1 has quit [Ping timeout: 256 seconds]
DaKnig has joined #nmigen
DaKnig has joined #nmigen
roamingr1 has joined #nmigen
samlittlewood has quit [Read error: Connection reset by peer]
samlittlewood_ has joined #nmigen
bvernoux has joined #nmigen
chipmuenk has quit [Quit: chipmuenk]
peeps[zen] is now known as peepsalot
jeanthom has joined #nmigen
revolve_ has quit [Read error: Connection reset by peer]
revolve has joined #nmigen
chipmuenk has joined #nmigen
peepsalot has quit [Quit: Connection reset by peep]
jeanthom has quit [Ping timeout: 240 seconds]
peepsalot has joined #nmigen
jeanthom has joined #nmigen
pftbest has quit [Remote host closed the connection]
pftbest has joined #nmigen
bvernoux has quit [Quit: Leaving]
bsmt6 has joined #nmigen
tpw_rules has quit [Excess Flood]
tpw_rules has joined #nmigen
bsmt has quit [Read error: Connection reset by peer]
bsmt6 is now known as bsmt
electronic_eel has quit [Ping timeout: 264 seconds]
electronic_eel has joined #nmigen
peepsalot has quit [Ping timeout: 260 seconds]
pftbest has quit [Remote host closed the connection]