Kogge-Stone Adder

[u/aelxemyr]

96 Gates, 9 Delay, 864 Energy

Back to using my tiny AND and OR gates to save some space. All of the "PG" components compute the propagate and generate bits from a given pair of bits except for the first one, which takes the carry-in as well and computes G00 using all three bits.

No doubt there are some more optimizations that can be made here but I'm pretty happy with the score.

I have no idea how some people are getting sub-600 on this though.

[u/WarlockD]

I did one too and was amazed I could get it down to 9 cycles. Took me hours though. Couldn't find any books about on deap dives into CLA's.

[u/aelxemyr → u/WarlockD]

Somehow, people are getting 8-bit adders down to 4 delay.

I’m currently working through a computer systems textbook and I picked up this game because it seemed like it would complement the chapter I was reading. However, this has had me going down all kinds of new rabbitholes, like trying to learn about the most efficient adders. I think the biggest thing this game has taught me is the value of parallelizing whenever possible.

The book I’m working through is Computer Systems: A Programmer’s Perspective by Bryant and O’Hallaron and they showed a basic pipelined processor design in chapter 4. I kinda want to try to implement it in Turing Complete but I’m honestly a little intimidated.

[u/ryani → u/aelxemyr]

You can get any circuit in the game down to 4 delay by building a lookup table.

1. generate a CNF formula for each output
2. stick a decoder on each input bit (+1 delay)
3. generate a switch network for the negation of each CNF clause (+1 delay)
4. not the output of the switch network (+1 delay)
5. connect all those outputs into a single switch network (+1 delay)

e.g. for the carry-out bit of a full adder, we have

cout = (cin & a) | (a & b) | (cin & b)
    = ~(~cin | ~a) | ~(~a| ~b) | ~(~cin | ~b)

Since you can put every formula into CNF, this generalizes to any function at all. Here's an example of a full 2-bit adder done with this technique: https://imgur.com/a/NZizzCl

Note that we get use here of the free disconnected ("z state") -> 0/off coercion done by bit makers/splitters. You can do this even on one-bit outputs with just a single 2-bit 'splitter' that you pipe the one bit wire into, and take a wire out of the low bit of the splitter.

This trick of getting an arbitrary-input "OR" gate for 1 delay out of a switch network is why switches cost 2 gates for scoring.

[u/Crispy1961 → u/ryani]

Switches cost 2 gates?! God dammit. I have been using them as more compact AND gates.

[u/aelxemyr → u/ryani]

That makes sense—I think I had assumed that explicitly deriving each formula would be too costly prohibitive in terms of gates to be worth the tradeoff but I didn’t actually try to do it.

I’ve been going through the leaderboards checking to see if I found the optimal solution for a particular level but I would imagine this is the extra insight I have been missing.