高速缓存模拟

Cache 模拟器

这个编程实验需要实现一个简单的cache, 并尝试实现各种替换算法来优化程序的性能. 在代码目录下执行

make

来编译, 生成可执行文件 a.out . 其运行方式如下:

./a.out [-r seed] [trace]

其中 seed 是随机种子, 可以用于确定性回放帮助调试, 缺省时会用系统时间作为种子; tracebz2 压缩格式的访存序列, 缺省时会产生随机访存序列来测试.

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的思想和设计

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 仍旧摆脱不了定时刷新的命运.

数据对齐和存储层次结构

想一想, 为什么编译器为变量分配存储空间的时候一般都会对齐? 访问一个没有对齐的存储空间会经历怎么样的过 程?

关于 cache 具体如何工作, 课上都已经详细讲过, 这里就不另外叙述了. 值得一提的是维基百科中的 CPU cache 页面, 里面除了课堂上讲过的知识, 还有诸多延伸, 值得仔细琢磨.

实现 cache

cache.c 中实现如下函数

// 从cache中读出`addr`地址处的4字节数据
// 若缺失, 需要先从内存中读入数据
uint32_t cache_read(uintptr_t addr);

// 往cache中`addr`地址所属的块写入数据`data`, 写掩码为`wmask`
// 例如当`wmask`为`0xff`时, 只写入低8比特
// 若缺失, 需要从先内存中读入数据
void cache_write(uintptr_t addr, uint32_t data, uint32_t wmask);

// 初始化一个数据大小为`2^total_size_width`B, 关联度为`2^associativity_width`的cache
// 例如`init_cache(14, 2)`将初始化一个16KB, 4路组相联的cache
// 将所有valid bit置为无效即可
void init_cache(int total_size_width, int associativity_width);

另外 cache 的一些特性如下:

  • 块大小为64B(见 common.hBLOCK_SIZE 的定义)
  • 替换算法采用随机方式
  • 写回, 写分配

mem.c 中提供了如下两个函数, cache 缺失/写回的时候需要用到它们:

// 从块号为`block_num`的内存地址中读出一整个cache块大小的内容到`buf`中
void mem_read(uintptr_t block_num, uint8_t *buf);

// 往块号为`block_num`的内存地址中写入一整个cache块大小的内容`buf`
void mem_write(uintptr_t block_num, uint8_t *buf);

如何测试你的cache实现

框架代码提供了一套CPU接口 cpu_read()cpu_write() , 它们会调用你实现的 cache_read()cache_write().

同时框架代码提供了一套 uncache 的接口 cpu_uncache_read()cpu_uncache_write() , 用于直接访问另一个独立的内存. 这样是为了对你的实现进行对比测试, 测试的主要思想是: 从 CPU 端来看, 有无 cache 并不影响读数据的结果.

因此, 框架代码会随机生成一些访存请求, 同时输入到两套 CPU 接口中, 并对比读接口的结果. 若在某一时刻发现读 结果不一致, 就会触发"assertion failed".

另外为了方便调试, 我们允许将随机种子作为参数来运行 cache 程序, 如果使用相同的种子多次运行, 就会产生一样 的随机数序列.


以上是 Lab3 - Cachesim 的所有内容。

results matching ""

    No results matching ""