爲什麼我在F＃中的並行性能不佳？

Question

我試圖學習F＃，這是我第一次嘗試並行編程。我正在努力尋找通過網格的最長路徑。我的尋路解決方案看起來像一個相當簡單的遞歸算法。然後我映射/縮小它來查找所有路徑並返回最長。

我有一個序列實現和map/reduce部分的3個不同的並行實現。在較小的網格上，我發現在並行實現中速度有些微的提高。在更大的網格上，並行實現實際上更慢！難道我做錯了什麼？

的3點平行的實現是：

• Array.Parallel.map
• 使用的Parallel.For，從這個問題就來了一種地圖實現：using Array.Parallel.map for decreasing running time
• 選自F PSeq.map＃PowerPack的

以下是使用不同尺寸輸入網格的4種實現的一些典型時序：

4x4 Grid 
GetLongestPath    19.845400 
GetLongestPathParallelArray 18.626200 
GetLongestPathParallelFor  7.084200 
GetLongestPathPSeq   163.271000 

5x5 Grid 
GetLongestPath    818.967500 
GetLongestPathParallelArray 629.563000 
GetLongestPathParallelFor 725.072500 
GetLongestPathPSeq   772.961300 

6x6 Grid 
GetLongestPath    3941.354000 
GetLongestPathParallelArray 3609.441800 
GetLongestPathParallelFor 3509.890500 
GetLongestPathPSeq   3295.218600 

7x7 Grid 
GetLongestPath    24466.655300 
GetLongestPathParallelArray 32098.823200 
GetLongestPathParallelFor 35274.629500 
GetLongestPathPSeq   24980.553600 

下面的代碼：

module Pathfinder 
open System 
open System.Threading.Tasks 
open Microsoft.FSharp.Collections 

let ListContains item list = List.exists (fun x -> x = item) list 
let LongestList (x:int list) (y:int list) = if x.Length >= y.Length then x else y 

let GetNeighborsNotAlreadyInPath (neighborMap: Map<int, int list>) path = 
    neighborMap.[List.head path] 
    |> List.filter (fun item -> not (ListContains item path)) 

let rec GetLongestPathFromAllNeighbors neighborMap currentPath longestPath = 
    let neighbors = GetNeighborsNotAlreadyInPath neighborMap currentPath 
    if neighbors = [] then 
     LongestList currentPath longestPath 
    else 
     neighbors 
     |> List.map (fun neighbor -> GetLongestPathFromAllNeighbors neighborMap (neighbor::currentPath) longestPath) 
     |> List.reduce LongestList 

let GetLongestPathFromPosition neighborMap i = 
    GetLongestPathFromAllNeighbors neighborMap [i] [] 

let GetLongestPath (neighborMap: Map<int, int list>) = 
    [| 0..neighborMap.Count-1 |] 
    |> Array.map (fun i -> GetLongestPathFromPosition neighborMap i) 
    |> Array.reduce LongestList 

let GetLongestPathParallelArray (neighborMap: Map<int, int list>) = 
    [| 0..neighborMap.Count-1 |] 
    |> Array.Parallel.map (fun i -> GetLongestPathFromPosition neighborMap i) 
    |> Array.reduce LongestList 

let GetLongestPathParallelFor (neighborMap: Map<int, int list>) = 
    let inline ParallelMap (f: 'T -> 'U) (array : 'T[]) : 'U[]= 
     let inputLength = array.Length 
     let result = Array.zeroCreate inputLength 
     Parallel.For(0, inputLength, fun i -> 
      result.[i] <- f array.[i]) |> ignore 
     result 

    [| 0..neighborMap.Count-1 |] 
    |> ParallelMap (fun i -> GetLongestPathFromPosition neighborMap i) 
    |> Array.reduce LongestList 

let GetLongestPathPSeq (neighborMap: Map<int, int list>) = 
    [| 0..neighborMap.Count-1 |] 
    |> PSeq.map (fun i -> GetLongestPathFromPosition neighborMap i) 
    |> PSeq.reduce LongestList 

這是建立從輸入柵格地圖代碼：

module Gobstoppers 
open System 

type GobstopperCollection = { Items: string[]; Width: int; NeighborMap: Map<int, int list> } 
type Gobstopper = { Position: int; Color: string; Shape: string; } 

let CreateGobstopperFromString (text:string) i = 
    { Position = i; Color = text.[0].ToString(); Shape = text.[1].ToString() } 

let CreateGobstopper (itemArray: string[]) i = 
    CreateGobstopperFromString itemArray.[i] i 

let FindNeighbors (itemArray: string[]) rowWidth i = 
    let onLeft = (i % rowWidth = 0) 
    let onRight = (i % rowWidth = rowWidth - 1) 
    let onTop = (i < rowWidth) 
    let onBottom = (i >= itemArray.Length - rowWidth) 

    [(if onTop || onLeft then -1 else i - rowWidth - 1); 
    (if onTop then -1 else i - rowWidth); 
    (if onTop || onRight then -1 else i - rowWidth + 1); 
    (if onLeft then -1 else i - 1); 
    (if onRight then -1 else i + 1); 
    (if onBottom || onLeft then -1 else i + rowWidth - 1); 
    (if onBottom then -1 else i + rowWidth); 
    (if onBottom || onRight then -1 else i + rowWidth + 1)] 
    |> List.filter (fun x -> x > -1) 

let FindCompatibleNeighbors itemArray rowWidth i = 
    let AreCompatible (a:Gobstopper) (b:string) = a.Color = b.[0].ToString() || a.Shape = b.[1].ToString() 
    FindNeighbors itemArray rowWidth i 
    |> List.map (fun x -> CreateGobstopper itemArray x) 
    |> List.filter (fun x -> AreCompatible x itemArray.[i]) 
    |> List.map (fun x -> x.Position) 

let Load (text:string) = 
    let itemArray = 
     text.Split('|') 
     |> Array.map (fun x -> x.Trim()) 
     |> Array.filter (fun x -> x <> "") 
    let rowWidth = int (sqrt (float itemArray.Length)) 
    let neighborMap = 
     itemArray 
     |> Array.mapi (fun i x -> i, FindCompatibleNeighbors itemArray rowWidth i) 
     |> Map.ofArray 

    { Items = itemArray; 
     Width = rowWidth; 
     NeighborMap = neighborMap } 

這裏的測試輸入：

module TestData 

let testGrid3 = "|yr|rr|rs| 
       |yr|gb|rp| 
       |bs|gr|yb|" 

let testGrid4 = "|yr|rr|rs|gp| 
       |yr|gb|rp|pp| 
       |bs|gr|yb|bs| 
       |br|rs|yb|bb|" 

let testGrid5 = "|yr|rr|rs|gp|rb| 
       |yr|gb|rp|pp|gr| 
       |bs|gr|yb|bs|bp| 
       |br|rs|yb|bb|bc| 
       |gs|yr|yr|rp|br|" 

let testGrid6 = "|yr|rr|rs|gp|rb|bc| 
       |yr|gb|rp|pp|gr|pb| 
       |bs|gr|yb|bs|bp|ps| 
       |br|rs|yb|bb|bc|rs| 
       |gs|yr|yr|rp|br|rb| 
       |pp|gr|ps|pb|pr|ps|" 

let testGrid7 = "|yr|rr|rs|gp|rb|bc|rb| 
       |yr|gb|rp|pp|gr|pb|rs| 
       |bs|gr|yb|bs|bp|ps|pp| 
       |br|rs|yb|bb|bc|rs|pb| 
       |gs|yr|yr|rp|br|rb|br| 
       |pp|gr|ps|pb|pr|ps|bp| 
       |gc|rb|gs|pp|bc|gb|rp|" 

let testGrid8 = "|yr|rr|rs|gp|rb|bc|rb|bp| 
       |yr|gb|rp|pp|gr|pb|rs|rp| 
       |bs|gr|yb|bs|bp|ps|pp|gb| 
       |br|rs|yb|bb|bc|rs|pb|pb| 
       |gs|yr|yr|rp|br|rb|br|pr| 
       |pp|gr|ps|pb|pr|ps|bp|rs| 
       |gc|rb|gs|pp|bc|gb|rp|pp| 
       |rp|gb|rs|ys|yc|yp|rb|bb|" 

這裏是我的控制檯應用程序的時間：

open System 
open System.Diagnostics 

let RunTimer runCount title testFunc = 
    printfn title 
    let RunTimedTest n = 
     let stopWatch = Stopwatch.StartNew() 
     let result = testFunc() 
     stopWatch.Stop() 
     printfn "%i - %f" n stopWatch.Elapsed.TotalMilliseconds 
     result 

    let results = [| 1..runCount |] |> Array.map (fun x -> RunTimedTest x) 
    printfn "%A" results.[0] 

let runCount = 1 
let gobs = Gobstoppers.Load TestData.testGrid6 

RunTimer runCount "GetLongestPath" (fun _ -> Pathfinder.GetLongestPath gobs.NeighborMap) 
RunTimer runCount "GetLongestPathParallelArray" (fun _ -> Pathfinder.GetLongestPathParallelArray gobs.NeighborMap) 
RunTimer runCount "GetLongestPathParallelFor" (fun _ -> Pathfinder.GetLongestPathParallelFor gobs.NeighborMap) 
RunTimer runCount "GetLongestPathPSeq" (fun _ -> Pathfinder.GetLongestPathPSeq gobs.NeighborMap) 

let line = Console.ReadLine() 

Answer 1

如果調度的工作無法以真正可以並行執行的方式進行分配，那麼當您分割工作時，所添加的所有內容都會消耗。

如果可以在多個內核之間並行執行工作，或者在等待期間可以使用等待/空閒時間來執行任務，那就是您可能獲得時間的時間。

在這種情況下，你所做的只是計算，所以沒有等待IO。這就是爲什麼代碼只會受益於多個內核（如果儘可能保持儘可能低的同步）

嘗試在更多內核上執行代碼。

Answer 2

我在哪裏，我認爲匿名函數 （樂趣我 - >運行的東西）之前碰到的一個問題

不clealy並行。我得到了零加速，但是寫一個輔助函數

let foo i = 
    run i etc 

Array.parallel.map（富）給了我一個很好的加速。其他評論也是相關的 - 真正的細粒度並行通常不會因開銷開銷而得到回報。你可能會更好地擁有N個工作者和共享的排隊工作