0

講義中に、私の教授は次のループを教えてくれました。

for (int i = 0; i < 100; i++) {
    a[i] = a[i] + b[i];
    b[i + 1] = c[i] + d[i];
}

彼は、ループの反復間の依存関係を指摘しました。これは、3 行目で、2 行目の次の反復で使用される値を設定するためです (次の反復で使用されるセットb[i+1]) b[i]。したがって、ループの各反復を並行して実行することはできません。

次に、彼はこの展開されたバージョンを提供してくれました。

a[1] = a[1] + b[1];
for (int i = 0; i < 98; i++) {
    b[i+1] = c[i] + d[i];
    a[i+1] = a[i] + b[i];
}
b[99] = c[99] + d[99];

彼は、ループの各反復を並行して実行できるようになったと主張しています。私が見る問題は、3 行目で 4 行目の次の反復で何が起こるかを設定しているb[i]ため、各反復を並行して実行できないことです。

私がそう言うのは正しいですか？もしそうなら、各反復を並列化できる最初のループの適切に展開されたバージョンはありますか?

4

1 に答える 1

1

教授がくれた展開版を書き留めるのを間違えたと思います。最初のアルゴリズムと同等であるためには、次のように読む必要があります。

a[0] = a[0] + b[0];
for (int i=0 ; i<99 ; ++i) {
    b[i+1] = c[i] + d[i];
    a[i+1] = a[i+1] + b[i+1];
}
b[100] = c[100] + d[100];

このバージョンでは、依存関係の問題がなくなっていることがわかります。

于 2012-03-12T07:59:56.510 に答える