[ During the summer the F# team at MSR Cambridge had the pleasure of having Juergen van Gael working with us, prior to his starting a PhD at the University of Cambridge. Juergen looked at three topics: probabilisitic modelling with F#, some machine learning algorithms with the APG team, and topics in math libary support for F#. Before he left Juergen wrote up his expereiences of using asynchronous workflows to parallelize some math algorithms. Here's his write up!

One caveat: asynchronous workflows can be used to do some simple CPU-intensive parallelizations, but have some overheads because at each step of the way we have to cater for the fact that tasks may be asynchronous, and this often means using operating system synchronization resources ("WaitHandles") along the way. Libraries like Parallel FX Futures will have great functionality for scheduling lots of synchronous tasks, like many of the ones used below. Juergen wrote this up before we could really make heavy us of Parallel FX so his write up doesn't mention them.

Basically, I'd say that as these technologies become widely used you should assess the characteristics of your tasks and use the right scheduling machinery for the job. Do your tasks need to perform non-blocking network or disk I/O? Then the .NET thread pool will likely have to be used in some way, because that's largely how .NET asynchronous I/O works, and F# asynchronous workflows are a reasonable way of doing this kind of programming. Are they simple synchronous computational tasks? Then Parallel FX Futures look like the right machinery there.

Anyway, over to Juergen! ]

I want to draw your attention to a feature of F# that I’ve become to like very much: asynchronous workflows. As a machine learning researcher, I often run into the scenario where I need to read in a lot of data, run a number of independent tasks (potentially in parallel) and later compute some aggregate information. A very recent example required me to compute optimal parameters for a classifier; unfortunately I could not compute gradient information and decided to brute force search over a parameter grid. Evaluating the classifier for every parameter is independent of all other evaluations though and could be done in parallel. Although asynchronous workflows are designed for other purposes, they allow you to do just this. Asynchronous workflows are a mechanism in F# to setup a computation by describing small tasks and how these tasks depend on each other. The feature that got me excited was that it is extremely simple to describe parallel tasks. Onto an example!

One way to picture an asynchronous workflows is as a directed acyclic graph where every node describes a simple computation: in F# this is represented as an Async<’a> task.

1
2
3
4
5

V1 = Z*Z  -----\
                \
V2 = sin(Z)    ----->  R = V1 + V2 + V3
                /
V3 = log(Z) ---/

The graph above shows a simple numerical computation which could be described with asynchronous workflows. Assume Z has some value prior to executing the computation in the graph above. It should be clear that the computations of the three v’s are independent and can be done in parallel; only after all three are computed the computation can proceed by computing R. The code snippet below shows how to describe the workflow in F#:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18

#light
 
let evals =
    let z = 4.0
    [ async { do printf "Computing z*z\n"
              return z * z };
      async { do printf "Computing sin(z)\n"
              return (sin z) };
      async { do printf "Computing log(z)\n"
              return (log z) } ]
 
let awr =
    async { let! vs = Async.Parallel evals
            do printf "Computing v1+v2+v3\n"
            return (Array.fold_left (fun a b -> a + b) 0.0 vs) }
 
let R = Async.Run awr
printf "Result = %f\n" R

First we initialize a variable evals which references a list of asynchronous computation each describing the computation of one v. It is important to note that no numerical computation is done at this point: we are just setting up the computation. Next we build another computation (awr) as a workflow by using the Async.Parallel construct. This construct takes a sequence of asynchronous workflows, schedules all of them in parallel, waits for the results and returns those packaged in a list of Async types. In the awr expression, we bind variable vs to the contents of the Async type returned by the parallel computations. Again, I want to stress that at this point we have only setup the computation. Only when we execute Async.Run do we commit the runtime to evaluate the whole workflow and wait for its results. On my machine this results in the following output:

1
2
3
4
5

Computing z*z
Computing sin(z)
Computing log(z)
Computing v1+v2+v3
Result = 16.629492

Although the computation we setup and executed above is trivial I hope I conveyed to you that asynchronous workflows are an interesting way to describe a parallel computation. Here is a possible implementation of a parallel matrix multiplication using asynchronous workflows. Note that in this example we chose to parallelize the computation of rows, but different granularities are possible. (Do not consider this to be a high performance, parallel matrix multiplication but rather as a workflow example.)

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

open Microsoft.FSharp.Collections
 
let ParallelMultiply A B =
    let n = Array2.length1 A
    let C = Array2.create n n 0.0
    let RowTask i =
        async { do for j=0 to n-1 do
                    for k=0 to n-1 do
                        C.[i,j] <- C.[i,j] + A.[i,k] * B.[k,j]
                do printf "Computing row %d\n" i
              }
    let p = Async.Parallel [ for i in [0..n-1] -> RowTask i ] |> Async.Ignore
    Async.Run p
    C
 
let n = 4
let rnd = System.Random()
let A = Array2.init n n (fun i j -> rnd.NextDouble())
let B = Array2.init n n (fun i j -> rnd.NextDouble())
printf "%A\n" A
printf "%A\n" B
let C = ParMult A B
printf "%A\n" C