cache lineの衝突による速度の低下を確認した
概要
密行列積を計算する単純なコードを書き、行列の大きさが$2$羃のときとそうでないときで速度比較をした。 $2$羃のとき、明らかな速度の低下が見られた。
結果
$ clang++ -std=c++14 -O2 a.cpp -DN=1030
$ ./a.out
3.212000 msec
$ clang++ -std=c++14 -O2 a.cpp -DN=1024
$ ./a.out
12.461000 msec
備考として、密行列積のloop interchangeをすると速度差は消える。 少ない数のcache lineしか使わないようになるため、衝突が発生しないのであろう。
implementation
#include <cstdio>
#include <random>
#include <chrono>
#define repeat(i,n) for (int i = 0; (i) < int(n); ++(i))
using namespace std;
double a[N][N];
double b[N][N];
double c[N][N];
void dgemm() {
repeat (y,N) {
repeat (x,N) {
repeat (z,N) {
c[y][x] += a[y][z] * b[z][x];
}
}
}
}
int main() {
// init matrices
random_device device;
default_random_engine gen(device());
uniform_real_distribution<double> dist;
repeat (y,N) repeat (x,N) a[y][x] = dist(gen);
repeat (y,N) repeat (x,N) b[y][x] = dist(gen);
// flush cache
constexpr int dirty = 128 * 1024 * 1024;
void * volatile p = malloc(dirty);
repeat (i, dirty) ((char *)p)[i] = gen() % 256;
free(p);
// run
chrono::high_resolution_clock::time_point clock_begin = chrono::high_resolution_clock::now();
dgemm();
chrono::high_resolution_clock::time_point clock_end = chrono::high_resolution_clock::now();
// output
printf("%lf msec\n", chrono::duration_cast<chrono::milliseconds>(clock_end - clock_begin).count() / 1000.0);
return 0;
}