5

250 MB のデータをストリーミングするアプリケーションがあり、データ チャンク (それぞれ 2 つの 32 ビット ワード) にシンプルで高速なニューラル ネットしきい値関数を適用します。(非常に単純な) 計算の結果に基づいて、チャンクは予想外に 64 個のビンの 1 つにプッシュされます。つまり、1 つの大きなストリームが入って、64 の短い (可変長) ストリームが出てきます。

これは、さまざまな検出関数で何度も繰り返されます。

コンピューティングは、メモリ帯域幅が制限されています。これは、はるかに計算量の多い判別関数を使用しても速度の変化がないためです。

メモリ帯域幅を最適化するために新しいストリームの書き込みを構造化する最良の方法は何ですか? 特に、キャッシュの使用とキャッシュ ラインのサイズを理解することが、これに大きな役割を果たしているのではないかと考えています。64 個の出力ストリームがあり、運が悪かったために多くが同じキャッシュ ラインにマップされたという最悪のケースを想像してみてください。次に、次の 64 ビットのデータをストリームに書き込むときに、CPU は古いキャッシュ ラインをメイン メモリにフラッシュし、適切なキャッシュ ラインにロードする必要があります。これらはそれぞれ 64 バイトの帯域幅を使用します... したがって、帯域幅が制限されたアプリケーションは、メモリ帯域幅の 95% を浪費している可能性があります (ただし、この仮想的な最悪のケースでは)。

効果を測定しようとすることさえ難しいため、それを回避する方法を設計することはさらにあいまいです. それとも、ハードウェアが私よりもうまく最適化するゴーストボトルネックを追いかけているのでしょうか?

違いがある場合は、Core II x86 プロセッサを使用しています。

編集:これはいくつかのサンプルコードです。配列を介してストリーミングし、その要素を疑似ランダムに選択されたさまざまな出力配列にコピーします。同じプログラムを異なる数のデスティネーション ビンで実行すると、同じ量の計算とメモリの読み取りと書き込みが行われたとしても、異なるランタイムが得られます。

2 出力ストリーム: 13 秒
8 出力ストリーム: 13 秒
32 出力ストリーム: 19 秒
128 出力ストリーム: 29 秒
512 出力ストリーム: 47 秒

512 を使用する場合と 2 つの出力ストリームを使用する場合の違いは 4 倍です (おそらく??) は、キャッシュ ラインの削除のオーバーヘッドが原因です。

#include <stdio.h>
#include <stdlib.h>
#include <ctime>

int main()
{
  const int size=1<<19;
  int streambits=3;
  int streamcount=1UL<<streambits; // # of output bins
  int *instore=(int *)malloc(size*sizeof(int));
  int **outstore=(int **)malloc(streamcount*sizeof(int *));
  int **out=(int **)malloc(streamcount*sizeof(int));
  unsigned int seed=0;

  for (int j=0; j<size; j++) instore[j]=j;

  for (int i=0; i< streamcount; ++i) 
    outstore[i]=(int *)malloc(size*sizeof(int));

  int startTime=time(NULL);
  for (int k=0; k<10000; k++) {
    for (int i=0; i<streamcount; i++) out[i]=outstore[i];
    int *in=instore;

    for (int j=0; j<size/2; j++) {
      seed=seed*0x1234567+0x7162521;
      int bin=seed>>(32-streambits); // pseudorandom destination bin
      *(out[bin]++)=*(in++);
      *(out[bin]++)=*(in++);
    }

  }
  int endTime=time(NULL);
  printf("Eval time=%ld\n", endTime-startTime);
}
4

5 に答える 5

4

64 個の出力ビンに書き込んでいると、さまざまなメモリ ロケーションを使用することになります。ビンが基本的にランダムに満たされる場合、同じキャッシュ ラインを共有する可能性のある 2 つのビンが存在する場合があることを意味します。大きな問題ではありません。Core 2 L1 キャッシュは 8 ウェイ アソシアティブです。つまり、問題が発生するのは 9 番目のキャッシュ ラインだけです。いつでも 65 のライブ メモリ参照 (1 読み取り/64 書き込み) で、8 方向連想は問題ありません。

L2 キャッシュは明らかに 12 方向の連想です (合計 3/6 MB であるため、12 はそれほど奇妙な数字ではありません)。したがって、L1 で衝突が発生したとしても、まだメイン メモリにヒットしていない可能性はかなり高いです。

ただし、これが気に入らない場合は、メモリ内のビンを再配置してください。各ビンを順番にストローする代わりに、インターリーブします。ビン 0 の場合、チャンク 0 ~ 15 をオフセット 0 ~ 63 に格納しますが、チャンク 16 ~ 31 をオフセット 8192 ~ 8255 に格納します。ビン 1 の場合、チャンク 0 ~ 15 をオフセット 64 ~ 127 などに格納します。これには数ビットのシフトとマスクが必要ですが、その結果、ビンのペアが 8 つのキャッシュ ラインを共有することになります。

この場合、コードを高速化するもう 1 つの方法は、特に x64 モードで SSE4 を使用することです。16 個のレジスタ x 128 ビットが得られ、読み取り (MOVNTDQA) を最適化してキャッシュ汚染を制限できます。ただし、それが読み取り速度に大きく役立つかどうかはわかりません-Core2プリフェッチャーがこれをキャッチすることを期待しています. 順次整数の読み取りは可能な最も単純な種類のアクセスであり、プリフェッチャーはそれを最適化する必要があります。

于 2009-04-02T14:52:10.040 に答える
3

各「チャンク」を識別するインライン メタデータを使用して、出力ストリームを単一のストリームとして書き込むオプションはありますか? 「チャンク」を読み取る場合は、しきい値関数を実行し、特定の出力ストリームに書き込む代わりに、それが属しているストリーム (1 バイト) に続いて元のデータを書き込むだけです。スラッシングを減らします。

これらのデータを何度も処理する必要があるとあなたが言ったという事実を除いて、私はこれをお勧めしません. 連続して実行するたびに、入力ストリームを読み取ってビン番号 (1 バイト) を取得し、次の 8 バイトでそのビンに対して必要なことを行います。

このメカニズムのキャッシュ動作に関する限り、データの 2 つのストリームをスライドするだけであり、最初のケースを除いてすべて、読み取り中のデータと同じ量のデータを書き込むため、ハードウェアは期待できるすべての支援を提供します。プリフェッチ、キャッシュラインの最適化などに関する限り。

データを処理するたびに余分なバイトを追加する必要がある場合、最悪の場合のキャッシュ動作は平均的なケースです。ストレージヒットに余裕があれば、それは私にとって勝利のようです.

于 2009-04-06T21:01:09.770 に答える
2

あなたが本当に必死になっている場合、ここにいくつかのアイデアがあります...

ハードウェアのアップグレードを検討してください。あなたのようなストリーミング アプリケーションの場合、i7 プロセッサに変更することで速度が大幅に向上することがわかりました。また、AMD プロセッサは、メモリ バウンドの作業では Core 2 よりも優れていると思われます (ただし、最近は使用していません)。

考えられるもう 1 つの解決策は、CUDA などの言語を使用してグラフィックス カードで処理を行うことです。グラフィックス カードは、非常に高いメモリ帯域幅を持ち、浮動小数点演算を高速に実行できるように調整されています。単純な最適化されていない C 実装と比較して、CUDA コードの開発時間は 5 倍から 20 倍になると予想されます。

于 2009-04-06T20:42:27.460 に答える
1

このような状況に対する本当の答えは、いくつかのアプローチをコード化し、時間を計ることです。あなたが明らかにしたこと。私のような人ができることは、他のアプローチを試してみることを提案することだけです.

例: キャッシュ スラッシング (出力ストリームが同じキャッシュ ラインにマッピングされている) がない場合でも、size = 1<<19 および sizeof(int)=4、32 ビットでサイズ int を書き込んでいる場合、つまり8MB のデータを書き込んでいますが、実際には 8MB を読み込んでから 8MB を書き込んでいます。データが x86 プロセッサの通常の WB (WriteBack) メモリにある場合、行に書き込むには、最初に行の古いコピーを読み取る必要があります。読み取ったデータを破棄することになります。

この不要な RFO 読み取りトラフィックは、(a) WC メモリを使用する (おそらくセットアップが面倒) か、(b) SSE ストリーミング ストア、別名 NT (Non-Temporal) ストアを使用することで排除できます。MOVNT* - MOVNTQ、MOVNTPS など (MO​​VNTDQA ストリーミング ロードもありますが、使用するのは面倒です)。

グーグルで見つけたこの論文が好きですhttp://blogs.fau.de/hager/2008/09/04/a-case-for-the-non-temporal-store/

現在: MOVNT* は WB メモリに適用されますが、少数の書き込み結合バッファを使用して WC メモリのように機能します。実際の数はプロセッサ モデルによって異なります。最初に搭載された Intel チップである P6 (別名 Pentium Pro) には 4 つしかありませんでした。うーん... Bulldozer の 4K WCC (Write Combining Cache) は基本的にhttp://semiaccurate.com/forums/showthread.php?t=6145&page=40ごとに 64 個の書き込み結合バッファーを提供しますが、従来の WC バッファーは 4 つしかありません。しかしhttp://www.intel.com/content/dam/doc/manual/64-ia-32-architectures-optimization-manual.pdfには、一部のプロセスには 6 つの WC バッファーがあり、一部のプロセスには 8 つあると書かれています。いくつかありますが、それほど多くはありません。通常は 64 ではありません。

しかし、ここで試してみることができます:自分自身を組み合わせて書き込みを実装します。

a) 64 個の (#streams) バッファーの単一セットに書き込みます。それぞれのサイズは 64B (キャッシュ ライン サイズ)、または 128 または 256B です。これらのバッファを通常の WB メモリに置きます。通常の店舗でもアクセスできますが、MOVNT* を使用できると便利です。

これらのバッファの 1 つがいっぱいになると、ストリームが実際に移動するはずのメモリ内の場所にバーストとしてコピーします。MOVNT* ストリーミング・ストアの使用。

これにより、最終的に * N バイトが一時バッファーに格納され、L1 キャッシュにヒットします * 64*64 バイトが一時バッファーに読み込まれます * 一時バッファーから N バイトが読み取られ、L1 キャッシュにヒットします。* ストリーミング ストアを介して書き込まれる N バイト - 基本的にメモリに直接書き込まれます。

つまり、N バイトのキャッシュ ヒット読み取り + N バイトのキャッシュ ヒットの書き込み + N バイトのキャッシュ ミス

対 N バイト キャッシュ ミス読み取り + N バイト キャッシュ書き込み読み取り。

N バイトのキャッシュ ミス読み取りを減らすと、余分なオーバーヘッドを補うことができない場合があります。

于 2012-11-06T06:10:09.573 に答える
1

ファイルをメモリにマップするために調査することをお勧めします。このようにして、カーネルがメモリ管理を処理できます。通常、カーネルはページ キャッシュの処理方法を最もよく知っています。これは、アプリケーションを複数のプラットフォームで実行する必要がある場合に特に当てはまります。さまざまな Oses がさまざまな方法でメモリ管理を処理するためです。

ACE ( http://www.cs.wustl.edu/~schmidt/ACE.html ) や Boost ( http://www.boost.org ) のようなフレームワークがあります。プラットフォームに依存しない方法。

于 2009-04-06T20:25:32.040 に答える