問題タブ [loop-unrolling]

XNA ゲームを作成していますが、いくつかのループを最適化する方法があるかどうか疑問に思っています。例えば：

タイルのコレクションを含む Map クラスがあるため、Map Update() ですべてのタイル Update() を呼び出すだけです。

これは問題なく動作しますが、Particle クラスのように、すべてのパーティクルが ParticleManager クラス (パーティクルのコレクションを含む) で管理されるように、いくつかのより大きな人口のオブジェクトでは最悪になる可能性があります。

ParticleManager はすべてのパーティクルに対してループし、各パーティクルはすべてのタイルの衝突をチェックします。したがって、20 個のパーティクルと 100 個のタイルがある場合、多くの計算が行われます。

そのため、ループの展開などのいくつかの最適化を考えていましたが、未定義の長さのループで機能するかどうかはわかりません (そうではないと思います) (コンパイラーはコンパイル時にこれらのループの長さを知らないため)。

総括する：

1. ループ展開を使用してこれらのループを最適化することは可能ですか?
2. 他のタイプの最適化についてアドバイスしてもらえますか?

ありがとう

「ループ展開の意味」は誰もが知っていると思います。念のため、具体的な例をすぐに示します。私が尋ねる質問は... x86-64アセンブリ言語でループを展開すると、実際にコードが高速になりますか? なぜ私がこの概念に疑問を持ち始めたのかを説明します。

「ループのアンローリング」という用語に慣れていない人のために、私が今書いているコードのループの一例を次に示します。

そして、これがそのループが展開されたように見えるものです:

上記の例は代表的なものですが、この議論には最適ではない可能性があることに注意してください。その理由は、条件分岐の数が多いためです。「取られなかった分岐」は他の命令と似ていると思いますが、その仮定は場合によっては正しくない可能性があります (あいまいな場合があります)。movqしたがって、この側面が関連する場合、これら 2 つの条件付き分岐は、またはこの説明のような単純な命令であると想定できますaddq(ただし、異なる場合は両方のケースに個別に対処することが望ましいです)。

ああ、2 つの最終条件:

#1: この質問は、シングル スレッドで実行中のコードにのみ適用されます。

＃2：この質問は、最新の高速〜4GHz CPU（FX-8350など）にのみ適用されます。

さて、ここで、ループの展開が実際に賢明かどうか疑問に思う点について説明します。

これらの新しいプロセッサは 4 GHz で動作し、各サイクルで 2 つまたは 3 つの命令を実行できる場合があります。上記の私のコードでは、最初の 2 つの命令は並列に実行できず、おそらく最後の 3 つの命令も並列に実行できません。しかし、並行して実行できる命令を含むループは、私の質問をより適切なものにするだけです。

したがって、各命令は 0.25 ナノ秒 (または並列で実行される命令の場合はそれ以下) で実行される可能性があります。これは、4 つの命令の実行に 1 ナノ秒かかることを意味します。4 つの命令の各セットは、およそ 16 バイトを消費します。これは、キャッシュ ラインの 1/4 であると想定しています。したがって、4 ラインの 4 セットは、実行に 4ns かかる必要があり、その時点でキャッシュ ラインを終了し、別のラインが必要になります。

これは、質問がより複雑になるところです。

したがって、16 個の命令と展開されたループ全体の 1/4 の後、CPU はさらに多くの命令を実行する必要があります。CPU がコードのループ バージョンを実行していた場合、まったく同じ命令を再度実行しますが、これは間違いなく L1 キャッシュに残っているため、フルボアの CPU 速度で実行し続けます。

しかし、CPU がわずか 4ns で次のキャッシュ ラインをロードしたと合理的に期待できますか? あるいは、並行して実行できる命令の場合、CPU が次のキャッシュ ラインをわずか 2ns でロードしたと合理的に期待できますか?

ダイナミックRAMについて私が知っていることから、それは...きついようです。CPU が連続するアドレスにアクセスすると、RAS (上位アドレス ビット) がラッチされたままになり、連続する 64 ビットまたは 128 ビットのメモリ チャンクが CAS により高速に出力されることがわかっています。しかし、CPU が 2ns または 4ns で 64 バイトを読み取ることを本当に期待できるでしょうか? これは、CPU が読み取り操作ごとに 64 ビット (8 バイト) を読み取るか、128 ビット (16 バイト) を読み取るかに応じて、DRAM からの読み取りサイクルが 4 または 8 になります。

私の特定のコードは、この質問をさらに実行する可能性があります。このアルゴリズムの性質上、私のコードでは、最初に分子と分母の最も重要な部分を比較し、アクセスごとに下位アドレスに向かって下向きに処理する必要があります。これにより、自動プリフェッチが機能しにくくなりますか?

さまざまな人がループと展開されたループをテストしているのを見てきました。しかし、私が見たすべての例には、致命的な設計上の欠陥があります。同じルーチンを何度も何度も呼び出し続けます...通常は何百万回も...理解するのに十分な大きさのタイマー値を取得するために。ちょっと待って！ほとんどのアプリケーションと同様に、コードで 1024 ビットの除算関数が呼び出されることはほとんどありません。これは、私が見たこれらのテストとは異なり、その性質上、命令が L1 命令キャッシュに留まり、アクセスされたデータが L1 データ キャッシュに留まることが保証されます。

もちろん、コードとデータがすでに L1 キャッシュにあることを確認すれば、展開されたループは高速になります。当たり前！

これらは代表的なテストではありません。

これらのテストは「最良のケースのパフォーマンス」を測定しますが、通常のプログラムの実行をまったく表していません。しかし、64 ビット アセンブリ言語コード (またはコンパイラのコード エミッター部分) を最適に記述する方法を決定するには、私たちの前提でより現実的になる必要があります。または、少なくともそう思うので、この質問をします。

これらの質問を徹底的かつ現実的な方法で経験した人はいますか?

関数を呼び出すと

静的配列を使用するとforeach、リリースモードで自動的に展開されますか?

できなければ

の代わりにアンローリングを実現するために使用されforeachます。

さらに、DMD によって生成されたコードを将来私自身が調査できるように、アセンブリ コードを生成する DMD へのフラグはありますか?

更新：これまでの私の解決策は次のとおりです。

それは大丈夫ですか？

O(N^4) 画像処理ループがあり、(Intel Vtune 2013 を使用して) プロファイリングした後、リタイアした命令の数が大幅に減少していることがわかります。マルチコア アーキテクチャでのこの動作を理解するのに助けが必要です。(私は Intel Xeon x5365 を使用しています - 2 つのコアごとに共有 L2 キャッシュを持つ 8 つのコアがあります)。また、分岐予想外も激増!! ///////////////EDITS/////////// 非展開コードのサンプルを以下に示します。

最も内側のループを 4 回の反復で展開しています (ループをどのように削除したかという一般的な理想が得られます。基本的には、Array[4] の配列を作成し、それぞれの値を入力します)。反復回数の合計を 75% 削減します。すべてのループ (load i、inc i、cmp i、jle ループ) に 4 つのループ処理命令があるとします。アンロール後の命令の総数は、(256-64)*4*256*256*496=24.96G 減少するはずです。 . プロファイリングされた結果は次のとおりです。

引退したインストルメントは 518.06G 減少しました。これがどのように起こっているのか、私にはわかりません。これに関する助けをいただければ幸いです（たとえそれが発生する可能性が低い場合でも）。また、ブランチの予測ミスが増えている理由を知りたいです。前もって感謝します！

496*O(N^3) ループがあります。一度に 1 つではなく 2 つの画像を操作するブロッキング最適化手法を実行しています。生の用語では、外側のループを展開しています。(コードの展開されていないバージョンは以下のとおりです:) ところで、私は 8 コアの Intel Xeon X5365 マシンを使用しており、クロックは 3 GHz、バス周波数は 1333 MHz、共有 8 MB L2 (2 コアごとに 4 MB が共有) です。 、L1-I 32KB、L1-D 32KB。

Intel Vtune-2013 (gcc-4.1 から作成されたバイナリを使用) を使用して結果をプロファイリングしたところ、反復ごとに 2 つの画像が処理されるため、メモリ帯域幅の使用量が 40% 削減されていることがわかります。ボクセルごとに 8 バイトのトラフィック）。これにより、バス サイクルが 11.7% 削減されます。また、内側のループでブロックサイズが大きくなるため、リソースのストールが 25.5% 減少します。これら 2 つは、応答時間が 18% 短縮されたことを示しています。謎の質問は、なぜ引退した指導者が 7.9% 増加したのかということです。(これにより、応答時間が 6.51% 増加しました) - 考えられる理由は次のとおりです。 1. ブロック内で分岐命令の数が増加するため (コア アーキテクチャには 8 ビットのグローバル履歴があるため)、廃止された分岐命令は 2.5% 増加しました。 （ それでも、誤算は相変わらず！私は知っています、魚のにおいがしますよね?!!)。しかし、残りの 5.4% についてはまだ回答がありません。誰か私に光を当ててください。私は完全に選択肢がなく、考える方法がありません。どうもありがとう！！

アセンブラでのプログラミングに慣れようとしています。最初はランダムなコードを選択して更新しようとしました。また、ループの展開についていくつか読んだことがありますが、どこから始めればよいかわかりません。

これは、すでに少し変更した私のコードです。

反復回数がわかっているが大きいループを展開するように GCC を説得するにはどうすればよいですか?

でコンパイルしてい-O3ます。

もちろん、問題の実際のコードはもっと複雑ですが、同じ動作をする簡単な例を次に示します。

...CONSTANT_COUNTが 8 (またはそれ以下) として定義されている場合、GCC はループをアンロールし、定数を伝搬し、関数全体を単純なreturn <value>;. 一方、CONSTANT_COUNTが 9 (またはそれ以上) の場合、ループは展開されず、GCC はループし、定数を読み取り、実行時にそれらを追加するバイナリを生成します。定数を返すだけに最適化されます。(はい、逆コンパイルされたバイナリを見てきました。)

次のように、ループを手動で展開すると、次のようになります。

またはこれ：

...その後、関数は定数を返すように最適化されます。そのため、GCC は一度アンロールされると、より大きなループの一定の伝播を処理できるように見えます。ハングアップは、最初に長いループを展開することを GCC に検討させるだけのようです。

ただし、 が実行時の式である場合があり、そのような場合でも同じコードが正しく機能する必要があるため、手動展開もBOOST_PP_REPEAT実行可能なオプションでもありません。(これらの場合、パフォーマンスはそれほど重要ではありません。)CONSTANT_COUNT

私は C (C++ ではない) で作業しているため、テンプレートのメタプログラミングもconstexpr利用することもできません。

、 、 、 、 、 、、、および-funroll-loopsに-funroll-all-loops大きな値を-fpeel-loops設定しようとしましたが、どれも違いがないようです。max-unrolled-insnsmax-average-unrolled-insnsmax-unroll-timesmax-peeled-insnsmax-peel-timesmax-completely-peeled-insnsmax-completely-peel-times

Linux x86_64でGCC 4.8.2を使用しています。

何か案は？不足しているフラグまたはパラメーターはありますか...?

I am trying to see how unrolling is done in GCC. I have written a C code to add elements of an array to do this.

I have compiled it with -o2 flag and -funroll-all-loops.

The object file for the above program has the following assembly code.

In each iteration it is a doing only one addition (7th line in the L3 section) and incrementing the content of rbp register by 1 (as in the last line of L3 section). This indicates that compiler is not unrolling the loop. I was expecting more additions to happen in one loop. My question is, why it is not unrolling the loop even after using the funroll flag?. Is there a possibility that compiler is not optimizing because it thinks that unrolling is not useful in this case ?. If that is true, then what should I do in order to make the compiler unroll the loops ?.