[Haskell-cafe] Problems with Parallel N Queens using Control.Parallel.Strategy
leilmyxwz at gmail.com
Sun Jun 22 20:49:26 UTC 2014
I'm currently reading Parallel and Concurrent Programming in Haskell.
I tried to implement an n-queens problem as an exercise, but a little
bit overwhelmed by the strategy mystery.
The code is listed at http://pastebin.com/ySgc3VSR.
I implemented the higher order skeleton of search and try to add
parallelism. My original idea was spawning a few threads while the
search tree was small and each thread handles the following expansion
of the tree. Hence, I gave a "maxDepth" variable to restrict the
parallelism. But this did not go very well if I set the maxDepth to
very small value, say, 2, 3, 4 etc. The speed up was very small.
Viewing in threadscope, it seems there was very small amount of
Then I tried to let it go, which means I set the tree depth to a value
larger than the maximum possible depth, say 20. Then it speeds up
about 1.4 times on 2-cores. Viewing in threadscope, it seems the 2
cores are fully utilized. But the report is a bit annoying:
SPARKS: 4686728 (100456 converted, 3461 overflowed, 0 dud, 4540817
GC'd, 41994 fizzled)
with no restrictions on the parallelism, a lot of sparks are not
converted and are GC'd.
I wonder if there is some way to further improve the results, reducing
un-convereted sparks and achieving better speed-up ratio.
More information about the Haskell-Cafe