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 绝对是满足需求的,可以自己测试下,这性能没法比。这从我写的一个很简单的程序就可以看出,但是也应该注意自己的编码习惯。

拆机清灰

     为了跑cudaminer,显卡温度直线上升,最高96度,这绝对受不了啊。关键是,温度一高,连带CPU也受影响。linux有个叫kworker的进程就会占用很高的CPU使用率。我觉得可能在调度吧。所以本来跑cudaminer是不影响电脑正常使用的,可现在会稍微有点影响。

     我觉得,做为一个计算机专业的,就应该学会拆电脑。反正已经过了保修期,坏了就修。而且让别人清不但要收钱,而且自己还不放心,漏我一个螺丝,或者没清干净都有可能。所以还是自己动手。

     准备工具:牙刷,起子,吹风机。起子是关键,因为螺丝会一不小心拧花,拧花了可以用502胶水先粘住起子和螺丝,再转。或者直接用老虎钳。

IMG_20140319_142526

     中间过程:由于拆机比较仓促,没有记下中间过程。要注意的是,asus的键盘是可以直接拆卸的。键盘上的4个扣子按一下,就可以拿出来了。然后一个个螺丝搞下来,小心丢失。

     最终结果: 用吹风机往外吹,然后用牙刷刷刷通风口,我就搞到这个地步。其实风扇上的灰不是很多,关键是通风口里的灰,感觉大部分是用牙刷刷掉的。完成之后,感觉吹出来的风都是凉的。跑起cudaminer也不要紧。GPU温度只有67度,下降30%。看来以后要定期清灰。

IMG_20140317_182735