“Is Parallel Programming Hard, and, If So, What Can You Do About It?” v2 Is Out

https://mirrors.edge.kernel.org/pub/linux/kernel/people/paulmck/perfbook/perfbook.html

by vkaku • 5 years ago

197 59 5 years ago

mirrors.edge.kernel.org

3JPLW• 5 years ago

A thread from 2020 (v2 RC 1): https://news.ycombinator.com/item?id=22030928

2015: https://news.ycombinator.com/item?id=9315152

2014: https://news.ycombinator.com/item?id=7381877

2011: https://news.ycombinator.com/item?id=2784515

dragontamer9• 5 years ago

Counterpoint: Parallel programming isn't very hard.

Seriously: try fork() + wait(), or spawn in bash / cmd line. make -j offers parallelism (and Ninja is "make -j by default").

OpenMP's "#pragma omp parallel for" is extremely easy to use.

Things get harder with thread libraries, but the "parallelism" part of pthreads is pretty easy. pthread_create(&thread_id, NULL, function, args);, at least if you're fine with the default settings.

C++ Threads are even easier than pthreads.

-----------

The hard part is:

1. Communication / Synchronization -- But really, condition variables are the most complicated thing most people need. fork() + wait() push the difficult communication part to the wait() or to pipes. But if you stick with wait() / waitpid() as your main communication mechanism, its pretty easy to think about.

2. High performance programming -- This is just hard, especially if you begin to reach for the highest performance "memory barrier / lock-free programming" styles. This is where "false sharing" comes in (your code correctly executes under false sharing, but slowly due to how the L1 cache handles multicore architectures).

---------

However, if you stick with a simple fork-join communication model (ex: pthread_join, or wait()/waitpid() based synchronization)... its really not too hard at all. Just try to stay away from the high-performance techniques unless you really need them.

volta83• 5 years ago

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

dragontamer9• 5 years ago

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.

imtringued4• 5 years ago

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

npsimons2• 5 years ago

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.

dragontamer9• 5 years ago

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.

phkahler• 5 years ago

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.

hctaw2• 5 years ago

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.

dragontamer9• 5 years ago

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.

genrez• 5 years ago

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.

imtringued4• 5 years ago

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

thorn• 5 years ago

Please, refrain from judging people here. I would rather prefer if we talked about this wonderful book that was released for free for our own enjoyment. I cannot even grasp the volume of work that went into this book.

zozbot234• 5 years ago

I cannot even grasp the volume of work that went into this book.

You actually can! The main format is PDF, but the author also has hard-copies for sale.

nickthemagicman• 5 years ago

Quality pun.

Dowwie• 5 years ago

More free materials on concurrency, including a book near the top published in 2016: https://homes.cs.washington.edu/~djg/teachingMaterials/spac

bullen3• 5 years ago

I think Joint Parallel is hard, as in when two threads on two different cores are trying to write+read to+from the same memory.

My solutions are:

1) Use Java on the server; it's GC:ed VM has a complex memory model that can handle fast lock-free concurrency relatively well, even using OO though you'll hit cache-misses.

2) Use C on the client, primitive variable types are generally atomic so if you know what you are doing (I don't because I haven't gotten that far yet) you should be able to joint parallelize cores with char, int and float arrays as data, also avoiding cache-misses!

There are many more arguments for this division, Java doesn't crash (usually) and C is truly portable (you cannot run Java on certain devices iOS, Switch, PS4).

setpatchaddress• 5 years ago

You cannot generally trust that C primitive types are atomic.

eschneider• 5 years ago

Can't. You can't trust that unless the types are specifically declared atomic.

CyberDildonics5• 5 years ago

This seems more like someone taking wild guesses instead of information from experience and fundamentals.

First, I don't think "Joint Parallel" is a common term and everything gets synced eventually at some level.

Your solutions are languages, which are separate from understanding parallelism and concurrency. Using java doesn't solve anything directly.

it's GC:ed VM has a complex memory model that can handle fast lock-free concurrency relatively well, even using OO though you'll hit cache-misses.

This is almost like talking about the sound of a color. Lock free programming is not a factor of a language. If there are good lock free data structures that work for your specific problems, then that can go a long way to solving synchronization. OO and cache misses have nothing to do with anything here, that comes down to how something is written, not the language.

Use C on the client, primitive variable types are generally atomic so if you know what you are doing

This is not true. C has nothing to with this, it is a matter of getting access to atomics. Also primitive types are not "generally atomic", 32 bit stores can be written atomically, but that doesn't address ordering, compare and swap or atomic adds.

you should be able to joint parallelize cores with char, int and float arrays as data, also avoiding cache-misses!

This seems like real information fed through google translate a few times. 'joint parallelize' doesn't mean anything. Avoiding cache misses is a matter of accessing memory sequentially. Arrays are orthogonal to atomics, each element needs to be dealt with individually.

bullen3• 5 years ago

I minted Joint Parallel and gave the definition!

This code runs: http://move.rupy.se/file/atomic.txt

And that's all you need to know really.

As for experience, I wrote my own app server with distributed database and multiplayer protocol from scratch by myself and proved it with a MMO that has 300.000 customers:

https://store.steampowered.com/app/486310/Meadow/

https://github.com/tinspin

maxlybbert• 5 years ago

I put off reading the book for ages because I was convinced that knowing about locks and atomic data accesses, and intentionally keeping things simple would be enough to stay out of trouble.

The book certainly does cover how to coordinate between multiple threads, but it goes further by pointing out that the real secret to multithreaded programming is designing things so that coordination is kept to a minimum. For one thing, the coordination often has the side effect of purging your CPU caches! You definitely get a lot of cache misses. Even if you use atomic operations on primitive types.

I believe you can get a lot out of the book even if you already know Java’s or POSIX’s threading models.

belgesel• 5 years ago

A question to parallel programming experts. Can we assume that a task that is well seperated to perform on single core is always better than multi-core?

I meant using multiple instances working on single core vs. single instance with multi threads.

aparsons• 5 years ago

If you flip some NUMA switches so tasks on the other core don’t add overhead, I’m inclined to say yes. But then modern schedulers are also so low-overhead that this case really only applies if you have a hard real-time requirement - in which case dedicated hardware is the norm

jandrewrogers3• 5 years ago

Data sharing between cores is the bane of parallel programming at every scale. Consequently, high-performance parallel systems are not multithreaded in any meaningful sense -- each thread operates almost exclusively on private local data. See also "thread-per-core" software architectures for maximizing absolute throughput, which has its origins in supercomputing.

However, this creates a new problem for any workload that is not embarrassingly parallel. If all data is private to a single thread/core then the workload can become very unevenly distributed across cores depending on the data they own, destroying efficient parallelism in another way. Unlike multithreading, quick adaptive load shedding to smooth out these hotspots can scale surprisingly well across a very large number of cores/nodes with little overhead for many workloads. This is how many massively parallel codes are written today for workloads that are not embarrassingly parallel.

Partitioning data across cores with out sharing is necessary to maximize throughput, and almost always better than multithreading, but insufficient. Fortunately, mitigating transient hotspots is a mostly solved problem.

electricshampo1• 5 years ago

For this load shedding in a single node, are you imagining something more than work stealing style approaches?

In a multi-node cooperative setting you need some way to transmit information that a given node is overloaded, some way to find nodes that have available capacity, and a low overhead way to shift the work over to them. If the work to be done depends solely on data that you have local to you, it seems silly to shift the data as well (depending on how big it is); this would only make sense when you have to combine data from a variety of nodes (which can be done on any other node, assuming that the current node is overloaded).

Probably not worth doing anything about short lived hotspots (<1s). I wonder what kind of granularity you have used in your systems (probably different for within node vs across nodes).

gpderetta• 5 years ago

Sharing read only data is not an issue at all. Sharing data written by only one thread also scales very well: The single writer principle is well understood and critical for designing efficient multi-threaded applications.

imtringued4• 5 years ago

The only way to achieve perfect linear scaling is to run N threads that never talk to each other, because a single thread program doesn't communicate with other threads.

Whether you run processes or threads shouldn't matter. As soon as you do communication, expect your program to get slower than what is theoretically possible. Multiprocess tends to have higher communication overhead (not always).

raspasov• 5 years ago

Am I the only person that is surprised that this book does not mention immutability even once?

jayd16• 5 years ago

They use the term read-only many times.

fearthetelomere3• 5 years ago

One of the biggest issues I encounter with concurrency is whether the code I've written could be optimized to reduce cache misses.

I feel like a lot of resources including this wonderful book gloss over reducing cache misses. Is it really that trivial? What are the tips and tricks involved?

CyberDildonics5• 5 years ago

Where is this a problem for you? The broad goal to minimize cache misses is the same as concurrency in general - minimize synchronization. This means understanding dependencies and doing work on each core in chunks that are as large as possible for the amount of latency you can tolerate between synchronizing.

fearthetelomere3• 5 years ago

- "A high-performance implementation would of course use padding or special alignment directives to avoid false sharing."

- "Cache alignment and padding often improves performance by reducing false sharing."

- "Software can use the alignment directives available in many compilers to avoid false sharing, and adding such directives is a common step in tuning parallel software."

There's just essentially two or three lines in the book that I could find that refer to optimizing cache use through padding/alignment, and that was after knowing what to search for. Although I wouldn't be surprised if I missed something.

In my experience, the discourse stops at the surface level, which makes the topic appear like it's obvious or trivial. But there are many follow-up questions that naturally arise for me:

- What are the trade-offs of cache-padding shared data? Why does it degrade performance for certain problems?

- What is a good rule-of-thumb for when to prioritize cache padding/alignment over cache locality?

- Are there other best practices like cache padding/alignment/locality that improve performance?

- What is an alignment directive and how does one use it?

I agree with what you've said, I was merely pointing out that I wish parallel programming resources delved more into this subject, as I feel that it's a practical and common issue. I'm sure it's not trivial and requires a fair bit of expertise, but that's why one would reach for a book like this after all.

bob1029• 5 years ago

The hardest part of parallel programming is tricking yourself into believing you need to worry about it at all.

9/10 times, if you use the right tools & techniques, a single x86 core (assuming you have access to a 'real' one) can easily chew through millions of business transactions per second and easily satisfy all technical requirements for whatever business system.

Latency is the ultimate devil. Getting your synchronous state to fit into L1/2 and processing transactions in (micro)batches of contiguous data is how you win the game. The closer your data is to your compute, the faster you can go.

The biggest problem most developers are struggling with right now is that they got tricked into scattering their business systems across many computers and potentially across multiple physical regions. The latency in L1 is measured in nanoseconds. The latency between 2 datacenters is measured in milliseconds. This is SIX orders of magnitude difference. Even if you squander 3 of those to some bad programming practices, you are still 1000x better off on a single box using a single thread than if you scattered your infra to the seven winds.

See: LMAX Disruptor for a case study in what the opposite end of the "infrastructure isnt my problem" spectrum looks like.

VHRanger• 5 years ago

A problem here is that people interpreted some common sense advice like SOLID into "break everything into classes pointing to each other".

Which creates maximally cache hostile code very fast -- any operation is often several pointer dereferencing (eg. back-and-forth to RAM).

flukus• 5 years ago

Even in code like this just being aware of cache levels and there relative timings can sometimes produce some impressive speedups with simple things like sorting the initial data to make it cache friendly. A recent one I improved was along the lines of:

  for t in transactions
    t.client = clients[t.ClientId]
    t.product = products[t.ProductId]

In this case sorting transactions by ClientId, ProductId was an orders of magnitude speedup because client and product were already in cache in L1/L2 cache most of the time. It could have been faster again with less SOLID but improvements like this are often easy and politically achievable because it keeps the sacrifice to the OO gods.

Treating Big O as the be all of performance has quite a lot to answer for in real world code, often constants aren't so constant.

tmotwu• 5 years ago

Parallel programming is not what you think it is. You're right that parallelism is not the answer to everything, but parallel programming is not even a paradigm people use to write basic business transaction logic. Distributed computing, yes, not parallel programming. Amdahl's law has more to do with diminishing returns in parallel processing moreso than physical proximity to memory.

9/10 times the hundred cycles you save from leveraging your caches vs memory accesses is eclipsed by millions/billions of extra cpu cycles you have to perform for certain computations. Not to mention not every application has predictable memory access patterns that would benefit from LRU/LFU policies.

Now that Moore's law is no longer the bible in computer architecture research, CPU designers have to resort to increasing core count. With the advent of machine learning and big data workloads, you'll spend thousands of years crunching numbers on a single threaded application.

Nasrudith• 5 years ago

It sounds like a dumb tautology but parallel programming is easy for parallel problems. It is harder to say maintain several interlinked grid cells in a simulation in parallel than it is to partion a non-interacting set to N cores to run in parallel and let the main thread know when everything is done.

“Is Parallel Programming Hard, and, If So, What Can You Do About It?” v2 Is Out

Related Stories