Ketil Malde wrote:

I'm sure somebody, somewhere, is working on speculative execution of Haskell code.

I think we both graduated (myself from MIT, Robert Ennals from Cambridge; I'm building compilers for supercomputers at Sun). If anyone else is working seriously on speculative evaluation of Haskell at the moment, please drop me a line, I'd love to hear of your existence.

Now that Sun is building Niagara with IIRC 8 cores on a chip, Intel is rumoured to put up to 16 cores on the post-Montecito Tukwila, Sony/IBM's Cell is said to be some kind of parallel design, and every self-respecting chip vendor is putting at least two cores on a chip and/or adding multithreaded cores.

One would expect a lazy and pure language to be excellent for parallelization, since the programmer is generally removed from the actual flow of execution anyway.

As I recall, this was one of the original goals of the Grip project (which built the original incarnation of GHC, if I have my history straight). Indeed, if you read any early paper on strictness analysis, you'd think that it was all about parallelizing lazy code. I'm now of the opinion that strictness analysis tells us where to *serialize* our code, because parallelism just won't be worth it. There are, I believe, a couple of major challenges: * It's easy to identify very small pieces of parallel work, but much harder to identify large, yet finite, pieces of work. Only the latter are really worth parallelizing. * If you don't compute speculatively, you'll never find enough work to do. * If you compute speculatively, you need some way to *stop* working on useless, yet infinite computations. Rob and I had two rather different takes on the same basic idea: run with some sort of resource limits, and stop working when you exhaust them. Roughly speaking, Rob then made sure you never speculated that bit of code again, while I just kept relying on the bounds to kick in. On pretty eager code, I did all right, but on code that actually needed the laziness (this was after a good bit of compiler munging to wring out most of the unnecessary laziness) I got killed---Rob's approach fixed the mistake by patching the code, and did much better thereafter. My ultimate goal was parallelization. However, I'm now convinced it would take about 2-3 programmer-years more of effort to realize that goal. Parallel garbage collection (which is *not* optional on a parallel Haskell implementation, as our experience with pH demonstrated) and very fine-grained thunk-update protocols are both tricky technical challenges. And that leaves aside the question of whether there's enough coarse-grained work buried among all that fine-grained work to make it all worthwhile. Anyone want to pay me to do this? :-)

At some point (for some n), being able to spawn n threads will gain you more than a factor c constant overhead, and Haskell programs, with a run-time system that can evaluate expressions in paralllel, will outperform single threaded C code.

Only if you can keep the granularity of the work large. This hasn't been so easy. -Jan-Willem Maessen Eager Haskell Implementor

Ketil Malde wrote:

Jan-Willem Maessen - Sun Labs East writes:

...

There are, I believe, a couple of major challenges: * It's easy to identify very small pieces of parallel work, but much harder to identify large, yet finite, pieces of work. Only the latter are really worth parallelizing.

By the former, are you thinking of so small grain that it is handled by out-of-order execution units in the CPU? And/or the C compiler?

I'm thinking of so small grain that the cost of fine-grained thread creation (tens of instructions) is comparable to the cost of running the thread itself (hundreds of instructions). ILP is a bit of a sideshow here. Usually there's plenty of integer ILP hanging about already.

...

* If you don't compute speculatively, you'll never find enough work to do.

Although I'm not familiar with the issues, my point is that the number of CPUs available, even in common household pee cees, is already more than one (P4 hyper-threading), and could be something like eight in the not-so-distant future. It no longer matters (much) if you waste `cycles, cycles are cheap. (The next next IA64, Montecito is 1.7G transistors, including 24Mb on-chip cache. The P4 is big, but you could fit thirty of them in that space. No way Montecito is going to have anywhere near 30x the performance)

So speculative execution, even if you end up throwing away 50% of the work you do, could in theory make your program faster anyway. This is a headache for C programs; my hope would be that a functional language would make it easier.

Be careful. A P4 will slow down if you get it hot enough. So "throwing away" that bit of extra performance may actually make things slower... And who gets to use the throwaway performance, anyhow? You want it, the OS wants it, other applications on your machine want it---you have to be able to adjust to varying amounts of "extra" compute power hanging around. [Actually, speaking from experience, half the compute power on my SMP ends up going to the GUI, the OS, or my browser---and it's great to have those things not slow down uniprocessor compute-bound tasks.]

...

* If you compute speculatively, you need some way to *stop* working on useless, yet infinite computations.

And you need to choose which computations to start working on, I guess. Predicting the future never was easy :-)

Indeed.

[perhaps getting off-topic, but hey, this is -cafe]

That's why I subscribe to -cafe at all! -Jan-Willem Maessen

-kzm

Jan-Willem Maessen writes (in the Haskell Cafe):

My ultimate goal was parallelization. However, I'm now convinced it would take about 2-3 programmer-years more of effort to realize that goal. Parallel garbage collection (which is *not* optional on a parallel Haskell implementation, as our experience with pH demonstrated) and very fine-grained thunk-update protocols are both tricky technical challenges. And that leaves aside the question of whether there's enough coarse-grained work buried among all that fine-grained work to make it all worthwhile.

I'm not sure how to interpret this. Will you also have solved the granularity problem in these two to three years? Cheers, Ronny Wichers Schreur