1

ループを展開するという概念は理解していますが、単純なループを展開する方法を誰かに説明してもらえますか?

ループを見せてから、何が起こっているのかを説明したそのループの展開バージョンを見せていただければ幸いです.

4

3 に答える 3

5

ループのアンローリングが最も効果的な場合、つまり依存関係の連鎖を明確にすることが重要だと思います。依存関係チェーンは、各計算が前の計算に依存する一連の操作です。たとえば、次のループには依存チェーンがあります。

for(i=0; i<n; i++) sum += a[i];

最新のプロセッサのほとんどは、サイクルごとに複数の順不同の操作を実行できます。これにより、命令のスループットが向上します。ただし、順不同の操作は、依存関係チェーンでこれを行うことはできません。上記のループでは、各計算は加算演算のレイテンシによって制限されます。

上記のループでは、このように 2 つの依存関係チェーンに展開できます。

sum1 = 0, sum2 = 0;
for(i=0; i<n/2; i++) sum1 += a[2*i], sum2 += a[2*i+1];
for(i=(n/2)*2; i<n; i++) sum += a[i]; // clean up for n odd
sum += sum1 + sum2;

現在、アウトオブオーダー プロセッサは、いずれかのチェーンで独立して動作し、同時にプロセッサに依存する可能性があります。

一般に、操作のレイテンシにクロック サイクルごとに実行できる操作の数を掛けた値だけアンロールする必要があります。たとえば、x86_64 プロセッサでは、クロック サイクルごとに少なくとも 1 つの SSE 追加を実行でき、SSE 追加のレイテンシは 3 であるため、3 回アンロールする必要があります。Haswell プロセッサを使用すると、クロック サイクルごとに 2 つの FMA 操作を実行でき、各 FMA 操作のレイテンシは 5 であるため、最大スループットを得るには 10 回アンロールする必要があります。

コンパイラに関する限り、GCC は依存チェーンを展開しません ( -funroll-loops. GCC で展開する必要があります。Clang では 4 回アンロールしますが、これは一般的にかなり良好です (場合によっては、Haswell と Broadwell では 10 回、Skylake では 8 回アンロールする必要があります)。

アンロールするもう 1 つの理由は、ループ内の操作の数が、クロック サイクルごとにプッシュ スルーできる命令の数を超えた場合です。たとえば、次のループで

for(i=0; i<n; i++) b[i] += 3.14159*a[i];

依存チェーンがないため、順不同で実行しても問題ありません。しかし、反復ごとに次の操作を必要とする命令セットを考えてみましょう。

2 SIMD load
1 SIMD store
1 SIMD multiply
1 SIMD addition
1 scalar addition for the loop counter
1 conditional jump

また、プロセッサがサイクルごとにこれらの命令を 5 つプッシュできると仮定しましょう。この場合、反復ごとに 7 つの命令がありますが、サイクルごとに実行できる命令は 5 つだけです。次に、ループ展開を使用して、カウンターへのスカラー加算iと条件付きジャンプのコストを償却できます。たとえば、ループを完全に展開した場合、これらの命令は必要ありません。

ループカウンターとジャンプのコストを償却するために、-funroll-loopsGCC で正常に動作します。これは 8 回アンロールします。つまり、カウンターの追加とジャンプは、反復ごとではなく、8 回の反復ごとに 1 回実行する必要があります。

于 2016-04-13T07:44:41.073 に答える
1

巻き（レギュラー）：

#define N 44

int main() {
    int A[N], B[N];
    int i;

    // fill A with stuff ...

    for(i = 0; i < N; i++) {
        B[i] = A[i] * (100 % i);
    }

    // do stuff with B ...
}

展開:

#define N 44

int main() {
    int A[N], B[N];
    int i;

    // fill A with stuff ...

    for(i = 0; i < N; i += 4) {
        B[i] = A[i] * (100 % i);
        B[i+1] = A[i+1] * (100 % i+1);
        B[i+2] = A[i+2] * (100 % i+2);
        B[i+3] = A[i+3] * (100 % i+3);
    }

    // do stuff with B ...
}

展開すると、プログラムのサイズが大きくなりますが、パフォーマンスが向上する可能性があります。パフォーマンスの向上は、分岐ペナルティ、キャッシュ ミス、および実行命令の減少による可能性があります。コード量の増加や読みやすさの低下など、明らかな欠点もあれば、それほど明白ではない欠点もあります。

于 2016-04-13T04:22:25.790 に答える