[libre-riscv-dev] [Bug 267] The efficiency of adder/subtractor

[bugzilla-daemon at libre-riscv.org]

http://bugs.libre-riscv.org/show_bug.cgi?id=267

--- Comment #7 from Jacob Lifshay <programmerjake at gmail.com> ---
(In reply to Jock Tanner from comment #4)
> Very roughly speaking, N-bit ripple-carry adder takes a*N transistors and
> b*N time for calculation, while straight-out carry-lookahead adder takes a^N
> transistors and b time. AFAIK in practical ALU design they always make a
> compromise between the two. And I just wonder what kind of compromise could
> be suitable for *reconfigurable*, high-speed ALU.
> 
> I imagine something cascadable, like 74181 bit-slice ALUs + 74182 carry
> generators [2], but with 'plexors in between. But the speed of such a design
> may be questionable.

I haven't checked which specific design yosys produces for an adder, but I know
there are divide and conquer carry lookahead designs that have area of
O(N*log(N)) and delay of O(log(N)) when ignoring delay due to wire length, so
that's much better than the above a^N value.

I found a paper with an overview of different carry lookahead adder designs:
https://www.ijrte.org/wp-content/uploads/papers/v7i5s4/E10920275S419.pdf

In fact, I'm planning on using the same kind of recursive divide and conquer
structure for purposes other than addition such as finding the first set bit or
a prefix-sum.

-- 
You are receiving this mail because:
You are on the CC list for the bug.