深入理解操作系统（16）第六章：存储器层次结构（2）高速缓存存储器+对程序性能的影响（包括：L1/L2高速缓存历史/缓存写：直写和写回/暂无L4级缓存/缓存命中率/存储器山/高速缓存友好的代码/）

1. 高速缓存存储器1.1 通用的高速缓存存储器组织结构1.1.1 L1/L2高速缓存由来1.1.2 通用的高速缓存存储器结构1.2 直接映射高速缓存1.3 组相联高速缓存1.4 全相联高速缓存1.5 有关写的问题1.5.1 高速缓读1.5.2 高速缓存写（直写和写回）1.6 指令高速缓存和统一的高速缓存1.6.1 指令/数据高速缓存，统一高速缓存1.6.3 暂无L4级高速缓存1.6.3 Intel Pentium系统的高速缓存结构1.7 高速缓存参数的性能影响1.7.1 多指标衡量高速缓存的性能1.7.2 影响因素1.7.3 高速缓存行、组和块的区别2. 编写高速缓存友好的代码3. 高速缓存对程序性能的影响3.1 存储器山3.2 重新排列循环以提高空间局部性3.3 使用分块来提高时间局部性4. 利用程序中的局部性5. 第六章总结

1. 高速缓存存储器

1.1 通用的高速缓存存储器组织结构

1.1.1 L1/L2高速缓存由来

早期计算机系统的存储器层次结构只有三层:CPU寄存器、主DRAM存储器和磁盘存储设备。

1. 背景：都是由于CPU和主存之间的差距2. 一级/L1缓存：由于CPU和主存之间逐渐增大的差距,系统设计者被迫在CPU寄存器文件和主存之间插入了一个小的SRAM存储器,称为L1高速缓存(一级缓存)。1. L1髙速缓存位于CPU芯片上(也就是,它是芯片上的高速缓存)2. LI高速缓存的访问速度几乎和寄存器一样快，1个或2个时钟周期3. 二级/L2缓存：随着CPU和主存之间的性能差距不断增大,系统设计者在LI高速缓存和主存之间又插入了一个高速缓存称为L2高速缓存1. L2高速缓存连接到存储器总线,或者连接到它自己的高速缓存总线2. 可以在几个时钟周期内访问到它。

有些高性能系统,例如那些基于Alpha的系统,甚至于在存储器总线上还有一层高速缓存,称为L3高速缓存,在层次结构中位于L2高速缓存和主存之间。虽然在安排上有相当多的种类,但是一般的原则都是一样的。

图6.24

1.1.2 通用的高速缓存存储器结构

考虑一个计算机系统,其中每个存储器地址有m位,形成M=2的m次方个不同的地址。这样一个机器的高速缓存被组织成一个S=2的s次方个高速缓存组(cache set)的数组。每个组包含E个高速缓存行(cache line)。每个行是由一个B=2的b次方字节的数据块(block)组成的,一个有效位(valid bit)指明这个行包含的数据是否有意义,还有t=m-(b+)个标记位(tag bit)(是当前块的存储器地址的位子集),它们惟一地标识存储在这个高速缓存行中的块。

略

1.2 直接映射高速缓存

略

1.3 组相联高速缓存

略

1.4 全相联高速缓存

略

1.5 有关写的问题

1.5.1 高速缓读

正如我们看到的,高速缓存关于读的操作非常简单。

首先,在高速缓存中查找所需字w的拷贝。如果命中,立即返回字w给CPU。如果不命中,从存储器中取出包含字w的块,将这个块存储到某个高速缓存打中(可能会驱逐一个有效的行),然后将字w返回给CPU

1.5.2 高速缓存写（直写和写回）

写的情况就要复杂一些了。假设CPU写一个已经缓存了的字w[写命中(write hit)]。

在高速缓存更新了它的w的拷贝之后,怎么更新w在存储器中的拷贝呢?

1. 最简单的方法,称为直写( write-through),就是立即将w的高速缓存块写回到存储器中。虽然简单,但是直写的缺点是每条存储指令都会引起总线上的一个写事务。2. 另一种方法,称为写回(wite-back),尽可能地推迟存储器更新,只有当替换算法要驱逐已更新的块时,才把它写到存储器。由于局部性,写回能显著地减少总线事务的数量,但是它的缺点是增加了复杂性。高速缓存必须为每个高速缓存行维护一个额外的修改位(dirty bit),表明这个高速缓存块是否被修改过

1.6 指令高速缓存和统一的高速缓存

1.6.1 指令/数据高速缓存，统一高速缓存

到目前为止,我们一直假设高速缓存只保存程序数据。不过,实际上,高速缓存既保存数据也保存指令。

1. 只保存指令的高速缓存称为 i-cache2. 只保存程序数据的高速缓存称为 d-cache3. 既保存指令又包括数据的高速缓存称为:统一的高速缓存(unified cache)

一个典型的桌面系统CPU芯片本身就包括一个 LI i-cache和一个 LI d-cache。

下图总结了基本的结构

图6.38

1.6.3 暂无L4级高速缓存

有些高端系统,例如那些基于 Alpha21164的系统,将L和L2高速缓存放在CPU芯片上,还有一个附加的、不在芯片上的L3高速缓存。

为了提高性能,现代处理器包括分离的在芯片上的 i-cache和 d-cache有两个独立的高速缓存,处理器能够在同一个时钟周期中读一个指令字和一个数据字。

就我们所知,没有系统使用了L4高速缓存,虽然处理器和存储器的速度差异在持续变大,也好像不太可能出现这样的情况

原因：主要还是成本问题。由于缓存非常消耗晶体管，因此成本往往却可以节省近1/3

例子：

这也是为什么AthlonIIX4 640这种强劲四核处理器价格却非常实惠的原因，

翼龙2处理器高达6M的三级缓存占用过多晶体管导致成本较高，而前者则在保持性能相差不大的同时，却大幅降低成本，提升了产品的竞争力。

扩展：L1和L2一般是给单个CPU核心用的，现在L1命中率大约80%，L2又大约80%，等于说L1+L2的命中率达到了(80+16)%=96%。但是L3就更多是为多核准备的了。

1.6.3 Intel Pentium系统的高速缓存结构

真实系统有哪种高速缓存结构：

Intel Pentium系统使用的高速缓存结构如图6.38所示,有一个在芯片上的 LI i-cache,一个在芯片上的 L1 d-cache,还有一个不在芯片上的L2统一高速缓存。

图6.39总结了这些高速缓存的基本参数

图6.39

1.7 高速缓存参数的性能影响

1.7.1 多指标衡量高速缓存的性能

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

1. 不命中率( miss rate)。在一个程序执行或程序的一部分执行期间,存储器引用不命中的比率。它是这样计算的:不命中数量/引用数量2. 命中率( hit rate)。命中的存储器引用比率。它等于1-不命中率3. 命中时间( hit time)。从高速缓存传送一个字到CPU所需的时间,包括组选择、行确认和字选择的时间。对于L1高速缓存来说,命中时间典型的是1~2个时钟周期4. 不命中处罚( miss penalty)。由于不命中所需要的额外的时间。L1不命中需要从L2得到服务的处罚,典型是5~10个周期。L1不命中需要从主存得到服务的处罚,典型是25~100个周期

1.7.2 影响因素

1. 高速缓存大小的影响较大的高速缓存可能会增加命中时间。对于芯片上的L1高速缓存来说这一点尤为重要,因为它的命中时间必须为一个时钟周期2. 块大小的影响现代系统通常会折中,使高速缓存块包含4~8个字3. 相联度的影响4. 写策略的影响一般而言,高速缓存越往下层,越可能使用写回而不是直写

1.7.3 高速缓存行、组和块的区别

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

1. 块：是一个固定大小的信息包,在高速缓存和主存(或下一层高速缓存)之间来回传送现代系统通常会折中,使高速缓存块包含4~8个字2. 行：是高速缓存中存储块以及其他信息(例如有效位和标记位)的容器3. 组：是一个或多个行的集合,直接映射高速缓存中的组只由一行组成。组相联和全相联高速缓存的组是由多个行组成

组相联和全相联高速缓存的组是由多个行组成在直接映射高速缓存中,组和行确实是等价的。

不过,在相联高速缓存中,组和行是很不一样的这两个词不能互换使用因为一行总是存储一个块,

术语“行”和“块”常互换使用。

例如,系統专家总是说高速缓存的“行大小”,实际上他们指得是块大小。

这样的用法十分普遍,只要你理解块和行之间的区别,它不会造成任何误会。

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

确保我们的代码高速缓存友好的基本方法

1.让最常见的情况运行得快。程序通常把大部分时间都花在少量的核心函数上,而这些函数通存储器层次结构常把大部分时间都花在了少量循环上。所以要把注意力集中在核心函数里的循环上,而忽略其他部分2.在每个循环内部使缓存不命中数量最小在其他条件,例如加载和存储的总次数,相同的情况下,不命中率较低的程序运行得更快

例子：

int sumvec(int V[n]){int i,sum=0;for(i=0,i<N;i++)sum += v[i]return sum;}

对于局部变量i和sum,循环体有良好的时间局部性。

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

3. 高速缓存对程序性能的影响

3.1 存储器山

一个程序从存储系统中读数据的速率被称为读吞吐率(read throughput),或者有时称为读带宽(read bandwidth)。

如果一个程序在s秒的时间段内读n个字节,那么这段时间内的读吞吐率就等于n/s,典型地是以兆字节每秒(MB/s)为单位的

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

一个存储器山图形；

图6.42

总结一下我们对存储器山的讨论：

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

3.2 重新排列循环以提高空间局部性

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

图1

矩阵乘法函数通常是用三个嵌套的循环来实现的,分别用索引分别是i、j和k来标识。

如果我们改变循环的次序,对代码进行一些其他的小改动,我们就能得到矩阵乘法的六个在功能上等价的版本,如图6.45所示。每个版本都以它循环的顺序来惟一地标识。

图6.45

矩阵乘法的性能

图6.47

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

1.对于大的n值,即使每个版本都执行相同数量的浮点算术操作,最快的版本比最慢的版本运行得快三倍

2.存储器访问数量和局部性都相同的版本,有大致相同的测量性能

3.存储性能最糟糕的两个版本,就每次迭代的访问数量和不命中数量而言,明显地比其他四个版本运行得慢,其他四个版本有较少的不命中次数或者较少的访问次数,或者兼而有之·

4.类AB例程——每次迭代有2个存储器访问和125次不命中—一在这种机器上运行得比类BC例程—每次迭代3个存储器访问和05次不命中—要好一点,后者用一个额外的存储器访问来换取较低的不命中率。要点就是对于性能来说,高速缓存不命中率并不是问题的全部。存储器访问的数量也很重要,而且在许多情况中,找到最好的性能就是要在这两者之间做出权衡。练习题632和633更深入地论述了这个问题

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

在上一节中,我们看到一些很简单的循环重新排列是如何能够提高空间局部性的。但是我们也看到,即使使用很好的循环嵌套,每次循环迭代的时间都随着数组大小的增长而增长。发生的事情是这样的,当数组大小增加时,时间局部性降低了,而高速缓存中容量不命中的数目增加了。为了改正这个问题,我们使用了一种普通的称为分块( blocking)的技术。

注意：

不过我们必须指出,与那些为了提高空间局部性的简单循环变换不同,分块使得代码更难阅读和理解。因此,它最适合于优化编译器或者频繁执行的库例程。不过学习和理解这项技术仍然是很有趣的,因为它是一个能够产生巨大性能收益的很普通的概念

分块的大致思想是：

将一个程序中的数据结构组织成称为块( block)的组块( chunks)。(这里，“块”指得是一个应用级的数据组块,而不是高速缓存块。)这样构造程序,使得能够将个块加载到L高速缓存中,并在这个块中进行所需的所有的读和写,然后丢掉这个块,加载下个块,依此类推

4. 利用程序中的局部性

正如我们看到的,存储系统被组织成一个存储设备的层次结构,较小、较快的设备靠近顶部，较大、较慢的设备靠近底部。

由于这种层次结构,程序访问存储位置的有效速率不是一个数字能描述的。相反,它是一个变化很大的程序局部性的函数(我们称之为存储器山),变化可以有几个数量级。有良好局部性的程序从快速Ll和L2高速缓存存储器中访问它的大部分数据。局部性差的程序从相对慢速的DRAM主存中访问它的大部分数据。

理解存储器层次结构本质的程序员能够利用这些知识,编写出更有效的程序,无论具体的存储系统结构是怎样的。

特别地,我们推荐下列技术：

1. 将你的注意力集中在内部循环上,大部分计算和存储器访问都发生在这里2. 通过按照数据对象存储在存储器中的顺序来读数据,从而使得你程序中的空间局部性最大3. 一旦从存倩器中读入了一个数据对象,就尽可能多地使用它,从而使得你程序中的时间局部性最大4. 记住,不命中率只是确定你代码性能的一个因素(虽然是重要的)。存储器访问数量也扮演着重要角色,有时需要在两者之间做一下折中

5. 第六章总结

总结：

1. 基本存储技术包括RAM(随机存储器)、ROM(非易失性存储器)和磁盘。2. RAM有两种基本类型。SRAM(静态RAM)快一些,但是也贵一些,它既可以用做CPU芯片上的高速缓存,也可以用做芯片外的高速缓存。DRAM 动态RAM(DRAM)慢一点,也便宜,做主存和图形帧缓冲区3. ROM:非易失性存储器,也称为只读存储器(ROM),即使是在关电的时候,也能保持它们的信息,它们用来存储固件(firmware)。如存储bios等，只读不写。断电保存4. 磁盘是非易失性存储设备,以每个位很低的成本保存大量的数据。代价是较长的访问时间。

一般而言,较快的存储技术每个位会更贵,而且容量较小。这些技术的价格和性能属性正在动态地以不同的速度变化着。

特别地,DRAM和磁盘访问时间滞后于CPU周期时间。

5. 系统通过将存储器组织成存储设备的层次结构来弥补这些差异,在这个层次结构中,较小、较快的设备在顶部较大、较慢的设备在底部。

因为编写良好的程序有好的局部性,大多数数据都可以从较高层次得到服务,结果就是存储系统能以较高层的速度运行,但却有较低层的成本和容量。程序员可以通过编写有良好空间和时间局部性的程序来动态地改进程序的运行时间。利用基于SRAM的高速缓存存储器特别重要,主要从L1高速缓存取数据的程序能比主要从存储器取数据的程序运行得快过一个数量级。

深入理解操作系统（16）第六章：存储器层次结构（2）高速缓存存储器+对程序性能的影响（包括：L1/L2高速缓存历史/缓存写：直写和写回/暂无L4级缓存/缓存命中率/存储器山/高速缓存友好的代码/）