2

私は F# を学ぼうとしていますが、これが並列プログラミングの最初の試みです。グリッドを通る最長のパスを見つけるパズルに取り組んでいます。私の経路探索ソリューションは、かなり単純な再帰アルゴリズムのようです。次に、それをマップ/削減してすべてのパスを見つけ、最長のものを返します。

map/reduce 部分のシリアル実装と 3 つの異なる並列実装があります。小さいグリッドでは、並列実装による速度のわずかな改善が見られます。より大きなグリッドでは、並列実装は実際には遅くなります! 私は何か間違ったことをしていますか？

3 つの並列実装は次のとおりです。

異なるサイズの入力グリッドを使用した 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()
4

2 に答える 2

2

スケジュールされた作業を実際に並行して実行できる方法で分散できない場合、追加するのは作業を分割するときのオーバーヘッドだけです。

実際に複数のコア間で作業を並行して実行できる場合、または待機/アイドル時間を使用して待機中にタスクを実行できる場合は、時間を稼ぐことができます。

この場合、あなたがするのは計算だけなので、IO を待つ必要はありません。これが、コードが複数のコアからのみ恩恵を受ける理由です (同期をできるだけ低く保つ場合)。

より多くのコアでコードを実行してみてください。

于 2013-05-06T06:21:04.713 に答える
0

私は無名関数を考える前に問題に遭遇しました（楽しい->何かを実行します）

明確に並列化しないでください。スピードアップはゼロですが、ヘルパー関数を書いています

let foo i =
    run i etc

Array.parallel.map (foo) はかなりのスピードアップをもたらしました。ただし、他のコメントも関連しています。実際に細粒度の並列処理を行っても、起動時のオーバーヘッドが原因で成果が得られないことがよくあります。N 人のワーカーと、やるべきことの共有キューを持つほうがよいかもしれません

于 2014-02-21T18:29:56.903 に答える