He's serious, right?

There's an article in Chip Design magazine by Peter Claydon, titled Implementing Multi-Core:The Devil is in the Detail. The standard argument that lots of slower processors can get more computing done, and with less power, than one big high-speed CPU.

Of course, this is true if the computing task is embarrassingly parallel. Graphics, packet switching in a router, high volume web services, and so on -- sure, no problem. But if the task is not like this, the serial bottleneck will kill the overall performance. Has the history of Thinking Machines been wiped from everyones memory?

We've known the problems for four decades. Are people still really falling for this stuff?

The Hippocratic Oath...

A nice post over on Living the Scientific Life.

The University of Toronto Institute of Medical Science formulated this:

I promise never to allow financial gain, competitiveness or ambition cloud my judgment in the conduct of ethical research and scholarship. I will pursue knowledge and create knowledge for the greater good, but never to the detriment of colleagues, supervisors, research subjects or the international community of scholars of which I am now a member.

Good stuff; us folks in science and engineering need to keep the big picture in mind. There's tons of pressure put on researchers and faculty to generate funding, push out papers, get awards, and so on. Probably more people than one would wish take the "easy route." It's a great privilege to work in science; the tenured gig at a decent university is particularly great. And as the wise man said, "with great power comes great responsibility."

Parallel EDA tools from DAC

DAC had a few sessions this year on multi-core processors, and how they were going to be used in electronic design automation. History buffs will note that there's actually some prior work in the area. For example....

• Performance of a parallel algorithm for standard cell placement on the Intel hypercube by M. Jones and P. Banerjee..... from DAC 87
  
• Massively parallel switch-level simulation: a feasibility study by Kravitz, Bryant, Rutenbar, DAC 89
  
• and of course there's a good tutorial: Tutorial on parallel processing for design automation applications (tutorial session) from DAC 86.
  

This is the tip of the iceberg. These papers are easy to find. Here's a link to the ACM portal for papers that have the word parallel in the title. Lots out there. Strangely, these don't get cited in the current work.

If we want to make EDA tools parallel, and there are stacks of papers of papers from the past 20 years on precisely that topic... why not just recompile what we have? Why not cite the prior work? Check out the current crop of papers -- and in particular the references. Not enough people doing their homework, if you ask me....

The original paper

Not many people have read the original paper (it's pretty hard to find), so here's a pointer to it. It's retyped by Guihai Chen (thanks!) into an easy-to-read PDF.

Note that this was actually a transcript from a talk, rather than a formal paper.  The context of the talk was as a debate between the "serial computing" advocates, and the "parallel computing" advocates.  There's a chart that illustrates the "expected zone of operation" for most computers -- essentially how much work was expected to be serial in nature, and how much parallel.  Some of the analysis work was done by Professor Knight (can't find his full name) at Stanford, so there's a lot of effort before the intuition sets in.

For most work loads, Amdahl expected that parallel machines would give diminishing returns -- and that seems to be the case.  No rule against having things that are massively parallel; just not the common case.

Also note that the "Law" was formulated by someone other than Amdahl.  In his ICCAD talk, he mentioned that he had given the above presentation, and because of the contentious nature of the whole event, he put it out of his mind.  A few years later, he started hearing about the law from others -- and was somewhat surprised that people had taken the ideas in the talk and run with them.

From the deck of the Titanic

Over the past few years, there's been a shift from serial performance to massive parallelism; pretty much anyone with a pulse has noticed this.  The alarm bells went off for me when the EE Times ran a story on Intel canceling a couple of designs, and going multi-core.  I'm anti-parallel, or to be a bit more precise, I'm pro-serial.  There's no way to swap increased numbers of processors for increased clock rate.  Intel getting out of the clock game said to me that Moore's Law was over, and that pretty soon, technology scaling will halt.

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.