6 ms·
Amdahl's Law
- hyperpallium2 6y agoThe general formulation is interesting, that some parts are sped up, and some aren't. Bottlenecks.
- Bluestein 6y ago"In computer architecture, Amdahl's law (or Amdahl's argument[1]) is a formula which gives the theoretical speedup in latency of the execution of a task at fixed workload that can be expected of a system whose resources are improved. It is named after computer scientist Gene Amdahl, and was presented at the AFIPS Spring Joint Computer Conference in 1967."
- dnautics 6y agoThe counterpoint is gustafson's law: https://en.m.wikipedia.org/wiki/Gustafson%27s_law https://en.m.wikipedia.org/wiki/Gustafson%27s_law
- hyperpallium2 6y agoI predicted that because some computations are hard or impossible to parallelize, attention would shift to solving real-world problems with computations that can be parallelized. 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.
- verdverm 6y ago"Gordon Freeman" (as he is affectionately referred to) would argue otherwise, fervently! - https://www.cs.binghamton.edu/~pmadden/pubs/dispelling-ieeedt-2013.pdf https://www.cs.binghamton.edu/~pmadden/pubs/dispelling-ieeed... - https://dl.acm.org/doi/abs/10.1145/1324499.1324502 https://dl.acm.org/doi/abs/10.1145/1324499.1324502 - https://community.cadence.com/cadence_blogs_8/b/ii/posts/eda-workshop-debate-erupts-over-parallel-programming?CommentId=504ea082-91ee-455b-aede-fdad45e9a76d&pifragment-1576=310 https://community.cadence.com/cadence_blogs_8/b/ii/posts/eda... - https://www.cs.binghamton.edu/~pmadden/ https://www.cs.binghamton.edu/~pmadden/
- hyperpallium2 6y agoI'm saying that techniques that are easy to parallelize will become more popular. 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.
- thyrsus 6y agoMany data centers are larger than houses. I expect them to get larger as cores get cheaper, and code gets smarter about NUMA.
- carlmr 6y ago>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. 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.
- yellowapple 6y agoRight, but how does that compare to the incumbents? The JVM and .NET CLR don't seem to be going anywhere. 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).
- jsolson 6y ago... how high did you expect CPU core count to be at this point with close to uniform memory access costs, and what changes did you expect to enable that degree of concurrent bus access without catastrophic stalling due to contention?
- hyperpallium2 6y agoI was thinking of GPU cores having random write access, but yes that has concurrent access problems. 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.
- monocasa 6y ago> BTW how do GPUs solve the concurrent bus access you mention, with many cores are writing pixels? Batching and buffering with spatial locality so that you can stream out relatively large bursts of pixels.
- kache_ 6y agoThis concept generalizes really well to many things outside of computing. For example, this is why adding more engineers to a team can slow things down.
- vegetablepotpie 6y agoI’m not so sure of that. Amdahls law tells you the speed up to expect when adding more cores to the parallelized portion of an algorithm. Whereas adding a new member to a team slows down one or more members for a matter of weeks/months because the members are spending time they would otherwise spend producing teaching the new member.
- hntrader 6y agoAmdahl's Law says that the marginal benefit of additional cores is always positive (or zero). What you're describing is negative marginal benefit.
- hinkley 6y agoCommunication overhead.
- hntrader 6y agoMostly that, but I would add cultural and competence issues as well - more internal politics, and C-teamers sneaking in that drag the team down. 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.
- loloquwowndueo 6y agoThat’s more of a dispelled myth and not Amdahl's law. https://en.m.wikipedia.org/wiki/The_Mythical_Man-Month https://en.m.wikipedia.org/wiki/The_Mythical_Man-Month Specifically :)
- majewsky 6y ago
- yongjik 6y agoI remember coming across Amdahl's law in the grad school and thinking, "Why is this even a law? Isn't it something completely obvious?" ...later I became a developer. Turns out it's not obvious.
- Veserv 6y agoI mean, the law part is still completely obvious. If you have a part that scales proportionally with workers (p) and a part that does not scale with workers (1 - p), then only the part that scales proportionally with workers scales with the number of workers (p / s), it is pretty much a tautology. 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.
- dwohnitmok 6y agoThere's a lot of things that are obvious when stated, but for various reasons people don't really grasp their ramifications. Put another way, it seems often difficult to grasp just how significant an already superficially internalized concept really is. 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).
- rileymat2 6y agoIsn’t it double that? 2piR
- jeswin 6y agoIs there are separate rule (or phrase/idiom) one can quote for the "Serial Programs" part of Amdahl's Law? 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.
- justinsaccount 6y agoI often use a variation of this line of thinking for determining if something is worth optimizing. 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.
- SatvikBeri 6y agoTechnically that's still just Amdahl's law, the statement has nothing to do with parallelism. I'm not sure when it became so heavily associated with parallelism.
- Mandatum 6y agoThis ties into the Theory of Constraints, right? Only as fast as the slowest part.
- anonytrary 6y agoIt also applies to chemistry, physics, and everything else. If you have a reaction that depends on step A and B, and A must happen before B, but B can be sped up arbitrarily with diminishing returns by introducing an enzyme, then the whole reaction will still take slightly longer than the time it takes to complete A.
- moonchild 6y agoSee also: the universal scalability law, a refinement thereupon - https://wso2.com/blog/research/scalability-modeling-using-universal-scalability-law https://wso2.com/blog/research/scalability-modeling-using-un...
- dang 6y agoSurprisingly few relevant past threads (that were any good), but I found these: Gene Amdahl has died - https://news.ycombinator.com/item?id=10557793 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 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 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 https://news.ycombinator.com/item?id=3490492 - Jan 2012 (1 comment)
- Bluestein 6y ago(We need a new "rule", rule ... 42? "If it exists, there is a HN thread on it. No exceptions." :)
- yellowapple 6y agoRule 42a: if a HN thread does not yet exist for it, then it is your civic duty to create one.
- Bluestein 6y agoI like this one better than 42, with the appeal to civic duty and all :)
- tomrod 6y agoRule 42a.1: if someone has created a novel thread, the community should support with up votes even if they disagree with the conclusions or assertions.
- Bluestein 6y agoThis. So much this ... 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).-
- onikolas7 6y agoThe insight from Amdahl's law is what led to the creation of hybrid processors like the Cell (used in the PlayStation 3 console). They quickly became irrelevant as GPGPU became more mainstream.
- vasco 6y agoOne thing that was taught to me in university related to this, is that in optimisation, "every little bit" does NOT help. This insight applies to everything, and is the cause of great frustration. The world should know about this law and that optimising the 3% case is useless in any field, if there's an 80% case staring you in the face.
- anonytrary 6y ago> ... if a program needs 20 hours to complete using a single thread, but a one-hour portion of the program cannot be parallelized ... then regardless of how many threads are devoted to a parallelized execution of this program, the minimum execution time cannot be less than one hour. 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 + ε.
- avh02 6y agoI had a special topics course in parallel computing in university - Amdahl's law is probably the single biggest takeaway from that course. 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
- Bluestein 6y agoSee the "many people dishwashing in a small kitchen" comment upthread :)
- saberience 6y agoMaybe I'm missing something here but isn't this mind-numbingly obvious? I've never read this before but this is exactly how my mental model for parallelisation has always worked.
- heinrichhartman 6y agoAhmdal's law describes the scaling behavior of systems with contention ("serialized workload portion"). This was generalized to the Universal Scalability Law by Neil Gunther which additionally takes into account "cross talk" for coordination between nodes. Systems with cross talk always run into configurations where adding more nodes will decrease the throughput of a system. This is best explained in Baron Schwarz's book: https://raw.githubusercontent.com/VividCortex/ebooks/master/scalability.pdf https://raw.githubusercontent.com/VividCortex/ebooks/master/... My notes on this topic are here: https://nbviewer.jupyter.org/github/HeinrichHartmann/Statistics-for-Engineers/blob/master/2017-10-17-Velocity-London/S8%20-%20Math%20V%20-%20Queuing%20Theory.ipynb https://nbviewer.jupyter.org/github/HeinrichHartmann/Statist...
- hutrdvnj 6y agoThis is why we need 100% parallel code, binaries that we can run in parallel across many different machines.
- sidpatil 6y agoThat won't make a difference unless the underlying algorithms can be perfectly parallelized. That's the whole point of Amdahl's Law.
- mettamage 6y agoAmdahl’s law reminds me to tell people why computer science can tell us why we can’t have more than 3 to 4 people washing dishes in a small kitchen. 1 washes dishes 2 to 3 are drying Everyone else would simply congest the process
- maweki 6y agoIn my research group we're sometimes benchmarking parallel systems (databases with parallelizable queries). Whenever there's a student thesis, I force them to explain Amdahl's Law in their thesis, and contextualize their work regarding this Law. 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.
- hugs 6y agoI thought about Amdahl's Law a lot when I started Sauce Labs. To make browser test automation faster, the initial plan was to throw more hardware at the problem by getting more servers and running tests in parallel. But we were always looking for other things to optimize because we knew "throw more hardware at the problem" was going to stop working at some point. One example was virtual machine startup speed. In early days on EC2, Windows VMs took 10-ish minutes to boot up, I think part of the reason was because they had to do a disk image transfer first. But if you can keep lots of redundant copies of disk images in lots of places, you can reduce that waste of time on pre-boot network data transfer and ride the Amdahl's Law curve a little longer. Another trick is having the VM "pre-booted" by having a VM snapshot to jump to avoid the entire boot process. Of course, getting this much low-level control over the boot process to optimize for parallelability means building out your own cloud, which is another story for another day...
- sunstone 6y agoThe Goal, but with computers.