{"id":545,"date":"2008-10-24T18:00:17","date_gmt":"2008-10-24T16:00:17","guid":{"rendered":"http:\/\/www.navision-blog.de\/2008\/10\/24\/using-plinq-in-fsharp-parallel-map-and-reduce-fold-functions-part-ii\/"},"modified":"2008-10-25T10:56:56","modified_gmt":"2008-10-25T08:56:56","slug":"using-plinq-in-fsharp-parallel-map-and-reduce-fold-functions-part-ii","status":"publish","type":"post","link":"http:\/\/www.navision-blog.de\/blog\/2008\/10\/24\/using-plinq-in-fsharp-parallel-map-and-reduce-fold-functions-part-ii\/","title":{"rendered":"Using PLINQ in F# – Parallel Map and Reduce (Fold) functions – part 2"},"content":{"rendered":"

Last time<\/a> I showed how it is possible to use parallel map and fold functions to compute the sum of all factorials between 1 and 3000. The result was a nearly perfect load balancing for this task on a two processor machine. This time I will derive a generic function that computes partial results in parallel and folds them to a final result.<\/p>\n

Let\u2019s consider our F# example:<\/p>\n

\n
let<\/span> add a b = a + b  <\/pre>\n
let<\/span> <\/strong>fac (x:bigint) = <\/pre>\n
  [1I..x] |> List.fold_left (*) 1I<\/pre>\n
let<\/span> sequential() =<\/strong><\/pre>\n
  [1I..3000I]<\/strong><\/pre>\n
   |> List.map fac<\/strong><\/pre>\n
   |> List.fold_left add 0I<\/strong><\/pre>\n<\/div>\n
This is the same as:<\/p>\n
\n
let<\/span> calcFactorialSum min max =<\/pre>\n
  [min..max] <\/pre>\n
   |> List.map fac<\/pre>\n
   |> List.fold_left add 0I  <\/pre>\n
 <\/pre>\n
let<\/span> f1() = calcFactorialSum    1I 2000I<\/pre>\n
let<\/span> f2() = calcFactorialSum 2001I 2200I<\/pre>\n
let<\/span> f3() = calcFactorialSum 2201I 2400I<\/pre>\n
let<\/span> f4() = calcFactorialSum 2401I 2600I<\/pre>\n
let<\/span> f5() = calcFactorialSum 2601I 2800I<\/pre>\n
let<\/span> f6() = calcFactorialSum 2801I 3000I<\/pre>\n
 <\/pre>\n
let<\/span> sequential2() =<\/pre>\n
  f1() + f2() + f3() + f4() + f5() + f6()<\/strong><\/pre>\n<\/div>\n
We spitted the summation into 6 independent tasks and computed the sum of the partial results. This has nearly no bearing on the runtime.<\/p>\n
But with the help of PLINQ we can compute each task in parallel:<\/p>\n
\n
\n
let<\/span> asParallel (list: 'a list) = <\/pre>\n
  list.AsParallel<'a>()<\/pre>\n<\/p><\/div>\n
let<\/span> runParallel functions = <\/pre>\n
    ParallelEnumerable.Select(<\/pre>\n
      asParallel functions, (fun<\/span> f -><\/span>  f() ) )<\/pre>\n
 <\/pre>\n
\n
let<\/span> pFold foldF seed (data:IParallelEnumerable<'a>)=<\/pre>\n
  ParallelEnumerable.Aggregate<'a,'b>(<\/pre>\n
    data, seed, new<\/span> Func<'b,'a,'b>(foldF))<\/pre>\n
 <\/pre>\n<\/p><\/div>\n
\n
let<\/span> calcFactorialsParallel() =<\/strong><\/pre>\n
  [f1; f2; f3; f4; f5; f6]<\/strong><\/pre>\n
    |> runParallel<\/strong><\/pre>\n
    |> pFold add 0I<\/strong><\/pre>\n<\/p><\/div>\n
<\/font><\/p>\n<\/div>\n
This time we build a list of functions (f1, f2, f3, f4, f5, f6) and run them in parallel. "runParallel<\/em>\u201d gives us back a list of the partial results, which we can fold with the function \u201cadd<\/em>\u201d to get the final result.<\/p>\n
On my Core 2 Duo E6550 with 2.33 GHz and 3.5 GB RAM I get the following results:<\/p>\n
\n
Time Normal: 26.576s<\/p>\n
Time Sequential2: 26.205s (Ratio: 0.99)<\/p>\n
Time \u201cParallel Functions\u201d: 18.426s (Ratio: 0.69)<\/strong><\/p>\n
Time PLINQ: 14.990s (Ratio: 0.56) (Last post<\/a>)<\/p>\n
Same Results: true<\/p>\n<\/blockquote>\n
We can see that the parallel computation of the functions f1 \u2013 f6 is much faster than the sequential.<\/p>\n
But why is the PLINQ-version (see last post<\/a>) still faster? We can easily see that each partial function needs a different runtime (e.g. it\u2019s much harder to calculate the factorials between 2800 and 3000 than between 2000 and 2200). On my machine I get:<\/p>\n
\n
Time F1: 8.738s<\/p>\n
Time F2: 2.663s<\/p>\n
Time F3: 3.119s<\/p>\n
Time F4: 3.492s<\/p>\n
Time F5: 3.889s<\/p>\n
Time F6: 4.442s<\/p>\n<\/blockquote>\n
The problem is that the Parallel Framework can only guess each runtime amount in advance. So the load balancing for 2 processors will not be optimal in every case. In the original PLINQ-version there are only small tasks, and the difference between each runtime is smaller. So it is easier to compute the load balancing.<\/p>\n
But of course we can do better if we split f1 into two functions f7 and f8:<\/p>\n
\n
let<\/span> f7() = calcFactorialSum    1I 1500I<\/pre>\n
let<\/span> f8() = calcFactorialSum 1501I 2000I<\/pre>\n<\/div>\n
So we can get a better load balancing:<\/p>\n
\n
Time F1: 8.721s<\/p>\n
Time F7: 4.753s<\/p>\n
Time F8: 4.829s<\/p>\n
Time Normal: 26.137s<\/p>\n
Time \u201cParallel Functions\u201d: 16.138s (Ratio: 0.62)<\/p>\n
Same Results: true<\/p>\n<\/blockquote>\n","protected":false},"excerpt":{"rendered":"
Last time I showed how it is possible to use parallel map and fold functions to compute the sum of all factorials between 1 and 3000. The result was a nearly perfect load balancing for this task on a two processor machine. This time I will derive a generic function that computes partial results in […]<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":[],"categories":[27,23,448,8,461],"tags":[664,660,464,463,450,462,665],"_links":{"self":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/545"}],"collection":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/comments?post=545"}],"version-history":[{"count":6,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/545\/revisions"}],"predecessor-version":[{"id":551,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/posts\/545\/revisions\/551"}],"wp:attachment":[{"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/media?parent=545"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/categories?post=545"},{"taxonomy":"post_tag","embeddable":true,"href":"http:\/\/www.navision-blog.de\/blog\/wp-json\/wp\/v2\/tags?post=545"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}