Parallel tree search

Question

Let's say I have a lazy Tree whose leaves are possible solutions to a problem

data Tree a = Node [Tree a] | Leaf (Maybe a)

I need to find just one solution (or find out that there are none).

I have a P-core machine. From both time and memory efficiency considerations, it only makes sense to search along P different branches in parallel.

For example, suppose you have four branches of about the same computational complexity (corresponding to T seconds of CPU time), and each of them has an answer.

If you evaluate all four branches truly in parallel on a dual-core machine, then they all will finish in about 2T seconds.

If you evaluate just the first two branches and postpone the other two, then you'll get an answer in only T seconds, also using twice as less memory.

My question is, is it possible to use any of the parallel Haskell infrastructure (Par monad, parallel strategies, ...) to achieve this, or do I have to use lower-level tools like async?

Answer 1

Both Strategies and the Par monad will only start evaluating a new parallel task if there is a CPU available, so in your example with four branches on a 2-core machine, only two will be evaluated. Furthermore, Strategies will GC the other tasks once you have an answer (although it might take a while to do that).

However, if each of those two branches creates more tasks, then you probably wanted to give priority to the newer tasks (i.e., depth-first), but Strategies at least will give priority to the older tasks. The Par monad I think gives priority to the newer ones (but I'd have to check that), however the Par monad will evaluate all the tasks before returning an answer, because that is how it enforces determinism.

So probably the only way to get this to work exactly as you want it, at the moment, is to write a custom scheduler for the Par monad.