Back to Questions
3.2k
views3
comments
Teaching NESL Concepts in F#
f#teachingfunctionalparallelcomplexity

I'm interested in teaching the key concepts behind NESL (Blelloch et al.'s nested data parallel language) but using F# as a platform in which students can try out and/or implement some of these concepts. Some of the key concepts behind NESL are explained in Blelloch's article in communications of the ACM:

[link:www.cs.cmu.edu]

A key element of NESL is that all its functions have well-defined complexity in terms of work and depth. Intuitively, work is the total number of operations that must be performed (ie: the cost of running the computation on a single processor). Depth is the maximum length of the program dependency chain (ie: the cost of running the computation assuming an infinite number of processors).

A canonical example of a NESL program is parallel quicksort (taken from here:
[link:www.cs.cmu.edu]):

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

function qsort(s) =
  if (#s < 2) then s
  else
    let pivot = s[rand(#s)];
         les = {e in s | e < pivot};
         eql = {e in s | e = pivot};
         grt = {e in s | e > pivot};
         result = {qsort(v) : v in [les, grt]}
    in result[0] ++ eql ++ result[1]

In this function, s is a sequence.  Some of the operations are:
  * #s -- the length of s (constant work & constant depth operation)
  * {e in s | predicate(e)} -- evaluate predicate(e) in parallel on all elements of s and filter the results accordingly. (work proportional to length(s); constant depth)
  * {qsort(v) : v in [les, grt]} -- for each v in les, grt, evaluate qsort(v) in parallel
  * a ++ b -- concatenate sequences a and b.  Do this in parallel with work proportional to the length(a) + length(b).  Depth is constant.

I have experience with functional languages in general (such as SML and O'Caml) but I'm new to F# specifically. I have glanced at the sequence expressions in F# and noticed that they are syntactically similar to NESL expressions, but at least the vanilla version is sequential. I have glanced at the Asynch library and noticed that it contains an operation to execute a sequence of Asynch's in parallel. I have noticed that in Blelloch's work and in related work in Haskell, there has been emphasis on the necessity of performing a flattening transformation in order to properly support nested parallelism. I haven't had a chance to figure out why such a transformation is essential. (But Simon Peyton Jones has some slides on it here: [link:research.microsoft.com]

I suppose my question is: Has anyone built an F# library that would allow me to easily translate the NESL examples presented in Blelloch's papers into F#? It is quite important that such a translation preserve the complexity-theoretic properties of the NESL operators in terms of their work and depth. If the translation does not preserve those properties, it is possible that it would still be useful to me, but I would have to know where the properties broke down --- I could imagine designing an assignment for my students asking them to devise experiments that show that the translation does not preserve various complexity-theoretic properties. Blinding speed (though nice) is less important to me than accurate complexity metrics and scaling.

Thanks in advance for any help,

David Walker
Princeton University

.

It's been years since I've messed with NESL, but IIRC the flattening transforms are necessary for performance by reducing the constant factors (which allowed the interpreted VCODE+CVL to perform as well as Fortran+MPI) but don't affect the complexity metrics. But I'm not sure that the standard F# libraries are well suited for this type of data-parallel programming.

As you mentioned, the NESL qsort translates pretty straightforwardly to F#:

1
2
3
4
5
6
7
8
9

let r = new System.Random();
let rec qsort (s : int[]) =
    if s.Length < 2 then s
    else let p = s.[r.Next(s.Length)] in
         let les = Array.filter ((>)p) s
         let eqs = Array.filter ((=)p) s
         let ges = Array.filter ((<)p) s
         let svs = [qsort les ; qsort ges] in
            Array.append svs.[0] <| Array.append eqs svs.[1]

Using the Async and PSeq modules the NESL code can be straightforwardly translated as:

1
2
3
4
5
6
7
8
9
10
11

let rec pqsort (s : int[]) =
    if s.Length < 2 then s
    else let p = s.[r.Next(s.Length)] in
         let parts = Async.Parallel [async {return PSeq.filter ((>)p) s |> PSeq.toArray} ;
                                     async {return PSeq.filter ((=)p) s |> PSeq.toArray} ;
                                     async {return PSeq.filter ((<)p) s |> PSeq.toArray}]
                     |> Async.RunSynchronously
         let les, eqs, ges = parts.[0], parts.[1], parts.[2]
         let svs = Async.RunSynchronously (Async.Parallel [async {return pqsort les} ;
                                                           async {return pqsort ges}])
         Array.append svs.[0] <| Array.append eqs svs.[1]

This should be pretty close to the NESL version's parallelism, if quite a bit wordier. It does make the various flavors of parallelism explicit: parallel filters, the three filters themselves can be executed in parallel, and the recursive sorts can be done in parallel. But it's really impressively slow - when I run this on an array of 100 elements it takes ~ 15 seconds to complete on a 2.26 ghz core duo 2 w/ 4g RAM. And I'm pretty sure that the lack of flattening isn't the source of the slowness. #time shows the following:

1

Real: 00:00:15.028, CPU: 00:00:00.031, GC gen0: 0, gen1: 0, gen2: 0

The flattening transformations would have changed the code into a version that did the filtering and sorting without needing to create the temporary arrays, but there's no GC going on so it's not like this unflattened version is consing itself to death or anything. Now I'm not an F# wizard, so maybe I'm doing something catastrophically wrong with my translation. But it's pretty disappointing to say the least.

By on 8/9/2010 8:42 PM ()

thanks so much for your help. This gets me started.

I'll look in to Parallel Link too.

Dave

By on 8/10/2010 2:20 PM ()

I haven't looked deeply, but for starters I would check out the Parallel LINQ stuff in the PowerPack. PSeq.map and PSeq.filter are some of the needed operations.

By on 8/9/2010 12:59 PM ()

    Topic tags

    IntelliFactory Offices Copyright (c) 2011-2012 IntelliFactory. All rights reserved.
    Home | Products | Consulting | Trainings | Blogs | Jobs | Contact Us | Terms of Use | Privacy Policy | Cookie Policy     		Built with WebSharper