8

私はこのようなループを持っています

start = __rdtsc();
unsigned long long count = 0;
for(int i = 0; i < N; i++)
    for(int j = 0; j < M; j++)
        count += tab[i][j];
stop = __rdtsc();
time = (stop - start) * 1/3;

データのプリフェッチが効率にどのように影響するかを確認する必要があります。値がカウントされる前に、メモリからキャッシュに値を強制的にプリフェッチする方法は?

4

4 に答える 4

9

GCC のみ:

__builtin_prefetch((const void*)(prefetch_address),0,0);

prefetch_address無効になる可能性があり、segfault は発生しません。と現在の位置の差が小さすぎるprefetch_addressと、効果がないか、速度が低下することさえあります。少なくとも 1k 先に設定してみてください。

于 2013-01-09T21:53:09.617 に答える
7

まず、これは静的配列 (例: ) または動的に割り当てられた配列 (例:およびそれに続くs)tabなどの大きな 2D 配列であると想定します。ここでは、実行時間を短縮するために、一部のデータをキャッシュからプリフェッチします。int tab[1024*1024][1024*1024]int** tabmalloctab

簡単に言えば、2D 配列の単純なリダクションが実行されるコードにプリフェッチを手動で挿入する必要はないと思います。最新の CPU は、必要に応じて利益があれば、自動プリフェッチを行います。

この問題について知っておくべき 2 つの事実:

tab(1)最内ループの内側の空間的局所性をすでに利用しています。tab[i][0](キャッシュ ミスまたはページ フォールトの後) が読み取られると、キャッシュ ライン サイズが 64 バイトであると仮定して、 から のデータがCPUキャッシュに格納されますtab[i][0]。tab[i][15]

(2) ただし、コードが行内をトラバースする場合、つまり に移動する場合tab[i][M-1]、tab[i+1][0]コールド キャッシュ ミスが発生する可能性が高くなります。特にtabが動的に割り当てられた配列で、各行が断片化された方法で割り当てられる可能性がある場合はそうです。ただし、配列が静的に割り当てられている場合、各行はメモリ内で連続して配置されます。

したがって、プリフェッチは、(1) 次の行の最初の項目を読み取り、(2)j + CACHE_LINE_SIZE/sizeof(tab[0][0])事前に読み取る場合にのみ意味があります。

__builtin_prefetch上部ループにプリフェッチ操作 (例: ) を挿入することで、これを行うことができます。ただし、最新のコンパイラは、常にそのようなプリフェッチ命令を発行するとは限りません。本当にそれを行いたい場合は、生成されたバイナリ コードを確認する必要があります。

ただし、先に述べたように、最新の CPU はほとんどの場合プリフェッチを自動的に行い、自動プリフェッチは手動コードよりもパフォーマンスが優れているため、これを行うことはお勧めしません。たとえば、Ivy Bridge プロセッサのような Intel CPU には、L1、L2、または L3 キャッシュへのプリフェッチなど、複数のデータ プリフェッチャーがあります。(ただし、モバイル プロセッサには派手なデータ プリフェッチャーはないと思います)。一部のプリフェッチャーは、隣接するキャッシュ ラインをロードします。

大規模な 2D 配列でより高価な計算を行う場合は、キャッシュに適した代替アルゴリズムが多数あります。注目すべき例は、ブロックされた（タイトルの付いた）行列乗算です。単純な行列乗算では多くのキャッシュ ミスが発生しますが、ブロックされたアルゴリズムでは、キャッシュに適合する小さなサブセットで計算することにより、キャッシュ ミスが大幅に減少します。このような参考文献を参照してください。

于 2013-01-10T01:07:08.133 に答える
4

最も簡単で移植性の高い方法は、単純にキャッシュライン バイトごとにデータを読み取ることです。タブが適切な 2 次元配列であると仮定すると、次のことができます。

char *tptr = (char *)&tab[0][0];
tptr += 64;
char temp;
volatile char keep_temp_alive;
for(int i = 0; i < N; i++)
{
    temp += *tptr;
    tptr += 64;
    for(j = 0; j < M; j++)
        count += tab[i][j];
}
keep_temp_alive = temp;

そんな感じ。ただし、次の場合に依存します。2. J ループは 64 バイトより大きくありません。temp += *tptr; tptr += 64;そうである場合は、ループの先頭にさらにステップを追加することをお勧めします。

keep_temp_aliveafter the loop は、コンパイラが不要な読み込みとして temp を完全に削除するのを防ぐために不可欠です。

残念ながら、組み込みの命令を提案するには汎用コードを書くのが遅すぎます。

于 2013-01-09T21:56:50.517 に答える