Cache优化

这学期上了一门多核计算的课程,讲到了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比较大。

Loop Fusion

这个的原理也很好理解,比如有如下代码。b[i]分别在一个循环里面读写,这样显然利用cache的优势。如果把下面的循环分成两部分,分别计算 b[i] = a[i] + 1;  c[i] = b[i] * 2; ,那效率显然低下,我会有测试结果。

 Loop Blocking

这是主要用在矩阵里,比如矩阵乘法,不可避免的两个矩阵中有一个不是按行取的,导致缓存性能差。解决方法是按块计算,如下图所示。loopblocking

下面的例子用了比较简单的算法,可以参考。这个性能的提高也是能目测的,见测试。

 Inter-array Padding

这个优化不针对数据的存取方式,而是数据在内存中的分布方式。比如现在有两个数组,都比较小如1024个int。然后可能映射到同一个cache块,导致相互读取的时候不断刷新cache,自然导致性能不好,解决方法是,放置一个padding的数组在这两个数组中间。这个比较难测试,性能优化也不是很突出。

Array Merging

这个比较有意思,也比较难理解。原算法是有两个数组,假设要统计分别相加的和。如下

那么问题在哪?就是A,B都比较小时,这种做法会产生两次cache miss,所以要优化。优化有好几种,比如用一个结构体或者用个二维数组。这测试还是有点麻烦的,因为比较一次miss和两次miss这个时间差太小了,所以要多次。多次的话又要每次清空cache,所以只能动态分配数组。二维数组的代码如下。

Array Transpose

这相当于loop interchange,就是把A[N][M]换成A[M][N]。因此我没有进行测试。

测试结果

我使用perf工具,稍微进行了几个技术的测试,其中有cache miss和miss rate,我从结果来看是miss rate会影响性能,但是直观来说应该是cache miss会影响性能。为了保证结果的真实性,我就放了miss rate的比较结果。当然还有加速比,如下面两张图所示,感觉还是比较符合实际的。

mc speedup

 

除了cache优化外,还有很多优化技术,看来写程序还有很长的路要走啊。但是也不用太在意,因为现在编译器太牛b。gcc -O2 绝对是满足需求的,可以自己测试下,这性能没法比。这从我写的一个很简单的程序就可以看出,但是也应该注意自己的编码习惯。