每个程序员都应该了解的内存知识--自翻

摘要:

随着cpu核心变得越来越快越来越多, 访存限制了程序运行速度. 硬件开发者开始研究更精密的内存控制和加速技术(比如 cache), 但是这些没有软件开发者的协调是没法发挥到极致的. 但不幸的是, 大多数软件开发者都不了解内存的结构和消耗. 这篇文章讲述了在现代商品硬件上内存系统的结构, 阐明了为什么 cache 被发明出来, 他们是怎么工作的, 和程序应该怎么使用内存才能达到商品级需求

斜体是自己加的注释, ()里的英文是翻译不明确的地方

希望高中英语老师饶我一命, 翻译过程中觉得自己的水平实在有限

原文下载链接: https://pan.baidu.com/s/1NL2LkExFEFDpl8Sh7xBjpQ

密码: lshc

--来自百度网盘超级会员V5的分享

1 简介

早期电脑的结构很简单, cpu, memory, 外存(mass storage 应该不是特指外存), 网口(/network interface?/), 都一起发展, 因此他们的性能很均衡, 比如 memory 和网络在提供数据上没有 cpu 快.

当计算机的基本结构稳定下来而且硬件开发者准注意优化单个的子系统时, 情况改变了. 一些组件的性能落后并成为了瓶颈. 特别是对于外存和memory系统, 由于经济原因比其他组件发展的慢得多

外存的速度问题主要通过软件来解决: 操作系统把最经常使用(或者将要被使用)的数据存储在主存中, 可以做到比访问硬盘快几个数量级, 存储设备加上了高速缓存而且操作系统不需要做出太大改变. 在这篇文章中我们会研究外存软件组织的更多细节.

不像存储系统, 解决主存的瓶颈问题是十分困难的并且几乎所有的方案都要求改变硬件, 如今这些改变主要包括以下形式

ram 硬件设计(速度和并行)
memory 控制设计
cpu 高速缓存
设备的直接内存控制(direct memory access)

这篇文章的大部分都会和 cpu cache 和memory 控制有关. 我们会探索 DMA. 作为开始, 我们会看一看现代计算机硬件的概况, 这是我们理解存储系统效率和限制的先决条件, 我们还会接触到不同种类的 RAM 并且阐述为什么他们之间仍存在差异

这篇文章不能涵盖一切, 它受限于硬件产品, 并且很多只会浅尝辄止, 推荐读者们去看更细节的文档.

当遇到操作系统的细节和方法时, 本文只针对 linux, 不涉及到其他操作系统, 作者没兴趣讨论其他操作系统, 如果读者需要使用别的操作系统就应该要求他们vendor?提供类似的文档.

最后一点, 本文包括一大堆 usually 和类似的词, 现实情况要复杂得多, 本文只讨论最常见, 最主流的版本. 绝对的陈述很少出现在这个领域, 所以需要这些形容词.

文章结构

这篇文章主要针对软件开发者, 对于硬件导向的读者本文深度不足. 在我们实践之前需要一些准备工作

为此, 第二部分描述了 RAM 技术. 这部分容易理解但对后面的内容不是绝对重要的. 在后面需要的地方会有对这一部分的参考, 急切的读者可以跳过这一部分

第三部分主要是关于 cpu cache. 其中有很多图片防止枯燥, 这部分对于理解之后的内容至关重要, 第四部分是干预虚拟内存是如何实施的, 也是后面的必要准备工作

第五部分是关于非统一内存访问(non uniform memory access)

第六部分是本文的中心. 它整合了前面的所有内容并为软件开发者提供了如何在不同情况下写出合适代码的建议. 非常没耐心的读者可以从这里开始, 如果有必要的话会看之前的章节来回顾.

第七部分介绍了帮助程序员的工具, 即使是完全理解了这些技术也不能一眼看出软件的问题在哪, 一些工具是很有必要的

第八部分我们展望可以期待的技术.

报告问题

作者想要对该文档做一段时间的更新, 这包括技术进步相关的更新和更正. 欢迎读者通过邮件汇报问题, 注意要标明文章的版本号, 这个版本信息可以再文章最后一页找到

致谢

感谢Johnray Fuller and the crew at LWN(特别是Jonathan Corbet 把作者的英文修改的更为正规, Markus Armbruster 为本文提供了很多有效的问题和疏漏)

关于这篇文章

这篇文章的标题是对David Goldberg的经典论文/What Every Computer Scientist Should Know About Floating-Point Arithmetic/的致敬, 这篇文章仍未广为流传, 尽管对于任何想要进行精确变成的程序员来说都应该是必须的准备

对于 pdf: xpdf 对于一些图像显示不佳, 建议使用 evince 或者 adobe. 如果你使用 evince 那么注意本文中超链接被广泛使用, 尽管查看器不像其他软件那样显示他们

2 现代商品硬件

由于特质化硬件正在减少, 了解商品硬件是很重要的. 现在规模的扩展更多是水平的而不是纵向的, 这意味着使用更多小的互连的电脑比很大的但是特别快的电脑更划算. 这是因为快且便宜的网络硬件广泛普及. 这些大的特质化系统仍然有使用空间并且仍然提供着商业价值, 但是市场比起商用硬件相形见绌(is dwarfed by). redhat 2007 期望对于未来的产品, 大多数数据中心的标准配置会是一个带有 4 个插槽的电脑, 每一个都有4 个 cpu 核(对于 intel cpu 会是多线程的). 这意味着数据中心的标准系统会有至多 64 个虚拟处理器. 更大的机器将会被支持, 但是 4 插槽 4 核的情况在现在被认为是最佳选择(sweet spot).

商品零件计算机的结构存在很大差异。因此对于超过 90%的硬件, 我们将专注于最重要的差别. 注意到这些技术细节正在快速变化, 所以建议读者考虑到本文的创作时间.

在过去的几年里, 个人电脑和小的服务器在一个芯片上被标准化为两部分, 北桥和南桥.图 2.1

所有的 cpu(图中的两个, 还可以有更多)共用一条总线fsb(the front site bus前端总线)连接到北桥, 北桥包括, 除了别的之外, 决定了 ram 是哪种类型的内存控制器, 不同种类的 ram, 比如 dram, rambus, 和 sdram, 需要不同的内存控制器.

为了连接到其他所有的系统设备, 北桥必须和南桥沟通, 南桥经常被称作 i/o 桥, 通过一系列总线处理和不同设备进行的沟通. 现在的 pci, pcie, sata, 和 usb 总线都很重要, 但是 pata, ieee1394, 串口和并行端口(parallel port)也都被南桥支持, 更老一点的系统有连接北桥的 AGP （Accelerated Graphics Port 图形加速接口）插槽. 这是处于性能考虑因为北桥和南桥之间的沟通太慢, 而今天 pcie 插槽全部和南桥相连

这样一个系统结构有很多重要的结果:

从 cpu 到其他cpu的数据连接必须走和北桥连接的同一总线
所有和 ram 的连接必须通过北桥
ram 只有一个端口(port)
cpu 和与南桥相连的设备的连接会经由北桥

在这个模式下许多的瓶颈出现了, 其中一个瓶颈就和 ram 与设备的连接有关. 在早期电脑中, 所有南北桥和设备的连接都必须经过 cpu, 降低整个系统的性能. 为了解决这个问题, 一些设备开始具备 DMA（直接内存访问 Direct memory access）, dma 允许设备借助北桥直接存储和接收来自 ram 的数据而不需要 cpu 的参与(以及他固有的性能损失). 今天所有的和任意总线连接的高性能设备都可以利用 dma. 尽管它极大的减少了 cpu 的负载, 但是他也造成了北桥的带宽竞争, 因为 dma 请求会与 ram 与 cpu 之间的交流产生竞争, 这个问题也必须被考虑

第二个瓶颈和北桥到 ram 的总线有关. 总线的细节取决于部署的内存种类, 在老的系统只有一条总线连接到所有的 ram 芯片, 所以并行访问时不可能的, 最近 ram 的种类要求两个分开的总线(ddr2), 加倍了可用的带宽, 北桥跨通道交叉存取memory，更先进的内存及时(FB-DRAM)添加了更多的通道(channel)

由于只有有限的可用带宽, 最小化延迟去组织内存访问对应性能来说是很重要的. 我们将会看到, 处理器比内存快得多而且必须等待访问内存, 尽管已经使用了cpu cache. 如果多个超线程, 核, 或者处理器同时访问内存, 访存的等待时间会更长, 这对于 dma 操作也是如此

然而, 访存比并发更加重要, 访问模式本身也会极大的影响存储系统的性能, 特别是有多个内存通道的时候, 在 2.2 章节我们会讨论关于 ram 访问模式的细节

在一些其他更贵的系统中, 北桥实际上不包括存储控制器(memory controller), 相反北桥会被连接到许多外部存储控制器, 图 2.2 四个 MC

这种结构的好处是存在不止一个内存总线而且总的可用带宽增加了, 这种设计也支持更多的内存. 并发内存访问模式通过同时访问不同的内存库(memory bank?)来减少延迟, 当许多进程直接连接到北桥时尤为明显, 如图 2.2. 对于这样的设计, 最基本的限制是北桥内部的带宽, 这对于这种结构是惊人的.

使用多个外部 mc 不是唯一增加内存带宽的途径, 另一个流行的方式是把 mc 融入 cpu 中并且为每个 cpu 增加memory, 这个结构由基于 amd opteron 处理器的 SMP 系统推广. 图 2.3 展示了这个系统. intel 会从 nehalem 处理器开始支持通用系统接口(common system interface), 他也基本使用了同样的方法, 为每一个处理器添加一个融入进去的 mc 和本地 memory.

有了这样一个结构, 由于有很多处理器, 就会有很多内存库(memory bank). 在一个 4cpu 的机器上, memory 带宽翻了四倍而不需要有着很大带宽的复杂北桥. 将 mc 融入 cpu 有一些额外的优势, 这里我们不深究。

这个结构也有很多劣势. 首先因为机器仍然需要系统的所有的memory 可以与处理器连通, memory 不再是统一的了(由于名字的原因Non-Uniform Memory Architecture). 本地 memory(融入 cpu 的 memory)可以以正常速度访问, 当 memory 连通到其他 cpu 时情况就不一样了, 这种情况下必须使用处理器之间的通讯方式, 为了从 cpu1 连到 cpu2 的 memory, 需要经过一次相互连接(interconnect). 当 cpu1 需要连接到 cpu4 的时候需要两次

每个这种连接都有一定的cost, 我们把连接到其他 cpu 需要花费的额外时间称为 numa 因子. 图 2.3 中的结构中, 每个 cpu 有两层: 直接相联的 cpu 和需要跨越两次连接的 cpu(/对角线/). 随着机器变得复杂, 层级会增长的很快, 也有一些结构(比如 ibm 的x445 和 sgi 的 altix 系列)有不止一种连接. cpu 被组织成节点, 在一个节点中, 访问 memory 的次数可能被统一或者有少量的 numa 因子. 节点之间的连接代价会非常大, numa 因子会很高

商品级 numa 机器今天仍然存在并且在将来会处于很重要的位置, 在 2008 年末, 每个 smp 机器都会使用 numa. numa 的 cost 使得认识到机器在使用 numa是很重要的. 在第 5 部分我们会讨论更多的机器结果和 linux 内核中关于这些内容的技术

除了接下来讨论的技术细节, 还有其他的影响 ram 性能的因素. 他们不是软件控制的, 因此本章不提及. 有兴趣的读者可以在 2.1 部分学习, 只有当需要进一步连接 ram 技术才需要学习这些部分, 而且可能会使你在买电脑的时候做出更好的抉择

接下来的两部分讨论了入门级别的硬件细节, 还有 mc 和 dram 芯片之间的连通协议程序员会发现这些信息很有用因为这些细节揭示了ram 是如何工作的. 尽管这些是可选的知识, 那些急切想要学习和日常生产相关知识的程序员可以跳到 2.2.5 部分

2.1 RAM 种类

这些年来有很多种 ram 而且之间都有差距, 有时差距很大. 老的款式今天只会使历史研究者感兴趣了. 我们不会深究这些. 我们会专注于现代 ram 种类, 我们只会浅尝辄止, 探索一些对内核可见的细节或者程序开发者对性能研究需要的细节

第一个有趣的细节围绕着为什么在同一个机器中有不同的 ram. 更具体的, 为什么同时有 sram 和 dram. 前者(sram)更快而且有相同的功能性, 为什么机器中不是所有的 ram 都是 sram? 是因为价钱, sram比 dram 贵得多. 两个因素都很重要, 但是第二个越来与重要. 为了明白他们的不同, 我们来看一下 sram 和 dram 的实现.

在剩下的部分我们会讨论 ram 实现的一些低级细节, 我们会把细节的等级降到最低, 为此我们会在"数字逻辑"级别讨论, 而不是在硬件设计者会使用的级别. 那个级别与我们的目的无关

2.1.1 Static RAM

图 2.4 展示了有六个晶体管 sram 的单元(cell)的结构. 这个单元的内核是由 M1-M4 4 个晶体管构成两个交叉耦合(cross-coupled)逆变器(inverter). 他们有两个稳态, 各自为 0 和 1. 只要 V_dd上有能量就是稳定的. 如果需要访问单元的状态，则字访问线WL升高. 这使得单元的状态逻辑立即在 BL 和 BL上划线可读如果单元状态必须被覆盖, BL 和 BL上划线会第一个被置于需要的值然后 WL 升高. 由于外面的驱动的 4 个晶体管更强, 这使得旧的状态会被覆盖

截屏2021-08-04 下午4.25.04

看[20]来了解更详细的单元工作原理, 为了接下来的描述, 下面这些很重要

一个单元需要 6 个晶体管, 有 4 个的变种但是他们有缺点
维持状态需要持续的电源
当字访问线升高时, 单元的状态立即就是可读的. 该信号和其他晶体管控制信号一样是矩形的(在两个二进制状态之间快速变换)
单元状态是稳定的, 不需要刷新循环

还有其他的慢的但是耗能少的 sram 变种, 但是我们不关注因为我们在了解快的 ram. 他们比起 dram 在系统中更容易被使用因为有简单的接口, 这时他们会被注意到

2.1.2 Dynamic RAM

dram 结构比 sram 简单的多. 图 2.5 显示了通常的 dram 单元设计. 它包括的只有一个晶体管和一个电容, 这个复杂度上的差别意味着他的实现和 sram 差的很大

一个 dram 单元把他的状态存储在电容器 C 里, 晶体管 M 被用来守卫(guard)对状态的访问. 为了读单元的状态, 访问线 AL 被升高, 这产生了数据线 DL 上的流, 有或没有取决于电容器的电压. 为了写入单元DL数据线被置于合适的位置, 然后 AL 被升高一段时间足以充满或者放干电容

dram 这种设计带来了许多的问题, 使用电容意味着读取单元会把电容放电, 这个过程不可以无限的重复, 电容必须在某一时刻再充电. 更糟的是, 为了容纳如此大量的单元(现在普通的一个芯片有 10⁹个单元), 电容的容量必须很低(在毫微微级别或者更低). 一个完全充电的电容容纳着数以千计的电子, 尽管电容的电阻很高(几兆兆欧姆), 失效只需要很短的时间. 这个问题称为"leakage"(泄露)

泄露就是 dram 单元必须持续刷新的原因, 对于大多数 dram 芯片, 这个刷新必须每 64ms 发生一次, 在刷新周期中没有访问是被允许的因为一次刷新就是一次简单的结果被丢弃的读操作。对于一些工作, 这个开销可能会使 50%的 memory 操作等待

第二个由小量的充电引起的问题是从单元读取的信息不是直接可用的. 数据线必须连接到读出放大器，该读出放大器可以在仍然必须算作1的整个电荷范围内区分存储的0或1。

第三个问题是读取单元造成电容电荷的耗尽, 这意味着每次读取操作都必须紧跟一个重新给电容充电的操作, 这个通过把读出放大器的输出反馈给电容来自动实现. 它意味着读取操作需要额外的能量和时间。

第四个问题是给电容充放电不是瞬时的, 读出放大器收到的信号不是矩形的, 所以必须使用保守的估计来确定何时可以使用单元的输出。电容充放电的公式为:

截屏2021-05-02 上午3.52.29

这意味着电容充放电需要花费一点时间(由电容的 C 和 R 决定). 这也意味着被读出放大器探测到的情况不是立即就可以使用的, 图 2.6 展示了充放电的曲线. x 轴的单位是 RC, 是时间的单位.

不像 sram，当字访问线被升高时结果可以立即被使用, dram 总需要花费一点时间直到电容充分的放电, 这个延迟严重的限制了 dram 能有多快.

这个简单的结构也有他的好处, 主要的好处就是尺寸, dram 在芯片上需要的空间比 sram 小的多, sram单元也需要独立的保持晶体管状态的能量. dram 单元的结构更简单而且更规则, 这意味着把他们紧密的打包在一个 die 上更简单.

总的来说, 还是在价格上胜出了. 除了在特制的硬件比如网络路由器, 我们必须使用基于 dram 的主存, 这对我们接下来要讨论的编程有很大意义, 但是首先我们先看一下实际中 dram 单元使用的细节

2.1.3 DRAM 访问

一个程序通过虚拟地址找到一个 memory 位置, 处理器把它翻译成物理地址并且最终 mc 找到和这个地址相对应的 ram 芯片. 为了选择到 ram 芯片上独立的 memory 单元, 一部分物理地址以多个地址线(address lines?)的形式传送.

从 mc 独立的找到 memory 地址是不切实际的: 4GB（2³²） ram 需要2³²地址线. 地址是以二进制编码传送的, 这样会使用少一些的地址线. 通过这种方式传递到 dram 芯片的地址必须首先被解码, 一个具有 N 个地址线的解复用器会有 2^N个输出线, 这些输出线可以被用来选择 memory 单元. 使用这种直接映射对于小规模芯片不是大问题.

但是如果芯片的数量增长了, 这个方式就不再适合了. 一个拥有 1Gbit 容量的芯片会需要 30 个地址线和 2³⁰个选择线(/输出/), 当不牺牲速度时，解复用器的大小会随着输入线的数量呈指数增加. 除了解复用器的复杂性（大小和时间）外，30个地址线的解复用器还需要大量的芯片实际空间. 更重要的是, 在地址线上同步传输 30 个脉冲比传送 15 个脉冲要难得多. 更少的线路必须以完全相同的长度或适当的时间布局.(7 现代 dram 种类比如 DDR3 可以自动适应时间, 但是容忍度是有限制的)

图 2.7 显示了高级的 dram 芯片, dram 单元被以行和列的方式组织起来, 他们可以被排列在一行但是那样 dram 芯片就需要一个巨大的解复用器. 通过数组访问, 这种设计可以使用一般大小的解复用器和多路选择器. 这是各方面巨大节省. 在例子中, 地址行 a₀ 和 a₁ 通过行地址选择(row address selection)解复用器从所有行中选择地址线, 当读取的时候, 所有单元的内容都对列地址选择多路选择器开放, 通过地址线 a₂ a₃ , 一列中的内容向dram 芯片的数据引脚开放. 这在很多 dram 芯片上并行的发生很多次来产生一堆 bit 和数据总选的宽度相对应.

在写的时候, 新的单元值被放在数据总线上, 然后当单元被用 ras(row address selection) 和 cas(column address selection) 选择时, 值会被存到单元中. 是一个很直接的设计呢. 在现实中显然有更多的复杂细节. 必须要明确在数据总线可以被读取的信号发出后会有多少的延迟. 正如前面所说, 电容不会立即放电. 单元中的信号是那么小以至于他需要被放大. 对于写来说必须明确在总线上通过 ras 和 cas 成功存储新的值在多长时间需要保持有效(又一次, 电容不会立即的充电和放电). 这些时间常数对于 dram 芯片的性能是很重要的, 我们会在接下来的章节讨论.

第二个扩展上的问题是, 有 30 个地址线连接每个 ram芯片也是不可行的. 芯片的引脚是很珍贵的资源, 数据必须被尽可能的并行传输已经足够坏了. mc 必须可以在每个 ram 模块(ram 芯片的集合)上寻址. 如果因为性能要求需要并行访问多个 ram 模块而且每个 ram 模块需要自己拥有 30 个以上的地址线, 那么 mc 就必须有, 对于8 个 ram 模块, 240+引脚仅仅用来应付地址.

为了解决这些次要的可扩展问题, 很长一段时间, dram都在自己进行地址的多路选择. 这意味着地址被传送到两部分: 第一部分包括行地址(图 2.7 a₀ 和 a₁ ), 这个选择保持活跃直到取消, 然后第二部分(a₂ a₃)选择列. 主要的不同在于只需要两个额外的地址线, 当 ras 和 cas 可用时会减少很多线路来指示地址, 但也有一点小代价来把地址分为两部分. 这个地址多路选择带来了他自己的问题, 我们会在 2.2 讨论.

2.1.4 结论

不要担心这部分的细节是不是有一点过载了, 这部分重要的内容有:

不全用 sram 是有原因的
地址线的数量和 mc, 主板, dram 模块, dram 芯片的 cost 有直接联系
在读写操作之前有一段时间间隔

接下来的部分会接触更多访问 dram memory 的细节. 我们不会深入访问 sram 的细节, 因为它通常是直接寻址的. 这是因为速度问题而且 sram 的大小有限, sram 现在在 cpu 的 cache 和 on-die ?上使用, 这里连接是很小的而且在 cpu 设计者的控制之下. cpu cache 是一个我们之后会讨论的内容但是我们需要知道的是 sram 单元有一个最大速度, 这个速度取决于花在 sram 上的 efforts(?). 速度可以仅比CPU core稍慢一两个数量级。

2.2 DRAM 访问的技术细节

在介绍 dram 的章节中我们看到了 dram 芯片多路复用地址来以地址引脚的形式保存资源. 我们也看到了访问 dram 单元会花费时间, 因为这些单元的容量不会立即的放电来产生一个稳定的信号. 我们也看到 dram 单元必须被刷新, 现在我们该把这些和到一起看看这些因子是怎么共同决定 dram 访问的了.

我们会专注于现代科技, 不去讨论异步 dram 和他的特点因为他们不再和此相关了. 对这些感兴趣的读者可以看看注释 3 和 19. 我们也不会讨论Rambus dram(RDRAM)即使这项技术并不老旧. 只是它不再系统 memory 中广泛使用. 我们会主要专注于同步 dram(SDRAM synchronous dram)和他的继承者DDR(double data rate dram).

sdram 正如名字所示, 根据一个时间源工作. mc 提供一个时钟, 他的频率决定了前端总线(front side bus FSB)的速度 - dram 芯片使用的 mc 的接口(/解释/ /fsb/). 截至撰写本文时, 频率有 800MHz, 1066MHz 1333MHz, 下一代声称还会有更高的频率(1600MHz). 这并不意味着这个总线上使用的频率有这么高, 相反, 现在的总线是双泵或者四泵的(double- or quad-pumped /ddr?/), 这意味着数据在每个循环中传送 2或者 4 次. 数量越高买的越好, 所以厂商喜欢把一个 4 泵 200MHz 的总线宣传为"有效的"800MHz

对于现在的 sdram, 每个数据传输包括 64 位(8bytes). fsb 的传输速率就是 8B 乘上有效总线频率(6.4GB/s 等于 4 泵 200MHz 总线). 这听起来很多但这是峰值，永远不会超过这个速度. 正如我们现在将看到的，与 RAM 模块对话的协议在无法传输数据时有很多停机时间. 这个停机时间是我们必须考虑的而且要缩短来达到最好的性能.

2.2.1 读访问协议

图 2.8 展示了 dram 模块上一些连接的活动, 他们发生在三个不同颜色的阶段. 通常时间从左往右进行. 我们这里只讨论总线时钟, \(\overline{\text{RAS}}\) \(\overline{\text{CAS}}\) 信号和地址总线数据总线. 一个读循环以 mc 在地址总线上使得行地址可访问并降低\(\overline{\text{RAS}}\)开始. 所有的信号都在时钟的上升沿被读取. 所以时钟是否是完全方形的并不重要, 只要她在被读取的时候是稳定的就行. 放置行地址使得 ram 芯片开始锁住被寻址的行.

\(\overline{\text{CAS}}\) 信号可以在 t_RCD(\(\overline{\text{RAS}}\) -to-\(\overline{\text{CAS}}\))时钟周期后被发送. 然后列地址被传送, 表现为在地址总线上可以访问并且降低\(\overline{\text{CAS}}\)线. 这样我们就能看清这两部分地址是怎么被通过相同的总线传输了.

现在寻址结束了数据可以被传递了, ram 芯片需要一些时间来准备这些. 这个延迟通常被叫做\(\overline{\text{CAS}}\)延迟(CL). 在图2.8 中cas延迟是2, 它可高可低, 取决于mc, 主板, dram模块的质量. 延迟也可以有半值(0.5). 如果CL=2.5 第一个数据就会在蓝区的第一个下降沿可以被访问.

有了这些去获得数据的准备, 只传送一个数据字会是很浪费的. 这就是为什么dram模块允许mc明确到底多少数据会被传输. 通常是2, 4, 8 个字. 这允许填满cache中的整行而不需要一个新的ras/cas序列. 这也使得 mc传送一个新的cas信号而不用重新选择行成为可能. 这样, 连续的memory地址就可以被很快的读写因为ras信号不用被发送，行也不需要被失活(deactivate, 见下面). 保持行“打开”是mc需要去决定的. 投机的让他一直开着在现实中是有缺点的(见[3]). 发送新的cas信号只取决于ram模块的频率(通常特指为Tx, x是一个值比如1, 2; 1代表着是一个高性能dram每个周期都会接受新的命令)/(be subject to受支配)/

在这个例子中sdram每个循环吐出一个字. 这是第一代做的事情, DDR可以每个循环传输两个字. 这削减了传输时间但是没有改变延迟. 原则上ddr2以同样的原理工作但实际上会有不同. 这里没必要深究, 要注意ddr2可以被做的更快, 更便宜, 更可靠, 更节能(见[6]).

2.2.2 预充电与激活

图2.8 没有涵盖整个周期, 它只展现了整个周期中访问dram的部分, 在一个新的ras信号可以发送之前, 当前被锁住的行必须被失活而去新的行必须被预充电. 我们可以专注于这样一种情景: 这是通过一条明确的指令完成的. 对于这个协议在某些情况下也有提升, 它允许这个额外的步骤被丢弃. 这个由预充电造成的延迟仍然会影响操作.

图2.9展示了从cas信号开始到下一行的cas信号的过程. 使用第一个cas信号的数据像之前一样在CL循环之后可以使用. 这个例子中带了两个字, 这在简单的sdram中会花费两个周期传输. 可以思考四个字在一个ddr芯片上的样子.

即使在频率只有 1 的dram模块上与充电指令也不能被立即发出. 它必须要等待数据传输. 在这个例子中它话费了两个时钟周期. CL也是如此但是这只是个巧合. 预充电信号没有专门的数据线. 取而代之, 一些设施通过降低WE和RAS线来同步的发送这个信号. 这个组合自己没有实际意义.

只要充电指令发出了, 它需要花费t_RP(row precharge time)个循环知道这个行可以被选择. 在图2.9 中许多时间(由紫色标识)与memory传输(亮蓝色)重合, 这很好! 但是t_RP 比传输时间更长所以下一个ras信号被暂停了一个周期.

如果我们继续图中的时间线我们会发现下一个数据传输在前一个停止的5个周期之后. 这意味着数据总线在7个周期中只有2个在使用. 乘以FSB速度和理论6.4GB/s的800MHz总线成为1.8GB/s. 这不好而且必须被避免. 这个技术在第6部分会被讨论来提高利用率. 但是程序员必须尽一份自己的努力.

在sdram模块中还有一个时间值我们未讨论, 在图2.9预充电指令植被数据传输时间限制, 另一个约束是一个sdram模块在一个ras信号之后需要一些时间才能预充电另一个行(记为t_RAS). 这个时间通常很长, 大概是t_RP的两到三倍. 如果在一个ras信号之后只有一个cas信号, 这个传输几个周期就会结束, 这将成为一个问题. 假设在图2.9 中初始的cas信号是由ras信号直接预先传递的而且t_RAS是8个周期. 那么预充电指令就会被额外延迟一个周期, 因为t_RCD, CL, t_RP的总和是7个周期.

DDR模块通常决定使用一个特殊的记号w-x-y-z-T. 比如2-3-2-8-T1, 这意味着

标记	值	意义
w	2	cas 延迟 CL
x	3	ras-to-cas 延迟 t_RCD
y	2	ras 预充电 t_RP
z	8	从预充电延迟中恢复 t_RAS
T	T1	指令频率

有许多其他的时间限制影响指令的发出和处理. 这五个限制是现实中最主要的决定模块性能的部分.

有时, 了解这些信息对于使用的计算机能够解释某些测量结果是有用的. 当买电脑的时候知道这些肯定是游泳的因为他们和FSB, sdram模块速度一样, 是决定电脑速度最重要的因素.

特别大胆的读者也可尝试去调整系统, 有时 bios 允许改变一些或者所有的值, sdram模块有可编程寄存器, 这些值可以放在这里. 如果ram模块的质量很高, 他肯呢个会减少一个或者奇特的延迟而不影响电脑的稳定性. 很多的超频(overclocking)网站提供做这件事的丰富的文档. 自己承担风险, 别说没被警告过.

2.2.3 再充电

在谈到dram的时候, 一个最容易被忽视的主题就是再充电. 正如2.1.2中解释的, dram单元必须被持续的刷新, 在剩下的系统中这个过程不是完全显式的发生. 有时候当一个行被再充电时是不可访问的, [3]的研究表明, 令人惊讶的是, dram的刷新机制可以戏剧性的影响性能.

JEDEC(Joint Electron Device Engineering Council)表明, 每一个dram单元都必须每64ms被刷新一次. 如果一个dram数组有8192个行, 这意味着mc必须平均每7.8125微秒发送一个刷新指令(刷新指令可以被排队所有现实中两个请求的最大间隔可以更长), mc负责安排刷新指令, dram模块跟踪最后被刷新的行的地址并且每个请求都自动增加地址的计数.

程序员对刷新和指令什么时候会发出无能为力, 但是在解释性能测量时记住dram的这一部分是很重要的. 如果要找回一个字, 但是这个字正在被刷新, 那么处理器就会暂停很长一段时间, 每一次刷新持续多久由dram模块决定.

2.2.4 memory 类型

值的花费一些时间在当前和即将被使用的memory类型上, 我们会从SDR(single data rate) sdram 开始因为他们是DDR(double data rate) sdram的基础, sdr是很简单的, memory单元和数据传输速率是统一的.

如图2.10 dram单元数组可以以相同的速度输出memory信息和传送到memory 总线上. 如果dram单元数组可以以100MHz的方式操作, 那么总线的一个单一单元的数据传输速度就是100Mb/s. 所有组件的频率f都是相同的, 提高dram芯片的吞吐量是很昂贵的因为能量消耗随着频率的增加上升. 由于单元数组很大会变得非常昂贵. 现实中甚至不止一个问题因为升高频率通常也要求升高维持系统稳定的电压. ddr sdram(追溯的称为ddr1)可以用来提升吞吐量而不需要增加任何频率.

sdr和ddr1之间的区别是, 如图2.11所示而且从名字也可以猜到, ddr1每个周期传输两倍的数据. 也就是(i.e.)ddr1芯片在上升沿和下降沿都传输数据. 这个有时候被称作“双泵”总线(double pumped bus)为了达到这个目的而去不增加单元数组的频率, 就需要引入一个缓冲. 这个缓冲每个数据线保存两位, 这就要求图2.7中的单元数组中, 数据总线要包括两条线. 实现起来很简单: 只需为两个 DRAM 单元使用相同的列地址, 并并行访问它们. 为了实现这个, 单元数组需要作出的改变也很少.

sdr dram 以他们的频率为标识(比如PC100 就是100MHz的sdr). 为了使ddr1 dram更好听, 销售者必须想出一个新策略因为频率没有改变. 他们想到了一个名字, 包括以byte为单位一个ddr模块(他们有64-bit总线)可以传输的速率: 100MHz * 64bit * 2 = 1600MB/s 由于一个100MHz的ddr模块被称作PC1600. 1600 > 100一切市场需求都被满足了, 它听起来很好尽管提升仅仅是两倍.

为了更充分的利用memory技术, ddr2包括了一些新的创新. 最明显的改变是如图2.12所示就是翻倍了总线的频率. 频率翻倍意味着带宽翻倍, 由于频率翻倍对于单元数组不经济, 限制需要i/o缓冲每个周期取4bits, 然后再送给总线. 这意味着 DDR2 模块的更改仅使 DIMM(/Dual-Inline-Memory-Modules/) 的 I/O 缓冲组件能够以更高的速度运行. 这当然是可能的而且不会需要太多的能耗, 这只是一个小的组件而不是整个模块. 销售者想出的ddr2的名字和ddr1相似, 只是乘2换成了乘4(现在我们有了“四泵”总线). 表2.1展示了现在使用的模块的名字.

命名还有一点变化, cpu, 主板, dram 模块使用的 fsb 速度通过使用有效频率而被指明了, 也就是, 他在传输的时钟周期的两个沿都起了作用从而使得数字膨胀. 因此, 一个有着 266MHz 总线的 133MHz 模块有着 533MHz 的 fsb 频率.

DDR3 的规范(真的那个, 不是在显卡中用的假的 GDDR3) 在从 DDR2 的演变过程中需要更多的改变, 电压会从 ddr2 的 1.8v 降到 ddr3 的 1.5v. 由于能耗和电压的平方成正比, 这个改变带来了 30%的提升. 由于这个原因die 的大小和其他电气特性 ddr3 都可以做的更好, 比如在相同频率下能耗减半, 二选一的, 使用更高的频率也可以达到同样的功率. 或者加倍容量可以实现相同的热耗散.

ddr3 模块的单元序列以外部总线四分之一的速度运行, 这需要一个 8bit 的 i/o 缓冲, 相比之下 ddr2 需要 4bit, 如图 2.13

最初，DDR3 模块可能会有略高的 CAS 延迟，只是因为 DDR2 技术更加成熟, 这会导致 ddr3 只有在频率上更有效, 比那些可以达到 ddr2 的更高, 特别是当带宽比延迟更重要的时候. 之前已经谈到 1.3v 模块会和 ddr2 有一样的 cas 延迟, 不论如何, 由于更快的总线而达到更快素的的可能性比增长的延迟更有价值.

ddr3 可能的问题是, 对于 1600Mb/s 或者更高的传输速率, 每个通道的模块数量会被减少到只有一个, 在更早的版本这个要求应用于所有的频率, 所以有人希望在将来可以接触对所有频率的限制.

表 2.2 展示了 ddr3 模块常见的名字. JEDEC 认可前四种. 考虑到 intel 的 45nm 处理器有 1600Mb/s 的 fsb 速度, 1866Mb/s 是超频市场需要的, 我们会在对ddr3 发展的后期看到更多这种类型.

所有的 ddr memory 都有一个问题: 增长的总线频率使得制造并行的数据总线很困难, 一个 ddr2 模块有 240 个引脚, 所有连接到数据和地址的引脚都必须被路由所以他们有几乎相近的长度, 除此之外, 如果不止一个 ddr 模块被连接到同一个总线, 对于每一个新增的模块信号都会变得易损坏, ddr2 的说明允许最多每个总线连接两个模块, ddr3 的说明允许在高频时最多连接一个模块, 每个通道有着 240 个引脚的北桥不能驱使超过两个通道, 可以选择另外的 mc 但是这会是昂贵的.

这意味着商用的主板被限制最多只能拥有 4 个 ddr2 或 ddr3 模块, 这个限制严格的阻碍了系统可拥有的 memory 数量, 即使老的 32-bit 的 IA-32 处理器也可以控制 64GB 的 ram, 而且家用的 memory 需求也在增长, 所以必须做点什么.

一种做法是为每一个处理器添加 mc 如第二部分所说, amd在 Opteron 上这么做的, intel 在 CSI 技术上是这么做的, 只要处理器能够使用的内存量可以连接到单个处理器就会有所帮助, 在某些情况下并不是这样, 并且会带来 numa 结构及其负面影响, 对于一些情况需要其他的解决方案.

memory 层次

intel 当前在大型服务器上的处理方式是FB-DRAM(fully buffered dram), fb-dram 模块使用和 ddr2 一样的 memory 芯片, 这很便宜. 区别在于 mc 之间的连接, fb-dram 没有使用平行数据总线而是使用一系列总线(Rambus DRAM had this back when, too, and SATA is the successor of PATA, as is PCI Express for PCI/AGP). 串行总线可以再一个更高的频率工作, 解决了串行总线的劣势甚至增加了带宽, 使用一系列总线的主要作用在于

一个channel可以使用更多的模块
每个 mc 可以控制更多 channel
串行总线设计为全双工
部署其他的总线和提高速度是很便宜的

和 ddr2 的 240 个针脚相比, 一个 fb-dram 模块只有 69 个针脚. 分清连接的 fb-dram 模块是很容易的因为总线的电效应可以被更好的处理, fb-dram 允许每个 channel 连接至多 8 个 dram 模块

和双通道的北桥的连接要求相比, 现在可以用更少的针脚驱动 6 个 fb-dram channel: 2240 针脚 vs 669针脚, 每个 channel 的路由都更简单, 这可以减少主板的成本

完全双工的并行总线对于传统的 dram 特别的昂贵, 重复这些线路太昂贵了. 使用串行总线(即使他们之间是不同的, 正如 fb-dram 要求的那样)这就不是问题而且串行总线就是被设计成全双工的, 这意味着在一些情况下, 理论上带宽是可以加倍的. 但这并不是并行被用来增加带宽的唯一地方, 由于 fb-dram 控制器可以同时控制最多 6 个 channel, 带宽可以使用 fb-dram 来使用更少的 ram 增加. 在有四个模块两个 channel 的 ddr2 系统的地方, 可以使用 4channel 的 fb-dram 控制器实现相同的性能, 实际的串行总线带宽取决于使用 fb-dram 的 ddr2(或 ddr3)芯片.

可以归纳为如下表格:

如果多个 dimm 使用在一个 channel 上, fb-dram 也有一些缺点, 信号在链中的每个 DIMM 处延迟（尽管是最低限度的），从而增加了延迟. 第二个问题是驱使着串行总线的芯片需要大量的能量因为有很高的频率而且要驱使总线, 但是对于使用相同频率和相同数量的 memory, fb-dram 总是比 ddr2 和ddr3 要快因为至多四个 dimm 可以各自拥有自己的 channel, 对于大的 memory 系统 ddr 无法使用商用组件.

2.2.5 结论

这一部分展示了连接 dram不是可以任意快的过程, 至少不能和运行的处理器还有访问寄存器和缓存一样快, 要记住 cpu 频率和 memory 频率的区别, intel core2 处理器以 2.933GHz 频率运行, 而一个 1.066GHz 的 fsb 有一个 11:1 的时钟比(1.066GHz 的总线是四倍频的), memory 总线上的每一个时钟停止都意味着处理器上的 11 个时钟周期停止, 对于大多数机器, 实际的 dram 使用是更缓慢的因此更加增加了延迟 , 在我们接下来谈到暂停的时候请记住这些数据.

读指令的时间表展示了 dram 能保持高数据速率. 整个 dram 行可以在一个stall被传送, 数据总线可以保持一致被占用, 对 ddr 来说这意味着每个周期可以传送两个 64bit 字, 使用 ddr2-800 和两个 channel 意味着 12.8GB/s 的速率.

但是除非这样设计, 连接 dram不会一直是连续的, 不连续的 memory 区域会被使用, 这意味着需要预充电和新的 ras 信号, 这是速度会下降而且 dram 需要帮助, 行被实际使用时, 预充电和ras 信号越快代价就越小.

硬件和软件预提取可以创造更多的重叠减少stall, 预提取也会及时帮助改变memory 操作, 所以在数据被真正需要之前就会有更少的连接, 这是一个频率问题, 一轮中产生出来的数据必须被存储, 下一轮需要的数据必须被读取, 通过改变读的时间, 写操作和读操作不需要基本同时发出.

2.3 其他主要 memory 用户

除了 cpu 还有其他系统组件可以连接主memory, 高性能 card 比如网卡和大存储控制器不能承担起运输所有他们需要或者提供给 cpu的数据, 因此, 他们直接从主 memory读写数据(direct memory access DMA), 在图 2.1 我们可以看到 card 可以使用 memory 直接可南北桥沟通, 其他总线, 比如 usb 也需要 fsb 带宽, 虽然他们不使用 dma, 因为南桥通过北桥使用 fsb 连接到处理器.

尽管 dma 很有用, 但它意味着 fsb 带宽有了更多的竞争, 在 DMA 流量高的时候，CPU 可能会在等待来自主memory的数据时比平时stall 更久. 使用合适的硬件就能解决这个问题, 有图 2.3 的结构, 可以确保计算使用没有被 dma 影响的节点, 也可以连接南桥到达节点, 均等的把 fsb 的负载分布到所有节点上, 这有无数种可能, 在第六部分我们会介绍帮助达到这种提升的软件技术和变成接口.

最后应该提到一些便宜的系统有非独立的图像系统, 专用图像 ram, 这些系统使用部分主 memory 当做图像ram, 由于访问图像 ram 是很经常的(对于一个 1024*768 显示屏有 16bpp 60Hz 我们是再说 94MB/s)并且系统 memory 不像显卡上的 ram, 没有两个 port这会本质上的影响系统性能特别是延迟, 他们利大于弊, 人们知道不会得到最好的性能买那些机器.

3 cpu 缓存

今天的 cpu 比 25 年前的精密很多, 那个时候, cpu core 的频率和 memory 总线在一个数量级, memory 访问只比寄存器访问慢一点, 但是这些在 90s 早期戏剧性的转变了, cpu 设计师们增加了 cpu core 的频率但是 memory 总线的频率和 ram 芯片的性能并没有成比例的增加, 这不是因为前面提到的更快的 ram 无法被造出来, 这是可以的但不经济, 和现代 cpu core一样快的 ram比任何 dram 都要贵几个数量级

如果要在有一个很小很快 ram 的机器和有一堆相对比较快的ram的机器之间做选择, 给定的工作集大小超过小 RAM 大小和访问二级存储介质如硬盘驱动器的成本, 后者肯定没错, 问题是二级存储介质的速度, 通常是硬盘, 一定是常驻工作区的交换分区的, 访问这些硬盘比访问 dram 还要慢好几个数量级.

幸运的是不必做 0或1 的选择, 电脑可以有一个小的高速sram和一个大的 dram. 一种组合是分配一个特定的处理器地址空间专用于包含 sram , 剩下的为dram, 操作系统的任务是最优的分配数据来充分利用 sram, 基本上 sram 在这种情境下以处理器寄存器的扩展来使用.

尽管这是一种可能的方案但却不是可行的, 忽略这种从支持 sram 的硬件资源memory 映射到进程虚拟地址空间的问题(本身就很困难)这种方法会要求每个进程在软件中管理这个 memory 区域的分配, 处理器之间这个 memory 区域的大小会差的很大(比如: 处理器们有不同数量的昂贵的支持sram的memory), 每个组成程序的模块都会声明自己拥有的高速 memory, 这在同步上会引入新的损耗, 简而言之, 拥有高速 memory 的收益会被管理他们带来的损耗完全抵消掉.

所以, 不去把 sram 安置到操作系统或者用户的控制下, 而是把它变成由处理器直接使用和管理的资源. 这种模式下, sram 被用来制作main memory 中数据的临时副本(即缓存), 他们很快就会被处理器用到. 这是可行的因为程序代码和数据有时间和空间局部性, 这意味着在短时间内很有可能相同的代码和数据被使用. 对代码这意味着有循环因此相同的代码被反复执行(很好的空间局部性例子). 数据访问也恰好局限于一个小的区域. 即使短时间内使用的 memory 不是很近, 也有很高的概率相同的数据会被再次使用(时间局部性). 对于代码这意味着, 举个例子, 在一个循环中一个函数被调用而且这个函数位于地址空间的其他位置, 这个函数可能在 memory 中距离很远, 但是对函数的调用在时间上会很近，对于数据这意味着同一时间使用的memory总量被理想的限制住了，但是被使用的memory由于ram随意访问的特性不会相邻很近，认识到局部性的存在是我们今天理解cpu缓存概念的关键。

一个简单的计算就能展示缓存在理论上是多有效，假设访问主存花费200时钟周期，访问缓存memory花费15时钟周期，那么代码使用100个数据每个一百次，在访存上不使用缓存会花费2000000时钟周期，如果所有数据都在缓存中只需要168500时钟周期，性能提升了91.5%。

sram缓存比主存小好几倍，在作者的经验里，有cpu缓存的工作站缓存大小通常是主存大小的1/1000（4MB缓存4GB主存）。这本身不构成问题，如果工作集（正在操作的数据集）比缓存小不会有什么问题，但是电脑不会无缘无故有很大的缓存，工作集势必比缓存要大，特别是对于运行多个进程的系统，工作集的大小是所有单独进程和内核的大小之和

处理有限的缓存大小需要一套好的策略来确定在任何给定时间应该缓存什么。由于并非工作集中的所有数据都在完全相同的时间使用，我们可以使用技术将缓存中的一些数据临时替换为其他数据。也许这可以在实际需要数据之前完成。这种预取将消除访问主存的一些成本，因为它相对于程序的执行是异步发生的。所有这些技术以及更多都可用于使缓存看起来比实际更大。我们将在 3.3 节中讨论它们。一旦利用了所有这些技术，就需要程序员来帮助处理器了。如何做到这一点将在第 6 节中讨论。

3.1 cpu缓存概述

在深入研究 CPU 缓存实现的技术细节之前，一些读者可能会发现首先了解缓存如何融入现代计算机系统的“大图”的更多细节很有用。

图 3.1：最低缓存配置

图 3.1 显示了最低缓存配置。它对应于可以部署 CPU 缓存的早期系统的架构。 CPU 内核不再直接连接到主内存。所有的加载和存储都必须通过缓存。 CPU核心和缓存之间的连接是一种特殊的、快速的连接。在简化的表示中，主存储器和高速缓存连接到系统总线，系统总线也可用于与系统的其他组件通信。我们将系统总线称为“FSB”（front-side-bus），这是今天使用的名称；见第 2.2 节。在本节中，我们忽略北桥；假定它的存在是为了促进 CPU们与主存储器的通信。

尽管过去几十年的大多数计算机都使用冯诺依曼架构，但经验表明，将用于代码和数据的缓存分开是有利的。自 1993 年以来，英特尔一直使用单独的代码和数据缓存，并且从未回头。代码和数据所需的内存区域几乎是相互独立的，这就是独立缓存更好地工作的原因。近年来出现了另一个优势：大多数常见处理器的指令解码步骤很慢；缓存解码的指令可以加快执行速度，尤其是当流水线由于错误预测或无法预测的分支而为空时。

引入缓存后不久，系统变得更加复杂。缓存和主存之间的速度差距再次拉大，以至于增加了另一级缓存，比一级缓存更大更慢。出于经济原因，仅增加一级缓存的大小不是一种选择。今天，甚至有正常使用的具有三级缓存的机器。具有这种处理器的系统如图 3.2 所示。随着单个 CPU 中core数量的增加，未来缓存层级的数量可能会增加更多。

图 3.2 显示了三个缓存级别，并介绍了我们将在文档的其余部分中使用的命名法。 L1d 是一级数据缓存，L1i 是一级指令缓存，等等。注意这是示意图；实际上，数据流在从核心到主存的过程中不需要通过任何更高级别的高速缓存。cpu设计者在缓存的接口上有很大的设计自由。对于程序员这些设计选择是可见的。

此外，我们有具有多个内核的处理器，每个内核可以有多个“线程”。内核和线程之间的区别在于，不同的内核拥有（几乎）所有硬件资源的独立副本。核心可以完全独立运行，除非它们同时使用相同的资源——例如与外部的连接。另一方面，线程共享处理器的几乎所有资源。英特尔的线程实现只有单独的线程寄存器，即使是有限的，一些寄存器也是共享的。因此，现代 CPU 的完整图如图 3.3 所示。

图 3.3：多处理器、多核、多线程

在此图中，我们有两个处理器，每个处理器有两个内核，每个处理器有两个线程。线程共享一级缓存。core（深灰色阴影）具有单独的 1 级缓存。 CPU 的所有内核共享更高级别的缓存。两个处理器（浅灰色阴影的两个大框）当然不共享任何缓存。所有这些都很重要，特别是当我们讨论缓存对多进程和多线程应用程序的影响时。

3.2 高级别的缓存操作

要了解使用缓存的成本和节省，我们必须将第 2 节中有关机器架构和 RAM 技术的知识与上一节中描述的缓存结构相结合。

默认情况下，CPU 内核读取或写入的所有数据都存储在缓存中。有些内存区域不能被缓存，但这只是操作系统实现者必须关心的事情；它对应用程序程序员是不可见的。还有一些指令允许程序员故意绕过某些缓存。这将在第 6 节中讨论。

如果 CPU 需要一个数据字，则首先搜索缓存。显然，缓存不能包含整个主存的内容（否则我们将不需要缓存），但由于所有内存地址都是可缓存的，因此每个缓存条目都使用主存中数据字的地址进行标记。这样，读取或写入地址的请求可以在缓存中搜索匹配的标签。此上下文中的地址可以是虚拟地址或物理地址，具体取决于缓存实现。

由于对于标签，除了实际内存之外，还需要额外的空间，因此选择一个字作为缓存的粒度是低效的。对于 x86 机器上的 32 位字，标签本身可能需要 32 位或更多。此外，由于空间局部性是缓存所基于的原则之一，不考虑这一点是很糟糕的。由于相邻的memory很可能一起使用，它也应该一起加载到缓存中。还记得我们在第 2.2.1 节中学到的内容：如果 RAM 模块可以在没有新的 CAS 甚至 RAS 的情况下连续传输许多数据字，那么它们的效率会更高。因此，存储在缓存中的条目不是单个字，而是几个连续字的“lines（行）”。在早期的缓存中，这些行是 32 字节长；现在的标准是 64 字节。如果内存总线是 64 位宽，这意味着每个高速缓存行需要 8 次传输。 DDR 有效地支持这种传输模式。

当处理器需要memory内容时，整个缓存行被加载到 L1d 中。每个缓存行的内存地址是通过根据高速缓存行大小屏蔽（mask）地址值来计算的。对于 64 字节缓存行，这意味着低 6 位为零。丢弃的位用作缓存行的偏移量（offset）。其余位在某些情况下用于定位缓存行并用作标记（tag）。在实践中，地址值被分成三个部分。对于 32 位地址，它可能如下所示：

cache line 示意图

对于大小为 2^O 的缓存行，低O位被用作缓存行的offset，接下来的 S 位选择“缓存集（cache set）”。我们将很快详细介绍为什么将集合而不是单个插槽（slot）用于缓存行。现在了解有 2^S 组缓存行就足够了。这留下了形成标签的前 32−S−O = T 位。T 位是与每个缓存行关联的值，用于区分缓存在同一缓存集中的所有别名（alias，All cache lines with the same S part of the address are known by the same alias.）。不必存储用于寻址缓存集的 S 位，因为它们对于同一集中的所有缓存行都是相同的。

当一条指令修改内存时，处理器仍然必须首先加载一个缓存行，因为没有指令一次修改整个缓存行（例外：写组合，如第 6.1 节所述）。因此，必须加载写入操作之前的缓存行内容。缓存不可能保存部分缓存行。已写入但尚未写回主存的高速缓存行被称为“脏（dirty）”。一旦写入，脏标志就会被清除。

为了能够在缓存中加载新数据，几乎总是首先需要在缓存中腾出空间。来自 L1d 的收回（eviction）将缓存行向下推到 L2（使用相同的缓存行大小）。这当然意味着必须在 L2 中腾出空间。这反过来可能会将内容推入 L3 并最终推入主内存。每次回收的成本都越来越高。这里描述的是现代 AMD 和 VIA 处理器首选的独占缓存（exclusive cache）模型。英特尔实现了包容性缓存（inclusive cache），其中 L1d 中的每个缓存行也存在于 L2 中。因此，从 L1d 驱逐要快得多。有了足够的二级缓存，在两个地方保存内容而浪费内存的缺点是最小的，并且在回收时得到了回报。独占缓存的一个可能优势是加载新的缓存行只需要触及 L1d 而不是 L2，这可能会更快。

只要不更改为处理器架构定义的内存模型，CPU 就可以随意管理缓存。例如，处理器利用很少或不使用内存总线活动并主动将脏缓存行写回主内存是可以的。 x86 和 x86-64 处理器之间、制造商之间甚至同一制造商的模型中的各种缓存架构都证明了内存模型抽象的力量。

在对称多处理器 (SMP symmetric multi-processor) 系统中，CPU 的高速缓存不能彼此独立工作。所有处理器都应该始终看到相同的内存内容。保持这种统一的内存视图称为“缓存一致性（cache coherency）”。如果一个处理器只看它自己的缓存和主存，它不会看到其他处理器中脏缓存行的内容。提供从另一个处理器直接访问一个处理器的缓存将非常昂贵并且是一个巨大的瓶颈。相反，处理器会检测另一个处理器何时想要读取或写入某个高速缓存行。

如果检测到写访问并且处理器在其缓存中具有缓存行的干净副本，则该高速缓存行被标记为无效（invalid）。未来的引用将需要重新加载缓存行。请注意，另一个 CPU 上的读取访问不需要失效，可以很好地保留多个干净的副本。

更复杂的缓存实现允许发生另一种可能性。假设一个处理器的缓存中的缓存行是脏的，而第二个处理器想要读取或写入该缓存行。在这种情况下，主内存已过期，请求处理器必须从第一个处理器获取缓存行内容。通过窥探（snooping），第一个处理器注意到这种情况并自动向请求处理器发送数据。这个动作绕过了主存，尽管在某些实现中，MC应该注意到这种直接传输并将更新的高速缓存行内容存储在主存中，如果访问是为了写入第一个处理器，则使其本地缓存行的副本无效。

随着时间的推移，已经开发了许多缓存一致性协议。最重要的是MESI，我们将在3.3.4节中介绍。所有这些的结果可以总结为几个简单的规则： • 任何其他处理器的缓存中都不呈现脏缓存行。 • 同一高速缓存行的干净副本可以驻留在任意多个高速缓存中。如果可以维护这些规则，即使在多处理器系统中，处理器也可以有效地使用它们的缓存。所有处理器需要做的就是监视彼此的写访问并将地址与本地缓存中的地址进行比较。在下一节中，我们将详细介绍有关实施的一些细节，尤其是成本。

最后，我们至少应该对与缓存命中和未命中相关的成本有一个印象。以下是 Intel 列出的 Pentium M 数据：

表格

这些是以 CPU 周期测量的实际访问时间。有趣的是，对于on-die L2 缓存访问时间的很大一部分（甚至可能是主要部分）是由线路延迟引起的。这是一个物理限制，它只会随着缓存大小的增加而变得更糟。只有缩小工艺（例如，在英特尔的产品阵容中，从 Merom 的 60nm 到 Penryn 的 45nm）才能改善这些数字。

表中的数字看起来很高，但幸运的是，不必为每次出现的缓存加载和未命中支付全部成本。部分成本是可以隐藏的。今天的处理器都使用不同长度的内部流水线，在这里指令被解码并准备执行。准备工作的一部分是从内存（或缓存）中加载值，如果它们被传输到寄存器。如果内存加载操作可以在流水线中足够早地启动，它可能会与其他操作并行发生，并且加载的整个成本可能会被隐藏。对于 L1d，这通常是可能的；对于一些具有长流水线的 L2 处理器也是如此。

提前启动内存读取有很多障碍。这可能就像没有足够的内存访问资源一样简单，也可能是由于加载的最终地址是另一条指令的结果。在这些情况下，负载成本不能（完全）隐藏。

对于写操作，CPU 不必等到值安全地存储在内存中。只要执行接下来的指令看起来与将值存储在内存中具有相同的效果，就没有什么可以阻止 CPU 走捷径。它可以提前开始执行下一条指令。借助可以保存常规寄存器中不再可用的值的影子寄存器（shadow register），甚至可以更改要存储的不完整写操作中的值。

图3.4

有关缓存行为影响的说明，请参见图 3.4。稍后我们将讨论生成数据的程序；它是一个程序的简单模拟，它以随机方式重复访问可配置数量的内存。每个数据项都有固定的大小。元素的数量取决于所选的工作集。Y 轴显示处理一个元素所需的平均 CPU 周期数；请注意，Y 轴的刻度是对数。这同样适用于 X 轴的所有此类图表。工作集的大小总是以 2 的幂表示。

该图显示了三个不同的平台。这并不奇怪：特定的处理器有 L1d 和 L2 缓存，但没有 L3。根据一些经验，我们可以推断出 L1d 的大小为 2¹³ 字节，而 L2 的大小为 2²⁰ 字节。如果整个工作集适合 L1d，则每个元素的每次操作周期低于 10。一旦超过 L1d 大小，处理器必须从 L2 加载数据，平均时间会上升到 28 左右。一旦 L2 不够时间再跳到 480 个周期甚至更多。这是许多或大多数操作必须从主存储器加载数据的时候。更糟糕的是：由于数据正在被修改，脏缓存行也必须被写回。

该图应该为研究有助于提高缓存使用率的编码改进提供足够的动力。我们在这里谈论的不是微不足道的百分之几的差异。我们谈论的是数量级的改进，这些改进有时是可能的。在第 6 节中，我们将讨论允许编写更高效代码的技术。下一节将详细介绍 CPU 缓存设计。这些知识是很好的，但对于论文的其余部分来说不是必需的。所以本节可以跳过。

3.3 CPU缓存实现细节

缓存实现者的问题是，巨大的主存中的每个单元都可能需要被缓存。如果程序的工作集足够大，这意味着有许多主存位置在争夺缓存中的位置。以前有人指出，高速缓存与主内存大小的比率为 1 比 1000 并不少见。

3.3.1 关联性

可以实现一个缓存，其中每个缓存行都可以保存任何内存位置的副本（参见图 3.5）。这称为完全关联缓存。为了访问高速缓存行，处理器内核必须将每个高速缓存行的标签与请求地址的标签进行比较。标签将由地址的整个部分组成，而不是缓存行的偏移量（这意味着，第 15 页上的图中的 S 为零）。

有一些缓存是这样实现的，但是通过查看当今使用的 L2 的数据，将表明这是不切实际的。给定一个 4MB 缓存和 64B 缓存行，该高速缓存将有 65,536 个条目。为了获得足够的性能，缓存逻辑必须能够在短短几个周期内从所有这些条目中挑选出与给定标签匹配的条目。为了实现这个需要需要花费很大的努力。

图3.5

对于每个高速缓存行，需要一个比较器来比较标签（注意，S 为零）。每个连接旁边的字母表示宽度（以位为单位）。如果没有给出，则大小为1位。每个比较器必须比较两个 T 位宽的值。然后，根据结果，选择适当的缓存行内容并使其可用。这需要合并与缓存桶（cache bucket）一样多的O数据行集。实现单个比较器所需的晶体管数量很大，特别是因为它必须工作得非常快。没有迭代比较器是可用的。节省比较器数量的唯一方法是通过迭代比较标签来减少它们的数量。因为相同的原因这不适合迭代比较器：它需要太长时间。

全关联高速缓存对于小型高速缓存很实用（例如，某些英特尔处理器上的 TLB（translation lookaside buffer）高速缓存是全关联高速缓存），但这些高速缓存很小，非常小。我们最多谈论几十个条目。

图3.6

对于 L1i、L1d 和更高级别的缓存，需要不同的方法。可以做的是限制搜索。在最极端的限制下，每个标签都映射到一个缓存条目。计算很简单：给定具有 65,536 个条目的 4MB/64B 缓存，我们可以使用地址的第 6 位到第 21 位（16 位）直接寻址每个条目。低 6 位是缓存行的索引。

这样一个直接映射缓存很快而且比较容易实现如图3.6所示。他只需要一个比较器，一个多路复用器（图中的两个，标签和数据是分开的，但这不是设计的硬性要求），以及一些仅选择有效缓存行内容的逻辑。由于速度要求，比较器很复杂，但现在只有一个；因此，可以花费更多的精力来加快速度。这种方法的真正复杂性在于多路复用器。简单多路复用器中的晶体管数量随 O(log N) 增长，其中 N 是高速缓存行的数量。这是可以容忍的，但可能会变慢，在这种情况下，可以通过在多路复用器中的晶体管上花费更多的空间来并行化一些工作和提高速度，从而提高速度。随着高速缓存大小的增加，晶体管的总数会缓慢增长，这使得该解决方案非常有吸引力。但它有一个缺点：只有当程序使用的地址相对于用于直接映射的位均匀分布时，它才能正常工作。如果它们不是，通常是这种情况，一些缓存条目被大量使用并因此被重复驱逐，而另一些则几乎不被使用或保持为空。

图 3.7：组关联缓存原理图

这个问题可以通过使缓存集关联来解决。组相联缓存结合了全相联缓存和直接映射缓存的优点，在很大程度上避免了这些设计的弱点。图 3.7 显示了组相联缓存的设计。标记和数据存储分为一组，其中一组由高速缓存行的地址选择。这类似于直接映射缓存。但是，缓存中的每个设置值不是只有一个元素，而是为相同的设置值缓存了少量值。并行比较所有集合成员的标签，这类似于完全关联缓存的功能。结果是一个缓存不容易被不幸或故意选择具有相同组号的地址所破坏，同时缓存的大小不受比较器数量的限制，可以经济地实现。如果缓存增长，（在此图中）只是增加的列数，而不是行数。只有当缓存的关联性增加时，行数（因此比较器）才会增加。今天的处理器对 L2 高速缓存或更高的缓存使用了高达 24 的关联级别。 L1 缓存通常使用 8 组。