Re: "the multi-core "crisis" " My fault again. 2 items. one a reply to the other

[David Farber <dave () farber net>]

Begin forwarded message:

From: Adam L Beberg <beberg () stanford edu>
Date: June 5, 2007 2:22:12 PM EDT
To: David Farber <dave () farber net>
Cc: "Andrew W. Donoho" <awd () DDG com>
Subject: Re: [IP] "the multi-core "crisis" " My fault again.

Andrew W. Donoho wrote on 6/5/2007 7:53 AM:
> Adam,
>     I must beg to differ with you.
>     Let me quote from my note:
> > > Most algorithms, other than the embarrassingly parallel ones,  
> > > will hit this wall.
>     With all due respect to your excellent work on Folding@Home,  
> your algorithms fall into the "embarrassingly parallel" category.

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 Cell processor itself is a very difficult machine to  
> program. Every person and team I talk to about it finds it  
> difficult to program. Why? Because it goes outside of the  
> traditional PDP-11/S360 model and requires the programmer to  
> explicitly manage his memory system.

This is a huge gift not a problem! If you look at the cell as a
distributed system instead of trying to use it as an SMP system you end
up with a beautify simple, elegant, and easy to program chip. Fast
and cheap too. Make no mistake, managing memory is the future because
all of the hardware problems center around predicting data flow and that
pesky speed of light.

> And now your second point:
...
>     There have been an almost infinite number of parallel  
> programming methodologies proposed. Yet, the one that is widely  
> deployed is OpenMP.

We use BrookGPU (also out of Stanford) to fold on the GPU's and manage
the insane hardware under the hood, and actually manage to be
computationally limited not bandwidth limited. It's a very simple way of
hiding all the complexity and nothing a run of the mill programmer can't
use - our GPU code is by a chemist. Yes he knows what's under the hood,
but it's all hidden by Brook so it's mostly trial and error until you
hit the hardware limits.

>     In other words, while there has been much work in the mechanics  
> of parallel computing, where are the useful intellectual results?  
> Where is the intellectual equivalent of calculus for parallel  
> programming?

Most of this is already solved, just forgotten. Ask Dave, or read the
papers from that era, that's what I do. (Now I fear I'm giving away my
secret of avoiding hard problems by just looking up the answer.)
Computer Science has a collective 20-year amnesia cycle going I cannot
explain, sadly this is getting even shorter. A recent conference I was
at was just depressing. That's probably the real crisis in CS.

>     That microprocessor leakage current forced deployment of multi- 
> core processors is a gift to computer science. As a result, 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. Yes, we will throw  
> extremely bright folks at these problems. As the scientific  
> community has in its field, we will also solve them.

Amdahl's Law still applies. The only people I know with "big" problems
if you ignore gaming for a moment are scientists, and you seem to agree.
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.

--
- Adam L. Beberg




Begin forwarded message:
From: "Andrew W. Donoho" <awd () DDG com>
Date: June 5, 2007 5:04:12 PM EDT
To: Adam L Beberg <beberg () stanford edu>
Cc: David Farber <dave () farber net>
Subject: Re: [IP] "the multi-core "crisis" " My fault again.

Dave, Feel free to send this to IP. I don't know if Adam wants his  
previous reply on IP. If not, then it would obviously be moot to post  
this response.


----


Adam,

	I think we are talking past each other. I agree that folks in the  
scientific community are surmounting huge computational problems.  
What I was complaining about is that very few general results are  
being translated into CS theory nor practice. They are point  
solutions. Perhaps there is no general solution and we just have a  
series of tools and methodologies. My scientifically educated self  
rebels at such a horrific thought.

	You are correct that our industry and academy have very short  
memories. This should be rectified and, I think, would be rectified  
with a better split between CS and computer engineering. This short  
memory also precludes the next step to synthesis that happens in  
every other scientific discipline.

I value your comments which I've elided below. I want to focus on the  
following comments because I think they clearly illustrate our  
differences and, I hope, provide useful intellectual fodder for our  
IP readers.


[Snip earlier text from the previous note.]

On Jun 5, 2007, at 13:22, Adam L Beberg wrote:

> Amdahl's Law still applies. The only people I know with "big" problems
> if you ignore gaming for a moment are scientists, and you seem to  
> agree.



Actually, I think there are big problems in almost every application  
of computing. Only in the sciences and gaming have we been willing to  
experiment with both novel architectures and invest the intellectual  
capital needed to exploit those architectures.




> 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.



I think Dave Patterson has started to enumerate a series of hard  
computational problems with his "dwarves". Some of them apply to  
traditional business applications. Please take a look at his paper,  
<http://www.eecs.berkeley.edu/Pubs/TechRpts/2006/EECS-2006-183.pdf>.  
I would be interested in your opinion on his factoring of the problem.

Have you published any papers describing your methodology? I would  
love to be proven wrong and await a description of how I can push  
back these many-core programming constraints.



> 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.



I think you are privileged to draw almost exclusively from the  
brightest programmers available. It is my experience that most  
programmers have trouble with threaded programs, much less, multi- 
core systems. Throwing in variable memory latencies and messaging  
topologies make many-core systems almost impossible for the average  
programmer to handle.

Furthermore, we have a great deal of experience programming 32 and 64  
way SMP systems. The vast consensus of industry is that programming  
these machines is hard. Most of the threading models do not provide  
sufficiently robust abstractions to handle the common parallel  
programming patterns. I, personally, think this is more than a  
library problem but, rather, a language/semantic problem. We know how  
to express sequential processes but do not have robust general  
languages to express parallel patterns.

As to why we might ever have considered this hard, I simply point to  
experimental scientific history. There are plenty of problems that we  
now consider "simple". Picking a particularly well known example,  
special relativity, shows this. Before special relativity, the  
Lorentz contraction empirically demonstrated by the Michelson-Morley  
experiment was a mystery. Afterwards, all was explained and was  
deemed simple. Similar transformations of perspective have transpired  
in CS. I hope that a similar revelation will occur in CS with respect  
to many-core computing. Heretofore, I have not seen any progress.

In summary, I agree that there have been a huge number of point  
solutions programming multi-core systems. I have not seen any general  
solutions that I can exploit in either industry or the academy.

Andrew

____________________________________
Andrew W. Donoho
awd () DDG com, PGP Key ID: 0x81D0F250
+1 (512) 453-6652 (o), +1 (512) 750-7596 (m)

"To take no detours from the high road of reason and social  
responsibility."
    -- Marcus Aurelius












-------------------------------------------
Archives: http://v2.listbox.com/member/archive/247/=now
RSS Feed: http://v2.listbox.com/member/archive/rss/247/
Powered by Listbox: http://www.listbox.com