キャッシュヒット率の測定

 perfというツールを使ってキャッシュヒット率を測定してみた。
キャッシュの影響なんてたかが知れていると甘くみていたら、痛い目るので要注意。

キャッシュの用語

知らない用語がちらほらあったので、簡単にまとめておく。

L1、L2、L3キャッシュ
Level1、Level2、Level3の略。
それぞれ速度、容量に違いがある。

速度L1 > L2 > L3
容量L1 < L2 < L3

高速なキャッシュほど容量が小さくヒット率は低い。
容量の大きいキャッシュはヒット率は高いが、低速。

というトレードオフがある。

プロセッサは以下の順序で処理実行に必要なデータを探す。
①L1キャッシュにアクセスし、ヒットすれば処理実行。ミスの場合は、L2へ。
②L2キャッシュにアクセスし、ヒットすれば処理実行。ミスの場合は、L3へ。
③L3キャッシュにアクセスし、ヒットすれば処理実行。ミスの場合はメインメモリへ。

L1dキャッシュとL1iキャッシュ
L1dはLevel 1 data cache。
L1iはLevel 1 instruction cache。

data cacheは、データをキャッシュするためのキャッシュ。

instruction cacheはプロセッサによって実行される命令をキャッシュするためのキャッシュ。

命令をキャッシュするとはどういうことか？

ストアドプログラム方式では実行されるプログラムもメモリに格納されているため、プロセッサは実行する命令をメモリから読まなければいけない。
よってプロセッサから見ると命令もある種のデータなのである。

キャッシュサイズを参照

Debian系マシンではlscpuコマンドでキャッシュサイズを確認できる。
L1-L3トータルで3MB以上ある。予想してたよりも容量大きい。

kenjih$ lscpu
Architecture:          i686
CPU 操作モード:   32-bit, 64-bit
Byte Order:            Little Endian
CPU(s):                4
On-line CPU(s) list:   0-3
コアあたりのスレッド数:2
ソケットあたりのコア数:2
Socket(s):             1
ベンダー ID:       GenuineIntel
CPU ファミリー:   6
モデル:             42
ステッピング:    7
CPU MHz:               800.000
BogoMIPS:              4988.44
仮想化:             VT-x
L1d キャッシュ:   32K
L1i キャッシュ:   32K
L2 キャッシュ:    256K
L3 キャッシュ:    3072K

キャッシュヒット率を計測

Linuxのパフォーマンス解析ツールperfを使って、キャッシュヒット率を計測してみた。 例として、以下の２つの方法で行列の掛け算を行ったときのキャッシュヒット率を計測する。

プログラムA (a.cpp)

#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;

const int N = 1024;

mat multiply(const mat &x, const mat &y) {
    int r = x.size();
    int m = y.size();
    int c = y[0].size();

    mat z(r, vec(c));
    for (int i = 0; i < r; i++) {
        for (int j = 0; j < c; j++) {
            for (int k = 0; k < m; k++) {
                z[i][j] += x[i][k] * y[k][j];
            }       
        }
    }

    return z;
}

int main(int argc, char **argv) {
    
    mat x(N, vec(N));
    mat y(N, vec(N));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            x[i][j] = i;
            y[i][j] = j;
        }
    }

    mat z = multiply(x, y);

    long long sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            sum += z[i][j];
        }
    }

    cout << sum << endl;

    return 0;
}

プログラムB (b.cpp)

#include <iostream>
#include <vector>

using namespace std;

typedef vector<int> vec;
typedef vector<vec> mat;

const int N = 1024;

mat multiply(const mat &x, const mat &y) {
    int r = x.size();
    int m = y.size();
    int c = y[0].size();

    mat z(r, vec(c));
    for (int i = 0; i < r; i++) {
        for (int k = 0; k < m; k++) {
            for (int j = 0; j < c; j++) {
                z[i][j] += x[i][k] * y[k][j];
            }       
        }
    }

    return z;
}

int main(int argc, char **argv) {
    
    mat x(N, vec(N));
    mat y(N, vec(N));

    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            x[i][j] = i;
            y[i][j] = j;
        }
    }

    mat z = multiply(x, y);

    long long sum = 0;
    for (int i = 0; i < N; i++) {
        for (int j = 0; j < N; j++) {
            sum += z[i][j];
        }
    }

    cout << sum << endl;

    return 0;
}

プログラムAとプログラムBの違いは、multiply関数のループの部分だけである。
プログラムAはi, j, kの順で、プログラムBはi, k, jの順でループを回す。

一見大した違いは無さそうであるが、キャッシュのヒット率によって大きな違いが生じる。

コンパイルは以下のように行った。

g++ -Wall -O2 a.cpp -std=c++0x -lm -o a

実行してみると、

プログラムA 9.260s

プログラムB 1.184s

となった。

約8倍ほどプログラムBの方が高速。

それぞれのプログラムでキャッシュ参照数、キャッシュミス数などを以下のコマンドで出力してみた。

perf stat -e cycles,instructions,cache-references,cache-misses ./a

結果は以下のとおり。

 プログラムA

 Performance counter stats for './a':

    27,363,421,784 cycles                    #    0.000 GHz                    
    11,880,422,836 instructions              #    0.43  insns per cycle        
        71,384,828 cache-references                                            
        57,242,356 cache-misses              #   80.188 % of all cache refs    

プログラムB

Performance counter stats for './b':

     3,618,482,791 cycles                    #    0.000 GHz                    
     6,495,956,182 instructions              #    1.80  insns per cycle        
         9,516,922 cache-references                                            
         4,136,614 cache-misses              #   43.466 % of all cache refs    

プログラムAでは、プログラムBの約13.8倍のキャッシュミスが発生していた。 つまりメモリアクセスの回数が13.8倍多いということ。 メモリアクセスがボトルネックとなって、1サイクルあたりの命令実行数にも差が生じていることが分かる。