F #: Dites-moi ce que je suis absent sur l'utilisation Async.Parallel

Question

ok, donc je fais 14 # Problème Project Euler, et je bidouiller avec des optimisations afin de se sentir f # out.

dans le code suivant:

let evenrule n = n/2L 
let oddrule n = 3L * n + 1L 

let applyRule n = 
    if n % 2L = 0L then evenrule n 
    else oddrule n 

let runRules n = 
    let rec loop a final = 
     if a = 1L then final 
     else loop (applyRule a) (final + 1L) 
    n, loop (int64 n) 1L 


let testlist = seq {for i in 3 .. 2 .. 1000000 do yield i } 

let getAns sq = sq |> Seq.head 

let seqfil (a,acc) (b,curr) = if acc = curr then (a,acc) else if acc < curr then (b,curr) else (a,acc) 

let pmap f l = 
    seq { for a in l do yield async {return f a} } 
    |> Seq.map Async.RunSynchronously 

let pmap2 f l = 
    seq { for a in l do yield async {return f a} } 
    |> Async.Parallel 
    |> Async.RunSynchronously 

let procseq f l = l 
        |> f runRules 
        |> Seq.reduce seqfil 
        |> fst 

let timer = System.Diagnostics.Stopwatch() 
timer.Start() 
let ans1 = testlist |> procseq Seq.map // 837799 00:00:08.6251990 
printfn "%A\t%A" ans1 timer.Elapsed 
timer.Reset() 

timer.Start() 
let ans2 = testlist |> procseq pmap 
printfn "%A\t%A" ans2 timer.Elapsed // 837799 00:00:12.3010250 
timer.Reset() 

timer.Start() 
let ans3 = testlist |> procseq pmap2 
printfn "%A\t%A" ans3 timer.Elapsed // 837799 00:00:58.2413990 
timer.Reset() 

Pourquoi le code exécuté Async.Parallel vraiment lent par rapport à la carte vers le haut? Je sais que je ne devrais pas voir beaucoup d'effet, puisque je suis seulement sur un mac dual core.

S'il vous plaît noter que je ne veux pas que l'aide de résolution de problèmes # 14, je veux juste savoir ce qui se passe avec mon code parallèle.

Answer 1

L'utilisation de Async.Parallel semble être correct. Les chiffres semblent vraiment suspects, mais je ne vois pas immédiatement ce qui pourrait être un problème ici.

Dans tous les cas, les flux de travail asynchrones sont vraiment plus adaptés pour les calculs qui impliquent une opération asynchrone (tels que E/S, la communication, dans l'attente d'événements, etc.). Pour les tâches intensives en CPU, il est préférable d'utiliser Parallel Extensions to .NET (qui font maintenant partie de .NET 4.0, malheureusement il n'y a pas de version .NET 2.0).

Pour ce faire de F #, vous aurez besoin F# PowerPack et l'ensemble FSharp.PowerPack.Parallel.Seq.dll, qui contient des versions parallèles des fonctions d'ordre supérieur pour travailler avec des séquences (comme map :-))

Ces fonctions renvoient une valeur de type pseq<'a> (appelé ParallelQuery<T> en C#), qui représentent une course de calcul retardé en parallèle (ce qui permet une meilleure optimisation lorsque vous utilisez plusieurs opérations en pipeline). Il y a aussi la fonction PSeq.reduce, donc vous voudrez peut-être l'utiliser dans votre traitement aussi (mis à part PSeq.map).

Answer 2

Sur ma boîte, il faut environ une demi-seconde pour exécuter une non-async. Comme il y a environ un demi-million d'éléments de travail ici, cela signifie que chacun d'entre eux tourne en environ 1 microseconde en moyenne.

Ces articles sont trop petits pour essayer de paralléliser individuellement. La surcharge de la programmation et de la synchronisation des threads dominera le travail réel. Vous devez choisir une meilleure granularité.

(Je vais travailler sur un code rapide ...)

EDIT:

Ok, le code tel quel n'est pas trop facile de re-faire pour changer la granularité des lots sans certains grands réécriture, donc je n'ai pas de nouveau code à partager qui ne donne pas trop loin. Mais j'ai réussi à le faire tourner presque deux fois plus rapidement sur ma boîte à 2 coeurs en faisant des lots de 50 000 éléments chacun et en faisant la "réduction de carte" sur chaque lot et une "réduction en parallèle" sur les 10 lots.

Voir aussi

http://blogs.msdn.com/pfxteam/archive/2008/08/12/8849984.aspx

en particulier la section "granularité des tâches".

Answer 3

Je veux juste savoir ce qui se passe avec mon code parallèle

Heh, ce qui est pas mal avec votre code parallèle.;-)

Voilà comment je résoudre le problème:

let rec inside (a : _ array) n = 
    if n <= 1L || a.[int n] > 0s then a.[int n] else 
     let p = 
     if n &&& 1L = 0L then inside a (n >>> 1) else 
      let n = 3L*n + 1L 
      if n < int64 a.Length then inside a n else outside a n 
     a.[int n] <- 1s + p 
     1s + p 
    and outside (a : _ array) n = 
    let n = if n &&& 1L = 0L then n >>> 1 else 3L*n + 1L 
    1s + if n < int64 a.Length then inside a n else outside a n 

    let euler14 n = 
    let a = Array.create (n+1) 0s 
    let a = Array.Parallel.init (n+1) (fun n -> inside a (int64 n)) 
    let i = Array.findIndex (Array.reduce max a |> (=)) a 
    i, a.[i] 

Ce programme utilise le parallélisme spéculatif avec une condition de course sûre et réalise un modeste 2 × sur mes 8 speedup noyaux.