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);
}