[Haskell-cafe] Dynamic thread management?

Hugh Perkins hughperkins at gmail.com
Fri Aug 10 13:27:39 EDT 2007

On 8/10/07, Bayley, Alistair <Alistair_Bayley at invescoperpetual.co.uk> wrote:
> Well, the Harris/Singh paper summarises the common problems:
> - not many programs are inherently parallel

If thats the case, then multicores are not going to be very useful.  Where
there's a will there's a way.

What I think is: if maps etc will be parallelized out where necessary by the
runtime, then people will adapt their programs to use them.

Right now, many people use imperative loops in Haskell to get the highest
performance (see the shootout examples for example).  In the future, this
will be shunned in preference of standard map and foldb operations.

- parallelism must be quite coarse to offset overheads
>    (which I think is the problem with expecting things like map and fold
> to parallelised automagically; they're just too small grained for it to
> be worthwhile)

Someone else said that.  I dont understand  what you mean.

Imagine I have a map like this:

map f [1..100000]

... and I have 64 cores..

So I divide the 100000 elements in my list by 64, and give each chunk of
1000-ish elements to each thread.  Easy I think?

Note that NDP is doing this too, *but NDP is trying to do this for
assymetric elements at compile-time, which is generally impossible*.  I
propose doing it at runtime, inside the VM, which is trivial and optimal.

More details/examples:

It's trivial to improve on NDP at runtime.  For example:

- we split our map into 64 pieces, give each one to a thread
- one piece finishes earlier than the others -> we split one of the other
pieces in two, and give one piece to the finished thread
- and so on...

-> reasonably optimal

Another example:

- we have a map of 64 elements, so we give one element to each thread
- all of the pieces but one finishes really quickly (say, within 1 second)
- so, we start to look at what is happening within the remaining piece
-> turns out it contains another map, so we split that map amongst our idle
-> and so on

Easy, flexible.

- lazy evaluation makes it harder

Not at runtime ;-)

Basically, it's harder than it sounds.

No ;-)   The more I talk about this the more confident I feel that this is
an easy, optimal solution.

The bits that stand out as being hard:

- people making their programs use map, foldb etc -> but I dont have to do
that, it will happen automatically.  Its sortof like distributing bread
automatically to people in London, via the free market.  Do you know that
the Russians once asked the Western world who was responsible for
distributing bread to people in London?  Answer: noone is, it happens
automatically ;-)

- migrate Haskell/GHC/Erlang/some-other-FP to have a bytecode/VM layer

- create a 1024-ish-core simulator.  In fact this is the only bit that I
dont have a clear vision for.
-------------- next part --------------
An HTML attachment was scrubbed...
URL: http://www.haskell.org/pipermail/haskell-cafe/attachments/20070811/fb721f2f/attachment.htm

More information about the Haskell-Cafe mailing list