F #: Скажите мне, что мне не хватает в использовании Async.Parallel

Question

нормально, поэтому я выполняю задачу ProjectEuler №14, и я возился с оптимизациями, чтобы чувствовать f # out.

в следующем коде:

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() 

Почему Async.Parallel код запуска очень медленно по сравнению с прямой на карте? Я знаю, что не должен видеть такой эффект, так как я только на двухъядерном Mac.

Обратите внимание, что я НЕ хочу помочь решить проблему № 14, я просто хочу знать, что случилось с моим параллельным кодом.

Answer 1

Использование Async.Parallel представляется правильным. Цифры действительно выглядят подозрительными, но я не сразу вижу, что может быть проблемой здесь.

В любом случае асинхронные рабочие процессы более подходят для вычислений, связанных с асинхронной операцией (например, I/O, связь, ожидание событий и т. Д.). Для задач с интенсивным процессором лучше использовать Parallel Extensions для .NET (которые теперь являются частью .NET 4.0, к сожалению, нет версии .NET 2.0).

Чтобы сделать это с F #, вам нужно F# PowerPack и FSharp.PowerPack.Parallel.Seq.dll узел, который содержит параллельные версии функций высшего порядка для работы с последовательностями (например, map :-))

Эти функции возвращают значение типа pseq<'a> (ParallelQuery<T> в C#), которые представляют собой отложенное вычисление, выполняющееся параллельно (это обеспечивает лучшую оптимизацию при использовании нескольких операций в конвейере). Существует также функция PSeq.reduce, поэтому вы можете использовать ее и в своей обработке (кроме PSeq.map).

Answer 2

На моей коробке требуется не менее полусекунды, чтобы запустить не-асинхронный. Поскольку здесь около полумиллиона рабочих единиц, это означает, что каждый из них работает в среднем примерно на 1 микросекунду.

Эти предметы слишком малы, чтобы попытаться распараллелить индивидуально. Накладные расходы на выполнение планирования и синхронизации потоков будут доминировать над реальной работой. Вам нужно выбрать лучшую гранулярность.

(я буду работать на какой-то быстрый код ...)

EDIT:

Ok, код как есть не так уж легко повторно сделать, чтобы изменить пакетное детализацию без некоторых основных переписывая, поэтому у меня нет нового кода для обмена, который не дает слишком много. Но я смог заставить его работать почти в два раза быстрее на моем 2-ядерном ящике, делая партии по 50 000 элементов каждый и делая «уменьшение карты» в каждой партии и «параллельную карту уменьшает» на 10 или около того партий.

Смотрите также

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

особенно раздел "задача зернистость".

Answer 3

Я просто хочу знать, что случилось с моим параллельным кодом

Хех, что не является неправильным с параллельным кодом.;-)

Вот как я бы решить эту проблему:

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] 

Этой программа использует спекулятивный параллелизм с безопасным состоянием гонки и достигает скромные 2 × ускорения на моих 8 ядрах.