News for hackers. Stuff that matters.
Re:The road to Zettalinux by rwmj on Friday September 23, 2022 @09:49AM (#32951938)
Distributed Shared Memory is a thing, but I'm not sure how widely it is used. I found that it gives you all the coordination problems of threads in symmetric multiprocessing but at a larger scale and with much slower synchronisation.

https://en.wikipedia.org/wiki/Distributed_shared_memory

Re:The road to Zettalinux by dragontamer on Friday September 23, 2022 @10:42AM (#32952582)
https://en.wikipedia.org/wiki/Remote_direct_memory_access

Again, I'm not a supercomputer programmer. But the whitepapers often discuss RDMA.

From my imagination, it sounds like any other "mmap". You, the programmer, just remembers that the mmap'd region is slower (since it is read/write to a Disk, rather than to RAM). Otherwise, you treat it "like RAM" from a programming perspective entirely for convenience sake.

As long as you know my_mmap_region->next = foobar(); is a slow I/O operation pretending to be memory, you're fine.

---------

Modern systems are converging upon this "single address space" programming model. PCIe 3.0 implements atomic operations and memory barriers, CXL is going to add cache-coherence over a remote / I/O interface. This means that all your memory_barriers / atomics / synchronization can be atomic-operations, and the OS will automatically translate these memory commands into the proper I/O level atomics/barriers to ensure proper synchronization.

This is all very new, only within the past few years. But I think its one of the most exciting things about modern computer design.

Yes, its slow. But its consistent and accurately modeled by all elements in the chain. Atomic-compare-and-swap over RDMA can allow for cache-coherent communications and synchronization over Ethernet, over GPUs, over CPUs, and any other accelerators sharing the same 64-bit memory space. Maybe not quite today, but soon.

This technology already exists for PCIe 3.0 CPU+GPUs synchronization from 8 years ago (Shared Virtual Memory). Its exciting to see it extend out into more I/O devices.

Re:The road to Zettalinux by c-linkage on Friday September 23, 2022 @03:09PM (#32955837)
Distributed Memory Access is just another kind of Non-Uniform Memory Access, which is Yet Another Leaky Abstraction. Specifically, if you care about performance at all you now have to worry about where in RAM your data lives.

Caring about where in memory your data lives is different from dealing with cache or paging. Programmers have to plan ahead to keep frequently accessed data in fast RAM, and infrequently accessed data in "slow" RAM. You'll probably need special APIs to allocate and manage memory in the different pools, not unlike the Address Windowing Extensions API in Microsoft Windows.

And once you extend "memory" outside the chassis, you'll have to design your application with the expectation that any memory access could fail because a network failure means the memory is no longer accessible.

If you only plan to deploy in a data center then maybe you can ignore pointer faults, but that is still a risk, especially if you decide to deploy something like Chaos Monkey to test your fault tolerance.

Re:The road to Zettalinux by zozbot234 on Friday September 23, 2022 @04:52PM (#32956907)
> And once you extend "memory" outside the chassis, you'll have to design your application with the expectation that any memory access could fail because a network failure means the memory is no longer accessible.

You have to deal with these things anyway in any kind of distributed setting. What this kind of location-independence via SSI really buys you is the ability to scale the exact same workloads down to a single cluster or even a single node when feasible, while keeping an efficient shared-memory programming model instead of doing slow explicit message passing. It seems like a pretty big simplification.

Re:The road to Zettalinux by jandrewrogers on Friday September 23, 2022 @06:06PM (#32957675)
I've written code for a few different large-scale SSI architectures. The shared-memory programming model is less efficient than explicit message passing in practice because it is much more difficult to optimize. The underlying infrastructure is essentially converged at this point, so performance mostly comes down to the usability of the programming model.

The marketing for SSI was that it was simple because programmers would not have to learn explicit message passing. Unfortunately, people that buy supercomputers tend to care about performance, so designing a supercomputer that is difficult to optimize misses the point. In real code, the only way to make them perform well was to layer topology-aware message passing on top of the shared memory model. At which point you should've just bought a message passing architecture.

There is only one type of large-scale SSI architecture that is able to somewhat maintain the illusion of uniform shared memory -- hardware latency-hiding e.g. barrel processors. If programmers have difficulty writing scalable code with message passing, then they definitely are going to struggle with this. These systems use a completely foreign programming paradigm that looks deceptively like vanilla C++. Exceptional efficient, and companies design new ones every few years, but without programmers that grok how to write optimal code they aren't much use.

Re:The road to Zettalinux by FuriouslyAdrift on Friday September 23, 2022 @03:25PM (#32956026)
RDMA is used heavily in SMB3 file systems for Microsoft HyperV failover clusters.
Re:The road to Zettalinux by throw10920 on Friday September 23, 2022 @10:49AM (#32952683)
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 with current technology.

Re:The road to Zettalinux by dragontamer on Friday September 23, 2022 @10:51AM (#32952708)
> 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.

Re:The road to Zettalinux by meisanother on Friday September 23, 2022 @11:25AM (#32953185)
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.

Re:The road to Zettalinux by dragontamer on Friday September 23, 2022 @11:40AM (#32953408)
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 by meisanother on Friday September 23, 2022 @12:19PM (#32953927)
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

Re:The road to Zettalinux by dragontamer on Friday September 23, 2022 @02:42PM (#32955578)
> 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.

Re:The road to Zettalinux by meisanother on Friday September 23, 2022 @07:15PM (#32958185)
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...

Re:The road to Zettalinux by throw10920 on Friday September 23, 2022 @11:40AM (#32953414)
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 by dragontamer on Friday September 23, 2022 @11:44AM (#32953483)
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 by adgjlsfhk1 on Friday September 23, 2022 @11:50PM (#32959595)
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.
Re:The road to Zettalinux by dragontamer on Sunday September 25, 2022 @03:02PM (#32974794)
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.

Re:The road to Zettalinux by pclmulqdq on Friday September 23, 2022 @12:20PM (#32953947)
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.
Re:The road to Zettalinux by sakras on Friday September 23, 2022 @01:41PM (#32954935)
At least at this latest SIGMOD, it felt like everyone and their dog was researching databases in an RDMA environment… so I’d imagine this stuff hasn’t peaked in popularity.