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

CPU MEM 画曲线

      在编程时突然想到为什么CPU会满负荷,我怎么样才能控制CPU的利用率? 感觉很有意思,我一开始是这么想的,CPU利用率跟运算类型有关,比如INT操作比float操作更费CPU。经过实验,基本没区别,看来跟这个没有关系。然后就应该是空闲时间的原因了。

       还有一个问题是现在CPU都是多线程的,操作系统会自动调度到不同线程上去,所以就算画出来效果也不是很好。还好操作系统有库让我自定义调度到哪个线程或者说那个CPU核。具体操作:

 

      关于sched具体操作,自行man:

  •       man sched.h
  •       man sched_setaffinity
  •       man cpu_set

 

      这个问题比较容易,现在已经可以试着画方波了。

 

cpu1

 

      接下去画了一下sin的,不太标准,有些问题没有解决,代码不贴,直接上图:

cpu4

      内存理论上来说比CPU简单,但是由于内存分配和释放需要一定时间,所以图像不是很准确,主要思想是运用malloc 和 free。实验中发现光malloc系统是没有真正分配内存的,只有memset或者赋值的时候,才会显示真正分配。下面来一张比较搓的图。

mem

“goto” in kernel

     Rules are for the guidance of wise men, and the obedience of fools.

————-   Douglas Bader

     很多教材上都强调不要使用goto,会让程序混乱逻辑不清。我突发奇想测试一下linux内核里有没有goto。方法:

grep goto * -r | wc -l

       在kernel 3.11.1中有110139个记录,我就吓了一跳。难道kernel的维护人员不知道这个常识。于是就搜索,发现早就有人提出过这个问题了。在linux today 一篇文章中就对此进行了讨论。

        其中有一句话让人幡然醒悟,”Rules are for the guidance of wise men, and the obedience of fools.” 规则指导智者,愚人服从规则。我是个愚人。看看上面的解释说:

 “No gotos” is a rule that makes sense in most circumstances. Great for protecting novices from shooting themselves in the foot. But to give another quote,

“The professional knows when to break the rules”. From my photography, I know that accidentally breaking the rules usually produces crap shots – stuff by people I call “snappers”. But deliberately breaking the rules can produce spectacular results.

 

       这个评论者很风趣,经常用俗语。他没有否定不能用goto的说法。但是不是一定不能用,“专业的知道什么时候该打破规则”.就像摄影一样,不小心打破规则就会出烂片,适时故意打破规则可以拍到惊艳的照片。果然我还是too naive.

      那么 什么时候该用goto呢?这个问题就好解决了,因为我已经知道goto是可以用的,而这个问题的由来是linux内核里出现很多goto,而linux内核是最牛的人在维护。那就直接看源码好了。下面的是随便截了一段代码。

 

       可以清晰的看出,goto在c语言中就是用来处理异常的。goto就非常方便,无需一步步退出反而让程序逻辑不清。大概就是这个意思。另外最近看了一点点汇编,发现goto应该是起源于汇编。

      综上,goto可以在处理异常等类似情况下使用,而用来模拟for while就是不应该的,确实会让程序混乱。