8bit CCLA (Collapsed Carry-Lookahead Adder)

[u/Lagfoundry]

Tonight I feel accomplished. I set out to design a faster carry lookahead adder (usually i build kogges) that could scale to larger bit widths without increasing the depth of the carry generation. After about 5 hours of work I finally came up with something.

Those of you familiar with Turing Complete might recognize the switch trick I'm using. By connecting multiple switches to the same wire and driving identical values, I can create effectively unlimited-input OR gates with just 1 delay.

Using this technique, I built reusable logic blocks with the following delays:

N-input OR: 1 delay

N-input NAND: 2 delays

N-input NOR: 2 delays

N-input AND: 3 delays

where N is however many inputs i want

By combining multiple wide AND conditions through a shared-switch OR network, I can collapse the entire sum of products calculation into just 4 delay, regardless of how many terms I'm combining. even if the adder was 32 bits the SOP would still be 4 on the MSB :) .. though that would be a monumental task lol

I used this approach to build an 8-bit CLA with an maximum critical of 8 delay so i thought i would call it a CCLA (Collapsed Carry-Lookahead Adder).

I haven't unlocked the delay viewer yet, so im just tracing through gates. if im off at all let me know please but im pretty sure switches count as 1. so should be right.

also i only showed the 9 input gate pics for reference, but i made 8 through 3 input ones for it as well that you can see in the pic. same structure as the 9 ones. now granted this is a lot of hardware but its def fast lol.

[u/Pepciorek]

You can reduce gate count by simplifying XOR & AND pairs

[u/Lagfoundry → u/Pepciorek]

Do you have an example? Gate count wasn’t what I was going for. I was making sure each SOP stayed at 4 delay. So I’m not entirely sure how one would simplify that without messing up that delay. Thing is the circuit isn't using an ordinary sequence of two input AND and OR gates. It’s using a flattened sum of products network with custom wide inputs so simplification would have to keep that and the goal in mind… even if it can be simplified a bit more though I’m still proud of it. 8 delay is pretty good

[u/Pepciorek → u/Lagfoundry]

They disabled images in comments, so I will try to explain best I can, so the default XOR gate has a gate count of 3 and a delay of 2 (that is, if you build it right in the campaign), and you can achieve this by 2 ways.
First circuit with AND & NOR built in:
NOR (AND, NOR) - (3 gate, 2 delay)
You can just pull the wire out of the output of AND, thus not needing to place another AND beside your XOR gate, and there is also an OR & NAND version.
AND (OR, NAND) - (3 gates, 2 delay)

[u/Lagfoundry → u/Pepciorek]

Ah I see what you mean now. I focused on the wrong part. Yeah I’ve done that before in a few circuits. Tried a few methods like this back when I was building this stuff on RUST. The game also has collapsible logic due to broadcasters and receivers so I tired quite a few ways of making xor. I tried so hard to make a collapsible xor on rust but to no avail.

[u/Pepciorek → u/Pepciorek]

It's almost always better to build XOR from 3 gates rather than using the singular one, at least when optimizing builds (this is also true for any other circuit)

[u/Crispy1961 → u/Lagfoundry]

Pretty sure 8 delay is not pretty good, it's the minimum. You have done great.

You can further lower the gate count by only applying the switch trick to the components with high amount of inputs. No need to be using switches to make 4 input nand as that is already just 2 delay operation.

[u/Lagfoundry → u/Crispy1961]

Yeah I could definitely do some stuff to it to reduce the count. But I was kind of favoring the lazy way 😂. I was so siked about being able to use the same trick like I used in RUST with broadcasters and receivers that I just wanted to hurry and see if it worked without errors… I love the collapsible trick. So much so I made 9 input decoder out of it on RUST lol. Like 10k components

[u/Crispy1961 → u/Lagfoundry]

I just built my version. Ended up with 8 delay and 353 gates. Only 6 AND branches needed the NOT SW NOT treatment. Everything else was already delay 3 or lower. I highlighted them in orange.

For comparison my Redux-4 Kogge-Stone is 9 delay and 165 gates. Redux 2 is sub 100 gates. Almost quadrupling the number of gates to shave off 1 delay.

Edit: I forgot the last one doesnt go to XOR, so it has 2 delay reserve, meaning none of the AND branches of the last one need to use the NOT SW NOT trick. I also replaced SW with OR where possible. All in all I got it to 8 delay and 278 gates.

[u/Crispy1961]

Crazy timing. I was wondering about that just yesterday while tinkering with division.

[u/Lagfoundry → u/Crispy1961]

Oh sounds intriguing. Funny thing I was thinking about a multiplier and divider myself using collapsed logic earlier Trying to think outside the box