15

最初の質問から続けて、64 ビット C プログラムの VTune プロファイリングで見つかったメモリ ホットスポットを最適化しようとしています。

特に、128 バイトのメモリ ブロックにすべてゼロが含まれているかどうかをテストする最速の方法を見つけたいと考えています。メモリ ブロックの任意のメモリ アラインメントを想定できます。64 バイトのアラインメントを使用しました。

私は、Intel Ivy Bridge Core i7 3770 プロセッサ、32 GB のメモリ、Microsoft vs2010 C コンパイラの無料バージョンを搭載した PC を使用しています。

私の最初の試みは：

const char* bytevecM;    // 4 GB block of memory, 64-byte aligned
size_t* psz;             // size_t is 64-bits
// ...
// "m7 & 0xffffff80" selects the 128 byte block to test for all zeros
psz = (size_t*)&bytevecM[(unsigned int)m7 & 0xffffff80];
if (psz[0]  == 0 && psz[1]  == 0
&&  psz[2]  == 0 && psz[3]  == 0
&&  psz[4]  == 0 && psz[5]  == 0
&&  psz[6]  == 0 && psz[7]  == 0
&&  psz[8]  == 0 && psz[9]  == 0
&&  psz[10] == 0 && psz[11] == 0
&&  psz[12] == 0 && psz[13] == 0
&&  psz[14] == 0 && psz[15] == 0) continue;
// ...

対応するアセンブリの VTune プロファイリングは次のとおりです。

cmp    qword ptr [rax],      0x0       0.171s
jnz    0x14000222                     42.426s
cmp    qword ptr [rax+0x8],  0x0       0.498s
jnz    0x14000222                      0.358s
cmp    qword ptr [rax+0x10], 0x0       0.124s
jnz    0x14000222                      0.031s
cmp    qword ptr [rax+0x18], 0x0       0.171s
jnz    0x14000222                      0.031s
cmp    qword ptr [rax+0x20], 0x0       0.233s
jnz    0x14000222                      0.560s
cmp    qword ptr [rax+0x28], 0x0       0.498s
jnz    0x14000222                      0.358s
cmp    qword ptr [rax+0x30], 0x0       0.140s
jnz    0x14000222
cmp    qword ptr [rax+0x38], 0x0       0.124s
jnz    0x14000222
cmp    qword ptr [rax+0x40], 0x0       0.156s
jnz    0x14000222                      2.550s
cmp    qword ptr [rax+0x48], 0x0       0.109s
jnz    0x14000222                      0.124s
cmp    qword ptr [rax+0x50], 0x0       0.078s
jnz    0x14000222                      0.016s
cmp    qword ptr [rax+0x58], 0x0       0.078s
jnz    0x14000222                      0.062s
cmp    qword ptr [rax+0x60], 0x0       0.093s
jnz    0x14000222                      0.467s
cmp    qword ptr [rax+0x68], 0x0       0.047s
jnz    0x14000222                      0.016s
cmp    qword ptr [rax+0x70], 0x0       0.109s
jnz    0x14000222                      0.047s
cmp    qword ptr [rax+0x78], 0x0       0.093s
jnz    0x14000222                      0.016s

インテルの組み込み関数を使用して、それを改善できました。

const char* bytevecM;                        // 4 GB block of memory
__m128i* psz;                                // __m128i is 128-bits
__m128i one = _mm_set1_epi32(0xffffffff);    // all bits one
// ...
psz = (__m128i*)&bytevecM[(unsigned int)m7 & 0xffffff80];
if (_mm_testz_si128(psz[0], one) && _mm_testz_si128(psz[1], one)
&&  _mm_testz_si128(psz[2], one) && _mm_testz_si128(psz[3], one)
&&  _mm_testz_si128(psz[4], one) && _mm_testz_si128(psz[5], one)
&&  _mm_testz_si128(psz[6], one) && _mm_testz_si128(psz[7], one)) continue;
// ...

対応するアセンブリの VTune プロファイリングは次のとおりです。

movdqa xmm0, xmmword ptr [rax]         0.218s
ptest  xmm0, xmm2                     35.425s
jnz    0x14000ddd                      0.700s
movdqa xmm0, xmmword ptr [rax+0x10]    0.124s
ptest  xmm0, xmm2                      0.078s
jnz    0x14000ddd                      0.218s
movdqa xmm0, xmmword ptr [rax+0x20]    0.155s
ptest  xmm0, xmm2                      0.498s
jnz    0x14000ddd                      0.296s
movdqa xmm0, xmmword ptr [rax+0x30]    0.187s
ptest  xmm0, xmm2                      0.031s
jnz    0x14000ddd
movdqa xmm0, xmmword ptr [rax+0x40]    0.093s
ptest  xmm0, xmm2                      2.162s
jnz    0x14000ddd                      0.280s
movdqa xmm0, xmmword ptr [rax+0x50]    0.109s
ptest  xmm0, xmm2                      0.031s
jnz    0x14000ddd                      0.124s
movdqa xmm0, xmmword ptr [rax+0x60]    0.109s
ptest  xmm0, xmm2                      0.404s
jnz    0x14000ddd                      0.124s
movdqa xmm0, xmmword ptr [rax+0x70]    0.093s
ptest  xmm0, xmm2                      0.078s
jnz    0x14000ddd                      0.016s

ご覧のとおり、アセンブリ手順が少なくなり、このバージョンはタイミング テストでさらに高速であることが証明されました。

私はインテルの SSE/AVX 命令の分野に非常に弱いので、このコードを高速化するためにどのように使用すればよいかについてのアドバイスを歓迎します。

利用可能な何百もの組み込み関数を精査しましたが、理想的な組み込み関数を見逃している可能性があります。特に、_mm_cmpeq_epi64(); を効果的に使用できませんでした。私はこの組み込み関数の「等しくない」バージョン (この問題により適しているようです) を探しましたが、結果は未熟でした。以下のコードは「機能します」が：

if (_mm_testz_si128(_mm_andnot_si128(_mm_cmpeq_epi64(psz[7], _mm_andnot_si128(_mm_cmpeq_epi64(psz[6], _mm_andnot_si128(_mm_cmpeq_epi64(psz[5], _mm_andnot_si128(_mm_cmpeq_epi64(psz[4], _mm_andnot_si128(_mm_cmpeq_epi64(psz[3], _mm_andnot_si128(_mm_cmpeq_epi64(psz[2], _mm_andnot_si128(_mm_cmpeq_epi64(psz[1], _mm_andnot_si128(_mm_cmpeq_epi64(psz[0], zero), one)), one)), one)), one)), one)), one)), one)), one), one)) continue;

それは判読不能の境界線上にあり、(当然のことながら) 上記の 2 つのバージョンよりもはるかに遅いことが証明されています。_mm_cmpeq_epi64() を使用するよりエレガントな方法が必要であると確信しており、それを実現する方法についてのアドバイスを歓迎します。

C の組み込み関数を使用することに加えて、この問題に対する未加工の Intel アセンブリ言語ソリューションも歓迎されます。

4

6 に答える 6

14

他の人が指摘しているように、主な問題は、チェックしている 128 バイトのデータがデータ キャッシュやTLBを欠いており、DRAM に送られていることです。これは遅いです。VTune はこれを伝えています

cmp    qword ptr [rax],      0x0       0.171s
jnz    0x14000222                     42.426s

途中に別の小さなホットスポットがあります

cmp    qword ptr [rax+0x40], 0x0       0.156s
jnz    0x14000222                      2.550s

JNZ 命令に起因する 42.4 + 2.5 秒は、実際にはメモリからの前のロードによって引き起こされたストールです... プロセッサは、プログラムをプロファイリングしている間、合計 45 秒間何もせずに座っています... DRAM で待機しています。

中途半端にある 2 番目のホットスポットは一体何なのかと疑問に思うかもしれません。さて、あなたは 128 バイトにアクセスしており、キャッシュ ラインは 64 バイトです。CPU は最初の 64 バイトを読み取るとすぐにプリフェッチを開始しました... しかし、最初の 64 バイトで十分な作業を行っていませんでした。メモリに移動するレイテンシと完全に重なります。

Ivy Bridge のメモリ帯域幅は非常に高いです (システムによって異なりますが、10 GB/秒以上だと思います)。メモリのブロックは 4GB です。連続してアクセスし、CPU がデータを事前に取得できるようにすると、1 秒未満で圧縮できるはずです。

私の推測では、不連続な方法で 128 バイト ブロックにアクセスすることで、CPU データ プリフェッチャーを妨害していると思われます。

アクセス パターンをシーケンシャルに変更すると、実行速度が驚くほど速くなります。その後、次のレベルの最適化について心配することができます。これにより、分岐予測がうまく機能するようになります。

考慮すべきもう 1 つのことは、TLB misses. これらは、特に 64 ビット システムではコストがかかります。4KB のページを使用するのではなく、 2MB の使用を検討してhuge pagesください。これらの Windows サポートについては、次のリンクを参照してください: Large-Page Support (Windows)

4GB のデータに多少ランダムな方法でアクセスする必要があるが、m7値のシーケンス (インデックス) を事前に知っている場合はpipeline、メモリを使用する前に明示的にフェッチすることができます (アクセスする前に数 100 CPU サイクルが必要です)。あなたは効果的にそれを使用します）。見る

メモリの最適化に関して一般的に役立つリンクをいくつか示します。

Ulrich Drepper によるメモリについてすべてのプログラマが知っておくべきこと

http://www.akkadia.org/drepper/cpumemory.pdf

マシン アーキテクチャ: プログラミング言語では決して語られないこと、Herb Sutter 著

http://www.gotw.ca/publications/concurrency-ddj.htm

http://nwcpp.org/static/talks/2007/Machine_Architecture_-_NWCPP.pdf

http://video.google.com/videoplay?docid=-4714369049736584770#

于 2013-03-02T15:51:56.610 に答える
5

回答投稿で申し訳ありませんが、コメントに対する評判が十分ではありません。
以下をテストとして使用するとどうなりますか?

if( (psz[0]  | psz[1]  | psz[2]  | psz[3]  |
     psz[4]  | psz[5]  | psz[6]  | psz[7]  |
     psz[8]  | psz[9]  | psz[10] | psz[11] |
     psz[12] | psz[13] | psz[14] | psz[15] ) == 0) continue;

残念ながら、私はそれをコンパイルするための 64 ビット システムを持っていません。また、コンパイラが C コードで何をするのか正確にはよくわかりませんが、バイナリまたはは個々の == 比較よりも高速であるように思えます。 . また、インテルの組み込み関数が何であるかはわかりませんが、上記のコードを、既に行ったのと同様の方法で最適化できる可能性があります。
私の答えがお役に立てば幸いです。
マルス

于 2013-03-02T08:22:43.743 に答える
2

Intel 文字列スキャン命令を検討しましたか? これらはデータ レートが非常に高くなる傾向があり、プロセッサはデータ アクセスがシーケンシャルであることを認識しています。

     mov      rdi, <blockaddress>
     cld
     xor      rax, rax
     mov      rcx, 128/8
     repe     scasq
     jne      ...

これは、データがキャッシュにないという問題には役立ちません。考慮したいチャンクが事前にわかっている場合は、インテルのプリフェッチ命令を使用して修正できます。http://software.intel.com/en-us/articles/use-software-data-prefetch-on-32-bit-intel-architectureを参照してください

[コメントで指摘された小さな問題を統合するためのコードの編集]

于 2013-03-02T17:19:38.717 に答える
2

128 バイト ブロックの 98% がすべてゼロであるため、4K ページあたり平均して非ゼロ バイトは 1 未満です。疎な配列で、それを疎な配列として保存しようとしましたか? 膨大な量のメモリとそれに付随するキャッシュ ミスの遅延を節約できます。普通の std::map の方が速くなっても驚かないでしょう。

于 2013-03-02T17:09:23.560 に答える
1

これまでに受け取った素晴らしいヒントに感謝します。

Mmarss の "mega or" アプローチは、生成されるアセンブリ言語命令が少ないため、パフォーマンスが向上すると確信していました。ただし、ベンチマーク プログラムを実行すると、元の不格好な && ソリューションでは 150 秒、元の不格好な Intel instrinsics ソリューションでは 145 秒だったのに対し、163 秒かかりました (これら 2 つは私の元の投稿で説明されています)。

完全を期すために、「mega or」アプローチに使用した C コードを次に示します。

if ((psz[0]  | psz[1]  | psz[2]  | psz[3]
|    psz[4]  | psz[5]  | psz[6]  | psz[7]
|    psz[8]  | psz[9]  | psz[10] | psz[11]
|    psz[12] | psz[13] | psz[14] | psz[15]) == 0) continue;

VTune アセンブリは次のとおりです。

mov    rax, qword ptr [rcx+0x78]    0.155s
or     rax, qword ptr [rcx+0x70]   80.972s
or     rax, qword ptr [rcx+0x68]    1.292s
or     rax, qword ptr [rcx+0x60]    0.311s
or     rax, qword ptr [rcx+0x58]    0.249s
or     rax, qword ptr [rcx+0x50]    1.229s
or     rax, qword ptr [rcx+0x48]    0.187s
or     rax, qword ptr [rcx+0x40]    0.233s
or     rax, qword ptr [rcx+0x38]    0.218s
or     rax, qword ptr [rcx+0x30]    1.742s
or     rax, qword ptr [rcx+0x28]    0.529s
or     rax, qword ptr [rcx+0x20]    0.233s
or     rax, qword ptr [rcx+0x18]    0.187s
or     rax, qword ptr [rcx+0x10]    1.244s
or     rax, qword ptr [rcx+0x8]     0.155s
or     rax, qword ptr [rcx]         0.124s
jz     0x1400070b9                  0.342s

次に、次の方法で「メガまたは」のアイデアをインテルの組み込み関数に変換してみました。

__m128i tt7;
// ...
tt7 = _mm_or_si128(_mm_or_si128(_mm_or_si128(psz[0], psz[1]),
      _mm_or_si128(psz[2], psz[3])),
      _mm_or_si128(_mm_or_si128(psz[4], psz[5]),
      _mm_or_si128(psz[6], psz[7])));
if ( (tt7.m128i_i64[0] | tt7.m128i_i64[1]) == 0) continue;

ただし、それは遅く、155 秒かかることが判明しました。その VTune アセンブリは次のとおりです。

movdqa xmm2, xmmword ptr [rax]         0.047s
movdqa xmm0, xmmword ptr [rax+0x20]   75.461s
movdqa xmm1, xmmword ptr [rax+0x40]    2.567s
por    xmm0, xmmword ptr [rax+0x30]    1.867s
por    xmm2, xmmword ptr [rax+0x10]    0.078s
por    xmm1, xmmword ptr [rax+0x50]    0.047s
por    xmm2, xmm0                      0.684s
movdqa xmm0, xmmword ptr [rax+0x60]    0.093s
por    xmm0, xmmword ptr [rax+0x70]    1.214s
por    xmm1, xmm0                      0.420s
por    xmm2, xmm1                      0.109s
movdqa xmmword ptr tt7$[rsp], xmm2     0.140s
mov    rax, qword ptr [rsp+0x28]       0.233s
or     rax, qword ptr [rsp+0x20]       1.027s
jz     0x1400070e2                     0.498s

上記の Intel 組み込み関数のアプローチはかなり粗雑です。それを改善するための提案は大歓迎です。

これは、測定の重要性を改めて示しています。どちらが速いかを推測するたびに、私は間違っていました。とはいえ、各変化を注意深く測定する限り、悪化することはなく、改善することしかできません。順方向よりも逆方向 (上記のように) の方が頻繁に行っていますが、この 1 週間で、小さなテスト プログラムの実行時間を 221 秒から 145 秒に短縮することができました。月、それは日を節約します。

于 2013-03-02T11:56:32.007 に答える