Cache的故事

不可逾越的鸿沟

随着集成电路技术的发展, CPU越来越快, 另一方面, DRAM的速度却受限于它本身的工作原理, 我们先简要解释一下这两者的差别. DRAM的存储空间可以看成若干个二维矩阵(若干个bank), 矩阵中的每个元素包含一个晶体管和一个电容, 晶体管充当开关的作用, 功能上相当于读写使能; 电容用来存储一个bit, 当电容的电量大于50%, 就认为是 1 , 否则就认为是 0 . 但是电容是会漏电的, 如果不进行任何操作的话, 电容中的电量就会不断下降, 1 最终会变成 0 , 存储数据就丢失了. 为了避免这种情况, DRAM必须定时刷新, 读出存储单元的每一个bit, 如果表示 1 , 就往里面充电. DRAM每次读操作都会读出二维矩阵中的一行, 由于电容会漏电的特性, 在将一行数据读出之前, 还要对这一行的电容进行预充电, 防止在读出的过程中有的电容电量下降到50%以下而被误认为是 0 .

而CPU的寄存器采用的是SRAM, 是通过一个触发器来存储一个bit, 具体来说就是4-6个晶体管, 只要不断电, SRAM中的数据就不会丢失, 不需要定时刷新, 也不需要预充电, 读写速度随着主频的提升而提升.

由于RISC架构的指令少, 格式规整, 硬件的逻辑不算特别复杂, CPU做出来之后, 芯片上还多出了很多面积. 为了把这些面积利用起来, 架构师们提出了cache的概念, 把剩下的面积用于SRAM, 同时也为了弥补CPU和Memory之前性能的鸿沟. CISC的运气就没那么好了, 指令多, 格式不规整, 硬件逻辑十分复杂, 在芯片上一时间腾不出地方来放cache, 所以你在i386手册上找不到和cache相关的内容. 当CISC架构师们意识到复杂的电路逻辑已经成为了提高性能的瓶颈时, 他们才向RISC取经, 把指令分解成微指令来执行:

                              R[EAX] <- M[var]
addl $1, var        =>        R[EAX] <- R[EAX] + 1
                              M[var] <- R[EAX]

这样就减少了硬件的逻辑, 让微指令的执行流水化的同时, 也可以腾出面积来做cache了, 不过这些都是后话了.

近水楼台先得月

Cache工作方式实际上是局部性原理的应用:

• 如果程序访问了一个内存区间, 那么这个内存区间很有可能在不久的将来会被再次访问, 这就是时间局部性. 例如循环执行一小段代码, 或者是对一个变量进行读写( addl $1, var 需要将 var 变量从内存中读出, 加1之后再写回内存).
• 如果程序访问了一个内存区间, 那么这个内存区间的相邻区间很有可能在不久的将来会被访问, 这就是空间局部性. 例如顺序执行代码, 或者是扫描数组元素.

相应的:

• 为了利用时间局部性, cache将暂时存放从内存读出的数据, 当CPU打算再次访问这些数据的时候, 它不需要去访问内存, 而是直接在cache中读出即可. 就这样把数据一放, 那些循环次数多达成千上万的小循环的执行速度马上提高了成千上万倍.
• 为了利用空间局部性, cache从内存中读数据的时候, 并不是CPU要多少读多少, 而是一次多读点. Cache向内存进行读写的基本单位是cache block(块). 现代的cache设计还会在空闲的时候进行预取(prefetch), 当CPU一直在计算的时候, cache会趁这段时间向内存拿点数据, 将来CPU正好需要的话就不用再花时间拿了.

这听起来很不错, 有了cache, 只要CPU访问cache的时候命中, 就不需要把大量时间花费在访存上面了. 不过为了保证cache的命中率, cache本身也需要处理很多问题, 例如:

• 一个内存区域可以被映射到多少个cache block? 少了容易冲突, 多了电路逻辑和功耗都会上升. 对这个问题的回答划分了不同的cache组织方式, 包括direct-mapped(直接映射), set associative(组相联)和fully associative(全相联).
• 冲突的时候, 需要替换哪一个cache block? 这个问题的回答涉及到替换算法, 最理想的情况是替换那个很长时间都没访问过的cache block, 这就是LRU算法. 但这对硬件实现来说太复杂了, 对于8-way set associative来说, 每一个set中的8个cache block都有 8! = 40320 种可能的访问情况, 编码至少需要16个bit, 译码则需要更大的代价, 电路逻辑和时延都会上升, 因此实际上会采用伪LRU算法, 近似记录cache block的访问情况, 从而降低硬件复杂度. 也有研究表明, 随机替换的效果也不会很差.
• 写cache的时候要不要每次都写回到内存? 这个问题涉及到写策略, write through(写通)策略要求每次cache的写操作都同时更新内存, cache中的数据和内存中的数据总是一致的; write back(写回)策略则等到cache block被替换才更新内存, 就节省了很多内存写操作, 但数据一致性得不到保证, 最新的数据有可能在cache中. 数据一致性在多核架构中是十分重要的, 如果一个核通过访问内存拿到了一个过时的数据, 用它来进行运算得到的结果就是错误的.
• 写缺失的时候要不要在cache中分配一个cache block? 分配就更容易引起冲突, 不分配就没有用到时间局部性.

这些问题并没有完美的回答, 任何一个选择都是tradeoff, 想获得好处势必要付出相应的代价, 计算机就是这样一个公平的世界.

另一个值得考虑的问题是如何降低cache缺失的代价. 一种方法是采用多级的cache结构, 当L1 cache发生缺失时, 就去L2 cache中查找, 只有当L2 cache也发生缺失时, 才去访问内存. L2 cache通常比L1 cache要大, 所以查找所花时间要多一些, 但怎么说也比访问内存要快. 还有一种方法是采用victim cache, 被替换的cache block先临时存放在victim cache中, 等到要访问那个不幸被替换的cache block的时候, 可以从victim cache中找回来. 实验数据表明, 仅仅是一个大小只有4项的victim cache, 对于direct-mapped组织方式的cache有十分明显的性能提升, 有时候可以节省高达90%的访存.

上面叙述的只是CPU cache, 事实上计算机世界到处蕴含着cache的思想. 在你阅读本页面的时候, 本页面的内容已经被存放到网页缓存中了; 使用 printf 并没有及时输出, 是因为每次只输出一个字符需要花很大的代价, 因此程序会将内容先放在输出缓存区, 等到缓冲区满了再输出, 这其实有点write back的影子. 像内存, 磁盘这些相对于CPU来说的"低速"硬件, 都有相应的硬件cache来提高性能. 例如现代的DRAM一般都包含以下两种功能:

1. 每个bank中都有一个行缓存, 读出一行的时候会把数据放到行缓存中, 如果接下来的访存操作的目的数据正好在行缓存中, 就直接对行缓存进行操作, 而不需要再进行预充电.
2. 采用burst(突发读写)技术, 每次读写DRAM的时候不仅读写目的存储单元, 把其相邻的存储单元也一同进行读写, 这样对于一些物理存储连续的操作(例如数组), 一次DRAM操作就可以读写多个存储单元了.

明白cache存在的价值之后, 你就不难理解这些技术的意义了. 可惜的是, DRAM仍旧摆脱不了定时刷新的命运.

在NEMU中实现cache

Cache的工作方式并不复杂(太复杂就不可能用硬件来实现了), 要在NEMU中模拟cache也并非难事. 从cache组织的角度来看, cache由若干cache block构成, 每一个cache block除了包含相应的存储空间之外, 还包括tag和一些标志位, 你可以很容易地使用结构体来表示一个cache的组织. 从操作的角度来看, 我们只需要提供cache的读和写两种操作就可以了.

这有点像面向对象的基本思维方式: 把对象的特性抽象成一种类型. 虽然C语言并不是面向对象的语言, 但我们还是可以借助C语言来模拟面向对象中"封装"的特性:

/* define "methods" (operations) */
int (* op1) (struct Type1 *this, int arg);
void (* op2) (struct Type1 *this, int arg1, char arg2);
/* ... */

} Type1;

/ define an "object" of this "class" / Type1 obj;

/ define methods / int add(Type1 *this, int n) { return this->attr1 + n; }

/ install methods / obj.op1 = add;

/ call methods "op1" / obj.op1(&obj, 123);
</div></div> 函数指针使得同一个类型的不同对象的同一个操作可以有不同的具体实现, 换句话说就是, 把多个不同的函数抽象成统一的接口. 相信你已经在PA2中领教过函数指针的威力了. 采用面向对象的思想, 要定义多个不同的对象会变得十分方便.

关于cache具体如何工作, 课上都已经详细讲过, 这里就不另外叙述了. 一个需要注意的地方是"读写数据跨越cache block的边界", 这时候你需要通过两次读写cache的操作来完成它. 框架代码提供了一个专门用于读写不对齐内存区域的宏 unalign_rw() (在 nemu/include/macro.h 中定义), 使用它可以较方便地处理上述情况. 值得一提的是维基百科中的CPU cache页面, 里面除了课堂上讲过的知识, 还有诸多延伸, 值得仔细琢磨.

cache ADDR