－－－

第 6 章

H A P T E R 6

存储器层次结构 #

到目前 为止，在对系 统的研究中， 我们依赖千一 个简单的计算机系统 模型， C P U 执行指令，而 存储器系统为 CP U 存放指令和数据。在简单模型中， 存储器系统是一个线性的字节数组， 而 CP U 能够在一个常数时间内访问每个存储器位置。虽然迄今为止这都是一个有效的模型， 但是它没有反映现代系统 实际工作的方式。

实际上， 存储器 系统( m em o r y s ys te m ) 是一个具有不同容量、成本和访问 时间的存储设备的层 次结构。CP U 寄存器保存着最常用的数据。靠近 C P U 的小的、快 速的 高速 缓存存储器 ( cache memor y) 作为一部分存储在相对慢速的 主存储器( main mem o r y ) 中数据和指令的缓冲区域。主存缓存存储在容量较大的、慢速磁盘上的数据，而这些磁盘常常又作为 存储在通过网络连接的其他机器的磁盘或磁带上的数据的缓冲区域。

存储器层次 结构是可行的，这 是因为与下 一个更低层次的存储设备相比来说， 一个编写良好的程序倾向千更频繁地访问某一个层次上的存储设 备。所以， 下一层的存储设备可以更慢速 一点，也 因此可以更大， 每个比特位更便宜。整体效果是一个大的存储器池， 其成本与 层次结构底层最便宜的存储设备相当， 但是却以接近于层次结构顶部存储设备的高 速率向程序 提供数据。

作为一个 程序员 ， 你需要理解存储器层次结构， 因为它对应用程序的性能有着巨大的影响。如果你的程序需要的数据是存储在 C P U 寄存器中的 ， 那么在指令的执行期间， 在 0 个周期内 就能访问 到它们。如果存储在高速缓存中，需 要 4 ~ 75 个周期。如果存储在主存中，需要上百个周期 。而如果存 储在磁盘上，需 要 大约几千万个周期！

这里就是计算机系统中一个基本而持久的思想：如果你理解了系统是如何将数据在存 储器层次结构中上上下下移动的，那么你就可以编写自己的应用程序，使得它们的数据项 存储在层次结构 中较高的地方 ， 在那里 CP U 能更快地访问到它们。

这个思想围 绕着计算 机程序的一 个称为局部性 (l oca lit y ) 的基本属性 。具有良好局部性的程序倾向于一次又一次地访问 相同的数据项集合 ， 或是倾向于访问 邻近的 数据项集合。具有良好局部性的程序比局部性差的程序更多 地倾向 于从存储器层次 结构中较高层次处访问数据项， 因此运行得更快。例如， 在 C ore i7 系统， 不同的矩阵乘法核心程序执行相同数量的算术操作， 但是有不同程度的局部性， 它们的运行时间可以 相差 40 倍！

在本章中 ， 我们会看看基本的存储技术一 SRA M 存储器、DRAM 存储器、ROM 存储器以及旋转的 和固态的硬盘一一－并描述它们是如何被组织成层次结 构的。特别地， 我们将注意力集中在高 速缓存存储器上， 它是作为 C P U 和主存之间的缓存区域， 因为它们对应用程序性能的 影响最大。我们向你展示如何分析 C 程序的 局部性， 并且介绍改进你的程序中局部性的技术。你还会学到一种描绘某台机器上存储器层次结构的性能的有趣方法， 称为“ 存储器山( memor y mountain)", 它展示出读访问时间是局部性的一个函数。

1. 1 存储技术

   计算机技术的成 功很大程度上源自于存储 技术的 巨大进步。早期的计算机只有几千字

节的随机访问存储器。最早的 IBM PC 甚至千没有硬盘。1982 年引入的 IBM PC-XT 有 l OM 字节的磁盘。到 2015 年，典 型的计算机巳有 300 000 倍于 PC-XT 的磁盘存储，而且磁盘的容量以每两年加倍的速度增长。

1. 1. 1 随机访问存储器

   随机访问存储 器( Ra ndom- Access Memory, R AM ) 分为两类 ： 静态的 和动态的 。静态RA M CS RAM ) 比动态 R A M ( DRAM ) 更快， 但也贵得多。SR A M 用来作为高速缓存存储器，既 可以在 CP U 芯片上 ， 也可以在片下。DR AM 用来作为主存以及图形系统的帧缓冲区 。典 型地， 一个桌面系统的 SRAM 不会超过几兆字节， 但是 DRA M 却有几百 或几千兆字节。

   1. 静态 RAM

      SR AM 将每个位 存储在一个双稳 态的 ( bista ble ) 存储器单元里。每个 单元是用一个六晶体管电路来实现的。这个电路有这样一个属性，它可以无限期地保持在两个不同的电压 配置( config ur a tion ) 或状态( s tate) 之一。其他任何状态都是不稳定的一 从不稳定状态开始， 电路会迅速地转移到 两个稳定状态中的一个。这样一个存储器单元类似于图 6-1 中画出的倒转的钟摆。

之 #

图 6-l 倒转的钟摆 。同 SRAM 单元一样，钟摆只有两个稳定的 配置或状态

当钟摆倾斜到最 左边或最右边时 ，它 是稳定的。从其他任何位置， 钟摆都会倒向一边或另一边。原则上， 钟摆也能 在垂直的 位置无限期地保待 平衡 ， 但是这个状态是亚稳 态的

(metastable) 最细微的 扰动也能使它倒下， 而且一旦倒下就永远不会再恢 复到垂直的位置。

由于 SRAM 存储器单元的双稳 态特性，只 要有电， 它就会永远地保持它的值。即使有干扰（例如电子噪音）来扰乱电压， 当干扰消除 时， 电路就会恢复到稳定值。

2 动 态 RAM

DR AM 将每个位存储 为对一个电 容的充电。这个电容非常小， 通常只有大约 30 毫微

微法拉 Cfe mtofarad ) - —- 3 0 X 10- is 法拉 。不过， 回想一下法拉是一个非常大的计量单位．

DR A M 存储器可以制造得 非常密集 每个单元由一个电容和一个访问晶体管组成。但是，与 SR AM 不同， D RAM 存储器单元对 干扰非常敏感。当电容的电压被扰乱之后，它就永 远不会恢复了。暴露在光线下会导致电容电压改变。实际 上， 数码照相机和摄像机中的 传感器本质上就是 DR AM 单元的阵列 。

很多原因会导致漏电 ， 使得 DR AM 单元在 10 ~ 100 毫秒时间内 失去电荷。幸运的是， 计算机运行的时钟周期是以纳秒来衡撒的 ， 所以相对而言这个保持时间是比较长的。内存系统必须周期性地通 过读出， 然后重写来 刷新内存 每一位 。有些系统也使用纠错码， 其中计算机的字会被多编码几个位（例如 64 位的字可能用 72 位来编码）， 这样一来， 电路可以发现并纠正一个字中任何单个的错误位。

图 6-2 总结 了 SRAM 和 DRAM 存 储器的特性。只要有供电， SR AM 就会保持不变。与 DRAM 不同 ， 它不需要刷新。SRAM 的 存取比 DRAM 快。SRAM 对诸 如光和电噪声这样的干扰不敏感。代价是 SRAM 单元 比 DRAM 单 元 使 用 更 多 的 晶 体 管 ， 因 而 密集度低，而且更贵，功耗更大。

SRAM DRAM

1. 传统的 D R A M

   了1二I :心：

   图 6-2 DR AM 和 SR AM 存储器的特性

DRAM 芯片中的单元（位）被分成 d 个超单元( supercell) , 每个超单元都由 w 个 DRAM 单元组 成。一个 d X w 的 DRAM 总共存 储了 dw 位信息。超单元被组织成一个 r 行 c 列的长方形阵列， 这里 rc= d。每个超单元有形如Ci , j ) 的 地址，这 里 1 表示行，而 ）表示列。

例如，图 6-3 展示的是一个 16X 8 的 DRAM 芯片的组织，有 d = 16 个超单元， 每个超单元有 w= 8 位， r = 4 行 ，c= 4 列。带阴影的方框表示地址( 2’ 1) 处 的 超 单 元 。 信 息 通过称为引脚 ( pin) 的外部连接器流入和流出芯片。每个引脚携带一个 1 位的信号。图 6-3 给出了两组引脚： 8 个 dat a 引脚，它们 能 传 送一个字节到芯片或从芯片传出一个字节，以 及 2 个 addr 引脚， 它们携带 2 位的行 和列超单元地址。其他携带控制信息的引脚没有显示出来。

DRAM芯片

；

2 ：

a/ddr►,:

｀

列

0 I 2 3

. , 1-丁 I

（佥到C氐PU吵)

控内制存器 2

3

超单元

( 2 , I )

j

d a 七a

图 6-3 一个 128 位 16 X 8 的 DRA M 芯片的高级视图

m 关千术语的注释

存储领域从来没有为 DRAM 的阵列 元素确 定一个标准的 名 字。 计算机构架师倾向于称 之为 “ 单元“，使 这个术语 具有 DRAM 存储 单元 之 意。电路 设 计 者倾向 于称之为

“宇＂，使之 具 有 主存一个字之 意。为 了避 免混淆， 我们采用 了无歧 义的术语“超单元”。

每个 DRAM 芯片被连接到某个称为内存控制 器 ( memory cont roller) 的电路， 这个电路可以一次传送 w 位到每个 DRAM 芯片或一次从每个 DRAM 芯片传出 w 位。为了读出超单元( i , j ) 的内容，内 存控制器将行地址 t 发送到 DRAM , 然后是列地址 J。 DRAM 把 超单元( i , j ) 的内容发回给控制器作为响应。行 地址 t 称为 RAS ( Row Access Strobe, 行访间选 通脉冲）请求。列地址 ］称为 CAS ( Column Access Strobe, 列访问选通脉冲）请求。注意， RAS 和 CAS 请求共享相同的 DRAM 地址引脚。

例如，要 从 图 6-3 中 16 X 8 的 DR AM 中读出超单元 ( 2 , 1), 内存控制器发送行地址

2’ 如 图 6-4a 所示。DRAM 的响应是将行 2 的整个内容都复制到一个内部行缓 冲区。接下来 ，内 存 控 制器发送列地址 1 , 如图 6-46 所示。DRAM 的响应是从行缓冲区复制出超单元 ( 2’ 1) 中 的 8 位 ，并 把它们发送到内存控制器。

DRAM芯片 DRAM芯片

： 列 ！

内存

控制器

addr

data

, …………………………..内……部……行……缓……冲..区……………….,

、……………………..内………..行….缓…..冲…..区………………：

a ) 选择行 2 ( RAS请求）

b ) 选择列 I ( CAS 请求） 图 6- 4 读 一 个 DRAM 超单元的内容

电路设计者将 DRAM 组织成二维阵列而不是线性数组的一个原因是降低芯片上地址

引 脚 的 数 晕 。 例 如 ，如 果 示 例 的 1 28 位 DRA M 被组织成一个 16 个超单 元的线 性数组，地址 为 0 ~ 15 , 那么芯片会需要 4 个地址引脚而不是 2 个 。二维阵列 组织的缺点是必须分两步 发 送 地址， 这增加了访问时间。

2. 内存模块

   DRAM 芯片封装在内存模 块( memory mod ule ) 中 ， 它 插到主板的扩展槽上。Core i7

   系统使用的 240 个引脚的双列直插内存模块( Dua l lnline Memory Module, DIMM), 它以

   64 位为块传送数据到内存控制器和从内存控制器传出数据。

   图 6-5 展示了一个内存模块的基本思想。示例模块用 8 个 64 Mbit 的 8 M X 8 的 DRAM 芯 片 ，总共 存储 64MB(兆字节）， 这 8 个芯片编号为 0~ 7。每个超单元存储主存的一个字节，而 用 相 应超 单元 地址 为(i’ j ) 的 8 个超单元来表示主存中字节地址 A 处的 64 位字。在图 6-5 的 示例中， DRAM O 存储第一个（低位）字节， DRA M 1 存储下一个字节，依 此类 推。

   要取出内存地址 A 处的一个字，内 存 控制器将 A 转换成一个超单元地址( i’ j )’ 并将它 发 送 到 内 存 模 块 ， 然 后 内 存 模 块 再 将 t 和 ］ 广播 到 每个 DRAM。作 为响应， 每个DR A M 输出它的( i’ j ) 超 单 元 的 8 位内容。模块中的电路收集这些输出，并 把 它们合并成一 个 64 位字，再 返 回 给内存控制器。

   通过将多个内存模块连接到内存控制器，能 够 聚 合 成 主 存 。 在 这 种 情 况 中 ， 当控制器收 到 一 个 地 址 A 时 ， 控制器选择包含 A 的模块 k’ 将 A 转换成它的 ( i’ j ) 的 形 式，并将( i’ j ) 发 送 到 模 块 k。

   练习题 6. 1 接下来， 设 r 表 示 一个 DR AM 阵列 中的行数， c 表 示 列 数， br 表 示行寻址所需的位数，从 表 示 列 寻址所 需 的位数。 对于下 面 每个 DRAM , 确定 2 的 幕数的

阵列 维数，使 得 max(rb , be ) 最小， ma x( rb

较 大的值 。

, b, ) 是对阵 列 的行或列 寻址所需的位数中

addr (row= i, col= j)

63 5655 4847 4039 3231 2423 1615 8 7 0

I I I I I I I I I #

位于主存地址 A处的64位字

口：超单元 ( i’ 八

由8个8M x 8的

DRAM组成的64MB

内存模块

内存

控制器

3. 增强的 DRAM

   图 6-5 读一个内存模块的内容

有许多种 DRAM 存储器， 而生产厂商试图跟上迅速增长的处理器速度， 市场上就会定期推 出新的种类。每种都是基于传统的 DRAM 单元， 并进行一些优化， 提高访问基本

DRAM 单元的速度。

• 快页模 式 DRAM CFast Page Mode DRAM, FPM DRAM ) 。传统的 DRAM 将超单元的 一整行复制到它的内部行缓 冲区中， 使用一个， 然后丢弃剩余的。FPM

  DRAM 允许对同一行连续地访问可以 直接从行缓冲区 得到服务，从 而改进了这一点。例如，要从 一个传统的 DRAM 的行 t 中读 4 个超单元，内 存控制器必须发送 4 个 RAS / CAS 请求， 即使是行地址 1 在每个情况中都是一样的。要从一个 FPM DRAM 的同一行中读取超单元，内 存控制器发送第一个 RAS/ CAS 请求， 后面跟三个 CAS 请求。初始的RAS/ CAS请求将行1 复制到行缓冲区， 并返回 CAS 寻址的那个超单元。接下来三个超单元直接从行缓冲区获得，因此返回得比初始的超单元更快。

• 扩展数据捡出 DRAM ( Extended Data Out DRAM, EDO DRAM) 。FP M DRAM 的一个增强的形式，它允 许各个 CAS 信号在时间上靠得更紧密一点 。

• 同步 DRAM(Synchronous DRAM, SDRAM)。就它们与内存控制器通信使用一组显式的控制信号来说， 常规的、FPM 和 EOO DRAM 都是异步的。SDRAM 用与驱动内存控制器相同的外部时钟信号的上升沿来代替许多这样的控制信号。我们不会深入讨论细节， 最终效果就是SDRAM能够比那些异步的存储器更快地输出它的超单元的内容。

  • 双倍 数据速 率 同 步 DRAM ( Double Data-Rate Synchronous DRAM, DOR SDRAM )。DDR SDRA M 是对 S DRA M 的一种增强， 它通过使用两个时钟沿作为控制信号， 从 而使 DR AM 的速度翻倍。不同类型的 DOR SDRA M 是用提高有效 带宽的很小的预取缓冲区的大小来划分的： DDR( 2 位）、DDR2( 4 位）和DDR( 8 位）。

  • 视 频 RA M( Video RAM, VRAM ) 。它用在图形系统的帧缓冲区中。 VRAM 的思想与 FPM DRAM 类似。两个主要区别是： 1) VRAM 的输出是通过依次对内部缓冲区的整个内 容进行移位得到的； 2) V R AM 允许对内存并行地读和写。因此， 系统可以在写下一次更新的新值（写）的同时，用帧缓冲区中的像素刷屏幕（读）。

    田日DRAM 技术流行的 历史

    直到 1995 年， 大 多 数 PC 都是 用 F P M DRAM 构 造的。1 996 1999 年， EDO DR AM 在市场 上占 据了主 导， 而 F P M DRAM 几乎销声 匿迹 了。 SD RAM 最早 出现在199 5 年的 高端 系统中， 到 2002 年， 大 多 数 PC 都是用 SDR AM 和 DOR SDR AM 制造的。到 2010 年之前， 大多数服务器和 桌面 系统都是 用 D DR3 SDRAM 构造的。 实际上， Intel Core i7 只支持 DDR3 SDRAM。

    6 非易失性存储器

    如果断电， DRAM 和 SR AM 会丢失它们的信息， 从这个意义上说， 它们是易失的 ( vola tile) 。另一方 面，非易 失性 存储器 ( nonvola tile memory ) 即使是在关电 后， 仍然保存着它们的信息。现在有很多 种非易失性存储器。由于历史原因， 虽然 RO M 中有的类型既

    可以读也 可以写， 但是它们整体上都被 称为 只读 存储 器 C Read-Only Memory, ROM)。ROM 是以它们能够被重编 程（写）的次数和对它们 进行重编程所用的机制来区分的。

    PROM(Programmable ROM, 可编程 RO M ) 只能被编程一次。P ROM 的每个存储器单元有一种熔丝 ( fuse) , 只能用高电 流熔断一次。

    可掠 写 可编 程 RO M (Erasable Programmable ROM, EPRO M ) 有一个透明的石英窗口，允 许光到 达 存储单元。紫 外线 光 照射 过 窗 口， EP RO M 单 元就被 清 除 为 0。对E PR O M 编程是通过使用 一种把 1 写入 EP RO M 的特殊设备来完成的。EP RO M 能够被擦除和重编程的次 数的数量级可以达到 1000 次。电 子 可擦 除 PRO M C Electrically Erasable PROM, EEPROM) 类似于 EP RO M , 但是它不需要一个物理上独立的编程设备，因此可以直接在印 制电路卡上编程。E EP RO M 能够被编程的次 数的数量级可以达到 105 次。

    闪存 ( flas h memory )是一类非易失性存储器， 基于 EE PRO M , 它已经成为了一种重要的存储技术 。闪存无处不在， 为大量的电子设备提供快速而持久的非易失性存储， 包括数码相机、手机、音乐 播放器、PDA 和笔记本、台式机和服务器计算机系统。在 6. 1. 3 节中， 我们会仔细研究一种新型的基于闪存的磁盘驱动器， 称为 固 态硬 盘 C Solid State Disk, SSD), 它能提供相对千传统旋转磁盘的一种更快速、更强健和更低能耗的选择。

    存储在 RO M 设备中的程序通 常被称为固件 ( firmware) 。当一个计算机系统通电以后， 它 会运行存储在 ROM 中的固件。一些系统在固件中提供了少最基本的输入和输出函数一 例如 PC 的 BIOS( 基本输入／输出系统）例程。复杂的设备， 像图形卡和磁盘驱动控

制器， 也依赖固件翻译来自 CP U 的 I / 0 ( 输入／输出）请求。

7. 访问主存

数据流通过 称为总线 ( bus ) 的共享电子电路在处理器和 DRA M 主存之间来来 回回。 每次 CPU 和主存之间的数据传送都是通过一系列步骤来完成的， 这些步骤称为 总线事务(bus t ransact io n) 。读事务 ( read t ra nsactio n) 从主存传送数据到 CP U。写事务 ( write trans­ action) 从 CPU 传送数据到主存。

总线是一组并行的导线， 能携带地址、数据和控制信号 。取决千总线 的设计，数 据和地址信号可以共享同一组导线，也可以使用不同的。同时，两个以上的设备也能共享同一 总线。控制线携带的 信号会同步事务，并标识出当前正在被 执行的事务的类型。例如， 当前关注的这 个事务是 到主存的吗？还是到诸如磁盘控制器这 样的其他 I / 0 设备？ 这个事务是读还是写？ 总线上的信息是地址还是数据项？

图 6-6 展示了一个示例计算机系统的配置。主要部件是 CPU 芯片、我们将称为 1/ 0

桥接器 CI / 0 bridg e )的芯片组（其中包括内存控制器）， 以及组成主存的 DR AM 内存模块。这些部 件由一对总线连接起来， 其中一条总线是 系统总线( s ys tem bus ) , 它连接 CP U 和1/ 0 桥接器 ， 另一条总线是内存 总线( memor y bus) , 它连接 1/ 0 桥接器 和主存。1/ 0 桥接器将系 统总线的电子信号翻译成内 存总线的电子信号。正如我们看到的那样， I / 0 桥也将 系统总线和内存总线连接到 I/ 0 总线， 像磁盘和图形卡这样的 1/ 0 设备共享 1/ 0 总线。不过现在，我 们将注意力 集中在内存总线上。

CPU芯片

系统总线

总线接口 三

内存总线

I

图 6-6 连接 C P U 和主存的总线结构示例

m 关千总线设计的 注释

总线设 计是计算机 系统一个复杂而且 变化迅速的方面 。 不同的 厂商提 出了不同的 总线体系结构，作为产品 差异化的一种方法 。例如， Intel 系统使用称 为北桥 ( northbridg e) 和南桥(so uth bridge)的芯片组分别 将 CPU 连接到内存和 1/ 0 设备。在比较老的 Pent ium 和Core

2 系统中， 前端总 线( Fr ont Side Bus , FSB) 将 CPU 连接到北桥 。来自 AMD 的 系统将 FSB

替换为超传输 ( H yperTransport ) 互联 ， 而更新一些的 Intel Core i7 系统使用的 是快速通道

(QuickPath) 互联。这些不同 总线体 系结构的细节超 出了 本书的 范围。反之， 我们会使 用图6-6 中的 高级 总线体系结构作 为一 个运行 示例贯穿本书。 这是一个简单但是有用的 抽象， 使得我们可以很 具体， 并且可以 掌握主要思想而不必与任何私有设计的 细节绑得 太紧。

考虑当 CP U 执行一个如下加载操作时会发生什么

movq A,%rax

这里， 地址 A 的内容被加载到寄存器%r a x 中。CP U 芯片上称为总线接 口( bus interface )

的电路在总线上发起读事务。读事务是由三个步骤组成的。首先， CPU 将地址 A 放到系统 总 线 上 。 I / 0 桥将信号传递到内存总线（图6- 7a ) 。接下来，主 存 感 觉 到 内 存 总 线 上的地址 信 号 ，从 内 存 总 线 读 地址，从 DRAM 取出数据字 ，并 将 数 据 写 到内存总线。I/ 0 桥将内 存 总 线 信 号 翻译成系统总线信号， 然后沿着系统总线传递（图6-7 b ) 。最后， CPU 感觉到系统总线上的数据，从 总 线上 读数据，并 将 数 据 复 制到寄存器%r a x ( 图 6- 7c) 。

寄存器文件

总 线 接口

I / 0 桥

I I

VO桥

二 I I X

总线接 口

c ) CP U从总线读 出字x, 并将它复制到寄存器 % r a x中图 6- 7 加 载操作 mo vqA, %r a x 的内存读事务

反过来， 当 CPU 执行一个像下面这样的存储操作时

movq %rax,A

这里， 寄 存器 %r a x 的 内 容 被写到地址 A , CPU 发起写事务。同样， 有三个基本步骤。首先，

CPU 将地址放到系统总线上。内存从内存总线读出地址， 并 等待 数 据 到 达（图 6-8a) 。接下来 ， CPU 将%r a x 中 的 数 据 字 复 制到系统总线（图6-8 6 ) 。最后， 主 存 从 内 存总线读出数据字 ，并 且 将这些位存储到 DRAM 中（图 6-8 c ) 。

6. 1. 2 磁盘存储

磁盘是广为应用的保存大量数据的存储设备，存 储 数 据 的 数 量 级 可 以 达到儿百到几千千 兆 字节， 而基 千 RAM 的存储器只能有几百或几千兆字节。不过，从 磁 盘 上 读 信息 的时间 为毫秒级，比 从 DRAM 读慢了 10 万倍， 比从 S RAM 读慢了 100 万倍。

寄存器文件

亳c a

，

总线接口

VO桥

I I A

a ) CPU将地址A放到 内存 总 线。主存读出这 个 地址 ，并等待数据字寄存器文件

主存

y

b ) CPU将数据字y放到总线上

寄存器文件

hax

总线接口

c ) 主存从总线读数据字y , 并将它存储在地址A

图 6-8 存 储 操 作 mo vq %r ax , A 的 内 存 写 事 务

i 磁盘是由 盘片 ( plat t e r ) 构成的。每个盘片有两面或者称为表 面 ( s ur fa ce ) , 表面覆盖着磁性记录材料。盘片中央有一个可以旋转的主轴 ( s pin dle) , 它使得盘片以固定的旋转速率(rota tion al ra te) 旋转， 通常是 5400 1 5 000 转每分钟( Revol u t io n Per M in ute , RP M) 。磁

i 盘通常 包含一个或多个这样的盘片， 并封装在一个密封的容器内。

卜 图 6- 9a 展示了一个典型的磁盘表面的结构。每个 表面是由一组称为磁道( t rac k ) 的同

！勺 心圆组 成的。每个磁 道被划分为一组扇区 ( s e cto r ) 。 每个 扇区包含相等数量的数据位（通常叱 是 512 字节）， 这些数据编码在扇区上的磁性材料中。扇区之间由一些间隙 ( ga p ) 分 隔 开，

这些间隙中不存 储数据位。间隙存储用来标识扇区的格式化位。

磁盘是由 一个或多个叠放在一起的盘片组成的，它 们被封装在一个密封的包装里， 如图 6-9b 所示。整个装置通常被称为磁盘驱动 器( d is k drive ) , 我们通常简称为磁盘( dis k ) 。有时 ， 我们会称磁盘为 旋转磁盘 ( ro t at ing dis k ) , 以使之区别千基于闪 存的 固 态硬盘(SSD), SSD 是没有移动部分的 。

磁盘制 造商通常用术 语柱面 ( cy linde r ) 来描述多个盘片驱动器的构造， 这里， 柱面是所有盘片表面上到主轴中心的距离相等的磁道的集合。例如， 如果一个驱动器有三个盘片和六个面 ， 每个表面上的磁道的编号都是一致的， 那么柱面 k 就是 6 个磁道 k 的集合。

a ) 一个盘片的视图

图 6-9 磁盘构造

柱面k

主轴

b ) 多个盘片的视图

盘片0 盘片1 盘片2

2. 磁盘容量

一个磁盘上可以记录的最大位数称为它的最大容量，或 者 简 称 为 容 量。磁盘容量是由以下 技术因素决定的：

• 记录密度 ( recording density)( 位／英寸）： 磁道一英寸的段中可以放入的位数。·

• 磁 道密度 ( t rack de nsit y) ( 道／英寸）： 从 盘片中心出发半径上一英寸的段内可以 有的磁道数。

• 面 密度 ( a rea l density)( 位／平方英寸）： 记 录密度与磁道密度的乘积。

  磁盘制造商不懈地努力以提高面密度（从而增加容量），而 面密度每隔几年就会翻倍。最初 的磁 盘， 是 在 面密度很低的时代设计的，将 每个磁道分为数目相同的扇区， 扇区的数目是由最靠内的磁道能记录的扇区数决定的。为了保持每个磁道有固定的扇区数，越往外 的磁道扇区隔得越开。在面密度相对比较低的时候，这种方法还算合理。不过，随着面密 度的提高，扇区之间的间隙（那里没有存储数据位）变得不可接受地大。因此，现代大容蜇 磁盘使用一种称为多 区记 录( multip le zone recordi ng ) 的技术，在 这种技术中，柱 面的集合被分割成不相交的子集合，称 为记录区 ( recordi ng zone) 。每个区包含一组连续的柱面。一个区中的每个柱面中的每条磁道都有相同数量的扇区，这个扇区的数量是由该区中最里面的 磁道所能包含的扇区数确定的。

  下面的公式给出了一个磁盘的容量：

磁 盘容 量 =

字节数 X 平均扇区数 磁道数 X 表面数 X 盘片数扇区 磁道 表面 盘片 磁盘

例如， 假设我们有一个磁盘， 有 5 个盘片， 每个扇区 512 个字节， 每个面 20 000 条磁道， 每条磁道平均 300 个扇区。那么这个磁盘的容量是：

磁盘容量= 512 字 节 X 30 0 扇 区 20 000 磁道 X 2 表面 5 盘 片扇区 磁道 表面 盘片 磁盘

= 30 720 000 000 字 节

= 30. 72 GB

注意， 制 造商是以千兆字节CGB) 或兆兆字节 ( T B) 为单位来表达磁盘容量的，这里

l GB= l 沪字 节 ， 1 T B= 1012 字 节 。

田 日 － 千兆字节有多大

不幸地 ，像 K C k ilo ) 、M( mega) 、G( giga) 和 T ( tera ) 这样的前缀的含义依 赖 于上下

文。对于与 DR A M 和 SR AM 容量相 关的 计量单位， 通常 K = 210 , M = 220 , G = 2 气 而

T = 2o4

。 对 于与 像 磁 盘和网 络 这样的 I/ 0 设 备 容 量相关的 计 量 单位， 通常 K = 103 ,

M = l 06 , G = l 0 9 , 而 T = l O气 速 率和吞吐量常常也使 用这些前缀。

幸运地，对于我们通常依赖的不需要复杂计算的估计值，无论是哪种假设在实际中 都工作 得很好。例如， 230 和 10 9 之 间 的相 对差 别 不 大： ( 230 - 10 勹 / 10 9 :::::::::7 % 。 类 似，

( 240 - 1 0 12 ) / 101 2:::::::::1 0 % 。

练习题 6. 2 计算这 样一个 磁盘的容量， 它 有 2 个 盘 片 ， 10 000 个柱 面， 每条磁 道平均有 400 个扇 区 ， 而每 个扇 区有 51 2 个字 节。

3 磁盘操作

磁盘用读／写 头( rea d/ writ e hea d ) 来读写存储在磁性表面的位， 而 读 写 头 连接到一个传动 臂( act uator arm ) 一端，如 图 6- l Oa 所示。通过沿着半径轴前后移动这个传动臂， 驱动器可以 将读／写头定位在盘面上的任何磁道上。这样的机械运动称为寻道( seek ) 。一旦读／ 写头定位到了期望的磁道上， 那么当磁道上的每个位通过它的下面时，读 ／写 头 可 以 感 知到这个位的值（读该位），也可以修改这个位的值（写该位）。有多个盘片的磁盘针对每个盘 面都有一个独立的读／写头 ， 如 图 6-1 0 6 所 示。读／写头垂直排列， 一 致 行 动 。 在 任何时刻， 所有的读／写头都位于同一个柱面上。

磁盘表面以固定 ,,,..,,,的旋转速率旋转 ／

,/

读／写头连到传动臂的末端．在磁盘表面上一层薄薄的气垫上飞翔

主轴

a ) 一个盘片的视图

图 6-10

磁盘的动态特性

b ) 多个盘片的视图

在传动臂末端的 读／写头在磁盘表面高度大约 0. 1 微米处的一层薄薄的气垫上飞翔（就是字面上这个意思），速度大约为80 km/ h。这可以比喻成将一座摩天大楼( 442 米高）放倒，然 后让 它在距离 地面 2. 5 cmCl 英寸）的高度上环绕地球飞行，绕 地球一天只需要 8 秒钟！在这样小的间隙里，盘 面上一粒微小的灰尘都像一块巨石。如果读／写头碰到了这样的一块巨石，读 ／写 头会停下来， 撞到盘面一 所谓的读／写头冲撞 ( head crash ) 。为此，磁盘总是 密封包装的。

磁盘以扇区大小的块来读写数据。对扇区的 访问 时间 ( acces s t im e ) 有 三个主要的部分： 寻道 时间 ( see k t im e ) 、旋转时间( rot at io na l la t ency ) 和传送时间 ( t ra ns fe r time) :

• 寻道时间： 为了读取某个目标扇区的内容， 传 动 臂 首 先 将 读／写 头 定 位到包含目标扇区的磁道上。移动传动臂所需的时间称为寻道时间。寻道时间 T,eek 依 赖于读／写头以前的位置和传动臂在盘面上移动的速度。现代驱动器中平均寻道时间 T avg seek 是 通过对几千次对随机扇区的寻道求平均值来测扯的， 通常为 3 9 ms 。一次寻道的最大时间 T max seek 可 以 高 达 20 ms 。
• 旋转时间： 一旦读／写头定位到了期望的磁道， 驱动器等待目标扇区的第一个位旋转到读／写头下。这个步骤的性能依 赖于当读／写头到达目标扇区时盘面的位置以及磁盘的旋转速度。在最 坏的情况下， 读／写头刚刚错过了目标扇区，必 须 等待磁盘转一整圈。因此，最大旋转延迟（以秒为单位）是

Tmax rotation=

RPM

X 60s

lmin

平均旋转时间 Tavg rotation是 Tmax rotation的 一半。

• 传送时 间： 当目标扇区的 第一个位位千读／写头下时， 驱动器就可以 开始读或者写该扇区的内容了。一个扇区的 传送时间依赖于旋转速度和每条磁道的扇区数目。因此，我们可以粗略地估计一个扇区以秒为单位的平均传送时间如下

  T = l X 1 X 60s

  avg transfer RPM ( 平均扇 区数 ／ 磁道） lmin

  我们可以估计访问一个磁盘扇区内容的平均时间 为平均 寻道时间、平均旋转延迟和平均传送时间之和。例如，考虑一个有如下参数的磁盘：

  参数 值

旋转速率

T,vg江 , k

每条磁道的平均扇区数

7200RPM

9ms

400

对于这个磁盘， 平均旋转延迟（以ms 为单位）是

Tavg rotauon = 1 / 2 X T max rotation = 1 / 2 X ( 60s / 7200 RPM) X 1000 ms / s ::::,::: 4 ms

平均传送时间是

Tavg transfer = 60/ 7200 RPM X 1/ 400 扇 区／ 磁道 X 1000 ms / s ::::,::: 0. 02 ms

总之，整个估计的访问时间是

Taccess = T, vg seek + T avg rotation + T ,vg transfer = 9 ms+ 4 ms + o. 02 ms = 13. 02 ms

这个例子说明了一些很重要的间题：

• 访问一个磁盘扇区中 512 个字节的时间主要是寻道时间和旋转延迟。访问扇区中的第一个字节用了很长时间， 但是访问剩下的字节几乎不用时间。

• 因为寻道时间 和旋转延迟大致相 等， 所以将寻道时间乘 2 是估计磁盘访问时间的简单而合理的方法。

• 对存储在 SR AM 中的一个 64 位字的访问时间大约是 4n s , 对 DRAM 的访问时间是

  60ns 。因此， 从内存中读一个 512 个字节扇区大小的块的时间对 SR AM 来说大约是

  256n s , 对 DRAM 来说大约是 4000ns 。磁盘访问 时间， 大约 l Oms , 是 SRAM 的大约 40 000 倍， 是 DR AM 的大约 2500 倍。

  沁因 练习题 6. 3 估计访问 下面这个缢盘上 一个扇 区的访问 时间（以 ms 为单 位）：

参数

旋转速率

Tavg seek

每条磁道的平均扇区数

值

15 000RPM

8 ms

500

1. 逻辑磁盘块

   正如我们看到的那样， 现代磁盘构造复杂， 有多个盘面， 这些盘面上有不同的记录区 。 为了对操作系统隐藏这样的复杂性， 现代磁盘将它们的构造呈现为一个简单的视图，

一个 B 个扇区大小的逻辑块的序列， 编 号 为 o, 1, …， B —1 。 磁 盘 封装中有一个小的硬件／固件设备，称 为磁 盘控制器，维 护 着 逻辑块号和实际（物理）磁盘扇区之间的映射关系。

当操作系统想要执行一个1/0 操作时 ，例 如读一个磁盘扇区的数据到主存，操 作 系统会发

送一个命令到磁盘控制器 ，让 它读某个逻辑块号。控制器上的固件执行一个快速表查找， 将一个逻辑块号翻译成一个（盘面， 磁 道， 扇区）的三元组， 这个三元组唯一地标识了对应的物理扇区。控制器上的硬件会解释这个三元组， 将读／写头移动到适当的柱面， 等 待 扇区移动到读／写头下， 将读／写头感知到的位放到控制器上的一个小缓冲区中，然后 将它们复制到主存中。

m 格式化的磁盘容量

磁盘控制器必须对磁盘进行格式化，然后才能在该磁盘上存储数据。格式化包括用 标识扇区的信息填写扇区之间的间隙，标识出表面有故障的柱面并且不使用它们，以及 在每个 区中预留出一 组柱面作 为备 用，如 果 区中一个或多 个柱 面在磁盘使用过程中坏掉了， 就可以使 用这 些备 用的 柱面。 因 为存 在 着这些备 用的 柱面， 所以磁盘制造商所说的格式化容量比最大容量要小。

练习题 6. 4 假设 1MB 的文件由 512 个字节 的逻辑块组成， 存储在具 有如下特性的磁盘驱动器上：

对于下面的 情况， 假设程 序顺 序地读 文 件的逻 辑块， 一个接 一个， 将读／写 头定位到 第一块上的 时间 是 T avg seek+T avgrota11o n o

·A. 最好的情况： 给定 逻辑块到 磁 盘 扇 区的 最好的 可 能 的映 射（即顺序的）， 估计读这

个文件需要的最优时间（以 ms 为 单位）。

B. 随机的情况： 如果块是随机地映射到 磁 盘扇 区的， 估计读这个 文件需要的 时间（以

ms 为 单位）。

2. 连接 1/ 0 设 备

   例如图形卡、监视器、鼠标、键盘和磁盘这样的输入／输出(l / 0 ) 设备，都 是 通过 l/ 0

   总线，例 如 Int el 的 外围设备 互 连( Periphe ral Component Int erconnect , PCD 总线连接到

   CPU 和主存 的。系统总线和内存总线是与 CPU 相关的，与 它 们 不 同 ，诸 如 PCI 这样的 I/

   0 总线设 计成与底层 CPU 无关。例如， P C 和 Mac 都可以使用 PCI 总线。图 6-11 展 示 了一个典型的 I/ 0 总线结构，它 连接了 CPU、主存和 l/ 0 设备。

   虽然 l/ 0 总线比系统总线和内存总线慢，但 是 它 可以容纳种类繁多的第三方 l/ 0 设备。例如，在 图 6-11 中 ， 有 三种不同类型的设备连接到总线。

• 通用串行 总线( Universa l Serial Bus, USB)控制器是一个连接到 USB 总线的设备的中转机构， USB总线是一个广泛使用的标准， 连接各种外围 l/ 0 设备，包 括键盘、鼠标、调制解调器、数码相机、游戏操纵杆、打印机、外部磁盘驱动器和固态硬盘。 USB 3. 0 总线的最大带宽 为 625MB / s。USB 3. 1 总线的最大带宽为 1250MB/ s。

• 图形卡（或适配器）包含硬 件 和软件逻辑，它 们 负 责 代表 CPU 在显示器上画像素。

• 主机 总线适配器将 一 个 或 多 个 磁盘连接到 I/ 0 总线，使 用 的 是 一 个 特 别 的 主机总线接 口定义的通信协议。两个最常用的这样的磁盘接口是 SCSI( 读作 " scuzzy" ) 和S AT A( 读作 " sat- uh" 。SCSI 磁盘通常比 SAT A 驱动器更快但是也更贵。SCSI主机 总 线 适 配器（通常称为 SCSI 控制器）可以支持多个磁盘驱动器， 与 S AT A 适配器不 同 ， 它 只 能 支 待 一 个 驱 动 器 。

  寄口存器文件日

  系统总线 内存总线

总线接口 凶,

!,’.•·•C.·..’",B·

USB Il三

VO总线

I

000 ;

针对诸如网络适

配器这样的其他

I 控制器 主机总线 设备的扩展插槽

t t t

鼠标 固态 键盘 监视器

硬盘 : I 如 盘 扣 妇 l 盎 i:，

* 磁 盘

'

'

'

一一一一一 －－－－－I＇

图 6-11 总线结构示例，它连 接 CP U、主存和 I/ 0 设备

其他的设备，例如网络适配器，可以通过将适配器插入到主板上空的扩展槽中，从而 连接到 I/ 0 总线， 这些插槽提供了到总线的直接电路连接。

6 访问磁盘

虽然详细描述 I/ 0 设备是如何工作的以及如何对它们进行编程超出了我们讨论的范围 ，但 是 我们可以给你一个概要的描述。例如，图 6-12 总结 了 当 CP U 从磁盘读数据时发生的步骤。

田 0 总线设计进展

图 6-11 中的 I/ 0 总线是一个简单的抽 象，使得 我们可以 具体描述但又不必和某个 系统的细节联 系过 于紧密。 它是 基 于外 围设 备 互联 ( Peripheral Component Interconnect, PCI) 总线的， 在 2010 年前使用非 常广泛。 PCI 模型中， 系统中所有的设备共享总线 ， 一个时刻只 能有一台设备 访问这些线路。在现代系统中， 共享的 PCI 总线已经被 PCEe(PCI express) 总线取代， PCie 是 一组高速 串行 、通过开关连 接的点到点链路， 类似于你 将在第 11 章中学习到 的开关以 太网。PCie 总线， 最大吞吐率为 16GB / s , 比 PCI 总线快一个数量级 ， PCI 总线的最大吞吐率为 533MB/ s。除 了测 量出的 I/ 0 性能， 不同总线设计之间的 区别 对应用程 序 来说是不可见的 ，所以 在本书中，我 们只使 用 简单的共享总线抽象。

CP U 使用一种称为内存映射 I/ O ( memor y-ma pped I/ 0 ) 的技术来向 I/ 0 设备发射命令

（图 6-12a) 。在使用内存映射 I/ 0 的系统中， 地址空间中有一块地址是为与 I/ 0 设备 通信保留的 。每个这样的地址称为一个 I/ 0 端口 (I / 0 port ) 。当一个设备连接到总线时， 它 与一个或多个端口相关联（或它被映射到一个或多个端口）。

CPU芯片

I

寄存器文件

三］

罕

鼠标 键盘 监视器 Cf

CPU芯片

1 寄存器文件

已 三

雪罕 芦忑

VO总线

b ) 磁盘控制器读扇区， 并 执行到主存的DMA传送

图 6-12

1. 当 OMA传送完成时， 磁盘控制器用中断的方式通知CPU 读一个磁盘扇区

来看一个简单的例子，假 设 磁 盘控制器映射到端口 OxaO 。 随 后 ， CPU 可能通过执行三个对地址 OxaO 的 存储 指 令 ，发 起 磁盘读：第 一 条 指 令 是发送一个命令字，告 诉 磁 盘发起一个读， 同时还发送了其他的参数，例如 当读完 成时 ，是否 中断 CP U( 我们会在 8. 1 节中讨论中断）。第二条指令指明应该读的逻辑块号。第三条指令指明应该存储磁盘扇区内容的主存地址。

当 CP U 发出了请求之后，在 磁 盘 执 行 读 的 时 候 ， 它 通常会做些其他的工作。回想一下， 一个 1G Hz 的 处理器时钟周期为 I ns , 在用来读磁盘的 16ms 时间里， 它 潜 在 地 可能执行 16 00 万条指令。在传输进行时，只 是 简单地等待， 什么都不做，是 一 种 极 大 的 浪费。

在磁盘控制器收到来自 CP U 的读命令之后 ，它 将逻辑块号翻译 成一个扇区地址，读该扇区的内容，然 后 将这 些内 容 直 接传送到主存，不需 要 CPU 的干涉（图6-12b) 。设 备可以自己 执行读或者写总线事 务 而不需 要 CP U 干涉的 过程， 称 为 直接 内 存 访问 ( Direct

Memory Access, DMA ) 。这种数 据传送称为 DMA 传送 CDMA trans fer ) 。

在 DMA 传送完成， 磁盘扇区的内容被安全地存储在主存中以后， 磁盘控制器通过给CPU 发送一个中断信号来通知 CPU(图 6-12c) 。基本思想是中断会发信号到 CPU 芯片的一个外部引脚上。这会 导致 CPU 暂停它当前正在做的工作， 跳转到一个操作系统例程， 这个程序会记 录下 1/0 已经完成， 然后将控制返 回到 CPU 被中断的地方。

田 日 商用磁盘的特性

磁盘制造商在他们的 网 页上公 布了许多 高级技术信息。例如， 希捷( Seagate) 公司 i 的网站 包含关 于他 们 最受 欢迎的 驱 动 器之一 Barracuda 7400 的如下信息。（远 不止如 ： 此 ! ) (S eagate. com)

，志

3. 1. 3 固态硬盘

   固态硬盘CSolid Stat e Dis k , SSD) 是一种基于闪存的存储技术（参见 6. 1. 1 节），在某些情况下是传统旋转磁盘的极有吸引力的替代产品。图 6-1 3 展示了它的基本思想。SSD 封装插到 I/ 0 总线上标准硬盘插槽（通常是 USB 或 SAT A ) 中， 行为就和其他硬盘一样， 处理来自 CP U 的读写逻辑磁 盘块的请求。一个 SSD 封装由一个或多个闪存芯片和闪存翻译层( flas h translation layer) 组成，闪 存芯片替代传统旋转磁盘中的机械驱动器， 而闪存翻译层是 一个硬件／固件设备， 扮演与磁盘控制器相同的角色，将 对逻辑块的请求翻译成对底层物理设备的访问。

   1/0 总线

固态硬盘 ( SSD )

- - - - - - –

！ 闪存

闪存翻译层

- - - - - - - - - -

！ 块0 块B-1

II 页 o I 页I I 口三工JI — 11 页o I 页I

..I. [勹芒了门

一一一一- - —- —- —- ————– —- —- —————————– ——————————

图 6-13 固态硬盘C SS D)

图 6-14 展示了典型 SSD 的性能特性。注意， 读 SSD 比写要快。随机读和写的 性能差别 是由底层闪存基本属性决定的。如图 6-13 所示， 一个闪存由 B 个块的序列组成， 每个块由 P 页组成。通常 ， 页的大小是 512 字节~ 4KB, 块是由 32 ~ 1 28 页组成的， 块的大小

为 16 KB~ 512KB。数据是以页为单位读写的。只有在一页所属的块整个被擦除之后， 才能写这一页（通常是 指该块中的所有 位都被设 置为 1 ) 。不 过， 一旦一个块被擦除了， 块中每一个页都 可以不需 要再进行擦除就写一次。在大约进行 100 000 次重复写之后， 块就会磨损坏。一旦 一个块磨损坏之后 ， 就不能再使用了。

图 6-1 4 一个商业固态硬盘的性能特性

资料来源： Intel SSD 730 产品 规 格 书[ 53] 。IOPS 是每秒 1/0 操 作 数 。吞 吐 量数 量基 于 4KB 块的 读 写

随机写很慢， 有两个原因。首先， 擦除块需要相对较长的 时间， l m s 级 的 ， 比访间页所需时 间要高一个数量级。其次， 如果写操作试图修改一个包含巳经有数据（也就是不是全为 1 ) 的页 p, 那么这个块中所有带有用数据的页都必须被复制到一个新（擦除过的）块， 然后才能 进行对页 p 的写。制造商已 经在闪存 翻译层中实现了 复杂的逻辑 ， 试图抵消擦写块的高 昂代价， 最小化内部写的次数， 但是随 机写的性能不太可能 和读一样好。

比起旋转磁盘 ， SSD 有很多优点。它们由半导体存储器构成 ， 没有移动的 部件， 因而随机访问 时间比旋转磁盘要快， 能耗更低， 同时也更结实。不过， 也有一些缺点。首先， 因为反复 写之后，闪 存块会磨损，所 以 SSD 也容易磨损。闪存翻译层中的平均 磨损( wear leveling ) 逻辑试图通 过将擦除平均分布在所 有的块上来最大化每个 块的 寿命。实际 上， 平均磨损逻 辑处理得非常好 ， 要很多 年 SSD 才会磨损坏（参考练习题6. 5 ) 。其次， SS D 每字 节比旋转磁盘 贵大约 30 倍， 因此常用的存储容量比旋转磁盘小 100 倍。不过，随 着 SSD 变得越来越受 欢迎，它 的价 格下降 得非常快，而两者 的价格差也 在减少。

在便携音乐设 备中， SSD 巳经完全的取代了旋转磁盘， 在笔记 本电脑中也越来越多地作为硬 盘的替代品， 甚至在台式机和服务器中也开始 出现了。虽然旋转磁盘还会继续存在，但 是显然， SS D 是一项重要的替代选择。

练习题 6. 5 正 如我 们 已 经 看到 的， SSD 的 一个 潜 在 的 缺 陷 是 底 层 闪 存 会磨损。例如， 图 6-14 所 示的 SSD , In tel 保证 能够经得 起 128 PB C 128 X 1015 字 节）的写。 给定 这 样的假 设， 根据下面的工 作负 载， 估计这款 SSD 的寿命（以年为 单位）：

1. 顺序写的最糟情况 ： 以 470MB/s( 该设备的平均顺序写吞吐量）的速度持续地写 SSD 。
   1. 随机写的最糟情况 ： 以 303MB/ s( 该设备的平均随机写吞吐量）的速度持续地写 SSD 。
   2. 平均情况 ： 以 20GB/ 天（某些计 算机 制造商在他 们的 移 动计 算机 工作 负 载模 拟测 试中假设 的平 均每 天写速 率）的速度 写 SSD 。

6. 1. 4 存储技术趋势

从我们对存储技术的讨论中，可以总结出几个很重要的思想：

不同 的存储技 术有 不 同的 价格和性能折中。S RAM 比 DRAM 快一点， 而 DR AM 比磁盘要快 很多。另一方面， 快速存储总是比慢速存储要贵的。SR AM 每字节的造价比DRAM 高， DRAM 的造价又比磁 盘高得多。SSD 位千 DRAM 和旋转磁盘之间。

不同 存储技术的价格和性能属性以 截然不 同的 速率 变化 着。图 6-15 总结了从 1985 年

以来的存储技术的价格和性能属性，那 时笫 一 台 P C 刚 刚 发明不久。这些数字是从以前的商 业 杂 志 中 和 W e b 上挑选出来的。虽然它们是从非正式的调查中得到的， 但 是 这些数字还是能揭示出一些有趣的趋势。

自从 1 98 5 年以来， S RAM 技术的成本和性能基本上是以相同的速度改善的。访问时间 和 每兆字节成本下降了大约 1 0 0 倍（图6- 1 5 a ) 。不过， D RAM 和磁盘的变化趋势更大， 而 且 更 不 一 致。DRAM 每兆字节成本下降了 44 0 0 0 倍（超过了四个数量级！）， 而 DRAM的 访 问 时 间 只 下 降 了 大 约 1 0 倍（图 6- 1 5 b ) 。 磁 盘技术有和 DRAM 相同的趋势， 甚至变化更 大 。 从 1 9 8 5 年以来，磁 盘存储的每兆字节成本暴跌了 3 000 0 0 0 倍（超过了六个数量 级！），但是 访问 时 间 提高得很慢，只 有 2 5 倍 左 右（图 6- 1 5 c ) 。 这些惊人的长期趋势突出了内 存 和 磁 盘 技术的一个基本事实：增 加 密度（从而降低成本）比降低访问时间容易得多。

DRAM 和磁盘的性 能滞后 于 C P U 的性能。正如我们在图 6- 1 5 d 中看到的那样，从

1 9 8 5 年到 2 0 1 0 年， C P U 周 期 时 间 提高了 5 0 0 倍。如果我们看有效周期时间 ( e ff ec t ive cy­ cle time) 我们定义为一个单独的 C P U ( 处理器）的周期时间除以它的处理器核数一 那么 从 1 9 8 5 年到 20 1 0 年的提高还要大一些， 为 2 0 0 0 倍。C P U 性能曲线在 2 0 0 3 年附近的突然 变 化 反映的是多核处理器的出现（参见 6 . 2 节的旁注），在 这 个 分 割 点 之 后 ，单 个 核的周期时间实际上增加了一点点，然后又开始下降，不过比以前的速度要慢一些。

图 6-15 存储和处理器技术发展趋势 。2010 年的 Co re i7 使用的是 Nehalem 处理器 ，

2015 年的 Co re i7 使用的是 H as well 核

注意，虽 然 SRAM 的 性能 滞后 千 CPU 的性能， 但还是 在保待增长。不 过， DRA M 和磁盘性能与 CPU 性能之间的差距实际上是在加大的。直到 20 03 年左右多核处理器的出现， 这个性能差距都是延迟的函数， DRAM 和磁盘的访问时间比单个处理器的周期时间提高得更 慢。不过，随 着 多 核 的 出 现， 这个性能越来越成为了吞吐量的函数， 多 个 处 理 器核并发 地向 DRAM 和磁盘发请求。

图 6-1 6 清楚地表明了各种趋势，以 半 对 数 为比例( s em i-log scale ) , 画出了图 6-1 5 中的访问时间和周期时间。

I00 000 000.0

10 000 000.0

I 000 000.0

JOO 000.0 –+- 磁 盘寻道时间

_._ SSD 访问 时间

JO 000.0

1000.0

100.0

10.0

1.0

0.1

0.0

1985 1990

1995

2000 2003 2005 2010

年份

2015

, 气 ) RAM访问时间

千 SRAM访问时间

-0- CPU周期时间

今 有效CPU周期时间

图 6-16 磁 盘 、 DRAM 和 CPU 速度之间逐渐增大的差距

正如我们将在 6. 4 节中看到的那样， 现代计算机频繁地使用基千 SRAM 的高速缓存， 试图弥补处理器－内存之间的差距。这种方法行之有效是因为应用程序的一个称为局部性 (localit y ) 的 基本属性，接 下 来 我们就讨论这个间题。

练习题 6. 6 使用图 6-15c 中从 200 5 年到 2015 年的数据， 估计到 哪一年你可以以 $ 500

的价 格买到 一个 1PBC1015 字节）的 旋转磁 盘。假 设美元价值不 变（没有通货 膨胀 ）。

m 当周 期时间保持不变： 多核处理器的到来

计算机历史是由一些在工业界和整个世界产生深远变化的单个事件标记出来的。有趣 的是，这些变化点趋向于每十年发生一次： 20 世纪 50 年代 Fortra n 的提出， 20 世 纪 60 年代早期 IBM 360 的出现 ， 20 世 纪 70 年代早期 Int ernet 的曙光（当 时称为 AP RA NE T ) , 20世纪 80 年代早期 IBM PC 的出现 ，以 及 20 世 纪 90 年代万维网 ( World Wide Web) 的出现 。最近这样的事件出现在 21 世纪初， 当计 算机制造商迎 头撞 上了所谓 的“能量墙( power

wall)", 发现他们无法再像以前一样迅速地增加CPU的时钟频率了，因为如果 那样芯片的功耗会太大。解决方法是用多个小处理 器核(core ) 取代单个大处理 器，从而提 高性能，每 个完整的处理器能够独立地、与其他核 并行地执行程序。这种多核 ( m ulti- core) 方法部 分有效，因为一 个处理器的功耗正比于 P = J C寸， 这里J 是时钟频率，C 是电容，而 v 是电压。电容 C 大致上正比于面积，所 以只要所有核的总面积不变，多核 造成的能耗就能保持不变。只要特征尺寸继续按照摩尔定律指数性地下降，每 个处理器中的核数，以及每个处理 器的有效性能，都会继续增加 。

从这个时间点以后，计算机越来越快，不是因为时钟频率的增加，而是因为每个处理器 中核数的 增加，也 因为体 系结构上的创新提高了 在这些核上运行程序的效率。我们可以从图6-16 中很清楚地看到这 个趋势。CPU 周期时间在 2003 年达到最低点，然后实际上是又开始上

升的，然 后变得平稳，之后 又开始以比以前慢一些的速率下降 。不过，由 于多核处理器的出现(2004 年出现双核， 2007 年出现四核）， 有效周期时间以接近于以前的速率持续下降。

6. 2 局部性

一个编写良好的计算机程序常常具有良 好的局部性 (l o ca lit y ) 。也就是， 它们倾向于引用邻近千其 他最近引用过的数据项的数据项， 或者最近引 用过的数据项本身。这种倾向性， 被称为局部 性原理( p rin cipl e of loca lit y ) , 是一个持久的概念， 对硬件和软件系统的设计 和性能都 有着极大的影 响。

局部性通常有 两种不同的 形式： 时间局 部性( t e m po ra l lo ca l it y ) 和空间 局部性( s patial lo ca lit y) 。在一个具有良好时间局部性的程序中 ， 被引用过一次的内存位置很可能 在不远的 将来再被多次引用。在一个具有良好空间局部性的程序中 ， 如果一个内存位置被引用了一次， 那么程序很可能在不远的将来引用附 近的一 个内存位置。

程序员应该理解局部性原理，因为一般而言，有良好局部性的程序比局部性差的程序 运行得更快。现代计算 机系统的各 个层次 ， 从硬件到操作系统、再到应用 程序， 它们的设计都利用了局部性。在硬件层，局 部性原理允许计算机设计者通过引入称为高速缓存存储器的 小 而快速的存储器来保存最近被引 用的 指令和数据项， 从而提高对主存的访问速度。在操作系统级， 局部性原理允许系统使用主存作为虚拟地址空间最近被引用块的高速缓存。类似地， 操作系统用主存来缓存磁盘 文件系统中最近被使 用的磁盘块。局部性原理在应用程序的设计中也扮演着重要的角色。例如， Web 浏览器 将最近被引 用的文档放在本地磁盘上，利用的 就是时间局部性。大容屈的 Web 服务器将最近被请求的文档放在前端磁盘高速缓存中， 这些缓存能满足对这些 文档的请 求， 而不需要服务器的任何干预。

6. 2. 1 对程序数据引用的局部性

考虑图 6-17a 中的简单函数， 它对一个向员的元素求和。这个程序有良好的局部性吗？要回答这个问题， 我们来看看每个变 量的引用模式。在这个例子中，变 量 s u m 在每次循环迭代中被引用一次 ， 因此， 对于 s u m 来说 ， 有好的时间 局部性。另一方面， 因为 s um 是标量， 对于 s um 来说， 没有空间局部性。

int swnvec(int v[N])

｛

int i, sum = O;

for (i = O; i < N; i++) sum+= v[i];

return sum;

地址内容

访问顺序

16

82

vI V

5

24

2 87

v 6

7

a ) 一 个具 有良好局部性的程序 b ) 向量v的引用模式 ( N = 8)

图 6-17 注意如何按照向量元素存储在内存中的顺序来访间它们

正如我们在图 6-176 中看到的， 向量 v 的元素是 被顺序读取的， 一个接一个， 按照它们存储在内存中的 顺序（为了方便， 我们假设数 组是从 地址 0 开始的）。因此， 对于变量 V, 函数有很好的空间局部性，但是时间局部性很差，因为每个向噩元素只被访问一次。因为 对千循环体中的每个变量，这个函数要么有好的空间局部性，要么有好的时间局部性，所 以我们可以断定 s umv e c 函数有良好的局部性。

我们说像 s umv e c 这 样顺序访问一个向批每个元素的函数，具 有 步 长 为 1 的引用 模 式(str ide- I reference pattern)(相对千元素的大小）。有时我们称步长为 1 的引用模式为顺序引用模式( seq uent ial reference pat tern ) 。一个连续向最中， 每隔 K 个 元 素 进 行 访 问 ， 就 称为步长为 K 的引 用模式( s t r id e- k reference pattern ) 。步长为 l 的引用模式是程序中空间局部性常见和重要的来源。一般而言，随着步长的增加，空间局部性下降。

对于引用多维数组的程序来说，步 长也是一个很重要的问题。例如，考 虑 图 6-18a 中的函数 s umarr a yr ows , 它 对 一个二维数组的元素求和。双重嵌套循环按照行优先顺序( ro w­ major order ) 读 数组 的元素。也就是，内 层 循 环读第一行的元素， 然后读第二行，依 此 类 推 。函数 s umarr a yr ows 具 有良好的空间局部性，因 为它按照数组被存储的行优先顺序来访问这个 数组（图6-186 ) 。其结果是得到一个很好的步长为 1 的引用模式 ，具有良好的空间局部性 。

int sumarrayrows (int a[M] [NJ)

｛

inti, j, sum= O;

for (i = 0 ; i < M; i ++)

for (j = 0; j < N; j ++) sum += a[i] [j];

return sum;

地址内容

访问顺序

。

aoo

a 01

12 16

20

a12

图 6-18

a ) 另一个具有良好局部性的程序 b ) 数组a的引用模式( M = 2, N=3)

有良好的空间局部性，是因为数组是按照与它存储在内存中一样的行优先顺序来被访问的

一些看上去很小的对程序的改动能够对它的局部性有很大的影响。例如，图 6-1 9a 中的函数 s umarr a y c o l s 计 算 的 结 果 和图 6-18a 中函数 s umar r a y r o ws 的 一 样。唯一的区别是我们交换了 1 和）的循环。这样交换循环对它的局部性有何影响？ 函数 s umarr a y c o l s 的空间局 部性很差 ，因 为它按照列顺序来扫描数组，而 不是按照行顺序。因为 C 数组在内存中是按照行顺序来存放的，结 果 就 得 到步长为 N 的引用模式， 如图 6-1 96 所示。

int surnarraycols(int a[M] [N])

｛

inti, j, sum= O;

for (j = 0; j < N; j ++)

for (i = 0 ; i < M; i ++)

sum+= a[i][j]; return sum，·

地址内容

访问顺序

a 01

12 16

20

a12

6. 2. 2

a ) 一个空间局部性很差的程序 b ) 数组a的引用模式( M = 2, N=3)

图 6- 1 9 函数的空间局部性很差 ， 这是因为它使用步长为 N 的引用模式来扫描

取指令的局部性

因为程序指令是存放在内存中的， CPU 必须取出（读出）这些指令，所 以 我们也能够评价一个程序关于取指令的局部性。例如，图 6-1 7 中 f or 循环体里的指令是按照连续的内存顺序执行的，因此循环有良好的空间局部性。因为循环体会被执行多次，所以它也有 很好的时间局部性。

--,

代码区别千程序数据的一个重要属性是在运行时它是不能被修改的。当程序正在执行 时， CPU 只从内存中读出它的指令。CPU 很少会重写或修改这些指令。

1. 2. 3 局部性小结

   在这一节中， 我们介绍了局部性的基本思想， 还给出了量化评价程序中局部性的一些简单原则：

   • 重复引用相同变量的 程序有良 好的时间局部性。

   • 对于具有步长为 K 的引用模式的程序， 步长越小， 空间局部性越好。具有步长为 l 的引用模式的程序有很好的空间局部性。在内存中以大步长跳来跳去的程序空间局 部性会很差。

   • 对千取指令来说，循环有好的时间和空间局部性。循环体越小，循环迭代次数越多， 局部性越好。

     在本章后面，在我们学习了高速缓存存储器以及它们是如何工作的之后，我们会介绍 如何用高速缓存命中率和不命中率来量化局部性的概念。你还会弄明白为什么有良好局部性的程序通常比局部性差的程序运行得更快。尽管如此，了解如何看一眼源代码就能获得 对程序中局部性的高层次的认识，是程序员要掌握的一项有用而且重要的技能。 ．

     练习题 6. 7 改变下面函数中循环的顺序，使得 它以步长为 1 的引用模式扫描三维数组 a :

     int sumarray3d (int a[NJ [NJ [NJ)

     ｛

     int i , j , k, sum “’ 0 ;

for (i = O; i < N; i++) {

for (j = O; j < N; j++) {

for (k = O; k < N; k++) { sum += a[k] [i] [j];

｝

｝

｝

return sum;

练习题 6 . 8 图 6- 20 中的 三个函数，以不同的 空间局部 性程度 ， 执行 相同的 操作。请对这些函数就空间局部性进行排序。解释你是如何得到排序结果的。

void clear1(point *P, int n)

｛

#define N 1000 typedef struct {

int vel[3];

int acc[3];

} point;

point p[N];

a) str uc t s 数组

图 6-20

int i , j;

for (i = O; i < n; i++) { for (j = O; j < 3; j++)

p[i] .vel[j] = O;

for (j = O; j < 3; j++)

p[i] . acc[j] = 0;

｝

b ) c l e ar l 函数

练习题 6. 8 的代码示 例

void clear2(point *P, int n)

｛

int i, j;

for (i = 0; i < n; i ++) {

for (j = 0; j < 3; j++) { p [i] . vel[j] = 0;

p [i] . ace [j] = 0;

｝

｝

void clear3(point *P, int n)

｛

int i, j;

for (j = 0; j < 3; j++) { for (i = O; i < n; i++)

p[i] .vel[ j] = O;

for (i = O; i < n; i++) p[i] .acc[j] = O;

｝

c) c l e ar 2 函数 d) c l e ar 3函数

图 6- 20 （续）

1. 3 存储器层次结构

   6. 1 节和 6. 2 节描述了存储技术和计算机软件的一些基本的和持久的属性 ：

   • 存储技 术： 不同存储技术的访问 时间差异很大。速度较快 的技术每字 节的成本要比速度较慢的技术高 ， 而且容最 较小。CP U 和主存之间的速度差距在增大。

   • 计算机软件 ： 一个编写良好的程序倾向 于展示出良 好的局部性。

     计算中一个喜人的巧合是， 硬件和软件的这些 基本属性互 相补充 得很完美 。它们这种相互补充的性 质使 人想 到一种组 织存储 器 系统的方 法， 称 为 存 储 器 层 次 结 构 ( memory 加 rarchy) , 所有的现代计算 机系统中都使用了这种方法。图 6- 21 展示了一个典型的存储器层次结构。一般而言，从高层往底层走，存储设备变得更慢、更便宜和更大。在最高层

     (LO), 是少量快速的 CPU 寄存器， C P U 可以在一个时钟周 期内访间它们。接下来是一个

更小更快和

（每字节） 成本更高的存储设备

更大

L3:

Ll :

L2

高速缓存

(SRAM)

L3

高速缓存

(SRAM)

CPU寄存器保存着从高速缓存存储器取出的字

} LI 高速缓存保存着从L2 高速缓存取出的缓存行

} L2高速缓存保存着从L3

高速缓存取出的缓存行

} L3高速缓存保存着从主存高速缓存取出的缓存行

更慢和

（每字节） 成本更低的存储设备

LS:

L4: 主存 ( DRAM )

本地二级存储（本地磁盘）

主存保存着从本地磁盘取出的磁盘块

本地磁盘保存着从远程网络服务器磁盘上取出的文件

图 6-21 存储器层次结构

或多个小型到中型的基于 SRAM 的高速缓存存储器， 可以 在儿个 CPU 时钟周期内访问它们 。 然后是一个大的基于 DRAM 的主存， 可以在几十到几百个时钟周期内访问它们。接下 来是慢速但是容扯很大的本地磁盘。最后，有 些 系统甚至包括了一层附加的远程服务器上 的 磁 盘 ， 要通 过 网 络来访问 它 们。例 如， 像安 德鲁 文件 系统 ( Andrew File System, AFS )或者网络文件系统 ( Netwo rk File System, NFS ) 这样的分布式文件系统，允 许程序访 问 存 储在远程的网络服务器上的文件。类似地，万 维 网允 许程序访问存储在世界上任何地 方的 Web 服务器上的远程文件。

m 其他的存储器层次结构

我们向你展示了一个存储器层次结构的示例，但是其他的组合也是可能的，而且确 实也 很 常见。例如，许 多站点（包括谷歌的数据 中心 ）将本地磁盘备份到存 档的磁带上。其中有些站点，在 需要时由人工装好磁 带。 而其他 站点则是 由磁 带机 器人 自动 地完成这项任务。 无论在哪种情况中，磁 带都是存储器层 次结构中的一层， 在本地磁盘层下 面， 本 书中提到的 通用原 则也 同样 适用于它。磁 带每 宇节比 磁 盘更便 宜， 它允 许站点将本地磁｝ 盘的多 个快照存档。代价是磁带的 访问时间要比磁盘的更长。 未看另一个例子， 固 态硬盘， 在存储器层 次结构 中扮 演着越 来越重要的角 色，连接 起 DRAM 和旋转磁盘之间的鸿沟。．

1. 3. 1 存储器层次结构中的缓存

   一般而言， 高速缓存( cache , 读作 " cas h” ) 是 一 个 小 而快速的存储设备， 它 作 为存储在更大、也更慢的设备中的数据对象的缓冲区域。使用高速缓存的过程称为缓存( caching, 读作 " cashing" ) 。

   存储器层次结构的中心思想是， 对于每个 k , 位于 K 层 的 更 快更小的存储设备作为位于k + l 层 的 更 大更 慢的存储设备的缓存。换句话说， 层 次结 构中的每一层都缓存来自较低一层 的 数 据 对象 。 例 如，本地 磁盘作为通过网络从远程磁盘取出的文件（例如 Web 页面）的缓存， 主存作为本地磁盘上数据的缓存， 依此类推， 直 到 最小的缓存- CPU 寄存器组。

   图 6- 22 展示了存储楛层次结构中缓存的一般性概念。第 k + l 层 的 存 储 器被划分成连续 的 数 据 对 象 组块( ch unk ) , 称为块< block ) 。每个块都有一个唯一的地址或名字， 使之区别 于 其 他 的 块。块可以是固定大小的（通常是这样的）， 也 可以是可变大小的（例如存储在 Web 服务器上的远程 H T ML 文件）。例如，图 6- 22 中第 k + l 层 存 储 器被划分成 16 个大小 固 定 的 块 ，编 号 为 0 ~ 15。

   第K 层： 亡工丿仁工丿仁五丿仁工丿 第K 层更小、更快、更昂贵的设备

   ｀ 缓存着第k+l 层块的一个子集

二 二 数据以块为大小传输

单元在层与层之间复制

亡严］二亡仁仁二二仁

第k+I 层： 1

工二三二正］巨三］

口口口三］巨三］

第k+ I层更大、更慢、更便宜的设备被划分成块

图 6-22 存储器层次结构中基本的缓存原理

类似地， 第 k 层的存储器被划分成较少的 块的集合， 每个块的 大小与 k + l 层的块的大小一样。在任何时刻 ， 第 K 层的缓存包含第 k + l 层块的 一个子集的副本。 例如， 在图 6-22 中， 第 k 层的缓存有 4 个块的空间 ， 当前包含块 4 、9、14 和 3 的副本。

数据总是以 块大小为传送单元 ( t ra nsfer un it ) 在第 k 层和第 k + I 层之间来回复制的。虽然在层次结构中任何一对相邻的层次之间块大小是固定的，但是其他的层次对之间可以 有不同的块大小。例如， 在图 6- 21 中， L l 和 LO 之间的传送通常使用的是 1 个字大小的块。 L2 和 L1 之间（以及 L 3 和 L2 之间、L4 和 L3 之间）的传送通常 使用的是几十个字 节的块。而 L 5 和 L4 之间的传送用的是大小为几百 或几千字节的块。一 般而言 ， 层次结构中较 低层（离 CP U 较远）的设备的访问时间较长， 因此为了 补偿这些较长的 访问时间，倾 向 于 使用较大的块。

1. 缓存命中

   当程序需要第 k + l 层的某个数据对象 d 时，它 首先在当前存储在第 k 层的一个块中查找 d 。 如果 d 刚好缓存在第 k 层中， 那么就是我们所说的缓存命 中( cache h代）。该 程序直接从第 k 层读取 d , 根据存储 器层次结构的性质，这 要比从第 k + l 层读取 d 更快。例如， 一个有良好时间局部 性的程序 可以从块 14 中读出一个数据对象， 得到一个对第 k 层的缓存命中。

2. 缓存不命中

   另一 方面， 如果第 K 层中没有缓存数据对象 d , 那么就是我们所说的缓存不命中(cache miss ) 。 当发生缓存不命中时， 第 k 层的缓存从第 k + l 层缓存中取出 包含 cl 的 那个块， 如果第 k 层的缓存已经满了 ， 可能就会覆盖现存的一 个块。

   覆盖一个现存的 块的过程称为替 换( replacing ) 或驱逐( evicting ) 这个块。被驱逐的这个块有时 也称为牺牲块 ( vict im blo ck) 。决定该替换哪个块是由缓存的替换 策略 ( replace­ ment polic y) 来控制的。例如， 一个具有随机替 换策略 的缓存会随机选择一 个牺牲块。一个具有 最近最少被使用CLRU) 替换策略的缓存会选择那个最后被访问的时间距现在最远的块。

   在第 k 层缓存从第 k + l 层取出那个块之后， 程序就能像前面一样从 第 k 层读出 d 了。例如，在 图 6-22 中， 在第 k 层中读块 1 2 中的一个数据对象， 会导致一个缓存不命 中， 因为块 1 2 当前不 在第 k 层缓存中。一旦把块 12 从第 k + l 层复制到第 k 层之后， 它就会保持在那里，等待稍后的访问。

3. 缓存不命中的 种类

   区分不同种类的缓存不命中有时候是很有帮助的。如果第 K 层的缓存是空的 ， 那么对任何数 据对象的访问都会不命中。一个空的缓存有时被称为冷缓 存 ( cold cache), 此类不命中称为 强制性 不命中( co m pulso r y m is s ) 或冷不命 中( cold mis s ) 。冷不命中很 重要 ， 因为它们通 常是短暂的 事件 ，不会 在反复访问 存储器使得缓存暖身 ( w a r m ed up ) 之后的稳定状态中出现。

   只要发生了不命中， 第 K 层的缓存就必须执行某个放置策略 ( place men t policy), 确定把它从第 k + l 层中取出的块放在哪里。最灵活的替 换策略是允 许来自第 k + l 层的任何块放在第 k 层的任何块中。对于存储器层次结 构中高层的缓存（靠近 CP U ) , 它们是用硬件来实现的，而且速度是最优的，这个策略实现起来通常很昂贵，因为随机地放置块，定位起 来代价很高。

因此， 硬件缓存通常使用的是更严格的放置策略， 这个策略将第 k + l 层的某个块限制放置在第 k 层块的一个小的子集中（有时只是一个块）。例如， 在图 6- 22 中， 我们可以确定第 k + l 层的块 1 必须放置在第 k 层的块(i mod 4 ) 中。例 如， 第 k + l 层的块 0、4、8 和 1 2 会映射到第 K 层的块 O; 块 1、5、9 和 1 3 会映射到块 1 ; 依此类推。注意 ， 图 6-22 中的示例缓存使用 的就是这个策略 。

这种限制性的放置策略 会引起一种不命中，称 为冲 突不命 中( confl ict miss ) , 在这种

情况中，缓存足够大，能够保存被引用的数据对象，但是因为这些对象会映射到同一个缓 存块， 缓存会一直不命中。例如，在图 6- 22 中，如 果程序请求块 0’ 然后块 8 , 然后块 o,

然后块 8 , 依此类推， 在第 k 层的缓存中， 对这两个块的 每次引 用都会不命中， 即使这个缓存总共可以容纳 4 个块。

程序通常是按照一系列阶段（如循环）来运行的，每个阶段访问缓存块的某个相对稳定不变的集合。例如， 一个嵌套的循环可能会 反复地访问 同一个数组的元素。这个块的集合称为这个阶段的工作 集 ( w or k ing set ) 。当 工作集的大小超过缓存的大小时， 缓存会经历容量不命 中( capacit y m iss ) 。换句话说就是， 缓存太小了， 不能处理这个工作集。

4. 缓存管理

   正如我们提到过的，存储器层次结构的本质是，每一层存储设备都是较低一层的缓 存。在每一层上，某种形式的逻辑必须管理缓存。这里，我们的意思是指某个东西要将缓 存划分成块， 在不同的层之间传送块 ， 判定是命中还是不 命中， 并处理它们。管理缓存的逻辑可以是硬件、软件， 或是两者的结 合。

   例如， 编译器管理寄存器文件， 缓存层次结构的最高层。它决定当发生不命中时何时发射加载， 以及确定哪个寄存器来存放数据。Ll 、L2 和 L3 层的缓存完全是由内 置在缓存中的硬件逻辑来管理的。在一个有虚拟内存的系统中， DRAM 主存作为存储在磁盘上的数据块的缓存， 是由操作 系统 软件和 CP U 上的 地址翻译 硬件共同管理的。对千一个具 有像 AFS 这样的分 布式文件系统的机器来说， 本地磁盘作为缓存，它 是由运行在本地机器上的 AFS 客户端进程管理的。在大多数时候， 缓存都是自动运行的， 不需要程序采取特殊的或显式的行动。

5. 3. 2 存储器层次结构概念小结

   概括来说，基于缓存的存储器层次结构行之有效，是因为较慢的存储设备比较快的存 储设备更便宜， 还因 为程序倾向 千展示局部性：

   • 利 用时间局部 性： 由于时间局部性， 同一数据对象可能会被多次使用。一旦一个数据对象在第一 次不命中时被复制到缓存中 ， 我们就会期望后面对该目标有一系列的访问命中。因为缓存比低一层的存储设备更快 ， 对后面的命中的服务会比最开始的不命中快很多。

     • 利 用空间局部性 ： 块通常包 含有多个数据对象。由于空间局部性， 我们会期望后面对该块中其他对象的访问能够补偿不命中后复制该块的花费。

       现代系统中到处都使用了缓存。正如从图 6-23 中能够看到的 那样， CP U 芯片、操作系统、分布式文件系统中和万维网上都使用了缓存 。各种各样硬件和软件的组合构成和管理着缓存。注意， 图 6-23 中有大量我们还未涉及的术语和缩写。在此我们包括这些术语和缩写是为了说明 缓存是多么的普遍。

类型 缓存什么 被缓存在何处 延迟（周期数） 由谁管理

图 6~23 缓 存 在 现 代 计 算 机 系 统 中 无 处 不 在 。 T L B : 翻译后备缓 冲器 ( T ra ns la tion Lookas ide Ruffer); MMU: 内存管理单元 ( Memory Management Unit ) ; OS: 操作系统 ( Operating System);

AFS: 安德鲁文件系统( Andrew File System) ; NFS : 网络文件系统 ( Network File System)

6. 4 高速缓存存储器

早期计算机系统的存储器层次结构只有三层： CPU 寄存器、DRA M 主存储 器 和磁 盘存储。不 过， 由 千 CP U 和主存之间逐渐增大的差距， 系统设计者被迫在 CPU 寄存器文件和主存之 间插入了一个小的 SRAM 高速 缓 存存储 器， 称为 L1 高 速 缓 存（一级缓存）， 如 图 6-24 所 示。L1 高速缓存的访问速度几乎和寄存器一样快，典 型 地是大约 4 个时钟周期。

CPU芯片

系统总线 内存总线

总接线口 三］

图 6- 24 高速缓存存储器的典烈总线结构

随着 CPU 和主存之间的 性能差 距不断增大 ， 系统设计者在 Ll 高速缓存和主存之间又插入了一 个更大的高速缓存， 称为 L2 高 速缓存， 可 以 在 大 约 1 0 个时钟周期内访问到它。有些现代系统还包括有一个更大的高速缓存，称 为 L3 高 速缓存， 在 存 储 器 层 次 结 构 中 ， 它位于 L2 高速缓存和主存之间， 可以在大约 50 个周期内访问到它。虽然安排上有相当多的变化， 但是通用原则是一样的。对于下一节中的讨论， 我们会假设一个简单的存储器层次结构， CPU 和主存之间只有一个 Ll 高速缓存。

6. 4. 1 通用的高速缓存存储器组织结构

考虑一个计算机系统 ，其 中 每 个 存 储 器地址有 m 位，形 成 M = 沪 个 不 同 的 地 址 。 如

图 6 - 25 a 所 示， 这样一个机器的高速缓存被组织成一个有 5 = 2’ 个高速缓 存组( ca ch e s e t ) 的

数组。每个组包含 E 个 高 速缓存行 ( cach e line ) 。每个行是由一个 B = Z1’ 字 节的数据块( block ) 组成的，一 个 有效位 ( va lid bit ) 指明这个行是否包含有意义的信息， 还有 t = m— ( b+ s ) 个标记位( t ag bit ) ( 是 当前块的内存地址的位的一个子集）， 它 们 唯 一 地标识存储在这个高速缓存行中的块。

每行1个 每行t个有效位标记位

每个高速缓存块有B=钞字节

广，''

匠言Io I I I···IB-

组0:

匡巠 二 1。I

I I … IB-lI ｝每组珩

S=25组

组I :

国 口三口1。I I I … IB-lI

阿 勹压门I I 1 I···la-1I

匡口

组s-

I I I … IB-1I #

匣 口巨门I I I I … IB-11

高速缓存大小C=BxE xS数据字节

a)

图 6- 23

b)

高 速 缓 存 ( S , E, B, m ) 的 通 用 组 织 。 a) 高 速 缓 存 是 一 个 高 速 缓 存 组 的 数 组 。 每 个 组 包 含一 个 或 多 个行 ， 每 个 行 包 含 一 个 有 效 位 ， 一 些 标 记 位 ， 以 及一 个 数 据块 ； b) 高速缓存的结构将 m 个地址位 划分 成 了 t 个标记 位 、s 个 组索 引位 和 b 个块 偏移 位

一般而言， 高速缓存的结构可以用元组 CS , E, B, m ) 来描述。高速缓存的大小（或容矗）C 指的是所有块的大小的和。标记位和有效位不包括在内。因此， C= S X E X B。

当一条加载指令指示 CP U 从 主存地址 A 中读一个字时， 它 将地址 A 发送到高速缓存。如果高速缓存正保存着地址 A 处那个字的副本，它 就立即将那个字发回给 CPU。那么高速缓存如何知道它是否包含地址 A 处那个字的副本的呢？ 高速缓存的结构使得它能通过简单地检查地址位， 找到所请求的字， 类似于使用极其简单的哈希函数的哈希表。下面介绍它是如何工作的：

参数 S 和 B 将 m 个地址位分为了三个字段，如 图 6-25b 所示。A 中 s 个组索引位是一个到 S 个组的数组的索引。第一个组是组 0 , 第二个组是组 1 , 依此类推。组索引位被解释为一个无符号整数，它告诉我们这个字必须存储在哪个组中。一旦我们知道了这个字必 须放在哪个组中， A 中 的 t 个标记位就告诉我们这个组中的哪一行包含这个字（如果有的话）。当且仅当设置了有效位并且该行的标记位与地址 A 中的标记位相匹配时，组 中的这一 行 才包含这个字。一旦我们在由组索引标识的组中定位了由标号所标识的行， 那么 b 个块偏移位给出了在 B 个字节的数据块中的字偏移。

你可能已经注意到了， 对 高速缓存的描述使用了很多符号。图 6- 26 对这些符号做了个小结，供你参考。

图 6-26 高速缓存参数小结

讫； 练习题 6. 9 下表 给出 了几 个不 同的 高速 缓存的 参数。 确定 每个高 速缓存的 高 速缓存组数 CS ) 、 标记位 数 ( t ) 、 组 索引位 数( s ) 以及块偏 移位 数 ( b) 。

1. 4. 2 直接映射高速缓存

   根据 每个组的高速缓存行数 E , 高速缓存被 分为不同的类。每个组只有一行( E = l ) 的高速缓存称 为直接映射高速缓存( dir ec t- mapped cache)( 见图 6-27 ) 。直接映射高速缓存是最容易实现和理解的 ， 所以我们会以 它为例来说明一些高速缓存 工作方式的通用概念。

   组0: I五邑口匡勹1 高速缓存块 I I} £=匋组 1 行

   组 I : I 匡囡口三勹二五亘亘五二=:J I

组S- 1: I匡囡口亘口1 高速缓存 块 I I

图 6-27 直 接映射高速缓存 ( £ = 1) 。 每个组只有一行

假设我们有 这样一个系统， 它有一个 CPU 、一个寄存器文件、一个 Ll 高速缓存和一个主存。当 CPU 执行一条读内存字 w 的指令， 它向 Ll 高速缓存请求这个 字。如果 Ll 高速缓存有 w 的一个缓存的副本， 那么就得到 L1 高速缓存命中， 高速缓存会很快抽取出

w, 并将它返 回给 CPU。否则就是缓存不命中， 当 Ll 高速缓存向主存请求包含 w 的块的一个副 本时， CPU 必须等待。当被请求的块最 终从内存到达时， Ll 高速缓存将这个块存放在它 的一个高速缓存行里， 从被存储的块中抽取出字 w , 然后将它返回给 CPU。高速

缓存确定一个请求是否命中，然后抽取出被请求的字的过程．分为三步： 1) 组选择； 2)

行匹配； 3 ) 字抽 取 。

1. 直接映射高速缓存 中的组选择

   在这一步中 ， 高速缓存从 w 的地址中间抽取出 s 个组索引位。这些位被解释成一个对应千一个组号的无符号整数。换旬话来说， 如果我们把高速缓 存看成是一个关于组的一维数 组， 那么这些组索引位就是一个到这个数组的索引 。图 6-28 展示了直接映射高速缓存的组选

   择是如何工作的。在这个例子中， 组索引位 00001 2 被解释为一个选择组 1 的整数索引。

   组0 : I 工[] I 标记 11 高速缓存块 I I

选择的组 ， 组I : I国豆

高速缓存块

t位 丿s 位 b位

I 标 记 1 1 I I

I 0 0 0 0 I I I

m-1

标记 组索引 块偏移

组S- 1: I 匡邑I 标记 II

高速缓存块 I I

图 6- 28 直接映射高速缓存中的组选择

1. 直接映射高速缓存中的 行匹配

   在上一步中我们已经选择了某个组 i’ 接下来的一步就要确定是否有字 w 的一个副本存储在组 t 包含的一个高速缓存行 中。在直 接映射高速缓存 中这很容易，而 且很快，这是因为每个组只有一行。当且仅当设置了有效位， 而且高速缓存行中的标记与 w 的地址中的标记相匹配时 ， 这一行中包含 w 的一个副本。

   图 6- 29 展示了直接映 射高速缓 存中行匹配是 如何工作的。在这个例子中， 选中的组中只有一个高速缓存行。这个行的有效位设置了，所以我们知道标记和块中的位是有意义 的。因为这个高速缓存行中的标记位与地址中的标记位相匹配，所以我们知道我们想要的 那个字的一个副本确实存储在这个行中。换旬话说，我们得到一个缓存命中。另一方面， 如果有效位没有设晋，或者标记不相匹配，那么我们就得到一个缓存不命中。

选择的组 ( i ) :

L

=I? ( I ) 有效位必须设置

01234567

( 2 ) 高速缓存行中的标

记位必须与地址中 ＝？

的标记位相匹配; —

t位 s位

I 0110 I i

m-1

( 3 ) 如果 ( I ) 和 ( 2 ) 满足， 那么高速缓存命中，块偏移就选择起始字节。

标记 组索引 块偏移

图 6-29 直接映射高速缓存中的行匹配和字选择。在高速缓存块中， w 。表示字 w

的低位字节， W 1 是下一个字节 ，依 此 类推

1. 直接映射高速缓存中的 字选择

   一旦命中， 我们知道 w 就在这个块中的 某个地方。最后一步确定所需要的字在块中是从 哪里开始的。如图 6- 29 所示， 块偏移位提供了所需要的字的第一个字节的偏移。就像我们把高速缓存看成一个行的数组一样，我们把块看成一个字节的数组，而字节偏移是到

这个数组的一个索引 。在这个示例中， 块偏移位是 100 2’ 它表明 w 的副本 是从块中的字节 4 开始的（我们假设字长为 4 字节）。

1. 直接映射高速缓存中不命中时的行替 换

   如果缓存不命中 ， 那么它需要从存储器层次结 构中的下一层取出被请求的 块， 然后将新的块存储在组索引 位指示的组中的一个高速缓存行中。一般而言， 如果组中都是有效高速缓存行了， 那么必须要驱逐出一 个现存的行。对于直接映射高速缓存来说， 每个组只包含有一行，替 换策略非 常简单： 用 新取出的行替 换当前的行。

   1. 综合 ： 运行中的 直接映射高速缓存

      高速缓 存用来选择组 和标识行的机制极其简单， 因为硬件必须在几个纳秒的时间内完成这些 工作。不过，用 这种方式来处理位是很令人因惑 的。一个具体的例子能帮助解释清楚这个过程。假 设我们有一个直接映射高速缓存 ， 描述如下

      ( S , E , B , m ) = ( 4 , 1, 2 , 4 )

      换句话说， 高速缓存有 4 个组， 每个组一行， 每个块 2 个字节， 而地址是 4 位的。我们还假设每个字都是单字节的。当然， 这样一些假设完全是不现实的， 但是它们能使示例保持简单。

      当你初学高 速缓存 时， 列举出整个地址空间并划分好位是很有帮助的， 就像我们在

      图 6-3 0 对 4 位的示例所做的那样。关于这个列举出的空间， 有一些有趣的事情值得注意 ：

图 6-30 示例直接映射高速缓存的 4 位地址空间

• 标记位和索引位连起来唯 一地标识了内存中的每个块。例如， 块 0 是由地址 0 和 1

  组成的， 块 1 是由地址 2 和 3 组成的， 块 2 是由地址 4 和 5 组成的， 依此类推。

• 因为有 8 个内存块， 但是只有 4 个高速缓存组 ， 所以多个块会映射到同一个高速缓存组（即它们有相同的组索引）。例如， 块 0 和 4 都映射到组 0 , 块 1 和 5 都映射到组 1’ 等等。

• 映射到同一个高速缓存组的块由标记位唯一地标识。例如， 块 0 的标记位为 o, 而

  块 4 的标记位为 1, 块 1 的标记位为 o , 而块 5 的标记位为 1, 以此类推。

  让我们来模 拟一下当 CPU 执行一系列读的时候， 高速缓存的执行情况。记住对于这

个示例，我 们假设 CPU 读 1 字节的字。虽然这种手工的模拟很乏味，你 可能想要跳过它， 但是根据我们的经验，在学生们做过几个这样的练习之前，他们是不能真正理解高速缓存 是如何工作的。

初始时，高 速缓存是空的（即每个有效位都是 0 ) :

表中的每一行都代表一个高速缓存行。第一列表明该行所属的组， 但 是 请 记 住提供这个位只 是 为了方便，实 际 上 它并 不真是高速缓存的一部分。后面四列代表每个高速缓存行的实际 的 位 。 现在，让 我们来看看当 CP U 执行一系列读时，都 发 生 了 什 么 ：

1. 读地址 0 的字。因为组 0 的有效位是 o, 是缓存不命中。高速缓存从内存（或低一

   层的高速缓存）取出块 o , 并把这个块存储在组 0 中。然后， 高速缓存返回新取出的高速缓存 行 的 块[ OJ的 m[ O] ( 内存位置 0 的内 容）。

。 。

1. 读地 址 l 的字。这次会是高速缓存命中。高速缓存立即从高速缓存行的块[ 1] 中返

   回 m[ l ] 。高速缓存的状态没有变化。

   1. 读地址 13 的字。由于组 2 中的高速缓存行不是有效的，所 以 有缓存不命中。高速缓 存 把 块 6 加载到组 2 中，然 后 从新 的 高速缓存行的块[ 1] 中返回 m[ 13] 。

      1. 读地址 8 的字。 这会发生缓存不命中。组 0 中的高速缓存行确实是有效的， 但是标 1 记不匹配。高速缓存将块 4 加 载到组 0 中（替换读地址 0 时读入的那一行）， 然后从新的商速缓存行的块[ OJ中返回 m[ 8] 。

         组 有效位 标记位 块[OJ 块[ I]

1. 读 地 址 0 的字。又会发生缓存不命中，因 为在前面引用地址 8 时， 我们刚好替换了块 0 。 这就是冲突不命中的一个例子，也 就是我们有足够的高速缓存空间， 但 是 却交替地引 用 映 射 到 同 一 个组的块。

。 。 #

1. 直接映射高速缓存中的 冲突不命中

   冲突不命中 在真实的程序中很常见，会导 致令人困惑的 性能问题。当程序访问大小为

   2 的幕的数组时 ， 直接映射 高速缓存中通常 会发生冲突不命中。例如， 考虑一个计算两个向量点积的函数：

   float dotprod (fl oat x[8] , fl oat y [8 ])

   ｛

   f l oa t sum= 0. 0;

   inti;

for (i =O;i < 8 ; i ++ ) sum += x [ i ] * y [i] ;

r e t ur n sum;

对于 x 和 y 来说， 这个函数有良好的空间局部性， 因此我们期望它的命中率会比较高。不幸的是 ， 并不总是如此。

假设浮点数是 4 个字节， x 被加载到从 地址 0 开始的 32 字节连续内存中 ， 而 y 紧跟在

x 之后， 从地址 32 开始。为了简便 ， 假设一个块是 16 个字节（足够容纳 4 个浮点数）， 高速缓存 由两个组组成， 高速缓存的整个 大小为 32 字节。我们会假设变量 sum 实际上存放在一个 CPU 寄存器中， 因此不需要内存引用。根据这些假设每个 x [ i ] 和 y [ i ] 会映射到相同的高速缓存 组：

在运行时， 循环的第一次迭代引用 X [ O J’ 缓存不命中会导致包含 x [OJ ~x [ 3 ) 的 块被

加载到组 0。接下来是对 y [ O ] 的引 用 ， 又一次缓存不命中，导 致包含 y [ OJ ~ y [ 3 J 的 块被复制到组 o , 覆盖前一次引用复制进来的 x 的值。在下一次迭代中， 对 X (1 ) 的引用不命中，导致 x [ OJ ~ x [ 3 ] 的 块被加载回组 o, 覆盖掉 y [ OJ ~ y [ 3 ) 的块。因而现在我们就有了

一个冲突不命中，而 且实际上后面每次 对 x 和 y 的引用都会导致冲突不 命中， 因为我们在

x 和 y 的块之间抖动( t h ra s h ) 。术语“抖动” 描述的是这样一种情况， 即高速缓存反复地加载和驱 逐相同的高速缓存块的组。

简要来说就是， 即使程序有良好的空间局部性 ， 而且我们的高速缓存中也有 足够的空间来存放 x [ i ] 和 y [ i ] 的块， 每次引用还是会导致冲突不命 中， 这是因为这些 块被映射到了同

一个高速缓存组。这种抖动导致速度下降 2 或 3 倍并不稀奇。另外， 还要 注意虽 然 我们的示例极其简单，但是对于更大、更现实的直接映射高速缓存来说，这个问题也是很真实的。

幸运的是， 一 旦 程序 员 意 识 到 了 正 在 发 生 什 么 ，就 很 容易 修 正 抖 动问 题 。 一 个 很 简 单的方法 是 在 每 个 数 组 的 结 尾 放 B 字 节 的 填 充 。 例 如 ， 不 是 将 x 定 义 为 fl oa t x (8), 而是定义成f l oa 七 x [12 ) 。 假 设 在 内 存 中 y 紧 跟 在 x 后 面 ，我 们有 下 面这 样的 从数组元素到组 的映 射：

在 x 结 尾 加 了 填 充 ， x [i ] 和 y [ i ] 现 在 就 映 射 到 了 不同 的 组 ，消除 了 抖 动 冲突不命中。

已 练习题 6. 10 在前面 d o 七p r o d 的 例 子 中 ， 在 我 们 对数 组 x 做 了 填 充之后， 所有对 x

和 y 的引用 的命 中率是 多少？

m 为什么用中间的位来做 索引

你也许 会奇怪， 为什 么 高速 缓 存 用 中间的位 来作为 组 索 引 ， 而不是 用 高 位 。 为什么 用中间的位 更好 ， 是 有 很 好 的 原 因 的 。 图 6-31 说 明 了 原 因。 如 果 高 位 用做 索引， 那么． 一些连续的 内存块就会映射到相同的 高速缓 存 块 。例如 ， 在 图 中， 头四 个块映射到笫 一

个高速 缓 存 组 ， 笫 二 个四个块映射到笫二 个组， 依 此 类推。如 果一 个程序 有良好的 空间局 部 性 ， 顺 序 扫 描 一 个数组的元素， 那么在 任 何 时 刻 ， 高速 缓 存 都 只 保 存 着一个块大小i

高位索引 中间位索引

I

凶00

凶 01 凶 JO 卯 11

4组高速缓存

= #

组索引位

图 6- 3 1 为什么用中间位来作为高速缓存的索引

的数组内容。这样对高速 缓 存 的使用效率很低。相比较 而言， 以中间位作为 索引， 相 邻的块总是 映射到不同的 高速缓存行。在这里的情况中， 高速缓存能够存 放整个大小为 C 的数 组片 ， 这里 C 是 高速 缓 存的大小。

练习题 6. 11 假想一个高 速缓存， 用 地址 的 高 s 位做 组 索 引， 那 么 内存 块连续 的 片

( ch un k ) 会被映射到 同 一个 高速 缓存组。

1. 每个这样的连续的数组片中有多少个块？

2. 考虑下面的代码 ， 它 运行在 一 个高 速 缓存 形 式 为 CS , E, B, m)=(512, 1, 32,

   32. 的系统上 ：

   int array[4096];

   for (i = O; i < 4096; i++)

   sum += array [i] ;

在任意时刻，存储在高速缓存中的数组块的最大数量为多少？

1. 4. 3 组相联高速缓存

   直接映射高速缓存中冲突不命中造成的问题源千每个组只有一行（或者，按 照 我们的术语来描述就是 E = l) 这个限制。组相联高速 缓 存( set as socia t ive cac he ) 放松了这条限制， 所以每个 组都保存有多千一个的高速缓存行。一个 l < E < C/ B 的高速缓存通常称为 E 路 组相联 高速缓存。在下一节中，我 们会讨论 E = C/ B 这种特殊情况。图 6-32 展 示了一个 2 路组相联高速缓存的结构。

   组o 1 [1 门勹尸｀冒三昙I}Ea每组2竹

组I : I围记I 标记 1 1 高速缓存块

匝 I 标记 11 高速缓存块

匠 I 标记 1 1

高速缓存块

组S- 1: I 匡琶J I 标 记 11 苞速缓存块

图 6-32 组相联高速缓存 O < E< C/ B)。在一个组相联高速缓存中， 每个组包含多于 一个行。这里的特例是一个 2 路组相联高速缓存

1. 组相联高速缓存中的组选择

   它的组选择与直接映射高速缓存的组选择一样， 组索引位标识组。图 6-33 总结了这个原理。

   1. 组相联高速缓存中的行匹配和字选择

      组相联高速缓存中的行匹配比直接映射高速缓存中的更复杂，因 为它必须检查多个行的标记 位和有效位，以 确 定 所 请 求 的 字是 否 在 集合中。传统的内存是一个值的数组，以 地址作为输 入，并 返 回 存 储 在 那 个 地 址 的 值 。 另 一 方 面， 相联存储 器是 一 个 ( k e y , va lu e ) 对的数组 ， 以 k e y 为输入，返 回 与 输 入 的 key 相匹配的( ke y , value ) 对中的 valu e 值。因此， 我们可以 把组相联高速缓存中的每个组都看成一个小的相联存储器， ke y 是 标 记和有效位， 而 valu e 就是块的内容。

选择的组

组0:

会 组I :

匣口亘勹[ 匡门居勹［

匣 口亘勹1

高速缓存块高速缓存块

高速缓存块

匣口亘三]I 高速缓存块

t位 b位

组S- 1:

匡 荨 I

高速缓存块

I

m-I

标记

组索引

匝 口压口1 高速缓存块

组相联高速缓存中的组选择

图 6-34 展示了相联高速缓存中行匹配的基本思想。这里的一个重要思想就是组中的任何一行都可以包含任何映射到这个组的内存块。所以高速缓存必须搜索组中的每一行， 寻找一个有效的行，其标记与地址中的标记相匹配。如果高速缓存找到了这样一行，那么 我们就命中，块 偏移从这个块中选择一个字， 和前面一样。

=1? ( I ) 有效位必须设置

01234567

选择的组 ( i ) :

( 2 ) 高速缓存行中某一行

的标记位必须匹配地址中的标记位。

日 I I I wo I w, Iw 2 I 叭

( 3 ) 如果 ( 1 ) 和 ( 2 ) 为真， 那么高速缓存命中，然后块偏移选择起始字节。

t位

I 0110 I

m-1

标记

s位

-:­

l b

组索引 块偏移

图 6-34

组相联高速缓存中的行匹配和字选择

3. 组相联高速缓存中不命中时的行替换

如果 CP U 请求的字不在组的任何一行中，那 么 就 是 缓 存 不 命 中 ， 高速缓存必须从内存中取出包含这个字的块。不过，一旦高速缓存取出了这个块，该替换哪个行呢？当然， 如果有一个空行，那它就是个很好的候选。但是如果该组中没有空行，那么我们必须从中 选择一个非空的行，希 望 CP U 不 会 很 快 引 用 这个被替换的行。

程序员很难在代码中利用高速缓存替换策略，所以在此我们不会过多地讲述其细节。 最简单的替换策略是随机选择要替换的行。其他更复杂的策略利用了局部性原理，以使在 比较近的 将来引用被替 换的行的概率最小。例如， 最不 常使 用 ( Leas t-F req uently-Used, LF U ) 策略会替换在过去某个时间窗口内引用次数最少的那一行。最近最少使 用 ( Least­ Recently-Used, LRU ) 策略会替换最后一次访问时间最久远的那一行。所有这些策略都需要额 外的 时间 和 硬 件 。 但 是 ，越 往存储器层次结构下面走， 远离 CPU , 一次不命中的开销就会更加昂贵，用更好的替换策略使得不命中最少也变得更加值得了。

6. 4. 4 全相联高速缓存

全相联高速 缓 存( fully associative cache) 是由一个包含所有高速缓存行的组（即E = C/

B ) 组成的。图 6-35 给出了基本结构。

匣 仁亘 三 l 厂 高速缓存块匡 口 压口 1 高速缓存块

组

E =唯一的一组中有E =C/B行

匣 口 亘 口 1 高速缓存块

图 6- 35 全相联高速缓存( E = C/ B) 。在全相联高速缓存中， 一个组包含所有的行

1. 全相联高速缓存中的组选择

   全相联高速缓存中的组选择非常简单，因 为只 有一个组，图 6-36 做了 个 小 结 。 注 意地址中没有组索引位，地址只被划分成了一个标记和一个块偏移。

   I 匡荨厂一高速缓存块

m-1

整个高速缓存只有一个组， 所以默认总是选择组0。

t位 b位

标记 块偏移

组0 :

1 击 勹 歪 勹 1 高速缓存块匠 勹 亘口 1 高速缓存块

图 6-36 全相联高速缓存中的组选择。注意没有组索引位

2. 全相联高速缓存中的行匹配和字选择

   全相联高速缓存中的行匹配和字选择与组相联高速缓存中的是一样的， 如图 6- 37 所示。它们之间的区别主要是规模大小的问题。

   =l? ( l ) 有效位必须设置

整个高速缓存

( 2 ) 高速缓存行中某一行的 ＝？

霍昙严匹配地址中户—[—、

t位

l 0110

m-1

b位

100

( 3 ) 如果 ( I ) 和 ( 2 ) 满足，那么 高速缓存命中，然后块偏移选

择起始字节。

。I

标记 块偏移

图 6-37 全相联高速缓存中的行匹配和字选择

因为高速缓存电路必须并行地搜索许多相匹配的标记，构 造一个又大又快的相联高速缓存很困难，而且很昂贵。因此，全相联高速缓存只适合做小的高速缓存，例如虚拟内存 系统中的 翻译备用缓冲器 ( T LB) , 它缓存 页表项（见9. 6. 2 节）。

压 练习题 6. 12 下面的问题能帮助你加强理解高速缓存是如何工作的。有如下假设：

• 内存是字节寻址的。
• 内存访 问的 是 1 字 节 的 字（不是 4 字 节的 字）。

436 笫一部分 程序结构和执行

• 地址的宽度为 1 3 位 。

  • 高速 缓存是 2 路组相联的CE = 2 ) , 块 大小为 4 字 节 ( B = 4 ) , 有 8 个 组 ( 5 = 8 ) 。高速缓存的内容如下， 所有的数 字都是以 十 六进 制来表 示的：

    2路组相联高速缓存

    行0 行1

    。 。

    。 。

2 EB

3 06

OB

32 I 12 08 78 AD

4 C7 I 06 78 07 cs 05 I 40 67 C2 3B

6 91 I AO B7 26 2D FO 。

7 46 DE 1 12 co 88 37

下面的图展 示的是地址格 式（每个小方框 一个位）。指出（在图 中标 出）用来确定下列内容的字段：

co 高速缓存块偏移

CI 高速缓存组索引

CT 高速缓存标记

12 11 10 9 8 7 6 5 4 3 2 1 0

芦 练 习题 6 . 13 假 设一个程序运行在练 习题 6-1 2 中的机器上， 它引用地 址 Ox 0E 3 4 处的1 个 字 节的 字。 指 出 访问的高 速 缓存条 目和十 六 进 制 表 示 的 返 回的 高 速 缓 存 字 节值。指 出是否会发 生缓存不命 中。 如果会出 现缓存不命 中， 用 “ 一” 来表 示 “ 返回的高速缓存字节”。

1. 地址格式（每个小方框一个 位）：

   12 11 10 9 8 7 6 5 4 3 2 1 0

2. 内存引用：

沁囡 练习题 6 . 14 对于存储器地址 Ox ODDS, 再做一遍 练 习 题 6 . 1 3 。

1. 地址格式（每个小方框一个位）；

   12 11 10 9 8 7 6 5 4 3 2 I 0

2. 内存引用：

区 练习题 6. 15 对于内存 地址 Ox 1 F E4 , 再做 一遍练 习题 6. 13。

1. 地址格式（每个小方框一个位）：

12 11

仁

2. 内存引用：

   10 9 8 7 6 5 ．

   I I I I I I

   3 2 I

   ［

亿 练习题 6. 16

制内存地址。

对于练习题 6. 1 2 中的 高速 缓存 ， 列 出 所 有的 在 组 3 中会命 中的 十 六进

1. 4. 5 有关写的问题

   正如我们看到的， 高速缓存关于读的操作非常简单。首先， 在高速缓存中查找所需字

   w 的副本 。如果命中， 立即返 回字 w 给 CPU。如果 不命中，从 存储器层次结构中较低层中取出包含字 w 的块， 将这个块 存储到某个高速缓存行中（可能会驱逐一个有效的行）， 然后返回字 w 。

   写的情况就要复杂一些了。假设我们要写一个已经缓 存了的字 w ( 写命 中， w r it e hit ) 。在高速缓存 更新了它的 w 的副本之后， 怎么更新 w 在层次 结构中紧接着低一层中的副本呢？ 最简单的 方法， 称为直写 ( w rit e- t h ro ug h ) , 就是立即将 w 的高速缓存块写回到紧接着的低一层中。虽然简单，但是直写的缺点是每次写都会引起总线流批。另一种方法，称为

   写回 ( writ e- back ) , 尽可能地推迟更新，只有当替换算法要驱逐这个更新过的块时，才把

   它写到紧接着的低一层中。由于局部性，写回能显著地减少总线流量，但是它的缺点是增 加了复 杂性。高速缓存必须为每个高速缓存行维护一个额外的修改位 ( d ir t y bit), 表明这个高速 缓存块是否被修改过。

   另一个问 题是如何处理写不命中。一种方法， 称为写分配( w rite-a llocat e ) , 加载相应的低一层中的块到高速缓存中，然后更新这个高速缓存块。写分配试图利用写的空间局部 性，但是缺点是每次不命中都会导致一个块从低一层传送到高速缓存。另一种方法，称为 非写 分配( not- w r ite-a lloca te ) , 避开高速缓存， 直接把这个字写到低一层中。直写高速缓存通常 是非写分配的。写回高速缓存通常是写分配的。

   为写操作优 化高速缓存是一个细致而困难的问题， 在此我们只略讲皮毛。细节随系统的不同而 不同， 而且通常 是私有的， 文档记录不详细。对于试图 编写高速缓存比较友好的

程序的程序员来说，我们建议在心里采用一个使用写回和写分配的高速缓存的模型。这样建议有几个原因。通常，由千较长的传送时间，存储器层次结构中较低层的缓存更可能使用写回， 而不是直写。例如， 虚拟内存系统（用主存作为存储在 磁盘上的 块的缓存）只使用写回。但是由于逻辑电路密度的提高，写回的高复杂性也越来越不成为阻碍了，我们在现代系统的所有层次上都能看到写回缓存。所以这种假设符合当前的趋势。假设使用写回写分配方法的另一个原因是，它与处理读的方式相对称，因为写回写分配试图利用局部性， 因此，我们可以在高层次上开发我们的程序，展示良好的空间和时间局部性，而不是试图为某一个存储器系统进行优化。

6. 4. 6 一个真实的高速缓存层次结构的解剖

到目前为止，我们一直假设高速缓存只保存程序数据。不过，实际上，高速缓存既保 存数据， 也保存指令。只保存指令的高速缓存称为 i-ca che 。只保存程序数据的高速缓存称为 d-ca che。既保存指令又包括数 据的高速缓存称为统 一的 高速缓存( unified cache ) 。现代处理器包括独立的 i- cache 和 cl- ca che 。这样做有很多原因。有两个独立 的高速缓存， 处理器能够同时读一个指令字和一个数据字。i-cache 通常是只 读的， 因此比较简单。通常会针对不同的访问模式来优化这两个高速缓存，它们可以有不同的块大小，相联度和容量。使 用不同的高速缓存也确保了数据访问不会与指令访问形成冲突不命中，反过来也是一样， 代价就是可能会引起容量不命中增加。

图 6-38 给出了 Intel Core i7 处理器的高速缓存层次结构。每个 CPU 芯片有四个核。每个核有自己私有的 L l i-cac he 、L l cl- cache 和 L2 统一的高速缓存。所有的核共享片上L3 统一的高速缓存。这个层次结构的一个有趣的特性是所有的 SRAM 高速缓存存储器都 在 CP U 芯片上。

处理器封装

L3统一的高速缓存

- ‘-. - - - - - _-’– - - - - - -气产尸产 ) J :

图 6- 38 Intel Core i7 的高速缓 存层次结构

图 6-39 总结了 Core i7 高速缓存的 基本特性。

6. 4. 7

图 6-39 Core i7 高速缓存层次结构的特性

高速缓存参数的性能影响

有许多指标来衡量高速缓存的性能：

• 不命 中率 ( m is s r a t e ) 。在一 个程序执行或程序的一部分执行期间，内 存引用不命中的比率。它是这样计算的： 不命 中数 量／引 用数 量。

  • 命中率( h it ra t e ) 。命 中的内存引用比率。它等于 1 一不命 中率。

  • 命中时间 ( h it t im e ) 。从高速缓存传送一个字到 C P U 所需的时间， 包括组选择、行确认和字选择的时 间。对于 L1 高速缓存来说，命 中时间的数量级是几个时钟周期。

  • 不命 中处罚 ( m is s p e n al t y ) 。由于不命中所需要的额外的时间。L1 不命中需要从 L2 得到服务的处罚 ，通常 是数 10 个周期 ；从 L3 得到服 务的处罚， 50 个周期；，从 主存得到的服务的处罚 ， 200 个周期。

    优化高速缓存的成本和性能的折中是一项很精细的工作， 它需要在现实的基准程序代码上进行大量的模拟， 因此超出了我们讨论的范酣。不过， 还是可以认识一些定 性的折 中考量的。

1. 高速缓存大小的影响

   一方面，较大的高速缓存可能会提高命中率。另一方面，使大存储器运行得更快总是 要难一些的 。结果， 较大的高速缓存可能会增加命中时间。这解释了为什么 L1 高速缓存比 L2 高速缓存小 ，以 及为什么 L2 高速缓存比 L3 高速缓存小 。

2. 块大小的 影响

   大的块有利有弊。一方面，较大的块能利用程序中可能存在的空间局部性，帮助提高 命中率。 不过， 对于给定的高速缓存 大小， 块越大就 意味着高速缓存行数越少，这 会损害时间局部性比空间局部性更好的程序中的命中率。较大的块对不命中处罚也有负面影响， 因为块越大 ， 传送时间就越长。现代系统（如C o r e i7 ) 会折中使高速缓存块包含 64 个字节。

3. 相联度的 影响

   这里的问 题是参数 E 选择的影响 ， E 是每个组中高速缓存行数。较高的相联度（也就是 E 的值较大）的优点是降低了高速缓存 由于冲突不 命中出现抖动的可能性。不过， 较高的相联 度会造成 较高的成本。较高的相联度实现起来很昂 贵， 而且很 难使之速度变快。每一行需要更多的标 记位， 每一行需 要额外的 LRU 状态位和额外的控制逻辑。较高的相联度会增加命中时间，因为复杂性增加了，另外，还会增加不命中处罚，因为选择牺牲行的 复杂性 也增加了。

   相联度的选择最终变成了命中时间 和不命中处罚 之间的折中。传统上， 努力争取时钟频率的高性能系统会 为 L1 高速缓存选择较低的相联度（这里的不命中处罚 只是几 个周期）， 而在不 命中处罚比较高的较低层上使用比较小的相联度。例 如， I n t e l Core i7 系统中， L1 和 L2 高速缓存 是 8 路组相联的， 而 L3 高速缓存是 16 路组相联的。

4. 写策略的 影响

   直写高 速缓存比较容易实现， 而且能使用独立于高速缓存的写缓冲 区 ( w r it e buffer),

   用来更 新内存。此外， 读不命中开销没这么大， 因为它们不会触发内存写。另一方面，写

回高速缓存引起的传送比较少，它允 许更多的到内存的带宽用于执行 OMA 的 1/0 设备。此外 ， 越往层次结构下面走 ， 传送时间增加， 减少传送的数量就变得更 加重要。一般而言， 高速缓存越往下 层，越 可能使用写回而不是直写。

日 日 高速缓存行、组和块有什么区别？

很容易混淆高速缓存行、组和块之间的区别。让我们来回顾一下这些概念，确 保概念清晰：

• 块是一个固定大小的信息 包， 在高速缓存和主存（或下一层高速缓存）之间来回传送。

  • 行是高速 缓存中的一个容 器，存 储块以及其他信 息（例如 有效位和标记位）。

  • 组是一个或 多 个行的集合 。直接映 射高速 缓存中的组只由一行组成。组相联和全相联高速缓存中的 组是由多 个行组成的。

    在直接映射高速缓 存中， 组和行实际上 是等价的 。不过 ， 在相联高速缓存中， 组和行是很不一 样的， 这两个词 不能互换 使用。

    因为一 行总是存储一个块 ， 术语“行” 和“块“ 通常互换 使用。例如， 系统专 家总是说高速缓 存的“行大小＂， 实际上 他们指 的是块大小。这样的 用 法十分普遍，只要你理解块和行 之间的 区别 ， 它不会 造成任何误会。

1. 5 编写高速缓存友好的代码

   在 6. 2 节中， 我们介绍了局部性的思想， 而且定性地谈了一下什么会具有良好的局部性。明白了高速缓存存储器是如何工作的，我们就能更加准确一些了。局部性比较好的程 序更容易有较低的不命中率，而不命中率较低的程序往往比不命中率较高的程序运行得更 快。因此，从 具 有良好局部性的意义上来说 ， 好的程序员 总是应该试着去编写高速缓存友 好( ca c he fr ie nd ly ) 的代码。下面就是我们用来确保代码高速缓存友好的基本方法 。

   1. 让最常见的情况运 行得快。程序通常把大部分时间都花在少僵的核心函数上，而这些函数通常把大部分时间都 花在了 少量循环上。所以要把注意力集中在核心函数里的循环上， 而忽略其他部分。

      2 ) 尽量减 小每 个循 环 内部 的缓存不命 中数量。在其他条件（例如加载和存储的总次

      数）相同的情况下， 不命中率较低的循环运行得更快。

      为了看看实际上这是怎么工作的 ， 考虑 6. 2 节中的函数 s umv e c :

      int sumvec(int v[N])

      ｛

      inti, sum= O;

for (i = 0; i < N; i ++) sum+= v[i];

return sum;

这个函数高速缓存友好吗？ 首先， 注意对 于局部变量 1 和 s um, 循环体有良好的时间局部性。实际上，因为它们都是局部变量，任何合理的优化编译器都会把它们缓存在寄存器文 件中， 也就是存储器层次结 构的最高层中。现在考虑一下对向量 v 的步长为 1 的引用。一般而言， 如果一个高速缓存的块大小为 B 字节， 那么一个步长为 K 的引用模式（这里 k 是以字为单位的）平均每次循环迭代 会有 m in ( 1 , (wordsize X k) / B) 次缓存不命中。当 k = l 时 ，它 取最小值， 所以对 v 的步长为 1 的引用确实是高速缓存友好的。例如，假 设 v 是块对齐的， 字为 4 个字节， 高速缓存块为 4 个字，而 高速缓存初始为空（冷高速缓存）。然

后，无 论 是 什 么 样的高速缓存结构，对 v 的 引 用 都 会得到下面的命中和不命中模式：

v [ i l i=O i=I i=2 i=3 i=4 i=S i=6 i=7

1 访问顺序， 命中[h]或不命中 [m] I/ I [ml I 2 [h] I 3 (h] I 4 [h] I 5 [m) I 6 [h] I 7 [h] 8 [h]

在这个例子中，对 v [ O] 的 引 用 会 不命中， 而相应的包含 v [ O] ~ v [ 3 ] 的 块 会 被从内存加载到 高速缓存中。因此， 接下来三个引用都会命中。对 v [ 4 ] 的引 用会导致不命中， 而一个新 的块被加载到高速缓存中， 接下来的三个引用都命中，依 此类推。总的来说， 四 个引用中， 三个会命中，在 这种冷缓存的情况下， 这是我们所能做到的最好的情况了。

总之，简 单 的 s u mv e c 示例说明了两个关千编写高速缓存友好的代码的重要问题：

• 对 局 部 变量的反复引用是好的，因 为编译器能够将它们缓存在寄存器文件中（时间局部性）。

• 步长为 1 的引用模式是好的，因 为存储器层次结构中所有层次上的缓存都是将数据存储为连续的块（空间局部性）。

  在对多维数组进行操作的程序中， 空间局 部性尤其重要。例如， 考 虑 6. 2 节 中 的

  s umar r a y r o ws 函 数 ，它 按 照 行 优 先 顺 序对一个二维数组的元素求 和：

  int s umarr a yr o 甘 s (int a[M] [NJ)

  ｛

  inti, j, sum= O;

for (i = 0; i < M; i ++)

for (j = O; j < N; j++) sum += a[i] [j];

return sum;

由于 C 语言以行优先顺序存储数组，所 以 这 个函数中的内循环有与 s u rnv e c 一样好的步长为 1 的访问 模式 。例如，假 设 我们对这个高速缓存做与对 s urnv e c 一 样的假设。那么对数组 a 的引用会得到下面的命中和不命中模式：

a [ i J f j J J=O

J = I

)=2

)=3

}=4

j=5

j=6

j=7

但是如果我们做一个看似无伤大雅的改变—— 交换循环的次序，看 看 会 发生 什么 ：

int sumarraycols(int a[M] [N])

｛

inti, j, sum= O;

for (j = 0; j < N; j++)

for (i = 0; i < M; i ++) sum += a [i] [j] ;

return sum;

在这种情况中， 我们是一列一列而不是一行一行地扫描数组的。如果我们够幸运， 整 个数组都在 高速缓存中，那 么 我们也会有相同的不命中率 1/ 4。不过， 如果数组比高速缓存要

大（更可能出现这种情况）， 那 么 每 次 对 a [il [j l 的 访 问 都 会 不 命 中！

较 高 的不 命 中 率 对 运 行 时 间 可 以 有 显 著 的 影 响 。 例 如 ， 在 桌 面 机 器 上 ， s u mar r a y­ r o ws 运 行 速 度 比 s u marr a y c o l s 快 25 倍。总之 ， 程 序 员 应 该 注 意 他 们 程 序 中 的 局部性， 试着编写利用局部性的程序。

; 练习题 6. 17 在信号处理和科学计算的应用中，转置矩阵的行和列是一个很重要的问题。从局部性的角 度 来 看， 它 也 很 有 趣， 因 为 它 的 引 用 模 式 既 是 以行 为 主 ( ro w­ w is e ) 的， 也 是以 列 为 主( co l u m n- w is e ) 的。例如， 考虑下面的转暨 函数：

typedef int array[2] [2];

3 void transposel(array dst, array src)

4 {

inti, j;

7 for (i = O; i < 2; i++) {

8 for (j = O; j < 2; j++) {

9 dst [j] [i] = src[i] [j] ; 10 }

｝

12 }

假设 在一 台具 有如下属性的机器上运行这段代码 ：

• sizeof (int) ==4。
  • sr c 数组从地址 0 开始 ， d s t 数组从地址 1 6 ( 十进制）开始。
• 只有一个 L1 数据高速缓存， 它是 直接映射的、直写和 写分 配的， 块 大小为 8 个字节。
• 这个高 速 缓存总的大小 为 1 6 个 数据 字 节 ， 一开始是 空 的。
• 对 sr c 和 d s t 数组 的访问 分别是读和 写 不命 中的唯 一来 源。

1. 对每个r o w 和 c o l , 指明 对 s r c [ row] [col ) 和 d s t [row] [col ] 的 访问是命中( h)

   还是 不命 中( m ) 。 例如， 读 s r c [OJ [ OJ 会 不命 中， 写 d s t [ O J [ OJ 也不命 中。

d s t 数组

列0 列 l

m 0行

1行

2. 对于一个大小 为 32 数据 字 节的高速缓存重 复这 个练 习。

sr c数组

列0 列l

m

沁 员 练习题 6. 18 最 近 一 个很 成 功 的 游 戏 S im A q ua rium 的 核心就是 一 个 紧 密 循 环 ( tight loo p ) , 它计算 256 个 海藻( algae ) 的平均位置。 在一 台具 有块大小为 16 字 节 ( B = 1 6 ) 、整个大小为 10 24 字 节的直接映射数据缓存的机器 上测量它的高速缓存性能。 定 义如下：

struct algae_position grid[16] [16]; int total_x = 0, total_y = O; inti, j;

还有如下假设：

• sizeof ( i n t ) ==4 。

• g r i d 从内存地 址 0 开始。

• 这个高速缓存开始时是空的。

• 唯一的内存 访问是 对数 组 gr i d 的元素的 访问。放在寄存器中。

  确定下面代码的高速缓存性能：

  for (i = O; i < 16; i++) {

  for (j = 0; j < 16; j++) { total_x += grid[i] [j] .x;

变量 i 、 j 、total x和七0 七a l y 存

｝

for (i = O; i < 16; i++) {

for (j = O; j < 16; j++) { total_y += grid[i] [j] .y;

10 ｝

11 ｝

1. 读总数是多少？

2. 缓存不命中的读总数是多少？

3. 不命中率是多少？

   饬 练习题 6. 19 给定 练 习题 6. 18 的假设， 确定下列代码的高速缓存性能：

   for (i = O; i < 16; i++){

   for (j = 0; j < 16; j++) { total_x +=grid[j] [i] .x; total_y +=grid[j] [i] .y;

   ｝

   ｝

4. 读总数是多少？

5. 高速缓存不命中的读总数是多少？

6. 不命中率是多少？

7. 如果高速缓存有两倍大，那么不命中率会是多少呢？

   讫§ 练习题 6. 20 给定 练 习题 6. 18 的假 设， 确定 下列代码 的高 速缓存 性能 ：

   for (i = O; i < 16; i++){

   for (j = O; j < 16; j++) { total_x +=grid[i] [j] .x; totaLy +=grid[i] [j] .y;

   ｝

   ｝

8. 读总数是多少？

9. 高速缓存不命中的读总数是多少？

10. 不命中率是多少？

11. 如果高速缓存有两倍大，那么不命中率会是多少呢？

6. 6 综合：高速缓存对程序性能的影响

本节通过研究高速缓存对运行在实际机器上的程序的性能影响，综合了我们对存储器层次结构的讨论。

6. 6. 1 存储器山

一个程序从存储系统中读数据的速率称为读吞吐 量( r e a d throughput), 或者有时称为读带宽( r e a d b a n d w id t h ) 。如果一个程序在 s 秒的时间段内读 n 个字节，那 么 这段时间内的读吞吐量就等于 n / s , 通常以兆字节每秒( M B / s ) 为单位。

如果我们要编写一个程序，它从 一个紧密程序循环( t ig h t program loop) 中发出一系列读请求 ，那 么测 量出 的读 吞 吐 量能让我们看到对于这个读序列来说的存储系统的性能。图 6-40

code/mem/mountainlmountain.c

long data[MAXELEMS];

2

I* The global array we’ll be traversing *f

1. I* test - Iterate over first “elems” elements of array “data” with

   1. * stride of “stride”, using 4 x 4 loop unrolling. s *I

      6 int test (int elems, int stride)

      7 {

2. long i, sx2 = stride*2, sx3 = stride*3, sx4 = stride*4;

3. long accO = 0, accl = 0, acc2 = 0, acc3 = O; 1o long length = el ems;

   11 long limit = length - sx4; 12

4. /* Combine 4 elements at a time *I

5. for (i = O; i < 1i 工 t ; i += sx4) {

6. accO = accO + data [i] ;

7. accl = acc1 + data[i+stride];

8. acc2 = acc2 + data[i +sx2] ;

9. acc3 = acc3 + data[i +sx3] ; 19 }

   20

10. I* Finish any remaining elements *I

11. for (; i < length; i+=stride) {

12. accO = accO + data [i] ; 24 }

    25 return ((accO + accl) + (acc2 + acc3)); 26 }

    27

    28 I* run - Run test(elems, stride) andreturn read throughput (MB/s). “size” is in bytes, “stride” is in array elements, and Mhz is CPU clock frequency in Mhz.

32 double run (int size, int stride, double Mhz) 33 {

1. double cycles;
2. int elerns = size / sizeof (double) ; 36
3. test (elerns, stride); I* Warm up the cache *I
4. cycles = fcyc2(test, elerns, stride, 0); I* Call test(elerns,stride) *I
5. return (size / stride) / (cycles / Mhz); I* Convert cycles to MB/s *I 40 }

code/memlmountain/mountain.c

图 6-40 测量和计 算读吞吐量的函数。我们可以通过以不同的 s i ze ( 对应千时间局部性）和

s tr i d e ( 对应于空间局部性）的值来调用r un 函数， 产生某台计算机的存储器山

给出了一对测量某个读序列读吞吐量的函数。

t e s t 函数通过以 步长 s tr i de 扫描一个数组的头 e l e ms 个元素来产生读序列。为了提高内 循环中 可用 的并行性， 使用了 4 X 4 展开（见5. 9 节）。r un 函数是一个包装函数， 调用 t e 江 函数， 并返回测最出的读吞吐量。第 37 行对 t e s t 函数的词用会对高速缓存做暖身。第 38 行的 f c yc 2 函数以参数 e l e ms 调用 t e s t 函数， 并估计 t e s t 函数的运行时间，以 CP U 周期为单位。注意，r un 函数的参数 s i ze 是以字节为单 位的， 而 t e s t 函数对应的参数 e l e ms 是以数组元素为单位的。另外 ， 注意 第 39 行将 MB/ s 计算为 1矿字节／秒， 而不是 220 字节／秒。

r un 函数的参数 s i ze 和 s tr i de 允许我们控制产生出的读序列的时间和空间局部性程度。 s i ze 的值越小， 得到的工作集越小 ， 因此时间局部性越好。s tr i de 的值越小， 得到的空间 局部性越好。如果我们反复以 不同的 s i ze 和 s tr i de 值调用r un 函数， 那么我们就能 得到一个读带 宽的时间和空间 局部性的二维函数， 称为存储器山 ( memor y moun­ tain )[ ll 2] 。

每个计算 机都有表明它存储器系统的能力特色的唯一的存储器山。例如， 图 6- 41 展示了 Intel Core i7 系统的存储器山。在这个例子中， s i ze 从 16KB 变到 128K B, stride 从 1 变到 1 2 个元素，每 个元素是一个 8 个字节的 l o ng i nt 。

空间局部性

的斜坡

16000

4000

2000

Core i7 Haswell

2.1 GHz

32 KB LI 高速缓存

256 KB L2高速缓存

8MB L3高速缓存

64B块大小

时间局部性

山脊

3 1.28K

512K

2M

盓

128M

大小（字节）

图 6- 41 存储器山。展示了读吞吐量， 它是时间 和空间局部性的函数

这座 Core i7 山的地形地势展现了一个很丰富 的结构。垂直千大小轴的是四条山脊， 分别对应 千工作 集完 全在 Ll 高速缓存、LZ 高速缓存、L3 高速缓存和主存 内的时间局部性区域。注意 ， Ll 山脊的最高点（那里 CP U 读速率为 14GB / s ) 与主存山脊的最 低点（那里

CPU 读速率 为 900M B/ s) 之间的差别有一个 数量级。

在 LZ、 L3 和主存山脊上，随 着步长的增加， 有一个空间局部性的斜坡， 空间局部性下降。注意，即使当工作集太大，不能全都装进任何一个高速缓存时，主存山脊的最高点 也比它的最低点高 8 倍。因此，即 使是当程序的时间局部性很差时， 空间局部性仍然能补救，并且是非常重要的。

有一条特别有趣的平 坦的山脊线， 对于步长 1 垂直于步长轴， 此时读吞吐輩相对保持不变， 为 1 2GB/ s , 即使工作集超出了 L1 和 L2 的大小。这显然是由 于 Core i7 存储器系统中的硬件预取( prefe tch ing ) 机制， 它 会自动 地识别顺序的、步长为 1 的引用模式， 试图在一些块被访问之前， 将它们取到高 速缓存中。虽然文档里没有记录这种预取算法的 细节， 但是从存储器山可以明显池看到这个算法对小步长效果最好 这也是代码中要使用步长 为 1 的顺序访问的另一个理由。

如果我们从这座山 中取出一个片段， 保持步长为常数， 如图 6-42 所示， 我们就能很 清楚地看到高速缓存的大小和时间局部性对性能的影响了。大小最大为 32KB 的工作集完全能放进 Ll cl-c ache 中， 因此， 读都是由 L1 来服务的， 吞吐最保持在峰值 12GB/ s 处。大小最大为 256KB 的工作集完全能放进统一的 L2 高速缓存中 ， 对千大小 最大为 8 M , 工作集完全 能放进统一的 L3 高速缓存中。更大的工作集大小 主要由主存来 服务。

14 000

12 000

10 000

乏芦 8000

、

主存区域 L3高速缓存区域

LI高速

L2高速缓存区域 缓存区域

i 6000

4000

2000

0 .

工作集大小（字节）

图 6-42 存储 器山中时间局部性的山脊。这幅图展示了图 6-41 中 s 七r i cte = S 时 的 一 个 片段

L2 和 L3 高速缓存区域最左边的边缘上读吞吐量的下降很有趣， 此时工作集大小为256K B 和 8 MB, 等于对应的高速缓 存的大小。为什么会出现这样的下降， 还不是完全清楚 。要确认的唯一方法就是执行一个详细的高速缓存模 拟， 但是这些下降很有可能是与其他数据和代码行的冲突造成的。

以相反的方向横切这座山，保持工作集大小不变，我们从中能看到空间局部性对读吞吐量 的影响。例如， 图 6-43 展示了丁作集大小固定为 4MB 时的片段。这个片段是沿着图 6- 41 中的L3 山脊切的，这里， 工作集完全能够放到 L3 高速缓存中， 但是对 L2 高速缓存来说太大了。

注意随着步长从 1 个字增长到 8 个字， 读吞吐量是如何平稳地下降的。在山的这个区域中， L2 中的读不命中会导致一个块从 L3 传送到 L2。后 面在 L2 中这个块上会有一定数量的命中， 这是取决千步长的 。随着步长的增加， L 2 不命中与 L2 命中的比值也增加了。因为服务不命中要比命中更慢， 所以读吞 吐量也下降了。一旦步长达到了 8 个字， 在这个系统上就等于块的 大小 64 个字节了， 每个读请求在 L2 中都会不命中， 必 须从 L3 服务。

因此， 对于至少为 8 个字的步长来说， 读吞吐最是一个常数速率， 是由从 L3 传送高速缓存块到 L2 的速率决定的。

12 000

10 000

8000

6000

4000

2000

s1 s2 s3 s4 s5 s6 s7 s8

步长 ( X 8字节）

s9 s10 s11

图 6-43 一个空间局部性的斜坡。这幅图展示了图 6-41 中大小= 4MB 时的一个片段

总结一下我们对存储器山的讨论，存储器系统的性能不是一个数字就能描述的。相 反，它是一座时间和空间局部性的山，这座山的上升高度差别可以超过一个数量级。明智 的程序员会试图构造他们的程序，使得程序运行在山峰而不是低谷。目标就是利用时间局 部性， 使得频繁使用的 字从 L1 中取出， 还要 利用空间局部性， 使得尽可能多的字从一个L1 高速缓存行 中访问到。

讫 练习题 6. 21 利用 图 6-41 中的存储器 山来估计从 L1 d- ca c h e 中读 一个 8 字 节的 字所需要的 时间（以 CPU 周期为 单位）。

1. 6. 2. 重新排列循环以提高空间局部性

   考虑一对 n X n 矩阵相乘的问题： C= AB 。例如， 如果 n = 2 , 那么

   [ C11C 12 ] = [ au a12][加b 12 ] C21 c22 a 21a22 b21 b22

   其中

   c11 =a11b11 +a12b21

   C1z = a 11 如 + a12 b22

   c21 = a 21 b11 +a22 b21 C22 = a 21 如 + a 22b 22

   矩阵乘法 函数通常是用 3 个嵌套的循环来实现的，分别 用 索引 z、 1 和K 来标识。如果改变循环的次 序， 对代码进行一些其他的小改动， 我们就能 得到矩阵乘法的 6 个在功能上等价的版本 ， 如图 6-44 所示。每个版本都以它循环的顺 序来唯一地标识。

   在高层次来看， 这 6 个版本是非常相似的。如果加 法是可结 合的， 那么每个版本计算出的结果完全 一样气 每个版本总共都执行 O ( n3 ) 个操作， 而加法和乘法的数量相同。A

8 正如我们在第 2 章中学到的 ，浮点 加法是可交换的 ， 但是通常是 不可结 合的。实际 上，如果 矩阵不 把极大的数和极小的数混在一起一存储物理属性的矩阵常常这样，那么假设浮点加法是可结合的也是合理的。

和B 的 矿个 元素中的每一个都要读 n 次；计 算 C 的 示 个 元素中的 每一个都要对 n 个值求和。不过，如果分析最里层循环迭代的行为，我们发现在访问数量和局部性上还是有区别的。为了分析，我们做了如下假设： - - ,.三

• 每个数组都是一个 do ub l e 类型的 n X n 的数组， s i z e o f (d o ub l e ) = B。

• 只 有一个高速缓存，其 块大小为 32 字节( B = 32 ) 。 ＇，

• 数组大小 n 很大， 以至于矩阵的 一行都不能完全装进 Ll 高速缓存中。

  ·编译器将局部变量存储到寄存器中，因此循环内对局部变量的引用不需要任何加载

或存储指令

codelm.emlmatmult/mm.c for (i = 0; i <::i;i; i++)

for (j = 0; j < n; j ++)

sum= 0.0;

for (k = 0; k < n ;, k++)

sum += A[i] [kl*B[k] [j];

for (j for

, ‘Cl-

code/memlmatmultlmm.c

== O; j < ’n; · j ++)

(i a;= 0 ; i < n ; i ++) {

• sum = 0., , ,,,

  , f or , (k = 0; k < n; k++)

  ’ ··· · s um ,f = A [i] [k] *B [k] [j];

C [i] [j] += suin;

• ; ·; . ,.

  C[il[j] += sum;

·’·_;, • h ide/ me成lmatmultlmm.,c - ＿

code/mem/matmultlmm.c

. • _ a) ij k版 本 、． ． ， ｀ 一 ,.. ,:._.,· . _,.. ,,• • _b) j ik版本 ， ． ． ．

, • ’ : : .,·

• ;,, : ., ‘、 . . . ．．屯: ..,. .

  • .,.. ,,·. ,• , _, , ,. · I ‘· . …_-

  ., ’ , . , r· .. ..· ,’•_,

code/mem/matmultlinm.c code/mem/matm it’Wmm.c

C .’ , . ’ . . . . • ·,: · ’ . .•. · , .· , ·, ., . , . . .. , ’ . ’’ , j l ’ •.- ., , , , ．、.•··. .. ·.’’ t.,r. •.· · ·’’ · 千·二J- ，

,> ＇

, · , : f or · ( j ’ ==· O; j < Ii; j +’+) , ’ ··• f ’ fo r ’ ’ Ck •,;; O; ‘.k ‘< ri;’ k ++) ·····-

2 ;· ‘.< < .’ fo r ( k: =, ‘O; k < ri.; k ++) { i- ;•. · , :_• ; :2 ·, ,, ;;, _‘f or \ f; ,,;_ o ;’ j <: n ;;-;j ++f { ‘一，心 t 1

3 . .. _,·.

._ · .: r.

:;,- J3[k]{jJ,; ., -:.

:i .. ·,. ;,.· '

) 3 ;; ; , i ‘. ) • :• r . r= _B[k} .f jJ ,;: >’::i ) -1’ ; ;., ;:,: . :fi 心

4 for (i = O; i < n; i++) 4 for (i =;o, O; _, i

社吵 ．，

• , 、 . . ! ..!

5 , C[i] [j] += A[i] [k]*r; . . 5 C i)(jJ += A[i] [k]*r;

/ _.,:– · ·, ’ }_ :-, :• . _ ; . :, -,-: . ,, · ; : , . i : - .·,.. ;. 6 ’ \_: ·’·: j:’ f: : ’ ,; ·’.,’. .:·

codelmem/matmult/mm.c

, , ’ 飞 ；｀ ＇ ＇， 、

．令

钉

c) j ld版本

codelmem/matmultlmm.c

d ) 炉版本

code/mem/matmultlmm.c

,; . ;’, .. . . . , \

, ’ , . . . . ··, ,,,•

‘产 i ,’ ,

.,.

for (k = O; k < Ii; k++,) · -, : . ..

· · ·

f or ’ Ci -’ ‘= b;、.i

< ri;· i ++) ‘. . , ｀

for (i = O; i < n; i++) { i ,

r = A (i] [k] ; , • ,

for (j = O; j < n; j++) C[i] [j] += r*B[k] [j];

｝

codelmemlmatmultlmm.c

e ) 的版本

f o 士 ( k = O; k < n; k++) { r = A[i][k];

for (j = O; j < n; j++)

C [i] [j] += A [i] [k] *r; rt d t

心:• < }

code/mem/matmultlmm.c

f) ikj版本

图 6- 44 矩阵乘法的六个版本。每：个 版本都以它循环的顺序来唯一地标识

, _,. ,: _;. . ‘! '

_ ; , , . , .. .

．～, -

户:·, 占’

_: l .:: f. ·. ‘..,-: ·:..-,;:- … :·: . . ·-": ; ·,, _ _.,i

.,.>.._,.,.,,·;’··七,; ;一．，,．, /，:＇}·;; 言获

图 6;,45总结了我们对内循环的分析结果。注意6个版本成对地形成了 3个等价类，’;._用内循环中访问的矩阵对来表示每个类。例如. 版本 ij k 和ji k 是类f.-1$的成员，: 因为它们在最内层的循环中引用的是矩阵A和I?(而不是C),。对千每个类，我们统计了每个内循环

迭代中加载（读）和存储（）写的数量，每次循环迭代中对A、B 和C的引用在高速缓存中丕

命中的数量，以及每次迭代缓存不命中的总数。

* 类 AB 例程的内循环（图t 44a 和图 6— b)以步长1 扫描数组 A 的- 行汗 因为每个高

速缓存块保存四个 8 字节的字，A 的不命中率是每次迭代不 命中 0·.-25 次。另 一方 面，内

循环以步长 n 扫描数组B 的一列。因 为 n 很大，每次对数组 B 的访问都会不命中，所以每次迭代总共会有 1 心 5 次不命中。

矩阵乘法版本

‘, • (类）;··,.

匕 、 ’ . '

ijk &jik (AB)

｀｀

丿kt& kji (AC)

• kij & ikj(BC)

图 6-45

每次迭代

加载次数 存储次数 A未命中次数 B未命中次数 C未命中次数 未命中总次数

0.25 1.00 0.00 1.25

1.00 0.00 LOO 2.00

0.00 0.25 0.25 0.50

矩阵乘法内循环的分析。6 个版本分为 3 个等价类，用 内循 环中访问 的数组对来 表示

类 AC 例程的内循环（图6-44c 和图5 _:4 4d ) 有、一些问题。每次迭代执行两个加载和一个存储（相对千类AB例 程， 它们执行 2 个 加载而没有存储）。内循环以步长n 扫描A 和C 的列。名结 果是每次加载都会不命中 ，所 以每次迭代总共有两个不命中。注意 ， 与类AB例程

相比，交换循环降低了空间局部 性。

BC 例程（图6 44e 和图 5:_44f)展示了一个很有趣的折中： 使用了两个加载和一个存储 ，

它们比 AB 例程多需要一个内存操作。另一方 面， 因为内循环以步长为 1 的访问模式按行

扫描B和c ·, 每 次迭代每个数组上的不命中率只有0 : 25 次不命中，所 以每次迭代总 共有

o·:so个不命中。

图 6 4 6 小结了一个Cotei7 系统上矩阵乘法各个版本的性能 。这个图画出了测量出的每次内循环迭代所需 的CPU周期数作为数组大小( n) 的函数。、

100

睾

; ‘. \·: : , :· : \ : .

子

太

，.’

50 100 150 200 250 300 350 400 450 500 550 600 650 7 的

！ 飞 ．，．、·,:.:;-:’

数组大小( n ) ..

图 6- 46 Core· 17 矩阵乘法性能

_·: .-,_

;_ , · :

对千这幅图有很多有意思的地方值得注意：

• 对于大的 n 值， 即使每个版本都执行相同数量的浮点算术操作 ， 最快的版本比最慢

、 的 版本运行得快几乎 40 俨口。

. : . .

• 每次迭代内存引用和不命中数量都相同的一对版本，有大致相同的测最性能。

  ) • 内 存行为最糟糕的两个版本，就每次迭代 的访问 数量和不命中数量 而言，明 显地比

  其他4个 版本运行得慢 ， 其他 4 个版本有较少的不命中 次数或者较少的 访问次数， 或者兼而有之。

• , • 在这个情况中 、， 与 内 存访问总数相比， 不命中率是一个更好的性能预测指标。例

如，即 使 类 BC 例 程( 2 个 加 载和 1 个存储）在内循环中比类 AB 例程( 2 个加载）执行更多的内存引用，类 BC 例程（每次迭代有 0. 5 个不命中）比类AB 例程（每次迭代有

1. 25 个不命中）性能还是要好很多。

• 对于大的 n 值，最 快 的 一对版本( ki j 和心 ）的性能保持不变。虽然这个数组远大于任何 SR A M 高速缓存存储器， 但 预 取 硬件足够聪明，能 够 认 出 步 长为 1 的访问模式 ，而 且速度足够快能够跟上内循环中的内存访问。这是设计这个内存系统的 Intel 的 工 程师所做的一项极好成就，向 程 序 员 提 供了甚至更多的鼓励，鼓 励 他们开发出具有良好空间局部性的程序。

  Li 使用分块来提高时间局部性

  有一项很有趣的技术， 称为 分 块( blocking ) , 它可以提高内循环的时间局部性。分块的大致思想是将一 个程 序 中的数 据结构组织 成的 大的 片 ( ch unk ) , 称 为 块 C blo ck) 。

  （在这个上下文中，“块” 指的是一个应 用级 的数据组块， 而 不是 高速 缓 存块。）这样构造程序，使 得 能够将一个片加 栽到 Ll 高 速 缓 存中， 并在这个片 中进行 所需的所有的读和写， 然后 丢掉这个片 ，加 栽下一 个片 ，依 此类推 。

  与为提 高空 间局部性所做 的简单循环变换 不同 ， 分块使得代码更难阅读和理解。由于这个原因 ， 它最适合 于优 化编译 器或 者频繁执行的库函数。由于 Core i7 有完善 的预取硬 件， 分块不会 提高矩阵 乘在 Core i7 上的性能。不过， 学习和理解这项技 术还是很有趣的， 因为它是 一个通用的 概念， 可以在一些没有 预取的 系统 上获得极大的性能收益。

1. 6. 3 在程序中利用局部性

   正如我们看到的，存储系统被组织成一个存储设备的层次结构，较小、较快的设备靠近顶部，较大、较慢的设备靠近底部。由千采用了这种层次结构，程序访问存储位置的实际速率不是一个数字能描述的。相反，它是一个变化很大的程序局部性的函数（我们称之为存储器山），变化可以有几个数量级。有良好局部性的程序从快速的高速缓存存储器中访问它的大部分数据。局部性差的程序从相对慢速的 DRA M 主存中访问它的大部分数据。

   理解存储器层次结构本质的程序员能够利用这些知识编写出更有效的程序，无论具体 的存储系统结构是怎样的。特别地， 我们推荐下列技术：

   • 将你的注意力集中在内循环上，大部分计算和内存访问都发生在这里。

• 通过按照数据对象存储在内存中的顺序、以步长为 1 的来读数据，从 而使得你程序中的空间局部性最大。

• 一旦从存储器中读入了一个数据对象， 就 尽 可 能 多 地 使 用 它 ，从 而 使 得 程序中的时间局部性最大。

  6. 7 小结

  基本存储技术包括随机存储器 ( RAM) 、非易失性存储器( ROM) 和磁盘。 RAM 有两种基本类型。 静态 RAM(SRAM) 快一些， 但是也贵一些， 它既可以用做 CPU 芯片上的高速缓存 ， 也可以用做芯片下的高速缓存。动态 RAM( DRAM) 慢一点，也便宜一些， 用做主存和图形帧缓 冲区。即使是在关电的时候 ，

  ROM 也能保持它们的信息， 可以用来存储固件 。旋转磁盘是机械的非易失性存储设备 ， 以每个位很低的成本保存大量的数据，但是其访问时间比 DRAM 长得多 。固态硬盘( SSD) 基丁非易失性的闪存 ， 对某些应用来说，越来越成为旋转磁盘的具有吸引力的替代产品。

  一般而言， 较快的存储技术每个位会更贵 ， 而且容量更小。这些技术的价格和性能属性正在以显 著

厅-

笫 6 章 存储器层次结构 451

不同的速度变化着 。特别地， DRAM 和磁盘访问时间 远远大于 CPU 周期时间。系统 通过将存储器组织成存储设备的层次结构来弥补这些差异，在这个层次结构中，较小、较快的设备在顶部，较大、较慢的设备在底部。因为编写良好的程序有好的局部性，大多数数据都可以从较高层得到服务，结果就是存储系统能以较高层的速度运行，但却有较低层的成本和容社。

程序员可以通过编写有良好空间和时间局部性的程序来显著地改进程序的运行时间。利用基于

SRAM的高速缓存 存储器特别重要 。主要从高速缓存取数据的程序能 比主要从内 存取数据的程序 运行得快得多 。

参考文献说明

内存和磁盘技术 变化得很快 。根据我们的 经验， 最好的技术信息 来源是制造商维 护的 Web 页面。像Micron、Toshiba 和 Samsung 这样的公 司， 提供了丰富的当前有关内存设备的技术信息。Seagate 和Western D屯ital 的页 面也提供了类 似的有关 磁盘的有用信息。

关于电路和逻辑设计的教科书提供了关于内存技术的详细信息[ 58 , 89] 。IEEE Spect rum 出版了 一系列有关 DRAM 的综述文章[ 55] 。计算机体系结构国际 会议( ISCA) 和高性能计算机体系结构 ( HPCA) 是关于 DRAM 存储性能特性的公 共论坛[ 28 , 29 , 18 ] 。

Wilkes 写了第一篇关千高速缓 存存储器的论文[ 117] 。Smith 写了一篇经典的综述[ 104] 。 Przyby lski 编写了一本 关于高速缓存设计的权威著作[ 86] 。 Hennessy 和 Patterson 提供了对高 速缓 存设计问题的全面讨论[ 46] 。Levinthal 写了一篇有关 Intel Core i7 的全面性能 指南[ 70] 。

Stricker 在[ 112] 中介绍了存储楛山的思想， 作为对存储 器系统的 全面描 述， 并且在后来的 工作描述中非正式 地提出了 术语“存储器山＂。编译器研究者通过 自动执行我们 在 6. 6 节中讨论过的那些手工代码转换来增加 局部性[ 22, 32, 66. 72, 79, 87 , 119] 。Carter 和他的 同事们提出了一个高速缓存 可知晓 的内存控制器 (cac he-aware memory contro ller) [ 17] 。其他的研究 者开 发出了 高速缓存不知晓的 ( cache obliv­

ious)算法，它被设 计用来在不明确知 道底层高速 缓存存储 器结构的情况下也能运行得很好[ 30, 38, 39,

9] 。

关于构造和使用磁 盘存储设备也有大最的论 著。许多存储技术研究 者找寻 方法，将 单个的磁盘集合成更大、更健壮 和更安 全的存储池[ 20 , 40 , 41, 83, 121] 。其他研究 者找寻利用高速 缓存和局部性来改进磁盘 访问性能的方法[ 12, 21] 。像 Exokernel 这样的系统提供了更多的对磁盘和存储 器资 源的 用户级控制[ 57] 。像安 德鲁文件系统[ 78] 和 Coda[94] 这样的 系统， 将存储器层 次结构扩展到了计算机网络和移动笔记本电脑。 Schindler 和 Ganger 开发了一个有趣的工具 ， 它能自动描述 SCSI 磁盘驱动器的构造和性能[ 95] 。研究者正 在研究构 造和使用基于闪存的 SSD的技术[ 8 , 81] 。

家庭作业

•• 6. 22

假设要求你设计一个每条磁道位数固定的旋转磁盘。你知道每条磁道的位数是由最里层磁道的周 长决定的，可以假设它就是中间那个圆洞的周长。因此，如果你把磁盘中间的洞做得大一点，每 条磁道的 位数就会增大 ， 但是总的 磁道数会减少 。如果用 r 来表示盘面的 半径， X • r 表示圆洞的半径， 那么 x 取什么值能使这个 磁盘的容量最大？

估计访问 下面这个 磁盘上扇区的平均时间（以ms 为单位）：

假设一个 2MB 的文件， 由 512 个字节的逻辑块组 成，存储 在具 有下述特性的磁 盘驱动器上 ：

;’. ·:’·, ,,)

. .

’ · ’ ) .. ,

< -.气’- -’

• 6 .‘‘2 5

  对于下面的 每种情况 ， 假设程序顺序 地读文件的逻辑块， 一个接一个， 并且对第一个块定位读／ 写头的时间 等于 T… ,.. k + T吓 g rotat,on o

1. 最好情况： 估计在所有可能的逻辑块到磁盘扇区的映射上读该文件所需 要的 最优时间（以ms 为单位）。

2. 随 机情况 ：．估计如果块是随机映射到磁盘扇区上时读 该文件所需要 的时间（以ins为单位）。

   下 面的表给出了一些不同的高速缓存的 参数。对千每个 高速缓存，填 写出表中缺失的字段。记住

   m 是物理地址的 位数，C 是高速缓存大小（数据字节数）， B 是以 字节为 单位的块大小， E 是相联

   、度 ，S 是高速缓存组数， t 是标记位数，s是组索引位数，而 b 是块偏移位数。、 ; ‘..•: : ‘、

::

} .., i;

•’ '

.,.,.

• 6 . 26 下面的表给出了一些 不同的高速缓存的 参数。你的任务是填写 出表中缺失的字段。记住 m炟物理

  地址的 位数， C 是高速缓存大小（数据字节数）， B 是以字节为单位的 块大小， E 是相联度， S是高速缓存组数， t 是标记位数， s 是组索引位数，而 b 是块偏移位数。

,’) -: ci ··.. ,:, , :‘c’

• 6 . 27 这个问题是关于练习题 6. 12 中的 高速缓存的。

1. 列出 所有会在组 1 中命中的十六进制内 存地址。

2. 列出所有会 在组 6 中命中的十六进制内存地址 。

   •• 6.-!2 , 这 个问题是关于练习题 6. 12 中的高速缓 存的。

   A. 列 出所有会在组 2 中命中的十六进制内 存地址。

• . …,, . B. 列出所有会在组 4中 命中的十六进制内存地址。

1. 列出所有会在组 5 中命中的十六进制内存地址。

2. 列出所有会 在组 7 中命中的十六进 制内存地 址。

   •• 6 29 假设我们有一个具有如下属性的系统：

   • 内存 是字节寻址的 。
   • 内存访问是对 1字 节字的（而不是 4 字 节字）。
   • 地址宽 12 位。

I’

i ;- , ; :

/ ·..

、，

、 1’. •’ .’.: ’ . . ,· ,

• 高速缓存是两路组相联 的CE = 2) , 块大小为 4 字节 ( B = 4) , 有 4 个组CS = 4) 。高 速缓存的内 容如下，所有的地址 、标记和值都以十六进制表示 ：＇

组索引 标记 有效位 字节0 字节l

字节2

字节3

00

:.83

.0. 0

83

｀

40

- FE ,

＿44

. .

41 ‘. I .42

97 cc

45 46

—

·43

DO 47

‘" ,,,.

1. a,

   ,.,,•.·. ·’. 、，.

   ＇ ,1 :: ·"，＇ 坎

; -,

； , 2

‘I ＿一

40

. .48 49

-;- 古 ～． ；

． ，

. 4A ., . .、.．. 4B J

;; I ; II : I

9A CO,

,’, 03 Ff

1. 下面的图给出了 一个地址的格式（每个小框表示一位）。指出用来确定下列信息的字段（在图中标号出来）：

   co 高速缓 存块偏移＿

CI 高速缓 存组索引～

CT 高速缓存标记

‘.; J ;_.., . ’ 、 、 ；

12 11 ·_·- lO ·· 9 8 ’ -‘7 . • .‘6 ·· -5· •· 4

. I I -I · I I:-· ,I–• I··-·"°I #

1. 对于下面每个内存访问 ，当 它 们是按照列出来的顺 序执行时， 指出是高速缓存命中还是不命中。如果可以从高速缓存中的信息 推断出来 ，请 也给出读出的 值。

. ,), · '

• 6. 30 假设我们有一个具有如下属性的系统：

  • 内存是字节寻址的？ 飞｀ ’ ;:: • 飞

    .• 内存访问是对 1 字节字的（而不是4 字节字）。，..c: .· •: :

    • 地址宽13 位。 ,· _; , .· ." ·:, •· ;- ·· ;

  • 高速缓存是四路组相联 的( £ = . 4) ’ 块大小为 4 字节( B = 4 ) , 有 8 个组 ( 5 = 8 ) 。

    考虑下 面的高速缓存 状态。所有的地址、标记和值都以十 六进制表示。每组有 4 行 ，索引 列

    包含组索引。标记列包含每 一行的标记值。V列包含每一行的有效位。字节 0 ~ 3 列包含每一行 的数据， 标号从左向右，字 节 0在 左边。

. . . ,i’· 一,,;· ‘’··’

·, . . . ’ . , , . ‘.<· ’ , · .. , . . . ., .. . ·•

4 路组相联高速缓存

., . .. ,.

; , ,; ‘.·,, ;

1. 这个高速缓 存的大小 ( C ) 是多少字节？
2. 下面的图 给出了一个地址的格式（每个小框表示一位）。指出用来确定下列信息的字段（在图中

标号出来）：

co 高速缓存块偏移

• ‘…;-

!- . . - ·’ . '

安

CI 高速缓存组索引

CT 高速缓存标记

12 11 10 9 8 7 6 5 4 3 2 I 0

** 6. 31 假设程序使用作业 6. 30 中的高速缓存，引 用位于地 址 Ox071 A 处 的 1 字节字。用 十六 进制表示出它所访间的高速缓存条目，以及返回的高速缓存字节值。指明是否发生了高速缓存不命中。如果 有高速缓存不命中，对千＂返回的高速缓存字节＂输人”一＂。提示：注意那些有效位！

1. 地址格式（每个小框表示一位）：

   12 11 10 9 8 7 6 5 4 3 2 1 0

2. 内存引用：

•• 6 . 32 对千内存地址 Ox1 6 E8 重复作业 6. 31。

1. 地址格式（每个小框表示一位）：

   12 11 IO 9 8 7 6 5 4 3 2 I 0

2. 内存引用：

•• 6 . 33 对于作业 6. 30 中的高速 缓存 ，列 出会在组 2 中命中的 8 个内存地址（以十六进制表示）。

•• 6. 34 考虑下面的矩阵转置函数：

typedef int array[4] [4];

2

3 void transpose2(array dst, array src)

4 {

5 int i, j;

6

7 for (i = o; i < 4; i ++) {

8 for (j = O; j < 4; j++) {

9 dst [j] [i] z src [i] [j];

10 }

11 }

12 }

假设这段代码运行在一台具有如下属性的机器上：

• s i ze o f (i n t ) ==4 。
• 数组 sr c 从地址 0 开始 ， 而数组 d s t 从地址 64 开始（十进制）。

  • 只有一个 L1 数据高速缓存 ，它是直接映射 、直写、写分配的， 块大小为 1 6 字节。

  • 这个高速缓 存总共有 32 个数据字节 ， 初始为空 。

  • 对 s r c 和 d 江 数组的访问分别是读和写不命中的唯一来 源。

    对于每个r ow 和 c o l , 指明对 sr c [row] [c ol ] 和 ds t [row] [col ] 的访间是命中Ch) 还是不命 中Cm) 。例如，读 sr c [0] [ 0] 会不命中， 而写 ds t [0] [0 ]也会不命中。

    d s t 数组 sr c 数组

.. 6. 35

对于一个总大小为 128 数据字节的高 速缓存 ，重复 练习题 6. 34。

d s t 数组

s r c 数组

•• 6. 36

这道题测试你 预测 C 语言代码的高速缓存行 为的能力。对下 面这段代码 进行分析 ：

int X [2] [128] ;

int i;

int sum= O;

for (i,. O; i < 128; i++) { sum +: x [O] [i] * x [1] [i] ;

｝

拿拿 6. 37

假设我们在下列条件下执行这段代码：

• s i ze o f (i n t ) ==4 。
• 数组 x 从内存地址 OxO 开始 ，按 照行优先顺序存储 。
• 在下面每种情 况中， 高速缓存最开始时 都是空的 。
• 唯一的内存访间是对数组 x 的条目进行访问。其他所有的 变量都存储 在寄存器中。给定这些假设，估计下列情况中的不命中率；

1. 情况 1 : 假设高速缓 存是 512 字节，直 接映射， 高速缓存 块大小 为 1 6 字节。不命中率是多少？

2. 情况 2 : 如果我们把高速 缓存的大小 翻倍到 1024 字节，不 命中率是多 少？

3. 情况 3 : 现在假设高 速缓存是 51 2 字节， 两路组相联， 使用 LRU 替换策略 ， 高速缓存块 大小为

   1 6 字节。不命中率是多 少？

4. 对于情况 3’ 更大的高速缓存 大小会帮助降 低不命中率吗？为什么能或者为什么不能？

5. 对于情况 3, 更大的块大小会帮 助降低不命中率吗？ 为什么能或者 为什么不能？

   这道题也是测试你 分析 C 语言代码的高速缓存行 为的能力 。假设我们在下列条件下 执行图 6-47 中的 3 个求 和函数 ：

• s i ze of (i n t ) ==4 。

• 机器有 4K B 直接映射的高速缓存，块 大小为 16 字节。

• 在两个循环中 ， 代码只对数组数据进行内存访问 。循环索引 和值 sum 都存放在寄存器中 。

• 数组 a 从内存地址 Ox 08000000 处开始存储。

  对于 N = 64 和 N = 60 两种情况， 在表中填写它们大概的 高速缓 存不命中率 。

,- ,.:

,i: _’.’;

'

, 、 ; . : . '

｀令，，·.·.

typedef int ar r’ay_t [N] [N]; ’ ·’· ,-.·

·i ,’ .• •.·,’

3 ， int

4 ｛

5

6

7

9

sum.A(array_t a)

int i, j;

.. int sum = O，·

for (i = O; i < N; i++)

for (j = O; j _< N; j++) { sum += a [i] [j] ;

10 ｝ ·一

. , ’ '

．..1．. 1

12

1·3•

14

15

16

17

return sum;

} ..

•,. (’ ‘•

i nt . sumB(arr.ay_t a)

{ .

int i,‘j;

ints 山 q = O;

, .._

18 for (j = 0; j < N; j++)

• 19

  i or (-i

  = -0; i : < N; i ++) {\ : :•

  . ·. ,·. .: ·.

20

21 ｝

sum += a[i] [j];

-.-,-::

22 return sum;

23

24

25 int sU1DC(array_t a) 26 ｛

1. inti, j;
2. intsum= O，·

J’’;

,

, . . . ..

又． .、; ; i >’

29 for (j = O; j < N; j’+=2)’

30 for (i = O; i < N; i+=2) {

31 sum:, +,;, fa [i l[ j l t,

a[i+1] [jl . . 迁

32

33

3斗．，，．

35

,,,·,r.

｝

｝

e t ur n ·s 11m; 1 '

+ a,[i] [j+1] + a[i+1] [j+1]) ; ,

，人 <,· ’ .

气， ＇＇， ＇

’ ,,，

．，＇｀｀，

; 、 ; ; 、 . '

,.,, 心

, 、 ‘::-

｀ ＇

\•. ,• 图，64- 7 · 作业5 :·37 中引 用 的函数 ;·. … • … 、· I ,

• 6. 3.8 , ;iM决定在白纸上印黄方格 ， 做成 Pos t l t 小贴纸。在打印过程中，他们需要设置方格中每个点的

  CMYK( 蓝色， 红色， 黄色， 黑色）值。3M 雇佣你判定下面算法在一个 具有2 048 字节、直接映射、

  块大小为 32 字节的数据高速缓存上的效率。，有 如下定义：

1 struct point_colo;r:.: { .": · . ·

2 int c;

;.

’ : “i ,·

’ ’ ‘;’ ; . '

．． ． ．

_、’;I . .

7

1. -j ’ St 如 ct point_color _s quar e (16) (16);

t ; 、-.: .: :·: i ‘- .嘈; 1 ;;-f· ·’. , ,: ‘‘j 心

心·:; :.::, :•i .·:’:·: . !’ : i-; ·:\,: : ;•’: ,-. g.

2. inti, j;

有 如下 假设

、： ，

:-, …I-; ·’

! 、:’, ·.’, •.’, 心 俨

,.., .

• s i zeof (i n t ) ==4。
• s qu ar e 起始千内存 地址 0。

• 高速缓存初始为空。

  -· :,;-•·.·

..

• 唯一的内存访问是对于 s q ua r e 数组中的元 素。变量 i 和］存放在寄存器中。.

. .” , ·’· 『

确定下列代码的高速缓存性能：

<‘T > . ‘,.

,: •

for (i = O; i < 16; i++){

for ( j = O; j < 16; j++) { square[i] [j] .c = O;

s quar e [ i ] [ j ] . m = O;

square[i] [j] .y = 1;

square[i] [j] .k = O;

., ·• : : : • .i:’. •.

• ’ ‘,’, .

‘’?,’

｝

* .’、

, . 矗 · 、

.,;· C, \ I’

,,.‘‘良

： ．＇；＇ ．，

1. 写总数是多少？
2. 在高速缓存中不命中的写总数是多少？
3. 不命中率是多少？

·.:

• . ,.., . ．

  ．：，…• ;! . (

  ： 一 ，, ．： , ,..、

．人、飞

• 6. 39

给定作业 6. 38 中的假设，确定 下列代码的 高速缓存性 能：寸

’ . ．.,.,.，….. ., …

,. .’ ,_; ,-;’, t·.’

for (i = O; i < 16; i++){

for (j = O; j < 16; j++) { square [j] [i] . c = 0;

square[j] [i] .m = O;

．％ , . 、; , ..

square CiJ [iJ _.y= 1寸

square [j] [i] . k = 0;

• ’ .:,

  ＼， • . \ I

  " - : ,,’,. . '

  .，.，

  :, ,， ,.’．

  ＇，户

:–, : ·

’ (· 中 ，l ‘· ’ "

，飞： ， ." .,..’

1. 写总数是多少？
   1. 在高速缓存中不命 中的写总数 是多少？

‘> ! '

. :, · ·: ! .’

" ! ’ ‘. 、. .

,:、、

1. 不命中率是多少?

   .. ! ’ ! :·.. … 、 、勹

   ,,, ; • : 气· 、 , .’

   .. ., . …

   一、宁 ，：

• 6. 40 给定作业 6. 38 中的假设，确定下列代码的 高速缓存性能 ：

;,,-.,;.、: ::,

for ’ O : ,..; d;

．＼＇，

i _<. ’ i 6 ; i +’+-) 1’ {’ :·: ·1

- ,: : '

,,.. ·::’ ; I,

2

:i: . . .’ 3 ,: :’::·,: ;·- ’ ,:

for (j = O; j < 16 ; j++) {

, ,, squ e[iJ [j] .y, = 1,;

} " .,,’:’’

! ! !,•! ….

个_;、: ,,·.一•;

l:’; .·

4·’. . .,. ..

f :, ’ ’ :, ·•·:.2 , ,, ; .·,. :·:, .,-:

, , ’ '

‘,,

·.,

’ , ·" , ,’

6 ; ,. f 吐 心 : ,: =, , O/ : i , <; ,16 ; i,

++) . { · ·

\, : :- :<.’·I

:·’

，＇，: ,.

. ’ `、!·’ ,;.._-,·’

7 for (j = O; j < 16; j ++) {

1. square [i] [j].c = 0 ; 、·!!t

2. square[i] [j] .m = O ;

3. square [i] [j] .k = 0 ;

   11

;;、上

. ,,..

,,,

＇ 、 ,. J , , :. 心 ；，"- j •• r , ·., '

,; _ ’ .

12

1. 写总数是多少？
2. 在高速缓存中不命中的写总数是多少？

(

" :· . > , ’ .• 飞 ．

.-·" :夕 ， ．；

..- _-. :. : :

’ . 一 飞，. i .•. ..’. ’ 飞”

，

.·,

l-;:,

3. 不命中率是多少’!.) '

•• 6. 41

！，飞

你正在编写一个新的 30 游戏 ， 希望能名利双收.,。现 在正在写 一个 函数｝ 使得在画下一帧之前先清空屏幕 缓冲区 。工 作的屏幕是 640-X 480 像 素数组 ＇。工 作的机器有一个 64K B 直接映 射高速缓 存，

1:-,

每行 4个字节； 使用下面的C语言数据结构： I · ’ ; ’ ’ ·. . ’ " .,. : . .. . l ·.. i _-’ . ; \;: ·’·.,:, /’.’

’ . ’ . ,:, " \ : ; ’ " ; ’ ·’ ’ ., " ’ : ’ ·. . /; ‘·. 、..,., • ,,_·. ·; ;

, 1 ,,sfr uc, t

P} Xe l {

• 、: ｀仁
• ’ :’,·

2 . .

• 七h at:’ • r; ‘’’、:(,–’.;: :: : ’ ’ ·.’. •.. ‘.’ 户 、 ， ’ : . '

I ’ 、

. .. . ,

;;:; · : .··- 3 : ,:: ;;, ch 吐 g; .-:-: '

,,_,. :、i . 、,’、:·> ·:-:: :·;,: '

．才I i；，r

char b; char a;

};

struct pixel buffer[480] [640]; int i, j;

char•cptr; int•iptr;

有如下假设：

• s i ze o f (c har ) ==l 和 s i ze c f (i n t ) ==4 。

  • b u f f er 起 始 于内存地址 0。

• 高速缓存初始为空 。

• 唯一的内存访问是对千 b u f f er 数组中元素的访问 。变昼 1 、j 、c p tr 和 i p tr 存放在寄存器中。下面代码中百分之多少的写会在高速缓存中不命中？

  for (j = 0; j < 640; j ++) {

  for (i = O; i < 480; i++){

  buff er [i ] [ j] r. • O;

  buffer[i] [j] .g• O;

  buffer[i] [j] . b • O;

  buffer[i) [j] .a = O;

  ｝

  ｝

** 6. 42

•• 6. 43

*＊* 6. 44

:: 6 45

给定作业 6. 41 中 的 假 设 ，下 面代码中百分之多少的写会在高速缓存中不命中？

char•cptr = (char•) buffer;

for (; cptr < (((char *) buff er) + 640 * 480 * 4) ; cptr++)

• cptr 一 O;

给定作业 6. 41 中 的 假设 ，下 面代 码中百分之多少的写会在高速缓存中不命中？

int *iptr z (int•)buffer;

for(; iptr < ((int•)buffer+ 640•480); iptr++)

*iptr = 0;

从 CS : A P P 的网站上下载 mo u n t a i n 程 序， 在你最喜欢的 PC/ L in u x 系统上运行它。根据结果估计你 系统上的高速缓存的大小。

在这项任务中，你 会把在第 5 章和第 6 章中学习到的概念应用到一个内存使用频繁的代码的优化 问 船 上。考虑一个复制并 转置一个类型为 i n t 的 N X N 矩阵的过程。也 就是， 对 于源矩阵 S 和目的矩阵 D , 我们要将每个元素 S; ,J 复制到 d,., 。只用一个简单的循环就能实现这段代码：

void transpose(int•dst, int•src, int dim)

｛

int i, j;

for (is O; i < dim; i++)

for (j = O; j < dim; j++)

dst [j•dim + i ] 一 s r c [i*dim + j];

:: 6 . 46

这里 ，过 程的参数是指向目的矩阵 ( d s t ) 和源矩阵 ( s r c ) 的指针，以 及矩阵的大小 N ( d i m) 。 你的工作是设计一个运行得尽可能快的转置函数。

这是练习题 6. 45 的一个有趣的变体。考虑将一个有向图 g 转换成它对应的无向图 g ’ 。图 g ’ 有一条

从 顶点 u 到顶点 v 的边，当 且仅当原图 g 中有一条 u 到 u 或者 v 到 u 的边。图 g 是由如下的它的邻接 矩阵( adjacenc y ma t rix ) G 表示的。如果 N 是 g 中顶点的数量， 那 么 G 是 一 个 N X N 的 矩阵，

它 的 元 素是全 0 或者全 1。假设 g 的顶点是这样命名的： V o , V 1 , …, “平 1 。 那 么 如 果 有一条从 v,

到 v,的 边，那 么 G [ i] [ 月 为 1, 否则为 0。注意， 邻 接矩阵对角线上的元素总是 1, 而无向图的邻

接矩阵是对称的。只用一个简单的循环就能实现这段代码：

void col_convert(int *G, int dim) { int i, j;

for (i = O; i < dim; i++)

for (j = O; j < dim; j++)

G [j *dim + i] = G [j *dim + i] 11 G[ 江 di m + j];

你的工作是设计一个运行得尽可能快的函数。同前面一样，要提出一个好的解答，你需要应用在第5 章和第 6 章中所学 到的概念。

练习题答案

6 1 这里的思 想是通过使 纵横比 ma x(r , c)/min(r, c)最小， 使得地址位数最小。换句话说， 数组越接近于正方形，地址位数越少。

6 2 这个小练习的主旨是确保你理解柱面和磁道之间的关系。一旦你弄明白了这个关系，那问题就很简单了：

磁盘容量= 51 2 字节 X 400 扇 区数

X 10 000 磁道数 X 2 表面数 X 2 盘 片数

扇区 track

=8 192 000 000 字 节

=8. 192GB

表面 盘片 磁盘

6 3

6 4

6. 5

对这个问题的解答是对磁盘访问 时间公式的直接应用 。平均旋转时间（以ms 为单位）为

T., g ,ot,11on = 1 / 2 X T max rntallon = 1 / 2 X (60s/15 000RPM) X lOOOms/s""" 2ms

平均传送时间为

T,vg,,,n,r«= (60s/15 000RPM) X 1 / 500 扇 区／磁 道 X l OOOms / s ,::::: 0. 008ms

总的来说，总的预计访问时间为

T,cms = T, vg seek + T,vg ,oi,11on + T, vg mnsfe, = 8ms + 2ms + 0. 008ms """ 1 Oms

这道题很好的检查了你对影响磁盘性能的因素的理解。首先我们需要确定这个文件和磁盘的一些基本属性。这个文件由 2000 个 512 字节的逻辑块组成。对于磁盘， T avg seek = 5 ms’Tmax rnt,t1on = 6 ms’ 而 T., . ‘°’ “’ o• = 3ms 。

1. 最好情 况： 在好的情况中 ， 块被映射到连续的扇区， 在同一柱面上 ， 那样就可以一块接一块地

   读， 不用移动读／写头。一旦读／写头定位到了第一个扇区，需 要磁盘转两整圈（每圈 1000 个扇区）来读所有 2000 个块。所 以， 读这个文件的总时间为 Ta,g seek + T.,g ,oi,1;on + 2 X T max ,om;on = 5 +

   3 + 12 = 20ms 。

2. 随机的情况： 在这种情 况中，块 被随机地映射到扇区上 ， 读 2000 块中的每一块都需 要 Tavg seek +

T .v. , o., uon ms, 所以读这个文件的总时间为( T… mk + T .,., 0 1 a,;on) X 2000 = 16 OOOmsCl 6 秒！）。 你现在可以看到为什么清理磁盘碎片是个好主意！

这是一个简单的练习，让 你对 SSD 的可行性有一些有趣的了解。回想一下对于磁盘， l P B = 109

MB 。 那么下面对单位的直接翻译得到了下 面的每种情 况的预测时间：

A. 最糟糕悄况顺序写( 470 MB/ s ) : (1 09 X 128) X Cl / 470 ) X Cl/(86 400X 365) ) ,:::::8 年。

B. 最糟糕情况随 机写( 303 MB/ s): 0 0 X.128) X (l / 303 ) .X (111/ ( 8 6· 400 X 365 )、)

1 3年 。 心

6. 6

c. 平均情况( 20G B/ 天）： (109 X 128) X0 / 20 000) X0 / 65) :““1,7- 535 年。 "” ‘.’-’,:. 、，、

所以即使 SSD 连续工作 ， 也能持续至少 8 年时间， 这大于大多数计算机的 预期寿命 。

在 2005 年到 2015 年的 10 年间，旋 转磁盘的单位价格下降 了大约, 16 6 倍，这 意味着价格大约每 18 个月下降 2 倍。假设这个趋势 一直持续 ， l P B 的 存储设备 ，在2 0.15 年 花费-3.0 000 美元， 在 7 次这种 2 倍的下降之后会降到 500 美元以下。因为这种下降每 i’s 个月发生一次 ， 我们 可以 预期在大约

20 25 年， 可以用 500 美元买到 l P B 的存储设备。

6. 7 为 了创建一个步长为1 的引用模式 ，必须改变循 环的次序 ， 使得最右边的索引变化得最快 ：

int s uma 工r ay3d ( i nt a[N] [NJ [NJ)

｛

inti, j, k, sum= O;

＇’,,．，．.,，

.’ ＇， '’

..\ , ‘.., • ,

心 for

廿(k = O;” k ’ < N,：;’’ k++) { ’ '

for (i = 0; i < N; i ++) {

for (j = O; j < N; j++) {

’ ·,,’

,_ · · ‘· .. .:

• ·, . 处

; _: ,’ ·’ 寸i

-- . }

｝

S’\llD += a [k] [i) [j] ;

;. .、；，一：

return sum;

这是一个很重要的思想。模式。． ．

.＇、,:、:-

要保证 你理解了 为什么这种循环次序改变就能得到一个步长为 1 的访问

fs 解 决这个问题的关键在干想象出 数组是S如何在内存中排列的，然 飞后分析引用模式。！ 函 数 l e ar l 以

步长为 1 的引用模式访问 数组， 因此明显地具有最好的空间局部性。函数 c l e a r 2 依次扫描 N 个结构中的每一个 ， 这是好的，但是在每个结构中，它以 步长不为 1 的模式跳 到下列相 对于结构起始位置的偏移处： 0 、12 、4 、16 、8、20。所以 c l e a r 2 的空间局部性比 c l .e ar l 的要差。函数 c l ea r 3 不仅在每个结 构中跳来跳去， 而且还从结构跳到结构， 所以 c,l e. r.3 的空间局部性比 c l e a r 2 和 c l e ar l 都 要差。

6. 9

; 1

，．，．

6. 10

这个解答是对图 6-26 中各种高速缓存参数定义的直接应用。不那么令人兴奋，但 是在能真正理解

高速缓存如何工作之前， 你需要理解高速缓存的结构是如何 导致这样划分地址位的 。‘r•: ·t 、

填充消除了 冲突不 命中。因此，四分之 三的引用 是命中的。

6 门 有时候，｀理 解为什 么某种思想是不好的，能够帮助你理解为什么另一种 是好的。,( 这 里 ，我 们看到

•.•＇，-’、i

6. 12

的 坏的想 法是用高位来索引高速缓存， 而不是用 中间的位。

A 用高位做索引 ， 每个连续的 数组片( chun灼由 2’ 个块组成 ，；这 里 t 是 标记位数。因此，数组头

2’ 个连续的块都 会映射到组 o, 接下来的 2’ 个块会映 射到组 1 . 依此类推o.: :’. 习

B, 对于直接映射高速缓存( S ,.: E ,, B, •1?1! :”"’:( 51 2 ,、1, 3-2, <32h · 高速缓 存容量是 ‘.512 个 3 2 字节的块 ，每个高速缓存行中 有 t = l 8 个标记位。因此，数组中头 沪个块会映射到组 o, 接下来沪个块会映射到组 l 。因为我们的 数组只由 ( 409 (] X 4 ) / 32 =;c51? 个块组成，所以数组中所有的块都

＼！ 被 映射到组 0。因此＇，在任 何时刻、，、高 速缓存 至多只能保存七个数组块，，‘即使 数 组足够小，能 够完全放到高速缓 存中。i 很明显，，用高位 做 索引 不能充分利用高速缓存。｀ ＇＇：， 炉

两个低位是块偏移( CO) • 然后是 3 位的组索引( CI) , 剩下的位作为标记 <CT ) ‘.- 厂 _;;,· ‘.

～ 笫 6 章 存储器层次结构 461

, ,• • I

;’. .·, .: ’ : 1,2 · · 11; 10

9. · 8 .:,7: · · 6 .. 5 : 4 : .• 3 .•.2 : ·i l 久。

>.,., .,’

lcTlcTlcT

CT . I CT . I CT lcr I CT I c 1 」CI ·1 .C’

I I.co I co I

6. 13

,;,,

地址： Ox0E34 .’、

1. 地址格式（每个小格子表示一个位）：

   ．，户，．．

   ．’．,· ·’ ，

   ; , :;

   ＇．， ．．．，；． ；；｀

, ＇ , -12 · 11. 10 9 8· :. 7 6 . 5 4 . . 3 2 I . 0

I O I 1’ I 1 I 1 I O 1· .0 I O·1 i - l · 1. I. o I 1 口

:,. . ,.,.

2. 内存引用：

   CT. · C L CT CT CT CT CT ct C.l

   CI cr c o · c o· ·

   , : ,, :; ’ 、. . ·;· .•

(; ··.:.·.’::’·;!’:/ ·.’; ‘:: -:.,. :.: 、: ;;.-, • •

’ ,._,

6. 14

:一. .. … .-

地址： Ox0DD5 一

1. 地址格式（每个小格子表示一个位）：

   • / ,.

     12 · , 11·. 10 ·· · 9 8 7 : 6 ·· 5

:、·

-4 3 2 I 0

I O I I. , I· 1 1 · I , I 1· .l r o , · 1

I I O I I I

:，,;< :··: - ; / : “,:: .-,;;: er < CT :. er : CT : CJ; · CT . CT CT.•·

… . fB; 内存引用： •·.. .-..: :;-·( .’、:.’,1 : ‘,、:：·,·’

CI 甲

．， 俨:，,. :. ..

CI· CO , CO

‘; ; · : ,·

;, / ,:·;::,:r :i\f·

心，：，八: !,< 1 ; 女, · i : ’ ;,, ; ;:: ; ·\

::，:; ,’•. ::. .;. ‘, , .;; :

,;’, ,; ‘.:’:/ ;·· , ·;

. .- ’ ..– . !，’,., ．． ． ，

· ·’:’ : , 丿

.

, ,., ｀＇

·,, . ,·

， ’ ’ :’; ’ ’ " . -

l ,_ _. . ，

<· ·’

-、i . _.’,-;

;., -

6. 15 地址： OxlFF4 ’ •. , · 人. ’ ; ….·,,, ; ，

. •· ’ ! ‘:

1. 地址格式（每个小格子表示一个位）：

‘•. .; . ..’

仑 ,.-. _,.

，

12 11 10 9 8 7 •, : •.,6 . 5

3· /!· 2 · . ·r: ’ d

. 令 .

、:.

I 1 I I I 1 I 1 I I I I I I I I

::: >-,: : CT>,. c t, , C T :/ :CT, CT < CT ·’ . er :·CT

已

CI·

0 I I ‘I 。 1。 |

Cl ·,; •Cl • CO :’.CO ;. ;,;

．、．,.

B.

.• .

I•.,i-’.>, ; : : : ‘. : ’ ·,

,- .•· >,’ ; :

\ ··•,

,’:’.,

• .. : ;’

• ,, ,. ．

  , “,C -’;

: 、乒 ’ .,.._..,·.<.;-’· ,··J .

一 声 ，

! .-,; •:- <: 、 』;

’ •:·( ,;,

‘.’.·; _; ;

; , ,! ; ( , , •:

" 勹’.,.:. ( - ..-

-)r·

> 一 j? 气 ，’. t ,’

< :,, ;•;< ‘.

I ; !,

6.16 这个问题是练习题6’. 12-::练习题6. 15 的 一种逆 过程，要 求你反向 工作，从高速缓存 的内 容推出

觅:.,!.

.•.

会在某个组中命中的地址 。在这种情况中，组 3 包含一个有效行．，标 记为 Ox32。因 为组中只有一

个有效行， 4 个地址会命中。这些地址的二进制形式为 ·o’on: o io611 。因此，在组 3中 命中的

4 个十六进制地址是 ： Ox06 4C、 Ox0 64D、 Ox0 64E 和 Ox0 64F。

6 17 A. 解决这个问 题的关键是想象 出图 6-48 中的图像。注意，每个高 速缓存行只包含数组的一 个行， 高速缓存正好只够保存一个数组， 而且对于所有的 i , sr c 和 ds t 的行 t 映射到同一个高速缓存行。因为高速缓存不够大，不足以

主存

容纳这两个数组，所以对一个数组的 o

引用总是驱逐出另一个数组的有用的 src { 16

行。例如， 对 ds t (OJ (O J 写会驱逐当我 dst {

们读 sr c [OJ [ O J 时 加载进 来的那一行。

高速缓存

雷

所以，当我们 接下来读 sr c [ O J ( l J 时， 会有一个不命中。

图 6–18 练 习题 6. 17 的图

2. 当高速缓存为 32 字节时 ， 它足够大， 能容纳这两个数组。因此，所 有的不命中都是开始时的冷不命中。

   ds t 数组 sr c数组

   列0 列l 列0 列1

行行0l

m m

m m I

行0 m m

行1 m h

ds t 数组 sr c 数组

列0 列l 列0 列1

行行 m h 行0 m h

m h 行1 m h

1. 18 每个 16 字节的高速缓存行包含着两个 连续的 a l ga e_yos i t i on 结构。每个 循环按照内存顺序访问这些结构，每次读一个整数元索。所以，每个循环的模式就是不命中、命中、不命中、命中，依此类推。注意， 对于这个问题， 我们不 必实际列举出读和不命中的 总数， 就能预测出不命中率。

   1. 读总数是多少? 512 个读。

   2. 缓存不命中的读总数是多少? 256 个不命中。

      C. 不命中率是多少? 256/ 512 = 50 %。

      6 19 对这个问题的关键是注意到这个 高速缓存只能保存数组的 1 / 2。所以 ，按 照列顺序来 扫描数组的第二部分会 驱逐扫描第一部分时 加载进来的那些行。例 如， 读 gr i d [8 ) [OJ 的第一个元索会驱逐当我们读 gr i d [OJ [ OJ 的 元素时加载进来的 那一行。这一行也包含 gr i d [ OJ [1 )。所 以， 当我们开始扫描下一列时， 对 g r i d [O) [ 1 ) 第一个元素的引用会不命中 。

2. 读总数是多少? 512 个读。

3. 缓存不命中的读总数是多少? 256 个不命中。

   c. 不命中率是多少? 256/ 512 = 50 % 。

   D. 如果高速缓存有两倍大，那么不命中率会是多少呢？如果高速缓存有现在的两倍大，那么它能够保存整个 g r 沁 数组。所有的不命中都 会是开始时的 冷不命中 ， 而不命中率会是 1/ 4 = 25% 。

4. 20 这个循环有很好的步长 为 1 的引用模式 ， 因此所有的不命中都是最开始时的 冷不命中。

   1. 读总数是多少? 512 个读。

   2. 缓存不命中的读总数是多少? 128 个不命中。

      c. 不命中率是多少? 128 / 512 = 25 % 。

      D. 如果高速缓存 有两倍大， 那么不命中率会是多少呢？无论高速缓 存的大小 增加多少， 都不会改变不命中率，因为冷不命中是不可避免的。

      6 21 从 Ll 的吞吐晕峰值是大约 12 OOOMB/ s , 时钟频率是 2100 MH z, 而每次读访问都是以 8 字节 l ong 类型为单位的 。所以，从 这张图中我们 可以估计出在这台机器 上从 Ll 访间一个字需要大约 2100/ 12 OOOX8=1. 4::::::1. 5 周期＇ 比正常访问 口 的延迟 4 周期快大约 2. 5 倍o 这是由于 4 X 4 的循环展开得到的并行允 许同时进行多个加载操作 。