CODEWITHSUNDEEP
f#functional-programmingtreeparallel-processing
pad
pad

Reputation: 41290

Options for parallelizing functions on F# tree

In my project, I have a data structure represented as follows:

type 'a Tree =
| Leaf of 'a
| Node of 'a Tree array

Due to the cost of traversing through large trees, I have to parallelize some following functions on this data structure:

Because of nature of the problem I'm working on, number of branches at each node is varied and workloads at the leaf level are quite small. The first question is what options should I consider for parallel execution on tree. I'm trying to use functions from Array.Parallel module on every node, however, because overheads of parallelism is too big, the parallel version is even slower than the sequential version. I may change array representation to List or PSeq if it is necessary.

The second question is how to control degree of parallelism on those functions. I'm thinking about controlling by depth of tree, number of branches at each node, workload complexity at the leaf level and number of leaves on tree, however, combining them together seems to be complex and unpredictable.

Upvotes: 3

Views: 422

Answers (2)

Daniel
Daniel

Reputation: 47904

How about separating traversal from any other processing? Perhaps create a work queue (MailboxProcessor is a good starting point) and, as the tree is traversed, enqueue additional work for background processing. It doesn't solve the parallel traversal problem (which seems tricky to get right for all cases) but with additional processing relegated to the background, it should go pretty quickly. You can experiment with the number of background workers until you find a good degree of parallelism. This all assumes the amount of work to be done for each node is non-trivial.

EDIT

Here's some code. I'm sure it can be improved. I had to hammer it out pretty quickly. But this shows the basic concept. It only has one "background worker," i.e., the MailboxProcessor. I'll leave updating it to use multiple workers to the imagination.

type Msg<'a, 'b> =
    | Work of 'a
    | Done of 'b

type MapTransformer(f) =
    let results = ResizeArray()
    let m = MailboxProcessor.Start(fun payload ->
        let rec loop() =
            async {
                let! msg = payload.Receive()
                match msg with
                | Work work -> 
                    results.Add(f work)
                    return! loop()                
                | Done (channel : AsyncReplyChannel<_>) -> 
                    channel.Reply(results :> seq<_>)
            }
        loop())
    member this.Enqueue(item) = m.Post(Work item)
    member this.Results = m.PostAndReply(fun c -> Done c)

let uberMap tree =
    let m = MapTransformer(fun x -> x + 1)
    tree |> List.iter (fun x -> m.Enqueue(x))
    m.Results

uberMap [1; 2; 3]
//outputs [2; 3; 4]

Upvotes: 4

wmeyer
wmeyer

Reputation: 3496

Array.Parallel uses System.Threading.Parallel.For. When you call that function, it tries to find an optimal schedule for the given task. However, with a typical recursive tree algorithm, this means a lot of calls to Parallel.For and you probably end up with far too many threads. (Unless Parallel.For is optimized for that use case which I don't know.)
So I think Daniel's suggestion is a good idea if the workload per node is not too small. An alternative idea is to introduce a threshold with respect to the remaining depth of a tree as described by Stephen Toub at the end of this blog entry.

Upvotes: 3

Related Questions