[Haskell-cafe] Problems with Parallel N Queens using Control.Parallel.Strategy

[bruce li]

Hello, Cafe,
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
parallelism.

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.

Thanks.