Hacker News Board Hacker News, browsed like a classic message board
Live data from Hacker News

The road to Zettalinux

lwn.net

Post reply on HN
Print view View original

101–110 of 199 posts

Re: The road to Zettalinux

#101

Post by dragontamer »

meisanother wrote: post #97
dragontamer wrote: post #74

Earlier quoted context omitted.

> 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…

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).

Re: The road to Zettalinux

#102

Post by throw10920 »

dragontamer wrote: post #74
throw10920 wrote: post #72

Earlier quoted context omitted.

That's what I was going to chime in with - you pay for that extra address width. Binary addition and multiplication latency is super-linear with regards to operand width. Larger pointers lead to more memory use, and memory access latency is non-constant with respect to size. It might make sense for large distributed systems to move to a 128-bit architecture, but I don't see any reason for consumer devices, at least w…

> 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…

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.

Re: The road to Zettalinux

#103

Post by dragontamer »

throw10920 wrote: post #102
dragontamer wrote: post #74

Earlier quoted context omitted.

> 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…

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.

Re: The road to Zettalinux

#104

Post by api »

gjvc wrote: post #96
api wrote: post #39

Earlier quoted context omitted.

I can't imagine a single Linux kernel instance or single program controlling that much bus-local RAM, but as you say there are other uses. One use I can imagine is massively distributed computing where pointers can refer to things that are either local or remote. These could even map onto IPv6 addresses where the least significant 64 bits are a local machine pointer and the most significant 64 bits are the machine's…

I can't imagine a single Linux kernel instance or single program controlling that much bus-local RAM, but as you say there are other uses. MS-DOS and 640K ...

The addressable size grows exponentially with more bits, not linearly. 2^64 is not twice as big as 2^32. It’s more than four billion times as big. 2^32 was only 65536 times as big as 2^16.

Going past 2^64 bytes of local high speed RAM becomes a physics problem. I won’t say never but it would not just be an evolutionary change from what we have and a processor that could perform useful computations on that much data would be equally nuts. Just moving that much data on a bus of today would take too long to be useful, let alone computing on it.

Re: The road to Zettalinux

#105

Post by sidewndr46 »

Aperocky wrote: post #60
rektide wrote: post #50

Earlier quoted context omitted.

Leaving cluster coherent address space behind - like you say - is doable. But you lose what the parent was saying: > If everyone has the same address space, then you can share pointers / graphs between nodes and the underlying routing/ethernet software will be passing the data automatically between all systems. Its actually quite convenient.

Sounds like a disaster in terms of potential bugs.

Instead of having another thread improperly manipulating your pointers and scribbling all over memory, now you can have an entire cluster of distributed machines doing it. This is a clear step forward.

Re: The road to Zettalinux

#106

Post by rektide »

Aperocky wrote: post #60
rektide wrote: post #50

Earlier quoted context omitted.

Leaving cluster coherent address space behind - like you say - is doable. But you lose what the parent was saying: > If everyone has the same address space, then you can share pointers / graphs between nodes and the underlying routing/ethernet software will be passing the data automatically between all systems. Its actually quite convenient.

Sounds like a disaster in terms of potential bugs.

Not that the industry doesnt broadly deserve this FUD take/takedown, but perhaps possibly maybe it might end up being really good & useful & clean & clear & lead to very high functioning very performant very highly observable systems, for some.

Having a single system image has many potential upsides, and understandability & reasonability are high among them.

Re: The road to Zettalinux

#107

Post by protomyth »

PaulHoule wrote: post #59
protomyth wrote: post #38

Earlier quoted context omitted.

The AS/400 and iSeries also use 128-bit pointers. 128-bit would be useful for multiple pointers already in common use such as ZFS and IP6 addresses. I expect it will the last hop for a long time.

Those are evolved from the System/38.

Yeah, IBM is one company that shows how to push the models down the road. They do take their legacy seriously.

Re: The road to Zettalinux

#108

Post by mpweiher »

kuratkull wrote: post #57
mpweiher wrote: post #11

Earlier quoted context omitted.

> in modern languages the rule is generally to have fixed-size integers. Modern languages have unlimited size integers :-) "Modern" as in "since at least the 80s, more likely 70s".

Good luck seeing your performance drop off a very sharp cliff if you start using larger numbers than your CPU can fit into a single register.

Well, in those case other languages fail.

Either silently with overflows, usually leading to security exploits, or by crashing.

So in either case you are betting that these cases are somewhere between rare and non-existent, particularly for your core/performance intensive code.

Being somewhat slower, probably in very isolated contexts (60-62 bits is quite a bit to overflow), but always correct seems like the better tradeoff.

YMMV. ¯\_(ツ)_/¯

Re: The road to Zettalinux

#109

Post by mpweiher »

fluoridation wrote: post #22
mpweiher wrote: post #11

Earlier quoted context omitted.

> in modern languages the rule is generally to have fixed-size integers. Modern languages have unlimited size integers :-) "Modern" as in "since at least the 80s, more likely 70s".

Good luck using those to specify the data layout of a network packet.

Well, for that you'd probably use a specialisation of Integer that's bounded and can thus be represented in a machine word.

Re: The road to Zettalinux

#110

Post by Beltiras »

vanderZwan wrote: post #93
Beltiras wrote: post #88

Earlier quoted context omitted.

I have horrid memories of debugging I had to do to get some god-awful fourier transform to calculate with 15 digits of precision to fit a spec. It's right at the boundary where double-precision stops being deterministic. Worst debugging week of my life.

> stops being deterministic I'm imagining the maths equivalent of Heisenbugs, is that correct?

No, just having to match how Matlab did the calculation (development of an index) to implementing the same thing in C++ (necessitating showing the calculation returned same significant digits for the precision we expected). I've seen a Heisenbug and that was really weird. Happened during uni so I didn't have to start tracing down compiler bugs. Not even sure if I could, happened with Java.
Post reply on HN