問題タブ [loop-unrolling]

次のループでは、連想演算を使用するように指示した場合にのみ、GCC はループをベクトル化します-Ofast。

これがアセンブリです-Ofast -mavx

これは、ループがベクトル化されたことを明確に示しています。

しかし、このループには依存関係の連鎖もあります。加算のレイテンシーを克服するために、x86_64 で少なくとも 3 回アンロールして部分合計を実行する必要があります (8 回アンロールする必要がある Skylake と、Haswell と Broadwell で 10 回アンロールする必要がある FMA 命令で加算を行うことを除く)。 . 私が理解している限り、でループを展開できます-funroll-loops。

との組み立てはこちら-Ofast -mavx -funroll-loops。

GCC はループを 8 回アンロールします。ただし、独立した合計は行いません。従属合計を 8 つ計算します。それは無意味であり、展開しないのと同じです。

GCC にループを展開させ、独立した部分和を実行させるにはどうすればよいですか?

編集：

Clang は-funroll-loops、SSE がなくても 4 つの独立した部分和に展開されますが、その AVX コードがそれほど効率的かどうかはわかりません。-funroll-loopsとにかくコンパイラはwithを必要としないはずな-Ofastので、少なくとも SSE では Clang がこれを正しく行っていることを確認するのは良いことです。

Clang 3.5.1 with -Ofast.

ICC 13.0.1 と-O32 つの独立した部分合計への展開。ICC はどうやら のみの連想演算を前提としてい-O3ます。

1 ～ 1,000,000 回の範囲で繰り返し実行する必要があり、コンパイル時には繰り返し回数がわからないコードがあるとします。ループの展開は、多数のループを考えると無視できる最適化であり、コンパイル時に指定された max_unrolls までしか最適化されないことを理解しています。私が思いついたアイデアは、実行時に指定された回数だけ some_function を本質的に繰り返し実行するバイナリ (または基数 2) 部分ループ アンローラーを実装することです。私はアイデアを実証するためにいくつかのコードを考え出しました。要約版を以下に示します。以下のコードで使用されているメソッドには、使いやすさの観点から多くの問題があります。

1. 基本的に 2^n-1 回アンロールをコピーするために、コーダーはベース 2 アンロールを手動でコピーする必要があります。
2. これは、このメソッドを使用する必要がある新しい関数ごとに再実行する必要もあります。

私の質問は 3 つあります。まず、私は何かが欠けています.コンパイラはすでにこれを行うのに十分なほどインテリジェントですか? for第二に、上記の問題を解決しながら、これを標準ループに対してベンチマークすることが可能になるように、これを実装する効率的な方法は何ですか。第三に、あなたの知る限り、これを既に実装しているライブラリがあります。

注意:私は純粋に楽しみのためにこれを行っていますが、これが効果的かどうかを知る専門知識はありません。コードのテストを行いましたが、非常に小さな改善しか見られませんでしたが、公正な比較を行うには、手動で展開することが十分ではなかったと思います。また、この方法が巨大なバイナリ サイズを作成する可能性があることは承知していますが、これは時間とメモリのトレードオフとして価値があると思います。また、アセンブリを投稿すると、それを理解するのにさらに1年ほどかかるでしょう.

仕組みは理解し#pragma unrollていますが、次の例があるとします。

LIMIT上記のカーネルでx、スレッドy数とブロック数で起動される の最適な値を決定したいと考えています。は～のLIMITいずれかになります。100 万は変数にとって非常に大きな数のように見えるため (100 万のループを展開するとレジスタ プレッシャが発生し、コンパイラがその展開を行うかどうかはわかりません)、「公正な」数とは何ですか? そして、その制限をどのように決定しますか？21<<20

次の AVX 操作を行う必要があります。

これは次のように書き直すことができます。

_mm256_shuffle_psこれは、3 番目のパラメーターとして即時の整数値のみを受け入れるにもかかわらず、gcc 4.9.1 でコンパイルされます。これは、これiがイミディエイトとして受け入れられることを意味し、ループが展開されたことを意味します。

だから私は興味があります:これはコンパイラによって保証されているものですか?それとも、最適化フラグが変更されたとき、またはgccバージョンが変更されたときにコンパイルエラーを引き起こす可能性がありますか? 他のコンパイラ (msvc、icc、clang...) の使用について

いくつかのループを最適化しようとしていますが、うまくいきましたが、部分的にしか正しくできていないのではないでしょうか。たとえば、次のループがあるとします。

これを係数 3 で展開すると、次のようになります。

現在、SSE の同等の翻訳は次のとおりです。

またはそれは：

コードのセクションについて少し混乱しています：

これは何をしますか？たとえば、ループをアンロールするために選択した係数で分割できない場合、余分な部分を実行するだけですか? ありがとうございました。

GCC (私は 4.8.4 を使用しています) にwhile一番下の関数のループを完全に展開するように指示する方法はありますか?つまり、このループをピールしますか? ループの反復回数は、コンパイル時にわかっています: 58。

最初に私が試したことを説明しましょう。

GAS出力を確認することにより：

XMM0 ～ XMM11 の 12 本のレジスタを使用します。フラグ-funroll-loopsを gcc に渡すと、次のようになります。

ループは 2 回だけ展開されます。GCC 最適化オプションを確認しました。GCC はそれ-funroll-loopsもオンにすると言い-frename-registersます。そのため、GCC がループをアンロールするとき、レジスタ割り当てのための以前の選択は、「残りの」レジスタを使用することです。しかし、XMM12 から XMM15 までは 4 つしか残っていないため、GCC は最高でも 2 回しか展開できません。利用可能な XMM レジスタが 16 個ではなく 48 個ある場合、GCC は問題なく while ループを 4 回アンロールします。

それでも私は別の実験をしました。最初に while ループを手動で 2 回展開し、 function を取得しましたGEPDOT_2。そしたら全然違いがない

と

GEPDOT_2すでにすべてのレジスタを使用しているため、展開は実行されません。

GCC は、誤った依存関係が導入される可能性を回避するために、レジスタの名前変更を行います。しかし、私の中にはそのような可能性がないことは確かGEPDOTです。あったとしても、それは重要ではありません。ループを自分で展開してみましたが、4 回展開すると 2 回展開するよりも速く、展開しないよりも高速です。もちろん、手動で何度も展開できますが、面倒です。GCCは私のためにこれを行うことができますか? ありがとう。

更新 1

@ user3386109 のコメントのおかげで、この質問を少し広げたいと思います。@ user3386109 は非常に良い質問をします。実際、スケジュールする並列命令が非常に多い場合に、最適なレジスタ割り当てを行うコンパイラの能力に疑問があります。

個人的には、最初にasmインライン アセンブリでループ本体 (HPC の鍵となる) をコーディングし、それを何度でも複製するのが確実な方法だと思います。今年の初めに人気のない投稿がありました: inline assembly . ループの反復回数 j は関数の引数であるため、コンパイル時には不明であるため、コードは少し異なります。その場合、ループを完全に展開することはできないので、アセンブリ コードを 2 回だけ複製し、ループをラベルに変換してジャンプしました。作成したアセンブリの結果として得られるパフォーマンスは、コンパイラが生成したアセンブリよりも約 5% 高いことがわかりました。これは、コンパイラが予想される最適な方法でレジスタを割り当てることができないことを示唆している可能性があります。

私は (そして今も) アセンブリ コーディングの初心者だったので、x86 アセンブリについて少し学ぶための良いケース スタディになりました。GEPDOTしかし、長い目で見れば、私はアセンブリの割合が大きいコードを書く傾向はありません。主に次の3つの理由があります。

1. asmインライン アセンブリは、移植性がないと批判されています。理由はわかりませんが。おそらく、マシンごとに異なるレジスタが上書きされているためでしょうか?
2. コンパイラも良くなっています。したがって、コンパイラーが適切な出力を生成するのを支援するために、アルゴリズムの最適化と C コーディングの習慣を改善することを引き続き好みます。
3. 最後の理由はもっと重要です。反復回数は必ずしも 58 回とは限りません。高性能の行列分解サブルーチンを開発しています。キャッシュ ブロック ファクターのnb場合、反復回数は になりますnb-2。nb以前の投稿で行ったように、関数の引数として指定するつもりはありません。これはマシン固有のパラメータで、マクロとして定義されます。したがって、反復回数はコンパイル時にわかりますが、マシンごとに異なる場合があります。さまざまなnb. したがって、ループを剥がすようにコンパイラに指示するだけの方法があれば、それは素晴らしいことです。

高性能でありながらポータブルなライブラリを作成する経験も共有していただければ幸いです。

次の命令があるとします。数値が正かどうか (負またはゼロ) をチェックし、正の場合はカウンターに 1 を追加します (数値が負かゼロかは気にしません)。これは、単純なループ展開で行うことができます。

私の質問は、ゼロまたは負であることも確認したい場合、どうすれば同じ効率的な構造を得ることができるかということです。この場合、私は 3 つのカウンターを持ちます (1 つは pos 用、もう 1 つは neg 用、もう 1 つは 0 用)。前の例と同じ構造を作ろうとしています (正の数を に%rax、負の数を に%rbx、ゼロをに格納しています%rcx):