[Open-graphics] peer review of a fast boolean addition algorithm, please...

[Mark]

Timothy Normand Miller wrote:
> On 8/29/07, Dennis Heuer <dh at triple-media.com> wrote:
>>
>> what do you think?
> 
> instruction.  I presume there'd be a similiar solution for SUB.
>
Negate one input, right?  Is there a better way?

> If you were to convert this to combinatorial logic, however, you'd
> pretty much just end up with a regular ripple-carry adder.
> 
I don't think that's quite right -- I think you'd wind up with something 
that looks much more like an array than a chain.  If you unroll this 
implementation completely, you wind up with n stages, each containing n 
2-input XORs and n 2-input ANDs.  Once you apply constant propagation, 
the bottom-right triangle gets optimized away (assuming the input is at 
the top & output at the bottom, MSB left & LSB right).  Assuming the 
circuit is mapped to two-input gates, my back-of-the-envelope result is:

        Ripple Heuer
       +------+--------
area  | 5n   | n(n+1)
delay | 2n-1 | n

Of course, these area & delay costs are just in principle.  In reality, 
architectural features make this kind of cursory analysis moot (at least 
in FPGAs -- I'm thinking of the fast carry chains present in any modern 
architecture and hard adders like those in DSP48 slices; I'm not an ASIC 
guy, but I'm sure there's an equivalent principle at work there, like 
domino logic magic or some clever use of pass transistors or something).

Of course, everything I said here could be riddled with mistakes.  Hope 
not! :)