8

私はループ変換技術について読んでいますが、ループのスキューによってループが並列化可能になる方法を理解するのに非常に苦労しています。最初のループと 2 番目のループの 2 つがあります。2 つの違いは何ですか? それらのうちの 2 つは、i と j の両方の前の反復に依存しています。または、なぜ最初のものではなく 2 番目のものでインターチェンジを行うことができるのでしょうか? どちらも i と j に依存しています

for(int i =2; i < 5; i++){
            for(int j =2; j < 5; j++){
                A[i][j] = A[i-1][j] + A[i][j-1];
            }
        }
for(int i =2; i < 5; i++){
            for(int j =2+i; j < 5+i; j++){
                A[i][j-i] = A[i-1][j-i] + A[i][j-1-i];
            }
        }
4

1 に答える 1

4

私はこれを信用していません。あなたのためにフォーマットして別のソースからコピーしただけです。お役に立てば幸いです。

[出典: ECE 1754、ループ変換技術の調査、Eric LaForest、2010 年 3 月 19 日]

2 つの実行反復間の距離がすべてです。最初の反復では、1 つの外側ループと内側ループの間の距離が 1 であるため、それらの間に依存関係があります。

ループのスキューはまさにそのとおりです。つまり、外側のループに対して内側のループの実行をゆがめます。これは、内側のループが外側のループに依存しており、並列で実行できない場合に役立ちます。たとえば、次のコードには {(1, 0),(0, 1)} の依存関係ベクトルがあります。どちらのループにも依存関係があるため、並列化できません。単純にループを交換しても、依存関係を保持するインデックスが交換されるだけで、何も達成されません。

do i = 2, n-1
do j = 2, m-1
a[i,j] =
      (a[i-1,j] + a[i,j-1] + a[i+1,j] + a[i,j+1]) / 4
end do
end do

ループのスキューは、外側のループのインデックスにいくつかのスキュー係数 f を掛けた値を内側のループの境界に追加し、内側のループ インデックスのすべての使用から同じ値を減算することによって実装されます。減算により、インデックスが新しいループ境界内に保持され、プログラムの正確性が維持されます。内側のループ反復への影響は、配列内の位置を現在の外側のループに対してfだけ前方にシフトし、同じ方法で外側のループへの依存距離を増加させることです。言い換えると、依存関係ベクトル (a, b) が与えられた場合、歪曲はそれを (a, fa + b) に変換します。この変換は依存関係の辞書式順序を保持するため、常に有効です。上記の内部ループに 1 のスキュー係数を適用すると、次のコードが生成されます。

do i = 2, n-1
do j = 2+i, m-1+i
a[i,j-i] =
(a[i-1,j-i] + a[i,j-1-i] + a[i+1,j-i] + a[i,j+1-i]) / 4
end do
end do

この新しいコードは同じ方法で実行されますが、{(1, 1),(0, 1)} の依存関係があります。両方のループにはまだ依存関係があります。ただし、この時点でループを交換すると、次のコードに示すように、依存ベクトル {(1, 0),(1, 1)} が生成されます。

do j = 4, m+n-2
do i = max(2, j-m+1), min(n-1, j-2)
a[i,j-i] =
(a[i-1,j-i] + a[i,j-1-i] + a[i+1,j-i] + a[i,j+1-i]) / 4
end do
end do

内側のループは、j に対するループ伝搬の依存関係がなくなり、i への依存関係が外側のループによって伝搬されるため、並列化できるようになりました。ゆがんだループの境界を交換することは、もはや単純ではないことに注意してください。もう一方のループの下限。

于 2014-09-22T21:52:20.390 に答える