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

[Farhan Mohamed Ali]

On Wed, August 29, 2007 5:14 pm, Mark said:
> 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?
> 
Negate + carry in of 1. I'm not too clear on how this adder handles a 
carry in.

>> 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).
> 
I see this adder as sort of a serial implementation of a carry lookahead 
adder. Completely unrolling the loop for a single cycle implementation 
would use quite a lot of hardware as you have shown. I think a minimal 
binary tree carry lookahead adder would be a better choice for an ASIC 
implementation as it would be faster and cost about the same.

Sorry Mark, i forgot to hit reply all earlier :P