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@haskell.org http://www.haskell.org/mailman/listinfo/haskell
_______________________________________________ Haskell mailing list Haskell@haskell.org http://www.haskell.org/mailman/listinfo/haskell