Google's Folding@Home on the "Multi-Core Crisis"

There’s been a fascinating exchange about programming for multi-core computers on Dave Farber’s Interesting People List. It started when Andrew Donoho wrote in a thread about the need for US colleges to retool their programming classes:

It is very clear that the software industry is going to hit a programming wall some time in the next 6 years (4 Moore’s Law generations). Microprocessors are going to progress from 4 to 64 processor cores. Most algorithms, other than the embarrassingly parallel ones, will hit this wall. This wall is not going to be surmounted by ‘code monkeys’. To truly exploit this coming surfeit of processors, we will need both architectural and software invention. This problem will need ‘classically trained’ disciplined thinkers. While I was not trained as a computer scientist (experimental physics was my field), the problem is going to need folks of the caliber that originally defined our core architectures. (The next Johnny Von Neumann, I’m looking for you.) In other words, we are entering an era of unprecedented architectural research and invention opportunity.

Adam Beberg replied:

Sorry Dave, I just can’t let the multi-core “crisis” comment stand
without a reply. That false meme needs to die.

I work on Folding@home, which is a 250K-node distributed system, where
each node is now days a dual-core at minimum, an 8-core Cell on avg, or
at maximum an on chip cluster of SMP elements with 1000’s of threads in
a NUMA setup of vector processors in the new GPUs. Nominally we have a
1M+core system operating as a coordinated whole.

The idea that 64 cores is a problem is patently absurd. Complex on many
levels? Sure. CS not available by the 80’s? No – the 64-node Caltech
Cosmic Cube was in 1981. Wall in sight for multi-core? Nope maybe at 1B
cores, I’ll keep you posted. GPU compilers ready for mainstream? Give
them another year. Courses to learn this stuff? Already out there.

Andrew then replied:

With all due respect to your excellent work on Folding@Home, your algorithms fall into the “embarrassingly parallel” category.

Adam didn’t agree at all:

While on the surface Folding@home appears in the job queue category of
SETI/BOINC projects, it’s not. Under the hood it’s a rather crazy
feedback process with Markov models and each new work unit depending on
the previous ones. If anything this is where the fun CS problems are,
and where the active research is. 10 years ago noone even thought you
could distribute these problems and had to use supercomputers.

The argument continued into all kinds of fabulous detail about the kinds of problems that are or are not amenable to parallel computing. In summing up, Andrew wrote:

the industrial world, which I am from, is hitting the wall of many core programming. Many of our economically important algorithms (value > $1 Billion) do not scale above 16-20 cores.

Adam replied:

Yes we will solve them, but we have to change our algorithms from what
most people are used to and this will take time. The same methods we use
for distributed folding also seem to translate to a wide variety of
other domains, so I see no hard walls on the horizon. I really do hope
we find a wall soon so I can climb it and I’m crossing my fingers for a
surprise at a billion.

The current generation of programmers is learning in a world of
multi-core, and from what I have seen they have zero if any trouble
dealing with it. Once they get some experience, we’ll wonder why this
was ever considered hard.