10

コンパイラがループ展開の最適化を実行する場合、ループを展開する要因、またはループ全体を展開するかどうかによって、どのように決定されますか？これはスペースとパフォーマンスのトレードオフであるため、プログラムのパフォーマンスを向上させる上で、この最適化手法は平均してどの程度効果的ですか。また、どのような条件下でこの手法（つまり、特定の操作または計算）を使用することが推奨されますか？

これは、特定のコンパイラに固有である必要はありません。これは、この手法の背後にある考え方と実際に観察されたことの概要を説明するものであれば何でもかまいません。

4

4 に答える 4

11

コンパイラがループ アンロールの最適化を実行するとき、ループをアンロールする要因や、ループ全体をアンロールするかどうかを判断する方法は?

スタックの消費と局所性。命令数。アンロールおよびインライン化されたプログラムに基づいて最適化を行う/伝播する機能。ループサイズが固定されているか、特定の範囲内にあると予想されるか。プロファイル入力 (該当する場合)。ループ本体から削除できる操作。等

これは平均してスペースとパフォーマンスのトレードオフであるため、プログラムのパフォーマンスを向上させる上で、この最適化手法はどの程度効果的ですか?

入力 (プログラム) に大きく依存します。遅くなる (一般的ではない) か、数倍速くなる可能性があります。最適に実行するプログラムを作成し、オプティマイザがその仕事を実行できるようにすることも学習されます。

また、どのような条件下でこの手法を使用することをお勧めしますか (つまり、特定の操作または計算)。

一般に、非常に小さなボディ、特に分岐がなく、データの局所性が良好なボディでの多数の反復。

オプションがアプリ、プロファイルに役立つかどうかを知りたい場合。

それ以上のことが必要な場合は、最適なプログラムの書き方を学習する時間を取っておく必要があります。これは、このテーマが非常に複雑であるためです。

于 2011-10-07T18:47:26.753 に答える
3

単純化した分析は、命令をカウントすることです。2 つの命令ループを 10 回アンロールすると、20 命令ではなく 11 命令になり、11/20 のスピードアップが得られます。しかし、最新のプロセッサ アーキテクチャでは、はるかに複雑です。キャッシュのサイズとプロセッサの命令パイプラインの特性によって異なります。上記の例は、2 倍ではなく 10 倍速く実行される可能性があります。10x ではなく 1000x で展開すると、実行速度が遅くなる可能性もあります。特定のプロセッサをターゲットにしないと、コンパイラ (またはそれらのために作成するプラグマ) は推測にすぎません。

于 2011-10-07T18:32:26.433 に答える
1

わかりました、まず第一に、コンパイラがこれを自動的に行う方法がわかりません。そして、コンパイラーが選択しなければならないアルゴリズムは、数百とまではいかなくても、少なくとも 10 はあると確信しています。
とにかく、それはおそらくコンパイラ固有です。

しかし、その有効性を計算するお手伝いをすることができます。

通常、この手法ではパフォーマンスが大幅に向上するわけではないことに注意してください。
しかし、ループ計算が繰り返されると、高いパーセンテージのパフォーマンスが得られます。
これは、通常、ループ内の関数がループの条件チェックよりもはるかに多くの計算時間を要するためです。

ですから、定数を使った単純なループがあるとしましょう。これは、怠惰すぎてコピー アンド ペーストを行うことができなかったか、単に見栄えが良くなると思ったからです。

for (int i = 0; i < 5; i++)
{
    DoSomething();
}

ここでは、 5 つの int 比較、5 つのインクリメント、および5 つのDoSomethig() 呼び出しがあります。
したがって、DoSomething() が比較的高速である場合、15 回の操作が行われます。
これをアンロールすると、たった 5 つの操作に減らすことができます。

DoSomething();
DoSomething();
DoSomething();
DoSomething();
DoSomething();

定数を使用すると簡単なので、変数を使用してどのように機能するかを見てみましょう。

for (int i = 0; i < n; i++)
{
    DoSomething();
}

ここでは、n回の int 比較、n回のインクリメント、およびn回のDoSomethig() 呼び出し = 3nがあります。ここで、完全に展開することはできませんが、一定の係数で展開することはできます ( nが大きくなると予想されるほど、より多く展開する必要があります)。

int i;
for (i = 0; i < n; i = i+3)
{
    DoSomething();
    DoSomething();
    DoSomething();
}
if (i - n == 2)
{
    DoSomething(); // We passed n by to, so there's one more left
}
else if (i - n == 1)
{
    DoSomething();  //We passed n by only 1, so there's two more left
    DoSomething();
}

ここでは、n/3+2の int 比較、n/3のインクリメント、n回のDoSomethig() 呼び出し = (1 2/3)*nがあります。(1 1/3)*nオペレーション
を節約できました。これにより、計算時間がほぼ半分に短縮されます。

参考までに、別の巧妙なアンロール手法は、ダフのデバイスと呼ばれます。
しかし、それは非常にコンパイラと言語の実装に固有です。これが実際にはさらに悪い言語があります。

于 2011-10-07T18:36:24.220 に答える
1

（私の意見では）ループを展開するのが良い場合：

ループは短く、おそらく使用されるすべての変数はプロセッサレジスタにあります。アンロール後、変数は「複製」されますが、まだレジスタにあるため、メモリ (またはキャッシュ) のペナルティはありません。

ループ (未知のループ展開数を持つ) は、少なくとも数回または数十回実行されるため、展開されたループ全体を命令キャッシュにロードする正当な理由があります。

ループが短い場合 (1 つまたは少数の命令)、再実行する必要があるかどうかを判断するためのコードが実行される頻度が低くなるため、展開に非常に役立つ可能性があります。

于 2011-10-07T18:31:43.300 に答える