Question About Inconsistent Behavior in Parallel BFS Implementation Using Domainslib Task Pool

[tjazerzen]

Description:

Context:

• Goal: Implement a parallel version of the breadth-first search (BFS) algorithm using Domainslib in OCaml.
• Method: Utilizing Domainslib.Task for parallel computation.
• Implementation: The parallel BFS (BfsAlgorithms.parallel) is designed to use a task pool for parallel execution. I used naively defined parallel map, as discussed in Question: Does a parallel map function exist in Domainslib? #117.

Code Overview:

module BfsAlgorithms : Bfs = struct
  (* ... other methods ... *)

  let parallel_map (f : 'a -> 'b) (task_pool : T.pool) (arr : 'a array) : 'b array =
    let len = Array.length arr in
    let res = Array.make len (f arr.(0)) in
    T.parallel_for task_pool ~start:0 ~finish:(len - 1) ~body:(fun i -> res.(i) <- f arr.(i));
    res

  let parallel (graph : UnweightedGraph.t) (start_node : Node.t) ~(task_pool: T.pool) : NodeSet.t list =
    (* implementation details *)
    (* uses parallel_map *)
end

(* ... other code ... *)

Issue: Inconsistent Execution Behavior

• Scenario 1: When invoking BfsAlgorithms.parallel via an intermediary function within Task.run, the parallel computation executes as expected.

  let task_pool = T.setup_pool ~num_domains:5 ()
  let bfs_parallel_wrapper pool = BfsAlgorithms.parallel small_graph small_graph_start_node
  let result = Task.run task_pool (fun () -> bfs_parallel_wrapper task_pool)
  T.teardown_pool task_pool

• Scenario 2: Directly invoking BfsAlgorithms.parallel within Task.run leads to no apparent computation being performed.

  let task_pool = T.setup_pool ~num_domains:5 ()
  let result = Task.run task_pool (fun () -> BfsAlgorithms.parallel small_graph small_graph_start_node ~task_pool)
  T.teardown_pool task_pool

Expected Behavior:

Both scenarios should exhibit the same behavior, as the only difference is the direct invocation of BfsAlgorithms.parallel in Scenario 2.

I was wondering if there is any known issue or subtlety with how Domainslib handles task pools and closures that could explain this discrepancy?

I'm new to parallel OCaml, so this could be fault on my side.

If any more context is needed, the full implementation may be found at https://github.com/tjazerzen/parallelisation-of-graph-algorithms-in-functional-programming-languages/blob/master/playground/graph/bfs.ml.

Best, Tjaz

[tjazerzen]

realized my problem, which doesn't have to do anything with parallelism. Closing...