キャッシュむずい
うーん…
#include <stdio.h> #include <stdlib.h> #include <emmintrin.h> static unsigned int rdtsc(void) { unsigned int lo,hi; asm volatile ("rdtsc" :"=a"(lo), "=d"(hi)); return lo; } #define W 256 #define H 4096 void copy1(__m128i *src, __m128i *dest) { int i,j; for (i=0; i<H; i++) { for (j=0; j<W; j++) { dest[(i+0)*W+j] = src[(i+0)*W+j]; } } } void copy2(__m128i *src, __m128i *dest) { int i,j; for (i=0; i<H; i+=2) { for (j=0; j<W; j++) { __m128i a,b; a = src[(i+0)*W+j]; b = src[(i+1)*W+j]; dest[(i+0)*W+j] = a; dest[(i+1)*W+j] = b; } } } void copy4(__m128i *src, __m128i *dest) { int i,j; __m128i a,b,c,d; for (i=0; i<H; i+=4) { for (j=0; j<W; j++) { a = src[(i+0)*W+j]; b = src[(i+1)*W+j]; c = src[(i+2)*W+j]; d = src[(i+3)*W+j]; dest[(i+0)*W+j] = a; dest[(i+1)*W+j] = b; dest[(i+2)*W+j] = c; dest[(i+3)*W+j] = d; } } } void copy16(__m128i *src, __m128i *dest) { int i,j; for (i=0; i<H; i+=16) { for (j=0; j<W; j++) { dest[(i+0)*W+j] = src[(i+0)*W+j]; dest[(i+1)*W+j] = src[(i+1)*W+j]; dest[(i+2)*W+j] = src[(i+2)*W+j]; dest[(i+3)*W+j] = src[(i+3)*W+j]; dest[(i+4)*W+j] = src[(i+4)*W+j]; dest[(i+5)*W+j] = src[(i+5)*W+j]; dest[(i+6)*W+j] = src[(i+6)*W+j]; dest[(i+7)*W+j] = src[(i+7)*W+j]; dest[(i+8)*W+j] = src[(i+8)*W+j]; dest[(i+9)*W+j] = src[(i+9)*W+j]; dest[(i+10)*W+j] = src[(i+10)*W+j]; dest[(i+11)*W+j] = src[(i+11)*W+j]; dest[(i+12)*W+j] = src[(i+12)*W+j]; dest[(i+13)*W+j] = src[(i+13)*W+j]; dest[(i+14)*W+j] = src[(i+14)*W+j]; dest[(i+15)*W+j] = src[(i+15)*W+j]; } } } void copyN(__m128i *src, __m128i *dest, int n) { int i,j,k; for (i=0; i<H; i+=n) { for (j=0; j<W; j++) { for (k=0; k<n; k++) { dest[(i+k)*W+j] = src[(i+k)*W+j]; } } } } int main() { unsigned int b[7],e[7]; void *p; __m128i *src; __m128i *dest; posix_memalign(&p, 16, 4096*8192); src = p; posix_memalign(&p, 16, 4096*8192); dest = p; copy1(dest, src); copy2(dest, src); copy4(dest, src); copy16(dest, src); copyN(dest, src,64); b[0] = rdtsc(); copy1(dest, src); copy1(dest, src); copy1(dest, src); copy1(dest, src); e[0] = rdtsc(); b[1] = rdtsc(); copy2(dest, src); copy2(dest, src); copy2(dest, src); copy2(dest, src); e[1] = rdtsc(); b[2] = rdtsc(); copy4(dest, src); copy4(dest, src); copy4(dest, src); copy4(dest, src); e[2] = rdtsc(); b[3] = rdtsc(); copy16(dest, src); copy16(dest, src); copy16(dest, src); copy16(dest, src); e[3] = rdtsc(); b[4] = rdtsc(); copyN(dest, src, 64); copyN(dest, src, 64); copyN(dest, src, 64); copyN(dest, src, 64); e[4] = rdtsc(); b[5] = rdtsc(); copyN(dest, src, 128); copyN(dest, src, 128); copyN(dest, src, 128); copyN(dest, src, 128); e[5] = rdtsc(); b[6] = rdtsc(); copyN(dest, src, 512); copyN(dest, src, 512); copyN(dest, src, 512); copyN(dest, src, 512); e[6] = rdtsc(); printf(" 1:%d\n",e[0]-b[0]); printf(" 2:%d\n",e[1]-b[1]); printf(" 4:%d\n",e[2]-b[2]); printf(" 16:%d\n",e[3]-b[3]); printf(" 64:%d\n",e[4]-b[4]); printf(" 128:%d\n",e[5]-b[5]); printf("1024:%d\n",e[6]-b[6]); return 0; }
これの結果が、
1:95653020 2:96958104 4:99469308 16:126624288 64:232365708 128:297237984 1024:441126636
こんな感じであるが、さて、これ、それぞれの違いはどこから来るでしょう？という問題で、多分、
1:95653020 2:96958104 /* ?? */ 4:99469308 /* ?? */ 16:126624288 /* プリフェッチが効かなくなる */ 64:232365708 /* L1Dの連想度的によくない */ 128:297237984 /* ?? */ 1024:441126636 /* L2の連想度的によくない */
なのかなー、という感じであるが、いまいち確証が持てない。
あと布団から出るのめんどくさくて、メインマシンがノートPCになりつつある昨今であり、Core2でも試すべきだが試していない。
x86のキャッシュは、
- キャッシュライン64byte
- L1D 8way 6〜8ライン
- L2 8way 数千ライン
- プリフェッチ8本
などとパラメータがたくさんあるのに加えて、ソフトウェアでプリフェッチ入れるとその命令自体が重くて遅くなったりするなど、何が最適かよーわからんというのがあって、さて、この問題を解くのは人間がやるべきか、自動でやるべきか？特に結論は無い。
