On 8/10/07, <b class="gmail_sendername">Bayley, Alistair</b> <<a href="mailto:Alistair_Bayley@invescoperpetual.co.uk" target="_blank" onclick="return top.js.OpenExtLink(window,event,this)">Alistair_Bayley@invescoperpetual.co.uk
</a>> wrote:<div><span class="gmail_quote"></span><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
Well, the Harris/Singh paper summarises the common problems:<br> - not many programs are inherently parallel</blockquote><div><br>If thats the case, then multicores are not going to be very useful. Where there's a will there's a way.
<br><br>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.<br><br>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.
<br></div><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;"> - parallelism must be quite coarse to offset overheads<br> (which I think is the problem with expecting things like map and fold
<br>to parallelised automagically; they're just too small grained for it to<br>be worthwhile)</blockquote><div><br>Someone else said that. I dont understand what you mean.<br><br>Imagine I have a map like this:<br>
<br>
map f [1..100000] <br></div><br>... and I have 64 cores..<br><br>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?<br><br>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.
<br><br>More details/examples:<br><br>It's trivial to improve on NDP at runtime. For example:<br><br>- we split our map into 64 pieces, give each one to a thread<br>-
one piece finishes earlier than the others -> we split one of the
other pieces in two, and give one piece to the finished thread
<br>- and so on...<br><br>-> reasonably optimal<br><br>Another example:<br><br>- we have a map of 64 elements, so we give one element to each thread<br>- all of the pieces but one finishes really quickly (say, within 1 second)
<br>- so, we start to look at what is happening within the remaining piece
<br>-> turns out it contains another map, so we split that map amongst our idle threads<br>-> and so on<br><br>Easy, flexible.<br><br><blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">
- lazy evaluation makes it harder</blockquote><div><br>Not at runtime ;-) <br><br></div>
<blockquote class="gmail_quote" style="border-left: 1px solid rgb(204, 204, 204); margin: 0pt 0pt 0pt 0.8ex; padding-left: 1ex;">Basically, it's harder than it sounds.</blockquote><div><br>No ;-) The more I talk about this the more confident I feel that this is an easy, optimal solution.
<br></div></div><br>The bits that stand out as being hard:<br><br>- 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 ;-)
<br><br>- migrate Haskell/GHC/Erlang/some-other-FP to have a bytecode/VM layer<br><br>- create a 1024-ish-core simulator. In fact this is the only bit that I dont have a clear vision for.<br><br>