Parallel Computing's Upper Limit
Does Quadrupling the Threads Quadruples the Speed?
Yesterday we got our first hands-on with Bend, which claims to simplify how we write parallel code.
So can we speed code up forever?
No. Amdahl's Law says there is a clear upper limit to what parallel computing can solve. The maximum improvement from parallelization is limited by the part of the system that cannot be parallelized.
Max 20x speedup on normal tasks with multi[core/thread/process]
Max 1000x speedup on highly parallelizable machine learning tasks with CUDA
Say we need to run six jobs. Run them one by one and it will take eight units of time. We can even give the benefit of not needing a "start" and "end" since the sequential process needs no fancy setup, so call it 6-8 units.
Parallelize them and you do need an explicit "start" and "end", delegating tasks to each worker and subsequently aggregating the results. Naively put, if we can run all six at once, we can finish the entire thing within three units.
In this (overly simplified) example, running six workers at once only results in roughly twice or thrice the speed.
We can express it as a formula.
Where
P is the proportion of the program that can be parallelized.
N is the number of processors.
(1−P) is the portion of the program that cannot be parallelized.
Beating those numbers was exceptionally hard. Bend uses a novel approach of interaction combinators, which represent algorithm operations in a discrete graph. We can then use divide and conquer, thus parallelizing the computation.
The team behind Bend claims that Bend can make it
12.66x faster with multi[core/thread/process]
57.86x faster with CUDA
Amdahl's law still stands.
No backlinks found