cache和代码优化(3)

5. cache优化
    从统计规律中得到的结论为：相联度越高，冲突失效就越小；义务失效和容量失效不受相联度的影响；义务失效不受Cache容量的影响；容量失效随着容量的增加而减少；即大小为N的直接映射Cache的失效率约等于大小为N/2的两路组相联的Cache失效率。
    为了提高性能，需要降低失效率和减少失效开销。减小失效率可以采用的方法有增大块大小，增大Cache容量，提高相联度，采用预取技术软件优化，。增大Cache容量，对冲突和容量失效的减少有利。通过预取可帮助减少义务失效，但必须小心不要把你需要的东西换出去，同时需要预测比较准确（对数据较困难，对指令相对容易）；增大块，可以减缓义务失效，但可能会增加冲突失效（因为在容量不变的情况下，块的数目减少了）。
    从统计数据可得到如下结论：对于给定Cache容量，块大小增加时，失效率开始是下降，但后来反而上升；Cache容量越大，使失效率达到最低的块大小就越大；块大小增加，可使义务失效减少（空间局部性原理），使冲突失效增加（因为Cache中块数量减少），失效开销增大（上下层间移动，数据传输时间变大）；设计块大小的原则，不能仅看失效率，必须使平均访存时间最小。
    在Cache和Memory之间增加一个小的全相联Cache （Victim cache）存放由于失效而被丢弃的那些块。通常Cache为直接映象，因而冲突失效率较大，Victim cache采用全相联而失效率较低，失效时，首先检查Victim cache是否有该块，如果有就将该块与Cache中相应块比较。含1到5项的Victim cache对减少失效很有效，尤其是对于那些小型的直接映射数据Cache。测试结果，项为4的Victim Cache能使4KB的直接映射数据Cache冲突失效减少20%--90%。
    预取包括软件和硬件预取。使用硬件预取的CPU在执行一块代码时，硬件预取下一块代码，因为CPU可能马上就要执行这块代码，这样可以降低或消除Cache的访问失效。 当块中有控制指令时，预取失效。预取的指令可以放在Icache中，也可以放在其他地方（存取速度比Memory块的地方）如指令流缓冲器（IBS）。研究结果：块大小为16字节，容量为4KB的直接映象Cache，1个块的IBS，可以捕获15％－25％的失效，4个块可捕获 50％的失效，16块可捕获72％的失效。预取数据采用同样的方法，1个块的IBS，可以捕获25％的失效，4个块可捕获 43％的失效。要注意预取是利用存储器的空闲带宽，而不是与正常的存储器操作竞争。

6. 代码优化
    如果程序会非常频繁的使用n段空间的数据，而这n段空间的地址的低位又非常接近，那么它们就会使用相同的line。如果n大于cache的路数，那么cache的没有命中也会非常频繁，因为每一段空间的数据会不停的将cache内的其他空间的数据挤出去。可以通过优化来改善数据的空间局部性和时间局部性来减少数据失效，基本方法为：数据合并；内外循环交换，循环融合；分块；减小程序。

    数组合并，优化空间局部性
   /* Before: 2 sequential arrays */
    int val[SIZE];
    int key[SIZE];
    /* After: 1 array of stuctures */
    struct merge {
        int val;
        int key;
    };
    struct merge merged_array[SIZE];
    Reducing conflicts between val & key;
    val和key被同时或相近的访问的概率很大，将他们组织在一起，同时缓存在在数据cache中，提高cache命中率

    内外循环交换，优化空间局部性
    /* Before */
    for (k = 0; k < 100; k = k+1)
       for (j = 0; j < 100; j = j+1)
          for (i = 0; i < 5000; i = i+1)
             x[i][j] = 2 * x[i][j];
    /* After */
    for (k = 0; k < 100; k = k+1)
       for (i = 0; i < 5000; i = i+1)
          for (j = 0; j < 100; j = j+1)
             x[i][j] = 2 * x[i][j];
    注意i和j是数组的不同维的下标，改变循环的秩序，使得相近的数据更多的可能被cache在一起，提高cache命中率

    分块
    /* Before */
    for (i = 0; i < N; i = i+1)
       for (j = 0; j < N; j = j+1){
          r = 0;
          for (k = 0; k < N; k = k+1){
             r = r + y[i][k]*z[k][j];
          }
          x[i][j] = r;
       }
    在两个内部循环中，数组Z的NXN元素都被读取，数组Y的一行N个元素被读取N次，数组X的一行N个元素被写入，整个循环一共访问2N3 <!--[if !vml]--><!--[endif]-->+N2<!--[endif]-->次。由于数据量很大，会造成冲突失效，每次都要访问内存。
    /* After */
    for (jj = 0; jj < N; jj = jj+B)
       for (kk = 0; kk < N; kk = kk+B)
          for (i = 0; i < N; i = i+1)
             for (j = jj; j < min(jj+B-1,N); j = j+1){
                r = 0;
                for (k = kk; k < min(kk+B-1,N); k = k+1){
                   r = r + y[i][k]*z[k][j];
                }
                x[i][j] = x[i][j] + r;
             }
    B称为分块因子Blocking Factor，不命中数降到 N <!--[if !vml]--><!--[endif]-->3/B+ 2N2 <!--[if !vml]--><!--[endif]-->。

    协助分支预测
    提高代码段及执行的cache命中率。具体参见另一篇文章《likely/unlikely macros》：http://blog.chinaunix.net/u1/45969/showart.php?id=422311。


总之，在需要程序性能的地方，充分利用代码和数据的时间以及空间局部性，提高cache的利用率和命中率。（说起来容易做起来难，霍霍）

责任编辑 webmaster

相关链接

cache和代码优化(3)

cache和代码优化(2)

cache和代码优化(1)

代码优化之Base64编码函数

cache调度算法LRU模拟程序

从Cache学习卓越编程

Linux内核中内存cache的实现

应用OSCache提升J2EE系统运行...