Amdahl's Law
en.wikipedia.org
en.wikipedia.org
...later I became a developer. Turns out it's not obvious.
The only reason why it is non-obvious how to take advantage of it in practice is that problems in the real world very rarely break down so cleanly into a completely serial piece and a trivially, arbitrarily parallelizable piece and even if you are lucky enough to find such a problem at a certain scale, the very act of breaking down the problem almost always eventually results in other previously ignorable constant or scaling factors becoming important either as you chop the problem into smaller pieces or as you scale to bigger problems. The difficulty lies entirely in posing the problem to be "solved", not the application of the law itself.
E.g. pigeonhole principle -> no perfect compression (among other similar proofs)
Another a favorite one I have is understanding just how "weird" it is that pi, a constant, exists. Take a rope and tie it around the Earth so that it fits snugly on the Earth's surface. How much more length of rope does it take so that the entire rope circling the whole of the Earth can be lifted 10 feet off its surface? ~31 feet (this was at least surprising to me the first time I was asked this question, which was long after I first learned about pi).
It is similar to the ideal gas law, for example, which can be proved from the axioms of classical thermodynamics and yet fails when the molecules start interacting.
Laws span the whole spectrum from purely empirical to provable within some theories' frameworks.
Maybe this is one factor in ML, deep learning neural nets vs. symbolic?
However, engineers tend not to develop techniques without actual hardware [1]. And CPU core-count has remained much lower than I expected [2]. Therefore, my prediction has not come to pass, yet. But it totally will!
1. In myself, I can imagine a maybe-possible situation one or two steps away from present reality, but not see the consequences... but the instant I learn it is definitely possible, I can see consequences.
2. Yes, GPU core-count is sky-high, but is limited by memory access.
- https://www.cs.binghamton.edu/~pmadden/pubs/dispelling-ieeed...
- https://dl.acm.org/doi/abs/10.1145/1324499.1324502
- https://community.cadence.com/cadence_blogs_8/b/ii/posts/eda...
Of course he's right, that if you can make a serial technique faster, you should do that.
I see a way to support his position: in past decades we got free speedups from silicon - then we hit a kind of "Peak Silicon". Just as for Peak Oil, it makes sense to try techniques that weren't worth it before.
Personally, I think the first step should be to give up all the horrific layers of bloat-on-bloat; but instead we got (e.g.) faster JVMs and JIT JS compilation.
But what about the step after that? He thinks we should mine the tailings (and he's surely right there's a lot to be found there).
I think multi-core seems the only extendable solution (til I guess computers are the size of houses again). But because it's so difficult to parallelize code, we'll instead change our approach, and favour techniques that are easy to parallelize. Arguably, this is currently happening with DL.
I've only skimmed the links you gave, so I don't have a deep appreciation of his position.
I think this is already happening. The trending languages I see in HN are Rust, nim, zig right now. We're going back to native, and in Rust's case also with fearless concurrency as a paradigm.
In this day and age I don't think the abstraction layer is the issue. Modern bytecode VMs are already able to be within an order of magnitude of native code, and I'd imagine there's still plenty of room there for improvement (WASM comes to mind). Unless you're on constrained hardware, or developing directly against hardware (rather than using an operating system, which is itself a horrific layer of bloat-on-bloat), a bytecode VM is still perfectly reasonable even for soft-real-time applications (let alone for applications that are throughput-sensitive rather than latency-sensitive).
Looking at the slowing of hardware advances this could be a 10 year lag in performance. I think that's quite significant.
I think byte code VMs have their place, and for many applications that may be enough, but if you have high performance needs it may be worth checking if the price is one you're willing to pay.
And yet, Java, C#, Erlang, Perl, Python, Ruby, Tcl... all of these languages and their VMs are decades old now. And yeah, the languages toward the end of that list ain't exactly speed demons, but the ones toward the front are already commonly used for high-performance applications with pretty dang good success, and even the ones toward the back of the pack are there for other reasons beyond just the VM (global interpreter locks, parsing overhead, things like that).
The VM, that is to say, ain't the issue. Hell, things like SPIR-V demonstrate that VMs are perfectly fine even for GPU computation. There's a price, sure, but eliminating that price is about as premature of an optimization at it gets for all but the most constrained of environments. There are almost certainly worse bottlenecks - and those bottlenecks are probably around I/O and memory, knowing most applications (and a bytecode VM often helps here, since the opcodes can be tuned for minimum size, often giving even RISC CPU opcodes a run for their money).
With C/C++ I agree, you'll spend weeks and years debugging depending on how long lived your application is, that you wouldn't have in Java or C#.
In the top 10 you will always find bytecode/vm based solutions not far from C/Rust implementations. Of course, these are highly optimized, but the assumption that native is always better is not always true.
What I find so beautiful about the native/close to the metal languages is that you can have clean code that's also near optimal, without optimizing a lot. Compared to the lengths people go to get some Python code to run fast it's the easier way.
Um, no:
1. Manual memory management doesn't have to be complex at all - and is arguably much easier to reason about than garbage collection, even if it's more error prone / less guaranteed-to-be-safe
2. Rust's manual memory management (i.e. the default kind of memory management in Rust) is of at least the same complexity as any other sort of manual memory management - if not more due to the need to be explicit around lifetimes and borrowing.
The memory management strategy is regardless orthogonal to whether there's a VM involved; there are garbage-collected native languages (Lisp, D) and not-garbage-collected VMs (WASM, or languages like Perl and Tcl if you count reference-counting as "not-garbage-collected") galore.
So we'll change problems/contexts to ones that are easily parallelizable.
In that dispelling-myths paper, Patrick Madden notes that a less efficient but faster-because-parallel method still uses more energy. A good point, but I'll note that because energy consumption is superlinear with frequency (e.g. a 2 core method at half the clock speed of a 1 core method will use less energy, assuming perfect parallelization), a parallel solution can be both faster and more energy efficient. GPU compute shows this e.g. bitcoin mining.
His last paragraph begins:
Despite these challenges, there is no choice but to forge ahead with parallelism
Finally... why is he known by the half-life protagonist? Does he look like him, or is there some thematic connection?
1. Maybe the entire context can be formalized and solved, so you can't "change the problem", but even then, real-world problems tend to keep changing, because of changing customer demands, competition, technology, legislation etc.
BTW how do GPUs solve the concurrent bus access you mention, with many cores are writing pixels?
Also, is this GPU-style processing, where each core writes a separate result (a texture/display pixel or transformed vector) but can read randomly (from textures), the only approach to parallelization that works? It's a form of scatter-gather.
Batching and buffering with spatial locality so that you can stream out relatively large bursts of pixels.
This is best explained in Baron Schwarz's book: https://raw.githubusercontent.com/VividCortex/ebooks/master/...
My notes on this topic are here: https://nbviewer.jupyter.org/github/HeinrichHartmann/Statist...
Gene Amdahl has died - https://news.ycombinator.com/item?id=10557793 - Nov 2015 (111 comments)
Compilers and More: Is Amdahl's Law Still Relevant? - https://news.ycombinator.com/item?id=8930987 - Jan 2015 (17 comments)
Amdahl's law in reverse: the wimpy core advantage - https://news.ycombinator.com/item?id=5265242 - Feb 2013 (16 comments)
Amdahl’s law - Amdahl's original paper - https://news.ycombinator.com/item?id=3490492 - Jan 2012 (1 comment)
(We need a new "rule", rule ... 42?
"If it exists, there is a HN thread on it. No exceptions." :)Tip of the hat to you sir.-
This is so much in the spirit of the site, methinks ...
... support the thread, because it -fosters discussion-, and have the wherewithal to have your point of view challenged.-
Expose yourself to the opposing viewpoint(s).-
This is one area where teams waste a lot of time; spending too much effort improving an area which doesn't matter so much. Amdahl's law could be quoted, but the articles generally skew heavily towards parallelism.
What you're describing is negative marginal benefit.
It's easy to make sure everyone in a small team is elite and has value alignment, and it's hard to maintain that as it gets bigger.
https://en.m.wikipedia.org/wiki/The_Mythical_Man-Month Specifically :)
It really does seem obvious. You can either do the sync part before or after the parallelized part. Since you cannot have infinite horizontal compute, the parallelized part will take some ε > 0 of time to finish, and the total execution time will be 1 + ε.
1 washes dishes
2 to 3 are drying
Everyone else would simply congest the process
It's amazing how applicable it is to more general things in life as well - can't remember examples right now but I've reasoned about many day-to-day things and realised Amdahl's law applies
From this most students correctly get the idea that they have to analyze the parts of the workload seperately, as their parallelization behaviour is not uniform.
For example, loading the data from a spinning disk - given one disk - behaves differently than, for example, the evaluation of a query once the data has been loaded.
Sometimes it can be hard to tell from profiling output or flame graphs just how much time is spent somewhere. Before trying to make something faster the first thing I do is turn it into a no-op.
If avoiding doing something entirely makes the program run 2% faster, then making that run in half the time is only going to give an overall 1% improvement.
I don't know if there's a name for this variation. It's just the same thing applied to different components and not specifically related to parallelism.