RE: [Caml-list] Parallel n-queens solver

["Jon Harrop" <jon@ffconsultancy.com>]

Frédéric wrote:
> It is the well known "skeleton paradigm" and BSP model (twice, since 1990)
> 
> Skeletons:
> http://en.wikipedia.org/wiki/Algorithmic_skeleton
> http://homepages.inf.ed.ac.uk/mic/Skeletons/index.html
> 
> BSP:
> http://en.wikipedia.org/wiki/Bulk_Synchronous_Parallel
> http://www.bsp-worldwide.org/

Very true. Subsequent fiddling turned up the following F# solution that uses a sequential pair of calls to Parallel.init (i.e. direct bulk synchronous parallelism) instead of the data flow parallelism:

  let run n =
    let timer = System.Diagnostics.Stopwatch.StartNew()
    let solve k =
      let sols = Array.init (n*n) (fun _ -> ResizeArray())
      solve k n (fun b ->
        let b = transformations b
        sols.[b.[1]*n + b.[0]].Add b)
      sols |> Array.map (fun sols -> sols.ToArray())
    let sols =
      let sols = Array.Parallel.init n solve
      Array.Parallel.init (n*n) (fun i ->
        let s = System.Collections.Generic.HashSet(HashIdentity.Structural)
        for sols in sols do
          let sols = sols.[i]
          for i=0 to sols.Length-1 do
            s.Add sols.[i] |> ignore
        s.Count)
      |> Array.sum
    printfn "%d solutions %d-queens problem in %gs" sols n timer.Elapsed.TotalSeconds

That old "invoke" combinator that evaluates a function application on a forked process and marshals the result back could be used to implement a naïve Parallel.init and, therefore, this solution could be translated to OCaml quite easily. However, it would still lack load balancing. That turns out to be ok in this particular case because the generated data is quite evenly distributed (and we assume that nothing else is running on the machine) but real applications might not be so lucky...

Turns out you can also use data flow parallelism entirely by replacing Array.Parallel.init with PSeq.init. In theory, this allows the second phase to occur concurrently with the first phase, being updated as new results are generated. In practice, I don't see a speedup.

Cheers,
Jon.