Hacker News Reader

Not to offend, but yeah, if you've already partitioned the work to be done, then of course it's not hard.

I'm pretty sure that anyone who's come into even vague contact with parallel programming understands that the hardest part is communication and synchronization.

Your post feels incredibly pedantic.

I think you underestimate the number of real-world problems that can be solved by a bash script executing "./some_task &" in a for loop, and using "jobs", "fg", and "bg" as needed.

For many problems, that's literally good enough parallelism.

--------

Case in point: I once needed to render an animation in Blender, and I noticed that Blender's built-in parallelism was kind of crap (it was an older version of Blender at the time. My 32-thread / 16-core system barely reached 400% utilization... I know I could do better).

So I just spawned 16x Blenders in headless mode, each handling a different frame of the animation, and achieved far higher utilization than the innate Blender parallelism.

Yes, literally:

        #!/bin/bash
        for i in `seq 1 16`;
        do
                blender (params) & # Yeah, just run a bunch of blenders in headless + background mode
        done

Bonus points: I tweaked the script to take advantage of NUMA-locality, by automatically pinning blender to one NUMA-node. All without ever touching a single line of C code.

-------

Communication / synchronization is hard. But parallelism (even high-performance NUMA-locality with thread affinity pinned to particular CPU nodes) doesn't have to be hard. Just think a bit smarter.

--------

The equivalent to doing "./some_job &" is fork() and wait() in POSIX C / C++. That's good enough for a ton of problems (hell, its how us older programmers achieved parallelism back in the CGI-BIN days).

Don't do complicated high-performance techniques if you only need a bit of parallelism. Don't overthink things, stick to simple parallelism when simple solutions solve simple problem.

Don't premature optimize into complicated producer/consumer patterns unless you actually need the performance. Definitely don't premature optimize into high-performance lockless programming techniques unless you really need to.

I mean in the example you gave, the work was already partitioned for you. That we have high level tools that make it easy doesn't change the fact that the work of rendering frames in an animation are very clear chunks of work that lend themselves naturally to parallelization.

We can quibble about the semantics of "parallel" programming all day, but I think that either too broad or too narrow a scope for the term misses the point: that data coherency is what makes parallel programming hard.

In the ultimate reductio ad absurdum, you can just say it falls into one of the two classes of hard computer science problems, that being "cache invalidation", where the "cache" is some form of shared data. In this sense, I agree with you: it's not the parallelism per se that's hard, but I think anyone talking about the difficulty of it quite clearly is referring to the shared data problems.

> I mean in the example you gave, the work was already partitioned for you.

In my experience, I keep running into problems *already partitioned*.

Make -j. 3d-animation frames. SAXY arrays. (Seriously, do you know how many for loops I've come across that can become #pragma omp parallel for and just automatically benefit from parallelism??). Multiple connections to a server (ex: Fork/join Apache model / CGI-bin / PHP / etc. etc.). Multiple connections to other servers (SMTP, IRC, etc. etc.)

A ton of problems are "easy parallelism" in my experience. Probably most problems. Yeah, there's some hard problems out there, but beginners should learn how to parallelize the easy stuff first.

The point is that these easy cases may just referred to as "work to do". Using more than one CPU core at the time to process through a backlog of work is just...the normal case. Doing work simultanously is not what people refer to when they say "parallel programming is hard"; and the pedantery is in insisting that people word themselves to exclude trivially parallel work when what they want to talk about are the cases where parallelism is not trivial.

The conversation above is like this:

"Solving cubic equations is hard"

"Actually, solving x ^ 3 = 27 is easy, just take the cubic root.."

"Well that is not what we meant when we said cubic equations, we were interested in the general case..."

"I see equations like x^3 = y all the time, it is not that often you have a linear term too..."

I see it differently.

* "Taking care of your car is hard".

* "No its not. 90% of the time, its just changing your oil, refilling the fuel tank, washer fluid, and rotating tires".

* "But you have to also replace the transmission fluid and sometimes rebuild the engine"

* "True, but those are not a very common tasks".

-----------

That's how I see it. Most parallelism is "easy parallelism" in my experience. The goal isn't necessarily to train programmers into being able to do "engine rebuilds", but instead train them for the easy "oil change / rotate tires" part of taking care of cars (or programs).

For programming: that's fork / wait(), or pthread_create() / pthread_join(), or #pragma omp parallel for. Those constructs covers the vast, vast majority of parallel constructs I've run across.

Yes, mutex is hard. Condition variables are hard. Lock-free programming is hard. High performance (false-sharing / MESI) is hard. GPU ballots / __shared__ memory / butterfly permutes are very hard. Prefix-sum / scan and Mergepath algorithms are hard. Lock-free Producer-consumer is really, really, really hard (Probably PH.D level hard)

But... I really don't come across a lot of situations where I need to Mergepath, GPU-ballot, or need to manually program / debug a Lock-free algorithm. That's just the facts. I'm glad I learned these constructs (and I await the day when a high-performance programming problem is given to me such that I need to "pull out the big guns" that I've spent a lot of effort learning)... but I recognize that its not really needed in typical day-to-day programming parallel jobs.

Even in GPU-programming: the bulk of GPU-programming is just simple fork/join stuff. A GPU-kernel is a fork, and when the GPU-kernel finishes execution, its an innate join() (with synchronization guaranteed). Its really not that hard in most situations.

Schedule your chain of GPU-kernels to execute in order (a "CUDA-stream"), and they automatically join and synchronize with themselves each time the kernel completes. Its that easy in most cases.

"Oh, but for maximum performance you want to use dynamic / recursive parallelism, or block-off your data into __shared__ memory and think about L1 caches". Erm, yes, if you care to put that much work into performance its hard. But you're no longer talking about parallelism per se, but instead the very difficult field of high-performance compute at that point.

Your analogy is very close to mine.

Following your analogy then -- this is a HN thread where car mechanics discuss a book about transmission fluids and engine rebuilding.

Did anyone make the point that most programmers often need to care about this stuff?

>* "True, but those are not a very common tasks".

Pretty much every survival/simulation game with complex mechanics suffers from low performance because at some point the simulation becomes very CPU intensive but parallelizing the code is still extremely difficult because of extensive interdependencies.

If you go with the trivial "divide the problem into the smallest parallelizable components" strategy you will end up with huge interconnected graphs, sometimes there isn't even a second graph that can be put on a second CPU core. If you are insane enough to divide the problem at the agent level then you end up with a synchronization nightmare. Sure, given enough effort you can do these all these things but that only entrenches the perception of parallelism being a last resort instead of being the default solution for everything.

I think a lot of people don't know how easy it can and should be to handle the easy cases. C++ has some parallel constructs, but they are not as simple as OpenMP because they're meant to handle the harder stuff.

I think it's important to show and use the easy ways before getting into the complex things.

I've read v1 of the book, and the author does cover the fact that many parallel problems can be covered by using shell scripts or databases. He calls these problems you are talking about "embarrassingly parallel" and encourages the reader to take advantage of parallel tools whenever possible.

The rest of the book talks about doing data sharing efficiently (i.e. for not embarrassingly parallel problems), including some things I don't think I ever would have run across otherwise like RCU. All the while he explains the use cases for each of the techniques. If you are interested in making the most of your processors (and I suspect you are given this post), and are up for a technical read, I'd highly recommend this book.

EDIT: By which I mean to say that he covers all the stuff you posted, and explains exactly when it is worthwhile to use the high performance and communication techniques. If you want to know just the basic stuff, read the first 3 chapters.

- Knock Knock

* Who's there?

- GPUs.

* Closes door.

- Knock knock

- Do you really want to ignore ~90% of the compute throughput and ~90% of the memory bandwidth of your machine?

- Knock knock

- ...

----

An AMD EPYC 7742 (Milan, Zen 3, announced last week, high-end server model) has ~100 GB/s DRAM bandwidth and 1-2 TFLOPS double precision.

A single PCI-e A100 has ~2Tb/s DRAM bandwidth, and 10-20 TFLOPs double precision. You can pack 4x of these per CPU socket... so you end up at 8 TB/s and 40-80 TFLOPs... That makes the GPUs like 99% of both the compute and memory BW of a socket.

Well, CPUs vs GPUs is pretty interesting actually. The #1 supercomputer right now is CPU-only, the A64Fx by Fujitsu. But you're right in that GPU-parallelism is the obvious parallel architecture available to modern programmers. For anyone spending less than $500,000 on a computer, GPUs are probably the most compute for the least amount of cost.

---------

The issue is that there's two difference concepts here:

1. Parallelism -- When a problem you're working on has an undefined ordering to it explicitly. Protocols and communications for example have undefined orders. You could write a state-machine explicitly, but writing a thread is usually much simpler to understand. Ultimately: this is cofunctions, Python Yield / generators, async-code, etc. etc. Remember: Djikstra invented semaphores on a single-core processor. The concept of "single core parallelism" is hugely useful and can grossly simplify code if used correctly.

2. High performance -- This is a different concept entirely!! GPUs are within the realm of high-performance parallelism (and not just merely "conceptual parallelism" in #1).

GPUs are hard because anyone who uses a GPU expects high performance. Be it the video gamer who wants raytracing on his video game, or the machine learning enthusiast training a billion neurons.

Writing a simple "GPU Hello World" is easy as all heck actually. Its all the performance stuff that gets really hard.

The A64Fx really is something between a CPU and a GPU, if we're being fair.

The only GPU-like thing it has is on-board HBM2 RAM (which other CPUs could do, but haven't bothered to do for some reason. Except that one Xeon Phi using the HMC competitor to HBM).

The SIMD-model of A64Fx: the SVE instruction set of ARM, is coming to mainstream Neoverse V-series ARM chips within a year or two.

SVE is CPU-parallelism. Well, its SIMD, but its just 512-bit SIMD (equivalent to AVX512 in width). So that's smaller scale SIMD / CPU parallelism IMO.

Those A64Fx are going to be branch-predicting and executing those SIMD-instructions out-of-order. Its a CPU.

-------

I consider GPUs to be the simpler in-order but more parallel stuff (AMD, NVidia, Xilinx maybe). But you're right in that the line keeps getting blurred each year. (NVidia's dual-issue pipelines is a very CPU-like feature. AVX512 and SVE pushing 512-bits is getting closer-and-closer to GPU-like SIMD widths)

GPUs can now basically do out-of-order execution using dynamic warp formation and driver-based prediction and optimization.

Branch prediction is useless in massively parallel workflows, because of linearization.

GPU SIMD is also more complicated than full-SIMD. Nowadays with work-stealing and multiple workgroups, you can have very similar performance characteristics to parallel SIMD on CPUs, just with more perfromance.

And in any case, OOE for SIMD instructions loses a lot of it's usefulness on many workflows.

> GPUs can now basically do out-of-order execution using dynamic warp formation and driver-based prediction and optimization.

That's... not OOE.

If you have:

    add [eax], ebx
    add ecx, edx

A CPU can execute "add ecx, edx" before the "add [eax], ebx" (especially if the [eax] memory read/write is far away: like in DDR4 or worse).

A GPU will ALWAYS execute the 1st line before the 2nd line. Dynamic warp formation means that SIMD-lanes can split-up in your warp, but none of the warp is executing anything out-of-order.

> Branch prediction is useless in massively parallel workflows, because of linearization.

Stockfish NNUE argues otherwise. Only part of the network updates at any given time. Its a massively-parallel problem, but you need dynamic / branch prediction to see which parts of the Neural-Net are actually updating.

The idea of CPU-designed networks (Neural Nets that PARTIALLY update, instead of a GPU-network that updates entirely) is intriguing to me. There might be other situations where branch prediction is helpful in other largely parallel problems.

----------

> And in any case, OOE for SIMD instructions loses a lot of it's usefulness on many workflows.

More like the SIMD offers enough parallelism to saturate the machine. But NNUE really shows where OOE / branch prediction can suddenly become unexpectedly helpful.

Classic SIMD algorithms do not account for branch prediction / OOE benefits. The very existence of high-speed SIMD + OOE + branch prediction is an unexplored part of computer science IMO.

The A64fx also has hardware synchronization barriers to synchronize cores, which is a pretty GPU-like thing (at least it is very common on GPUs, and rare on CPUs).

https://github.com/fujitsu/A64FX/blob/master/doc/A64FX_Speci...

GPU nodes are extremely expensive. People aren't renting them by accident.

False sharing isn't that hard to deal with. Soundness is much harder to deal with than performance, and lock/wait free programming isn't about raw speed - it's about prioritizing latency over throughput, or providing latency guarantees. A slightly less difficult problem (but still very difficult in practice) is determining if your application needs to prioritize latency or throughput, most assume the latter and use strategies that emphasize the former.

And if you can tolerate the overhead of spawning processes than none of this really matters, fork/join is fine.

> Soundness is much harder to deal with than performance

Soundness within a pure Fork/join model is easier than you might think.

If any data needs to be shared between threads, just pthread_join() / wait(). Then execute the shared-portion of the data in a single thread. Then fork() back off after the sequential portion is complete.

There's no race condition because all the other threads are dead after the pthread_join() or wait() calls. As such, you're fully sound.

> And if you can tolerate the overhead of spawning processes than none of this really matters, fork/join is fine.

Exactly.

The main issue at hand here is that "parallel models" are useful mechanisms to organize code. A lot of parallel programming isn't about speed of execution, but instead about representing an innately parallel problem in their code.

If you have an "innately parallel problem" but do NOT care about performance, just pthread_create() / pthread_join() or fork()/wait() and be done with it.

That's a frankly insane way to write parallel programs. Parallel evaluation is about maximum utilization of system resources balanced against the inherent overhead of synchronization/spawning/joining.

It has nothing to do with code organization.

> If you have an "innately parallel problem" but do NOT care about performance, just pthread_create() / pthread_join() or fork()/wait() and be done with it.

No, just do it in serial. It's easier to read and debug. If you do care about performance and the tasks vastly dominate the time of spawning/joining, then fork/join. It's slightly harder to read and much more difficult to debug, but an order of magnitude faster for a large number of problems.

It should also be noted that promises/futures are close cousins of this model, and their implementation is significantly more complex than pthread_create/pthread_join (but APIs are much nicer, imo, since they do the imperative/cooperative transformation for you).

> That's a frankly insane way to write parallel programs.

Don't hate it until you try it!

    #pragma openmp parallel for
    for(...) { ... } // Parallel portion

    // No longer parallel. Implicit join!
    foobar(); // execute sequentially

    #pragma openmp parallel for
    for(...) { ... } // Parallel portion again

It really covers a lot of parallel situations. Its often better than no parallelism at all (especially with 4-core/8-threads on even the cheapest CPUs today), and its really, really, really easy.

---------

Also consider how CUDA / OpenCL kernels execute.

    someCUDAKernel<<<ten-thousand CUDA-threads>>>(params);
    cudaMemcpy(...); // transfers data from GPU back to CPU.
    foobar(data); // Fully sequential portion when parallelism is non-obvious
    cudaMemcpy(...); // transfer data from CPU back to GPU
    someCUDAKernel2<<<ten-thousand CUDA-threads>>>(params); // Parallelism when its easy

Which is basically how most Tensorflow operations work today. (Bonus points: the "foobar" sequential portion is written in Python, something like 1000x slower than C/C++, but you don't care because 99.999% of the work is done inside of those CUDA-kernels)

This "stupid" fork-join parallelism is really the core concept of modern heterogenous processors. A really easy way to increase utilization of both CPU-and-GPU resources.

There are three problems.

1. Your problem is not big enough to justify it (CPU cores aren't idle because people are evil, there just isnt enough work in the first place)

2. Companies don't spend money on performance optimizations unless they have to (parallelism is just an optimization for your boss)

3. Not every problem can be divided easily, requiring contortions that are only understood by people who specialize in parallel programming