[Haskell] Implicit parallel functional programming
John Hughes
rjmh at cs.chalmers.se
Thu Jan 20 04:29:10 EST 2005
Lennart Augustsson and Thomas Johnsson got some encouraging results
fifteen years ago with their nu-G-machine. They compiled Lazy ML for a
shared memory multiprocessor, and benchmarked against the sequential LML
compiler, the precursor of hbc and at that time the best compiler for a
lazy functional language. They observed speed-ups of at least 20% even
with only two processors, and with four the speed-ups were in the range
2-3.3x. The idea was to use "sparks" to start parallel computations,
which were ignored, and thus cheap, unless a processor was actually
available. OK, then benchmarks were tiny (n-queens), and the LML
compiler had higher overheads for ordinary computation than GHC, but
still, it's an encouraging result for exploiting multi-core machines.
Here's the reference:
>@inproceedings{99386,
> author = {Lennart Augustsson and Thomas Johnsson},
> title = {Parallel graph reduction with the (v , G)-machine},
> booktitle = {FPCA '89: Proceedings of the fourth international conference on Functional programming languages and computer architecture},
> year = {1989},
> isbn = {0-89791-328-0},
> pages = {202--213},
> location = {Imperial College, London, United Kingdom},
> doi = {http://doi.acm.org/10.1145/99370.99386},
> publisher = {ACM Press},
> }
>
John
>
>>
>> I thought the "lazy functional languages are great for implicit
>> parallelism" thing died out some time ago - at least as far as
>> running the programs on conventional hardware is concerned.
>>
>> Designing an algorithm that breaks apart a "sequential" lazy program
>> into parallel chunks of the appropriate size is **HARD** (with double
>> asterixes). The time and space behavior of a lazy program is complex
>> enough for the _programmer_ to reason about, let alone an automated
>> analysis - which has no knowledge of what the program is actually
>> trying to do.
>>
>> I think a more likely approach lies in the direction of the so called
>> "parallel strategies". If you haven't already, I would strongly
>> suggest reading: Algorithm + Strategy = Parallelism, 1998, PW
>> Trinder, et al.
>> You can get this paper from Simon Peyton Jones's homepage.
>>
>> Also, at the end of Hans Wolfgang-Loidl's thesis he develops a
>> granularity analysis for a Haskell subset - one of the first steps in
>> any kind of implicit parallelism. It's a pretty good effort, but at
>> the end of it all it still relies on a pre-existing table of
>> information about recursive functions. I think that these kind of
>> analyses tend suffer from uncomputability problems more than most.
>>
>> If you've still got your heart set on implicit parallelism, then
>> there's a (very slow) simulator you might want to poke around with. I
>> wrote it based around Clem Baker-Finch's "Abstract machine for
>> parallel lazy evaluation", which supports fully speculative implicit
>> parallelism.
>>
>> There's a link to it on my homepage at
>> http://cs.anu.edu.au/people/Ben.Lippmeier
>>
>>
>> Keean Schupke wrote:
>>
>>> I have to say I disagree... I feel Haskell is highly suited to
>>> implicit parallel execution... The key to "implicit" parallelisation
>>> is that it is implicit - not explicit, so the programmer should feel
>>> like they are programming a sequential language. If we can assume
>>> little memory access penalties for threads running on other CPUs
>>> (shared cache model), it seems to be a matter of putting locks on
>>> the right structures, and allowing any worker-thread to take the
>>> next function ready to run from the scheduler.
>>> Keean.
>>
>>
>> _______________________________________________
>> Haskell mailing list
>> Haskell at haskell.org
>> http://www.haskell.org/mailman/listinfo/haskell
>
>
> _______________________________________________
> Haskell mailing list
> Haskell at haskell.org
> http://www.haskell.org/mailman/listinfo/haskell
More information about the Haskell
mailing list