What's wrong with multi-core, you say? Well.... parallel computing companies have failed to go anywhere for the past four decades. Every few years, someone comes along, proclaiming a golden age of parallel computing; everyone gets all excited, and then these prophets quietly slip away in the night, generally with a sack of cash and a few prestigious awards.
The main challenge is Amdahl's Law -- hence the name of the blog. It's a bit of a simplification, but surprisingly useful. Assume you look at some source code, and can determine that P percent of the machine instructions you need to execute can be done in parallel. If you have n processors, then the run time for the parallel section can be sped up by a factor of n (this is really optimistic, but we'll go with it anyway). The serial part, though, (1-P), chunks along at the same pace.
Gene Amdahl presented this in a classic talk from 1967. If P=90%, you have 10% serial -- and the speed up over a serial processor is at most 10X, no matter how many processors are available. Getting to 90% is very difficult; Amdahl's back-of-the-envelope guesstimate was that for most applications, you could expect somewhere from 60 to 70% parallel code. There would be applications higher (some very close to 100%), and some lower, but his ballpark seems to be about right.
With all the excitement over multi-core, I feel like I'm sitting on the deck of the Titanic, watching the captain put the engines on full, accelerating towards the iceberg. We've crashed here dozens of times before, and we're doing exactly the same thing again.
Read up on Amdahl's Law if you have not done so already. You can see a video of Gene Amdahl talking about the law, as well as a panel discussion -- from November 2007. These next few years are going to be a fun ride.
2 comments:
Patrick, I'll see your Amdahl's Law and raise you Gustafson's Law, which says that any sufficiently large problem can be efficiently parallelized. Of course, like Moore's Law, neither Amdahl's Law nor Gustafson's Law are actual, physical laws. They are conjectures about the innate nature of human artifacts known as computers. However, we in the embedded space see our way clearly to parallelization. In fact, we systems designers have always used parallel design, just not with processors. Many complex systems use dozens or hundreds of hardware blocks all working in parallel. It really makes no difference if the block is composed of hardwired logic or a firmware-driven processor.
P-complete problems are those decision problems to which any problem in P can be reduced using logarithmic space. After decades of trying, we still have no way to parallelise P-complete problems in any reasonable way. This seems as far away as solving NP-complete problems in deterministic polynomial time.
None of this would matter if P-complete problems were uninteresting. Unfortunately, they include linear programming and the circuit value problem.
In contrast, Gustafson's Law is based on the assumption that one can replace the problem with a different one as the number of processors increases, keeping the actual length of the sequential part the same.
The new, larger problem might have a smaller sequential fraction, but when one is trying to reduce the wall-clock time it is really, really unhelpful to suggest running a discrete simulation for more steps, or to decrease the cell size of a finite element mesh. A more efficient computation does not translate into a faster one. With Intel now bringing slower clock speed "new and improved" multicore CPUs to market, relying on Gustafson's Law can mean an increase in wall-clock time as one moves to newer hardware.
So there may be some problems where Amdahl's Law trumps Gustafson's. And not even Gustafson can help us in the face of reductions in CPU clock speeds.
Post a Comment