The thing I finally realized after being big on parallel algorithms and such since first learning about them in university is that, honestly, most things don't need to be cleverly parallel.
The majority of tasks are "embarrassingly parallel" as they say. Which is just to mean, there are a lot of standalone tasks that need to be done. For example, any web server is embarrassingly parallel. You don't need to be clever, you just need to have the processing power available to handle them.
True, a lot of tasks are not embarrassingly parallel, as you point out, but most tasks that run on supercomputers are embarassingly parallel. That's why those supercomputers have value in that problem domain in the first place.
Exactly, pretty much any parallel algorithm is embarrassingly parallel (gather or calculate a bunch of data, process it and merge it together) so I question the need for continuously needing in-process parallelism instead of solving it trivially.
Embarrassingly parallel problems are relatively rare. Even GPU cores are quite big and they’re explicitly dedicated to mostly embarrassing parallelism.
The complexity is sadly mostly inherent in the problems being solved.
The term "embarrassingly parallel" doesn't refer to algorithms, it refers to problems which can be computed in such a manner, stating that they're not very interesting for parallel algorithms research. But yeah, it's kind of a stupid term. Would you be okay with "pleasingly parallel"? ;)
I'm really surprised at the arguing in this thread.
Embarrassingly parallel algorithms are trivial in pretty much every language. That is why is embarrassing.
>And then you also need to implement mailboxes to receive new data
If you did, it is not embarrassingly parallel.
You know, a huge amount of parallel work is done in C/C++. It was the language used for multiple parallel algorithms courses in my university. Being able to do basic MPI type stuff in C does not make you a top programmer. And not being able to do an embarrassingly parallel algorithm in C would ring alarm bells.
People down vote this, so I will provide a bit more explanation: Parallelism is 'easy' as long as you have natural separated problems. This is the reason embarrassingly problems are so great for many-core systems. Every single sub-problem can be done without having to synchronize with other parts of the system. Unfortunately, most problems aren't that way, but instead are interlocked on multiple axes:
- Minimal granularity: You can never run more cores than you have problems at the same time, but you also cannot just split problems as long as you want or the overhead of splitting will kill all performance gains you'd had (x+y in an extra thread/process is technically possible, in reality pretty stupid)
- Synchronization points: Most problems are not completely separate from each other, so you can do part of the problem in parallel but at some point you have to converge and do something with the combined result.
- Comparable task size: In an ideal world all of your tasks would take exactly as long as the other, because if one task takes far longer than the others you have to wait for it. So, the minimal run time of your parallel problem is bound by the time of your longest sub-problem. If one of the problems takes far longer than the others (and they depend on each other) you've lost.
The last one is more of a "meta" point: Complexity doesn't scale linear for dependent problems. That's another reason embarrassingly parallel problems are so nice. You cannot only run them all in parallel, you can think about each one as a completely separate problem. The moment you have dependencies you have to think about how to bring them all together and that gets hard very fast if you have many moving parts.
So, to sum it up: Many small things conspire against just scaling something which works great for two or four cores up to eight, 16, 32 or whatever. If you happen to have an embarrassingly parallel problem you're golden, but unfortunately only a small subset of interesting problems are that way and for other problems scaling is hard.
If you do not understand that "embarrassingly parallel" is a technical term and that it's generally understood that most programs are not easily parallelizable, there is not a discussion we can have here.
That's called an 'embarrassingly parallel' problem, it's not the general case. I guess, just like 'big O', people have to take a class to appreciate the space of what it's possible to parallelize and how much it buys you.
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.
It doesn't matter how much of an expert you are if your algorithm fundamentally isn't parallel though. We just don't know how to parallelise some things.
It's just we see so many parallel collections, parallel streaming, parallel map, parallel for-loop efforts, and they always rely on the problem being embarrassingly parallel in the first place!
Parallelizing a turd across hundreds of machines doesn't mean you're doing something genius, it just means you now have a hundred machines that have to deal with your shit.
Most programs don't use anywhere near enough cpu to make parallel algorithms pay off. So you may as well keep it simple, especially if you aren't hitting the limits of your current algorithms. Simplicity means less code, which means less bugs.
I think the idea is that your locks and threads are so close latency wise that you only need a few to get the job done. Versus trying to figure out how to parallelize things, some of which are inherently non-parallelizable. But sometimes you don't know until you try! Ain't life grand?
The majority of tasks are "embarrassingly parallel" as they say. Which is just to mean, there are a lot of standalone tasks that need to be done. For example, any web server is embarrassingly parallel. You don't need to be clever, you just need to have the processing power available to handle them.
reply