0

（編集済み）

Parallel.For ループを使用して、関数を並列化して LCS を解決しようとしています。この関数は対角線で進み、前のセルに基づいて現在の対角セルの値を取得します。

シーケンシャル関数は次のとおりです。

let public lcs_seq_1d_diags (x:char[]) (y:char[]) = 
    let m = x.Length
    let n = y.Length

    let mutable dk2 = Array.create (1+m) 0
    let mutable dk1 = Array.create (1+m) 0
    let mutable dk = Array.create (1+m) 0

    for k = 2 to m+n do
        let low = max 1 (k-m)
        let high = min (k-1) n

        for j = low to high do
            let i = k - j
            if x.[i-1] = y.[j-1] then
                dk.[i] <- dk2.[i-1] + 1
            else 
                dk.[i] <- max dk1.[i] dk1.[i-1]


        let mutable temp = dk2
        dk2 <- dk1
        dk1 <- dk
        dk <- temp

    dk1.[m]

私の並列化の試み:

let public lcs_par_1d_seq (x:char[]) (y:char[]) = 
    let m = x.Length
    let n = y.Length

    let dk2 = Array.create (1+m) 0
    let cell2 = ref dk2
    printfn "\r\n0: %A" dk2
    let dk1 = Array.create (1+m) 0
    let cell1 = ref dk1
    printfn "1: %A" dk1
    let dk = Array.create (1+m) 0
    let cell = ref dk

    for k = 2 to m+n do
        let low = max 1 (k-m)
        let high = min (k-1) n
        //for each cell in current diagonal
        Parallel.For(low, high, (fun j ->
            let i = k - j
            if x.[i-1] = y.[j-1] then
                dk.[i] <- dk2.[i-1] + 1
            else 
                dk.[i] <- max dk1.[i] dk1.[i-1])) |> ignore

        if trace then 
            let ilow = k - high
            let ihigh = k - low
            printfn "k=%d i=%d..%d dk=%A" k ilow ihigh dk.[ilow..ihigh]

        let mutable temp = !cell2
        cell2 := !cell1
        cell1 := !cell
        cell := temp

    dk1.[m]

順次ループのトレース結果:

0: [|0; 0; 0; 0; 0; 0; 0|]
1: [|0; 0; 0; 0; 0; 0; 0|]
k=2 i=1..1 dk=[|0|]
k=3 i=1..2 dk=[|0; 0|]
k=4 i=1..3 dk=[|1; 1; 1|]
k=5 i=1..4 dk=[|1; 1; 1; 1|]
k=6 i=1..5 dk=[|1; 1; 1; 1; 1|]
k=7 i=1..6 dk=[|1; 2; 2; 1; 2; 1|]
k=8 i=1..6 dk=[|1; 2; 2; 2; 2; 2|]
k=9 i=1..6 dk=[|1; 2; 2; 2; 2; 2|]
k=10 i=1..6 dk=[|1; 2; 2; 2; 3; 2|]
k=11 i=2..6 dk=[|2; 2; 2; 3; 3|]
k=12 i=3..6 dk=[|2; 2; 3; 3|]
k=13 i=4..6 dk=[|2; 3; 3|]
k=14 i=5..6 dk=[|3; 4|]
k=15 i=6..6 dk=[|4|]
... duration: 19 ms
res_seq_1d_diags = 4
Press any key to continue . . .

並列ループのトレース結果:

0: [|0; 0; 0; 0; 0; 0; 0|]
1: [|0; 0; 0; 0; 0; 0; 0|]
k=2 i=1..1 dk=[|0|]
k=3 i=1..2 dk=[|0; 0|]
k=4 i=1..3 dk=[|0; 1; 1|]
k=5 i=1..4 dk=[|0; 0; 0; 0|]
k=6 i=1..5 dk=[|0; 0; 0; 0; 0|]
k=7 i=1..6 dk=[|0; 1; 1; 0; 1; 0|]
k=8 i=1..6 dk=[|0; 0; 0; 0; 0; 1|]
k=9 i=1..6 dk=[|0; 0; 0; 0; 0; 0|]
k=10 i=1..6 dk=[|0; 1; 0; 0; 1; 0|]
k=11 i=2..6 dk=[|1; 0; 0; 0; 1|]
k=12 i=3..6 dk=[|0; 0; 0; 0|]
k=13 i=4..6 dk=[|0; 1; 0|]
k=14 i=5..6 dk=[|1; 1|]
k=15 i=6..6 dk=[|1|]
... duration: 23 ms
res_par_1d_seq = 0
Press any key to continue . . .

トレースを生成するコードは次のとおりです。

        if trace then 
        let ilow = k - high
        let ihigh = k - low
        printfn "k=%d i=%d..%d dk=%A" k ilow ihigh dk.[ilow..ihigh]

ここで 'dk' は、各行列対角のセルの値を指します (つまり、最初の対角には値 0 を持つ 1 つのセルがあり、2 番目の対角には値 0 と 0 を持つ 2 つのセルがあります)。

基本的に、並列バージョンでは、一部のスレッドが互いの値をオーバーライドしているようです。これを回避し、並列バージョンで値を適切に保存する方法を教えてください。

4

3 に答える 3

1

まず、あなたのコードはあなたの出力と一致しない (あなたのコードでは の長さdkは決して変わらない) ので、私はあなたのコードが実際に何をするかを理解しようとはしない.

refさて、あなたの問題は細胞とは何の関係もありません。問題は、現在の反復における の値が、前の反復のと の値、および各反復におけるこれらの変数の適切なローテーションにdk依存することです。これは、少なくとも直接的には、コードが並列化できないことを意味します。dk1dk2

于 2013-04-24T11:47:32.107 に答える
0

並列化可能なコードの場合、各ループが互いに独立するようにコードを記述する方法を最初に考える必要があります。つまり、 atの値が atiの値に依存する場合、 またはが最初に計算されるかどうかがi-1わからないため、ループは並列化できません。ii-1

あなたの場合、おそらく各対角線の LCS を計算し、iそれを に格納するようなことを行いlcs[i]ます。その結果は、他の対角線にあるものから独立しているため、並列化可能です。その後、そのループの後、戻ることができますlcs.Max()。

于 2013-04-24T16:08:43.160 に答える