Comment by jacquesm | Hacker News Reader

Comment by jacquesm | Hacker News Reader

Parent Full thread

You don't avoid Amdahls law nicely or otherwise for those problems to which it applies. It's a mathematical thing, not a technical thing.

Problems that are split up over many cores, processes or even clusters of machines always have some serial component, and that serial component determines the minimum run-time for the whole computation.

So even if all the rest of the work would be reduced to '0' then there would still be that serial component left, whatever it was.

This is not at all about playing mp3s or server loads such as web serving that are embarrassingly parallel and that can be run in a shared nothing environment. It is all about computing solutions to problems where there is some shared state between the various parts of the computation.

In computations like that the serial bits are visible as bottle-necks in the data flow, either because there is a synchronization point and some kind of reduction of the data that can only be done in a serial fashion, an ordering or some other operation that can only be done by a limited number of the total available cores. Those sections, and only those sections will put a lower limit on how fast you can solve that particular problem for a given data set.

You are right, my wording was incorrect. I'll try to put what I wanted to say in the words of Dr. Thomas Puzak, IBM: "Everyone knows Amdahl's law, but quickly forgets it".

That said, Amdahl's law does NOT apply to problems, it applies to programs: https://en.wikipedia.org/wiki/Amdahl%27s_law What I was trying to say is that, from my experience, if you take an existing program and try to parallelize it with minimal effort (e.g. parallelize all loops), then you may end up with having a serious percentage of serial code. (Or you don't, because your data is large enough, see Gustafson's law: https://en.wikipedia.org/wiki/Gustafson%27s_Law ) However, if you put in more effort and re-architect the program, you'll usually worry about a lot of problems, but Amdahl's law is not one of them. Yes, you didn't "avoid" Amdahl's law (and you can find counter-examples where Amdahl's law is a real concern).

I actually heard a talk about ordering in in-memory databases. It basically comes down to Gustafson's law: If your dataset is rather small, the overhead of parallelization (some of which can be attributed to Amdahl's law) isn't worth it, you just do it on one core. But because your dataset is small, it is so fast that nobody cares. If your dataset is large, each core sorts a subset. Then you start aggregating, and the final aggregation is serial. However, because you already have sorted lists, you can use a different algorithm that merges this very quickly (but would perform bad on unsorted data). I can't remember any specific numbers, but the bottom line was that even with a very beefy server that had 4 sockets and plenty of cores, the serial part wasn't an issue in terms of overall performance. Keep in mind that the author talked about a Multi-core myth and not a Many-core myth.

Again, I don't argue that near-linear speedup is possible for most problems. Most often it's not. But naming Amdahl's law as the only reason is wrong.

Reply on news.ycombinator.com