#Adding Bytes with Parallel Prefixes

1 messages · Page 1 of 1 (latest)

broken gazelle
#

Some general adder tricks hidden inside custom components. Explanation of CCs:

stiB: An upiside-down bit splitter for aesthetics

GP + X: The left output (and all cyan wires) is a two-bit line containing Generate (AND) and Propagate (OR) terms. The right (pink) output is XOR.

Black: Given two two-bit Generate/Propagate lines, outputs a merged G/P line. G' = (G0&P1) | G1. P' = P0&P1

Gray: Given two two-bit Generate/Propagate lines, outputs a merged Generate bit. G' = (G0&P1) | G1

G: Pulls the generate bit out of a G/P line

Cyan wires are 2-bit G/P lines. Pink wires are XOR. Green wires are carry bits.

This can be improved significantly from the score you see by sacrificing clarity, but I think it's a good starting point for relating things back to the way diagrams are drawn for these things. Hopefully it helps someone.

SPOILER_image.png
jaunty forge
#

It looks like a textbook picture, amazing.

broken gazelle
#

Modified slightly to be more regular and textbook-correct. "Gray" now returns a 2-bit G/P line, but the "P" is always 0. This allows a terminal gray node to take input from another gray node, as they do in all adders. Side effect: much better gate cost, but that's not really the goal here, it's not my best adder

SPOILER_image.png
fading parrot
#

Would you mind sharing the layout of your black nodes? Every time I try to recreate your G' I get short circuits in my switches (Attached is my example: Top row is P and G 1, Middle row is P and G 0, and bottom row is P and G prime)

A similar layout worked fine when I was using XOR for P in my first layer, but switching to OR has broken some of the assumptions I made

SPOILER_image.png
#

(I'm also assuming that the gray nodes are identical, with the P' circuitry removed_

broken gazelle
#

You're right about gray cells. If you're using switches and the OR form, P' needs to be true whenever G' is true

#

That can be done without increasing delay

fading parrot
#

OOOH... No wonder your gate score is so high

fading parrot
#

My 6 delay solution has a worse score than my 7 delay solution D:

broken gazelle
#

Yeah, I've convinced myself that the 6 delay solutions that are towards the top of the leaderboard can't really be of this form. C_user alluded to making use of !G to cut gates (maybe it was !P?). I strongly suspect the top solutions aren't using parallel prefix at all

fading parrot
#

IIRC the 4 delay solutions use some sort of 2-3-3 CLA arrangement. But it seems like PPAs are probably the best general score

jaunty forge
#

up to now, best 5-delay adder and 6-delay adder are 2-2-2-2

#

I have 88/6 and 106/5.

#

I don't think they are PPA.

willow lava
#

How do you go even go below 7 Delay? 1 or + 3 steps (1 delay each) + 1 or (switch or) + 1 xor

willow lava
#

Is there a way of removing the extra XOR? with some kind of switch hack? how do you avoid the short circuits?

prisma ice
#

Is that carry in generate or propagate?

earnest wing
#

How are your black and gray nodes 1 delay? Every time I try to do a 1 delay node with switches, I get a short circuit

vivid helm
earnest wing
#

I am an idiot. I somehow didn't think of recomputing. I only thought "Hey, I have G' right here, why don't I use it"

vivid helm
#

I think I just though of some breaktrough ...

prisma ice
#

How is your gate score so low? I finally got your solution with 6 delay, but my gate score is way higher at 146

dapper kiln
#

Delay score of 6 is WILD!

jaunty forge