9

キャッシュミス率が高いサンプルプログラムを考え出そうとしています。次のように、列ごとに行列にアクセスできると思いました。

#include <stdlib.h>

int main(void)
{
    int i, j, k;

    int w = 1000;
    int h = 1000;

    int **block = malloc(w * sizeof(int*));
    for (i = 0; i < w; i++) {
        block[i] = malloc(h * sizeof(int));
    }

    for (k = 0; k < 10; k++) {
        for (i = 0; i < w; i++) {
            for (j = 0; j < h; j++) {
                block[j][i] = 0;
            }
        }
    }

    return 0;
}

これを-O0フラグでコンパイルし、perf stat -r 5 -B -e cache-references,cache-misses ./a.outそれを使用して実行すると、次のようになります。

 Performance counter stats for './a.out' (5 runs):

    715,463 cache-references                                      ( +-  0.42% )
    527,634 cache-misses          #   73.747 % of all cache refs  ( +-  2.53% )

0.112001160 seconds time elapsed                                  ( +-  1.58% )

これは私の目的には十分です。ただし、先に進んでマトリックスのサイズを変更すると、次のように2000x2000なります。

 Performance counter stats for './a.out' (5 runs):

  6,364,995 cache-references                                      ( +-  2.32% )
  2,534,989 cache-misses          #   39.827 % of all cache refs  ( +-  0.02% )

0.461104903 seconds time elapsed                                  ( +-  0.92% )

さらに大きくすると、次のように3000x3000なります。

 Performance counter stats for './a.out' (5 runs):

 59,204,028 cache-references                                      ( +-  1.36% )
  5,662,629 cache-misses          #    9.565 % of all cache refs  ( +-  0.11% )

1.116573625 seconds time elapsed                                  ( +-  0.32% )

サイズが大きくなるにつれてキャッシュミス率が高くなると予想されるため、これは奇妙です。可能な限りプラットフォームに依存しないものが必要です。コンピュータ アーキテクチャ クラスはずっと前のことなので、どんな洞察も歓迎されます..

ノート

比較的プラットフォームに依存しないものが必要だと言いましたが、それでもこれらは私の仕様です:

  • インテル® コア™ i5-2467M
  • 4 GiB RAM
  • 64 ビット Ubuntu 12.04
4

2 に答える 2

9

最新のCPUでは自動プリフェッチに注意してください。ストライドアクセスを検出できることがよくあります。おそらく、ランダムアクセスパターンを試してください。例：

int main(void)
{
    int i;

    int n = 1000 * 1000;

    int *block = malloc(n * sizeof(int));

    for (i = 0; i < n / 10; i++) {
         int ri = rand() % n;
         block[ri] = 0;
    }

    return 0;
}
于 2013-01-31T21:44:41.007 に答える
2

これらのプログラムを比較したり、実際に何かを保証したりできるかどうかは完全にはわかりません。これは、OS が個々のメモリ チャンクをどのように割り当てているかに依存するためです。

少なくともすべてのメモリを単一のブロックとして割り当て、そのブロックにインデックスを付けてすべての配列 (int*およびint) を取得する必要があります。そうすれば、一貫した出発点が得られます。毎回再コンパイルする代わりに、配列サイズを引数として渡すことができます。

また、必要以上のメモリを割り当て、各行 (または列、記述した方法) を配置して、マトリックスの 1 つの行 (列) のみがキャッシュに読み込まれるように微調整することもできます。一度。 つまり、キャッシュのサイズを調べて、各チャンクを少なくともそのバイト数離して配置します。

free終了する前に、実際に記憶する必要があることに注意してください。

他の人がすでに指摘しているように、アクセス パターンをランダム化することは良い考えです。

于 2013-01-31T22:00:06.110 に答える