这学期上了一门多核计算的课程,讲到了Cache优化,虽然很久之前就知道各种各样的优化技术,但自己从来没有试过。趁此机会,做了几个实验。主要参考An Overview of Cache Optimization Techniques and Cache。
Cache的作用就是利用数据局部性原理,先预测性的把数据从内存缓存到Cache。参考wiki,i5的L1-Cache的存取周期只有4 clocks,L2是11 clocks。内存则是近百clocks。性能差异显而易见。所以我们要做的就是如何利用这个特点。文章中介绍了6种方法。
Loop Interchange
这是最简单的一种,而且一般不会写出Cache不友好的代码。原理是计算机内存在存储数组时是按行存的,所以如果按行取效率高,按列取就会傻b。所以正确的代码,应该如下这么写。同时,要获得更好的测试效果,应该让M比较大。
1 2 3 4 5 6 7 8 9 10 11 12 | int a[N][M] = {0}; void perf_test(int sum) { int i, j; for (i=0; i<N; ++i) { for (j=0; j<M; ++j) { sum += a[i][j]; } } return; } |
Loop Fusion
这个的原理也很好理解,比如有如下代码。b[i]分别在一个循环里面读写,这样显然利用cache的优势。如果把下面的循环分成两部分,分别计算 b[i] = a[i] + 1; c[i] = b[i] * 2; ,那效率显然低下,我会有测试结果。
1 2 3 4 5 6 7 8 9 | void perf_test() { int i; for (i=0; i<N; ++i) { b[i] = a[i] + 1; c[i] = b[i] * 2; } return; } |
Loop Blocking
这是主要用在矩阵里,比如矩阵乘法,不可避免的两个矩阵中有一个不是按行取的,导致缓存性能差。解决方法是按块计算,如下图所示。
下面的例子用了比较简单的算法,可以参考。这个性能的提高也是能目测的,见测试。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 | void perf_test() { int i, j, ii, jj; for (i=0; i<N; i+=B) { for (j=0; j<N; j+=B) { for (ii=i; ii<MIN(i+B-1, N); ++ii) { for (jj=j; jj<MIN(j+B-1, N); ++jj) { b[jj][ii] = a[ii][jj] + 1; } } } } return; } |
Inter-array Padding
这个优化不针对数据的存取方式,而是数据在内存中的分布方式。比如现在有两个数组,都比较小如1024个int。然后可能映射到同一个cache块,导致相互读取的时候不断刷新cache,自然导致性能不好,解决方法是,放置一个padding的数组在这两个数组中间。这个比较难测试,性能优化也不是很突出。
1 2 3 | double a[N] = {0}; double pad[800]; double b[N] = {0}; |
Array Merging
这个比较有意思,也比较难理解。原算法是有两个数组,假设要统计分别相加的和。如下
1 2 3 4 5 6 7 8 9 | int perf_test(int *A, int *B, int sum) { int i,j; for (i=0; i<N; ++i) { A[i] += (A[i] + B[i]); } return sum; } |
那么问题在哪?就是A,B都比较小时,这种做法会产生两次cache miss,所以要优化。优化有好几种,比如用一个结构体或者用个二维数组。这测试还是有点麻烦的,因为比较一次miss和两次miss这个时间差太小了,所以要多次。多次的话又要每次清空cache,所以只能动态分配数组。二维数组的代码如下。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 | #include <stdio.h> #include <stdlib.h> #define N 1024 #define ITER 1000000 int perf_test(int (*A)[2], int sum) { int i,j; int *tmp; for (i=0; i<N; ++i) { tmp = A[i]; sum += (tmp[0] + tmp[1]); } return sum; } int main ( int argc, char *argv[] ) { int i; int (*A)[2]; int sum = 0; for (i=0; i<ITER; ++i) { A = malloc(N * sizeof(*A)); sum += perf_test(A, sum); free(A); } printf("%d\n", sum); return EXIT_SUCCESS; } |
Array Transpose
这相当于loop interchange,就是把A[N][M]换成A[M][N]。因此我没有进行测试。
测试结果
我使用perf工具,稍微进行了几个技术的测试,其中有cache miss和miss rate,我从结果来看是miss rate会影响性能,但是直观来说应该是cache miss会影响性能。为了保证结果的真实性,我就放了miss rate的比较结果。当然还有加速比,如下面两张图所示,感觉还是比较符合实际的。
除了cache优化外,还有很多优化技术,看来写程序还有很长的路要走啊。但是也不用太在意,因为现在编译器太牛b。gcc -O2 绝对是满足需求的,可以自己测试下,这性能没法比。这从我写的一个很简单的程序就可以看出,但是也应该注意自己的编码习惯。
近期评论