Compute NFA transitions in parallel

Question

I have this piece of code written in F#:

type NondeterministicFiniteAutomaton = {
    initialState: string
    finalStates: string List
    transitions: Map<string * char, string List>
}

let private nextState (symbol:char) (state:string) (transitions:Map<string * char, string List>) =
    transitions |> Map.tryFind (state, symbol)

let rec private haltState (input:string) (index:int) (state:string) (transitions:Map<string * char, string List>) =
    match index with
    | x when x = input.Length -> state
    | _ ->
        match nextState input.[index] state transitions with
        | x when x.IsNone -> null
        | x -> haltState input (index+1) x.Value transitions

In the last line, x.Value will return a list of states that my automaton can enter, say ["s1"; "s2"; "s3"]. For each state in this list, I want to call haltState in parallel, thus calculating each possible path in parallel.

• How can I call them in parallel?
• How can I "join" them when they are done?

Answer 1

I'd recommend first writing the complete sequential version. Then you can see if adding parallelism makes sense for the computations you'll be doing.

As for joining the results, this is something you'll need to do even in the sequential version. Your haltState function returns a single string, but if this is a NFA, then it may end in multiple different states. So you could change it to return a sequence of possible results:

let rec private haltState (input:string) (index:int) (state:string) (transitions:Map<string * char, string List>) =
    match index with
    | x when x = input.Length -> Seq.singleton x
    | _ ->
        match nextState input.[index] state transitions with
        | None -> Seq.empty
        | Some states -> 
            states |> Seq.collect (fun state -> 
              haltState input (index+1) state transitions)

This returns a sequence and it joins the sequences generated for multiple possible states using Seq.collect. Note that I also used more idiomatic pattern matching on option values.

You could parallelize this using Array.Parallel.map, but I doubt this will make the processing faster - the overhead is probably going to be larger.

let rec private haltState (input:string) (index:int) (state:string) (transitions:Map<string * char, string List>) =
    match index with
    | x when x = input.Length -> [| state |]
    | _ ->
        match nextState input.[index] state transitions with
        | None -> [| |]
        | Some states -> 
            states
            |> Array.ofSeq
            |> Array.Parallel.collect (fun state -> haltState input (index+1) state transitions)