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 的单元格，第二个对角线有两个值为 0 和 0 的单元格，等等）。

基本上，在并行版本中，一些线程似乎会覆盖彼此的值。有什么建议可以避免这种情况并让值在并行版本中正确保存？

4

3 回答 3

1

首先，由于您的代码与您的输出不匹配（代码中的长度dk永远不会改变），因此我不会尝试了解您的代码实际上做了什么。

ref现在，您的问题与细胞无关。问题是dk当前迭代中的值取决于前一次迭代的值dk1和值以及dk2每次迭代中这些变量的正确旋转。这意味着您的代码不可并行化，至少不能直接并行化。

于 2013-04-24T11:47:32.107 回答
0

我发现了问题——我没有在 Parallel 循环中使用我的 refs。它现在按预期工作。我仍然非常感谢您的帮助，并且还拿起了建议的书籍。

多谢你们。

于 2013-04-25T21:48:00.717 回答
0

对于可并行化的代码，您需要首先考虑编写代码的方法，以便每个循环相互独立。即，如果您的值 ati取决于 at 的值i-1，则循环不可并行化，因为您不知道是否i或i-1将首先计算。

在您的情况下，可能会执行类似计算每个对角线的 LCSi并将其存储在lcs[i]. 该结果应该独立于位于其他对角线上的任何东西，因此是可并行的。然后在该循​​环之后，您可以返回lcs.Max().

于 2013-04-24T16:08:43.160 回答