コードのキャッシュサイズへの影響

Question

キャッシュサイズのコードへの影響を調べたいと思います。大規模アレイで動作するプログラムでは、アレイがキャッシュに収まる場合には大幅な高速化が可能です。

どうすればこのことを確認できますか？

私はこのCプログラムを実行しようとした：場合、プログラムが速く実行する場合

確認するために、（製品を保ち、ひいては定数命令の数）ARRAYSIZE及び反復の値をとる

#define L1_CACHE_SIZE  32  // Kbytes 8192 integers 
#define L2_CACHE_SIZE  256  // Kbytes 65536 integers 
#define L3_CACHE_SIZE  4096 // Kbytes 

#define ARRAYSIZE 32000 
#define ITERATIONS 250 

int arr[ARRAYSIZE]; 

/*************** TIME MEASSUREMENTS ***************/ 

double microsecs() { 
    struct timeval t; 
    if (gettimeofday(&t, NULL) < 0) 
    return 0.0; 
    return (t.tv_usec + t.tv_sec * 1000000.0);  
} 

void init_array() { 
    int i; 
    for (i = 0; i < ARRAYSIZE; i++) { 
     arr[i] = (rand() % 100); 
    } 
} 

int operation() { 
    int i, j; 
    int sum = 0; 
    for (j = 0; j < ITERATIONS; j++) { 
     for (i = 0; i < ARRAYSIZE; i++) { 
      sum =+ arr[i]; 
     } 
    } 

    return sum; 
} 

void main() { 

    init_array(); 

    double t1 = microsecs(); 
    int result = operation(); 
    double t2 = microsecs(); 

    double t = t2 - t1; 

    printf("CPU time %f milliseconds\n", t/1000); 
    printf("Result: %d\n", result);  
} 

を配列はキャッシュに収まるが、私はいつも同じCPU時間を得る。

私は間違っていると誰も言うことができますか？

Answer 1

コードに入力ミスがあります。 = +の代わりに+ =。

Answer 2

[未初期化]セクションにリンクされています。このセクションの変数のデフォルト値はゼロです。このセクションのすべてのページは、最初にzero pageへのR/Oマップされています。これはLinux/Unix中心ですが、おそらく最新のOSにも当てはまります

したがって、配列のサイズに関係なく、キャッシュされる1ページからフェッチするだけなので、同じ結果が得られます。

テストを行う前に、arrのすべてに何かを書き込むことによって、「ゼロページマッピング」を解除する必要があります。つまり、最初にmemsetのようなことをしてください。これにより、OSはCOW（コピーオンライト）メカニズムを使用してarrの線形ページマッピングを作成します。

Answer 3

あなたが本当にやりたいことは、「記憶の山」を構築することです。メモリ山は、メモリアクセスがプログラムのパフォーマンスに与える影響を視覚化するのに役立ちます。具体的には、読み取りスループットと空間的局所性および時間的局所性を測定する。良好な空間的局所性は、連続したメモリアクセスがお互いに近接していることを意味し、良好な時間的局所性は、特定のメモリ位置が短いプログラム時間内に複数回アクセスされることを意味する。ここには、キャッシュパフォーマンスとメモリ山を簡潔に記述したa linkがあります。そのリンクに記載されている教科書の第3版は、メモリとキャッシュの性能について学ぶための非常に良いリファレンスです。具体的には第6章です。 （実際、私は現在、私はこの質問に答えるように、参照としてそのセクションを使用しています）

別linkは、私がここにコピーしているあなたはキャッシュのパフォーマンスを測定するために使用できるテスト関数、を示しています。

void test(int elems, int stride) 
{ 
    int i, result = 0; 
    volatile int sink; 
    for (i = 0; i < elems; i+=stride) 
     result += data[i]; 
    sink = result; 
} 

を

ストライドは時間的局所性です - メモリアクセスがどのくらい離れているか。 考えられるのは、この関数が実行にかかったサイクル数を見積もることです。スループットを得るには、（size/stride）/（cycles/MHz）を使用します。sizeは配列のバイト数、cyclesはこの関数の結果、MHzはプロセッサのクロック速度です。キャッシュを "ウォームアップ"するための測定を行う前に、これを一度呼び出すことをお勧めします。次に、ループを実行して測定を行います。

私はGitHub repositoryを見つけました。自分のマシンに3Dメモリマウンテンを構築することができました。私はあなたが異なるプロセッサを持つ複数のマシンでそれを試し、違いを比較することをお勧めします。