問題タブ [loop-unrolling]

ループのアンローリングに関してプログラムを最適化するツールがあるのだろうか。

次のpythonコードがあります：

このコード セグメントを最適化して、ループの展開を少し理解できるようにしたいと考えています。Python で、C オプティマイザーについて知りたいです。

オリジナルコード

while ループ展開

上記のように展開できません。いつもhttp://en.wikipedia.org/wiki/Loop_unrollingのようにする必要がありますか?

上記のコードに示されているように、私の推測では、

for（; in_x！= 0; in_x >> = 1）

コンパイラはループを展開しません。可能な最大のin_xについて確信が持てないためです。

私が正しいか間違っているか、そしてそのようなことに対処するためのより良い方法があるかどうかを知りたいです。

あるいは、問題は、コンパイラに実行時の値の範囲を指示するコードを記述できるかのように一般化でき、そのようなコードは必ずしも実行時のバイナリにコンパイルされるとは限りません。

本当に、コンパイラXDと戦う

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

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

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

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

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

私は集中的にメモリにバインドされているコードを扱ってきました。キャッシュ ブロック、sw プリフェッチ、ループ展開などを手動で実装することにより、シングル コア内で最適化しようとしています。キャッシュ ブロックによってパフォーマンスが大幅に向上しますが。ただし、ループ展開を導入すると、パフォーマンスが大幅に低下します。

すべてのテスト ケースで、コンパイラ フラグ -O2 および -ipo を使用して Intel icc でコンパイルしています。

私のコードはこれに似ています（3D 25ポイントステンシル）：

最も内側のループ (次元 i) でループ展開を行い、x、y、z 方向にそれぞれ展開係数 2、4、8 で展開すると、9 つのケースすべてでパフォーマンスが低下します。つまり、方向 x で 2 ずつ展開し、展開します。 y 方向に 2 ずつ展開、z 方向に 2 展開、x 方向に 4 展開 ... など。キャッシュのブロックよりも優れた v.good パフォーマンスの向上を実現します。

Intel Vtune を使用してコードのプロファイリングも試みました。リモート DRAM によってサービスされる 1.LLC ミスと 2.LLC ロード ミスが主な原因のボトルネックのように見えました。

最も内側の最速のループを展開するとパフォーマンスが低下するのに、最も外側の最も遅い次元を展開するとパフォーマンスが向上する理由を理解できません。ただし、後者の場合のこの改善は、icc でコンパイルするときに -O2 と -ipo を使用した場合です。

これらの統計の解釈方法がわかりません。誰かがこれに光を当てるのを助けることができますか.

次のコードを検討してください

g++、clang++、icc などのコンパイラは、このようなループを展開できますか? 残念ながら、アセンブリが出力からループが展開されるかどうかを確認できるかどうかはわかりません。（そして、私はg ++にしかアクセスできません。）

私には、これにはコンパイラーに代わって通常よりもスマートさが必要になるように思われます。最初にイテレーターがランダムアクセスイテレーターであると推測し、次にループが実行される回数を把握します。最適化が有効になっている場合、コンパイラはこれを行うことができますか?

返信ありがとうございます。時期尚早な最適化について講義を始める前に、これは好奇心のエクササイズです。

次の 2 つの実装は、使用するコンパイラに関係なく、同じパフォーマンスでまったく同じものを生成するのではないかと思います。

最初のものでは、ループで使用される TSIZE がテンプレート パラメーターであるため、必要に応じてコンパイラがループを展開することがほぼ保証されます。最初のケースでループが展開された場合、2 番目のケースで展開されますか (唯一の違いは、TSIZE が static const に格納されていることです)。

どうもありがとうございました。

Linuxカーネルドライバー（ARM用）を作成していて、irqハンドラーで割り込みビットをチェックする必要があります。

一度に1ビット以上を設定できることに注意してください。

だからこれはコードです：

(1 << 0)ただし、(1 << 16)コンパイル時に計算されますが、計算されません。また、ループには積分の比較と加算があります。(1 << i)(1 << (i + 16))

これはirqハンドラーであるため、作業は最短時間で実行する必要があります。これにより、少し最適化する必要があるかどうかを考えさせられます。

可能な方法は？

1.ループを分割しますが、違いはないようです...

2.intr比較する値の代わりにシフトしますか？

3.ループを完全に展開します（図には示されていません）。それはコードを少し厄介にするでしょう。

4.他にもっと良い方法はありますか？

5.それとも、コンパイラが実際に最も最適化された方法を生成するということですか？

編集：私はgccコンパイラにその特定のループを展開するように指示する方法を探していましたが、私の検索によればそれは不可能のようです...

CUDA では、#pragmaunroll ディレクティブを使用してループを展開し、命令レベルの並列性を高めることでパフォーマンスを向上させることができます。オプションで、#pragmaループをアンロールする必要がある回数を指定する数値を続けることができます。

残念ながら、ドキュメントには、このディレクティブをいつ使用する必要があるかについての具体的な指示はありません。既知のトリップ カウントを持つ小さなループは既にコンパイラによって#pragma展開されているため、より大きなループで展開を使用する必要がありますか? 可変カウンターを使用した小さなループでは? また、オプションのアンロール数はどうですか? また、cuda 固有のループ展開に関する推奨ドキュメントはありますか?

その下には、模擬試験の問題があります。この表には、実際にはすべてのソリューションが記入されています。ただし、ソリューションが何であるかについて明確にする必要があります。（水平線の下の質問を読んでください）。

たとえば、A2 と A3 のソリューション行を理解したいと思います。

ご覧のとおり、A2 では次のような状況が発生しています。

1. x * y
2. xy * r
3. xyr * z

それでは、それがパイプラインでどのようになるかを見てみましょう。

したがって、依存関係の競合がないため、xyr * z と x2 * y2 を重ねることができます。しかし、それは3サイクルを取り除くだけですよね?

したがって、(12 - 3) / 3 = 9 / 3 = 1 エレメントあたり 3 サイクル (3 エレメント) となります。では、どうやって A2 の 8/3 CPE を得ているのでしょうか?

この概念を理解する助けがあれば大歓迎です! テストは来週までないので、急ぐ必要はありません。他に必要な情報があれば教えてください！

(以下は、完全に解答が記入された表とともに、完全なテスト問題のテキストです)

n 個の整数の配列の積を計算する次の関数を考えてみましょう。

ループを 3 倍に展開しました。

製品の計算というラベルの付いた行では、次のように、括弧を使用して計算の 5 つの異なる関連付けを作成できます。

関数のパフォーマンスを要素あたりのサイクル数 (CPE) で表します。この本で説明されているように、この測定では、長さ n の配列の実行時間がクロック サイクルで測定され、Cn + K の形式の関数であると想定しています。ここで、C は CPE です。

Intel Pentium III で関数の 5 つのバージョンを測定しました。このマシンでの整数乗算演算のレイテンシは 4 サイクルで、発行時間は 1 サイクルであることを思い出してください。

次の表は、CPE のいくつかの値と、欠落している他の値を示しています。測定された CPE 値は、実際に観察された値です。「理論上の CPE」とは、整数乗数の遅延と発行時間が唯一の制限要因である場合に達成されるパフォーマンスを意味します。

不足しているエントリを入力します。測定された CPE の欠損値については、同じ計算動作を持つ他のバージョンの値を使用できます。理論上の CPE の値については、乗数のレイテンシと発行時間のみを考慮して反復に必要なサイクル数を決定し、3 で割ることができます。