CPU Cache简介

备注：需对CPU有一定理解，建议阅读CPU简介

为什么需要CPUCache

真空中光速为299,792,458米/秒，目前，Intel的i7频率可以达到4GHz，简单换算一下，可以得出结论：光（电流）在一个Cycle内移动的距离约为0.075米。显然，目前的内存条的芯片（反正两面。约为3.75cm）大大超过了这个长度，换句话说，理论上，在一个Cycle内内存条上总有一个位置是我们无法触摸。

实际上，早期的计算机结构相对简单，就是不同组件构成的一个体系，包括CPU，内存条，硬盘和网卡等，各组件之间的性能相对平衡。后来，随着各个组件的不断发展，各自形成了一个相对独立的子体系，众所周知的摩尔定律，就是描述CPU性能的迅猛发展。不同组件之间的性能差异日益显著。

巧妇难为无米之炊，内存不给力，再快的CPU也无用武之地。难道真的没有办法提高内存的性能吗？答案是有。

内存可以分为两大类：SRAM（静态）和DRAM（动态），因为如下是两者的电路对比：

前者性能高，状态稳定，直接访问M1~M4晶体管，获取当前的内存状态（0或1），而后者将内存状态保存在C（电容器），这个设计有三个问题，第一是访问容器C会导致放电，因此，需要不停的刷新充电，这个过程中无法访问该内存存放的数据，同时需要使用放大器才能区分状态（0或1），每次读操作后需要重新充电，总之，这导致了动态内存的设计下，无法直接获取内存状态。

原则上，我也是看不懂上图的，但直觉告诉我，前者比后者复杂的多。俗话说“人至贱则无敌”，最终，出于成本的考虑，更便宜的动态内存成为主流。

假设你是一个图书馆的管理员，配有一张迷你办公桌。每次有人借书，你会检查办公桌上是否有这本书，如果有就直接给借书人；如果没有，你就需要去书库中找到这本书，再给借书人。很明显，前者几乎不会花费时间，相当于读取寄存器数据，后者就要花不少时间，相对于读取内存数据。

如果是三十年前，那这个场景不会有什么变化，但后来，我们可以做一个小书架，放在书桌旁，能装几本书。缺点是这个书架得用黄花梨做。随着工艺的提高，我们可以做一个三层小书架。这样，我们可以“预测”那些最受欢迎的书，放到书架上，减少（耗时的）书库取书的次数。这就是用静态内存来做CPU Cache的思路。

如何设计Cache

缓存机制，理论上缓解了CPU和内存之间性能差距日益增大这个难题。但实际中，缓存数据是否是当前CPU所需要的数据，这就是一个很严肃的问题了。

首先，一级缓存只有32K，而通常内存条则是8G，这就是一个抽屉问题：8*1024个球放到32个抽屉里，如何提高抽屉的利用率，避免过劳或过闲；如何设置球的优先级，是上一次访问的数据优先级高，还是访问次数最多的数据优先级高，或者随机给一个优先级，这是一个Replace policy的设计。

N-way associative

N-way associative具体算法在之前的《CPU简介》中已经谈到，这里默认大家都了解，不讨论具体该细节。

如上图，吃饭时间到了，狗狗会遍历所有饭盒，看是否有空位，如果有，则占有该饭盒；如果没有，则挑一个好欺负的狗狗，霸占它的饭盒。这和数据存储是一个思路：假设有8个抽屉，现在需要放一个球，会依次打开抽屉看是否有空抽屉，这称为full associative。好处是能找到一个抽屉来存放球（数据），缺点是需要遍历所有抽屉，当抽屉数目过长时，复杂度是O(n)，线性增长。

为了优化遍历时间，自然想到用Hash Table。基于上面抽屉的场景，我们现在对8个抽屉编号，所有的球也都有一个唯一的编号（内存地址），然后用编号除以8，根据余数找到对应的抽屉，如果抽屉里面有球，则替换。这样，找到抽屉的时间为O(1)，但缺点是容易出现Hash冲突，导致效率下降。这称为direct mapping。

full associative和direct mapping各有利弊，于是两者结合，也就是目前采用的N-way associative的设计方案。如上图，6195 的二进制是 00...0110000 011 0011。这样，在8(2^3)sets中，取绿色的三位，存放在索引3；在4(2^2)sets中，取绿色的二位，存放在索引3中，里面有两个“抽屉”（2-way）可供选择；在2(2^1)sets中，取绿色的后一位，存放在索引1中，里面有四个“抽屉”（4-way）可供选择。

不难发现，full associative和direct mapping是一维的行或列的设计方式，1-way就相当于direct mapping，8-way就是full associative。N-way则是一种行和列的二维设计，提高了灵活性，在遍历和减少Hash冲突之间的互相平衡。

如上的公式，我们可以通过C++ template设计一个N-way associative，实现一个缓存策略的模拟。

template <intnCacheSize, intnWayNum, intnBlockSize>
class associativity
{}

Replace policy

有了数据存储方案，如果没有空的区块时，应该替换哪一个区块呢？这里面也涉及到一个算法：每次有新的数据增加到Cache区块时，需要更新每一个区块的优先级，确定一个当前最不重要的数据，以便下次需要时替换。

Belady
最常见的替换算法，FIFO先进先出的策略。每次数据加入队列时，如果该数据已经存在，仍然认为是旧数据
Random
顾名思义，抽死签，随机找一个block替换
LRU:Least recently used
类似FIFO，每次数据加入队列时，如果该数据已经存在，认为是新数据
LFU：Least-frequently used
引用计数，引用次数最少的将被替换掉

当然还有很多替换策略，如上是我自己写的Cache中加入的替换策略，发现并没有明显的好坏之分。

三级缓存

我们的设计中，有三级缓存C1~C3的层级关系，对应到代码中，三者的实现原理都一样，都可以通过templateclass实现，无非是N-way和CacheSize的不同而已。但我们还需要一个CacheManager来管理三个缓存以及内存之间的关系。

首先，写数据时，是否需要写入到内存，还是暂时保存在缓存中，离开缓存时再写入内存；三级缓存中，是否允许存在重复数据；当数据从高一级的缓存中替换出来时，如何加入到下一级缓存中。

最后，需要增加一个计数能力，统计一下缓存命中率。下图是我设计的一个三级缓存模拟器，绿色是一级缓存命中，蓝色是二级，橙色是三级，红色是未命中。

Locality

通过上面两部分，我们能了解为何设计CPU Cache以及实现思路，在程序设计时，这些知识有什么用处呢？如何能让我们的编码具备较高的缓存命中率呢？毕竟，有了先进的武器，如果不能熟练掌握，也是无济于事。

Access data sequentially

for (int i = 0; i <arr.Length; i += K) arr[i] *= 3;

如上，随着K增加，K=16是一个临界点，说明该CPUCache中，一个Block（Cache Line）存储了16 * sizeof(int) = 64字节，基于缓存的考虑，不难理解，因为CacheLine中的数据连续，因此缓存命中率较高，读写速度很快，因此，在这个临界点内，K的变化，尽管会减少操作指令，但不会带来性能的提升。

记得当年刚毕业时做的面试题，其中一个是遍历二维数组A[M][N]，for(M) { for(N)}和for(N){ for(M)}之间有什么区别。前者行优先，访问的内存依次连续，而后者是列优先，内存不连续。

通常一个class会封装多个组件，比如一个Entity，里面包含AI模块，Physics物理模拟模块以及Render模块，通常，我们习惯这样写代码来遍历多个Entity Array：

while (!gameOver)

{

    // Process AI.

    for (int i = 0;i < numEntities; i++)

    {

        entities[i]->ai()->update();

    }

    // Updatephysics.

    for (int i = 0;i < numEntities; i++)

    {

        entities[i]->physics()->update();

    }

    // Draw toscreen.

    for (int i = 0;i < numEntities; i++)

    {

        entities[i]->render()->render();

    }

    // Other gameloop machinery for timing...
}

看上去逻辑优雅，这也是OOP的设计核心：状态的管理。但从Cache的角度而言则非常糟糕，数据角度上，内存是跳跃的。

假如我们改造一下代码，将Entity类拆分成三个组件对应的类，然后依次遍历具体的方法：

AIComponent* aiComponents =

new AIComponent[MAX_ENTITIES];

PhysicsComponent* physicsComponents =

new PhysicsComponent[MAX_ENTITIES];

RenderComponent* renderComponents =

new RenderComponent[MAX_ENTITIES];

while (!gameOver)

{

    // Process AI.

    for (int i = 0;i < numEntities; i++)

    {

        aiComponents[i].update();

    }

    // Updatephysics.

    for (int i = 0;i < numEntities; i++)

    {

        physicsComponents[i].update();

    }

    // Draw toscreen.

    for (int i = 0;i < numEntities; i++)

    {

        renderComponents[i].render();

    }

    // Other gameloop machinery for timing...

}

此时，数据访问上，内存是连续的，性能就会有明显的提升，测试中性能提升了50倍。

large data structures

我们在看这段有意思的代码：

public longUpdate(byte[] arr, int K)

{

    // Number of iterations – arbitrary

    const int rep =1024*1024; 

    int p = 0;

    for (int i = 0;i < rep; i++)

    {

        arr[p]++;

        p += K;

        if (p >=arr.Length) p = 0;

    }

}

如下图，依次增大array length和K-Step，白色表示时间较短，蓝色表示时间久，会发现，当K为2的N次方时，会有一根突出的蓝线。原因是K间隔下的内存地址，正好导致了Hash冲突，引起了内存和缓存之间的频繁交替，因此性能会下降。