Hacker News Reader

Comment by dragontamer | Hacker News Reader

> Binary addition ... is super-linear with regards to operand width

No its not. That's why Kogge-Stone's carry lookahead adder was such an amazing result. O(log(n)) latency with respect to operand width with O(n) total half-adders used.

It may seem like its super-linear. But the power of prefix-sums leads to a spectacular and elegant solution. Kogge-stone (and the concept of prefix-sums) is one of the most important parallel-programming / parallel-system results of the last 50 years. Dare I say it, its _THE_ most important parallel programming concept.

> multiplication latency

You could just... not implement 128-bit multiplication. Just support 128-bit pointers (aka: addition) and leave multiplication for 64-bits and below.

View on HN

There's also something beautiful about seeing or creating a Kogge-Stone implementation on silicon.

I know it was one of the first time I thought to myself: this is not just a straightforward pipeline, yet it all follows such a beautifully geometrical interconnect pattern. Super fast, yet very elegant to layout.

The original paper is a masterpiece to read as well, if you haven't read it.

"A Parallel Algorithm for the Efficient Solution of a General Class of Recurrence Equation", by Kogge and Stone.

It proves the result for _all_ associative operations (technically, a class slightly larger than associative. Kogge and Stone called this a "semi-associative" operation).

Well, just got it. Thanks for the reference!

A bit sad that 1974 papers are still behind a IEEE paywall...

Edit: Just finished reading it. I have to say that the generalization of 3.2 got a bit over me, but otherwise it's pretty amazing that they could define such a generalization. Intuition for those type of problem is often to proceed one step at a time, N times.

That it is provably doable in log2(N) is great, especially since it allows for a choice of the depth/number of processors you want to use for the problem. Hopefully next time I design a latency-constrained system I remember to look at that article

> Hopefully next time I design a latency-constrained system I remember to look at that article

Nah. Your next step is to read "Data parallel algorithms" by Hillis and Steele, which starts to show how these principles can be applied to code. (Much higher-level, easier to follow, paper. From ACM too, so its free since its older than 2000)

Then you realize that all you're doing is following the steps towards "Map-reduce" and modern parallel code and just use Map Reduce / NVidia cub::scan / etc. etc. and all the modern stuff that is built from these fundamental concepts.

Kogge and Stone's paper sits at the root of it all though.

From Data Parallel algorithms by Hillis and Steele conclusion: 'if the number of lines of code is fixed and the amount of data is allowed to grow arbitrarily, then the ratio of code to data will necessarily approach zero. The parallelism to be gained by concurrently operating on multiple data elements will therefore be greater than the parallelism to be gained by concurrently executing lines of code'

I feel like this sums up the way of thinking one must have in this paradigm.

It's funny because when designing digital hardware, you're kind-of trained to see things under that angle, since often the commands you write will expand in that tree-like structure, but to gates/ALU instead of data.

Then managing the data-path often piggy-backs on the hardware structure you just generated.

I feel like I have a overall grasp on these concept, yet there's so much interesting results that I don't know about...

You're right, binary addition isn't super-linear. It is non-constant, though, which is a slightly surprising result if you don't know much about hardware.

Kogge-stone's O(Log2(n)) latency complexity might as well be constant. The difference between 64-bit and 128-bit is the difference between 6 and 7.

There's going to be no issues implementing a 128-bit adder. None at all.

a 10% latency hit on addition would definitely be noticable. that's roughly 1.5 years of IPC improvements at the current rate of CPU progress.

That's really not how that works.

Transistors have a "latency" measured in picoseconds, not nanoseconds.

A 128-bit adder will have a latency of 1-clock cycle, a 10% increase from a 64-bit adder of latency of 1-clock cycle. Aka: it doesn't matter cause it'd almost certainly fit inside of the clock cycle of modern CPUs.

Multiplication of 128 bit numbers is also not a big issue. Today you can do it with 4 MULs and some addition, and it would still be faster than 64-bit division. Hardware multiplication of 128-bit numbers would have area problems more than speed problems. You could always throw out the top 128 bits of the result (since 128x128 has a 256 bit result), and the circuit wouldn't be much bigger than a full 64 bit multiplier.

Reply on news.ycombinator.com