深入理解计算机系统_第6章 存储器层次结构
6.2 局部性
程序的局部性：倾向于引用邻近于其他最近引用过的数据项的数据项，或者引用最近引用过的数据项本身。
局部性的两种不同形式：时间局部性和空间局部性
时间局部性：被引用过一次的内存位置很可能在不远的将来再次被引用；
空间局部性： 如果一个内存位置被引用了， 那么程序可能在不久的将来引用附近的一个内存位置；
有良好局部性的程序运行得更快；
6.2.1 对程序数据引用的局部性
int sumvec(int v[N])
{
int i, sum = 0;
for(i = 0; i < N; i++)
sum += v[i];
return sum;
}
变量sum在每次循环中被引用一次，因此具有很好的实践局部性；sum是标量，因此没有空间局部性；
v是向量，每次循环中按照顺序访问向量中的元素，因此有很好的空间局部性；v中的元素只被访问一次，因此没有时间局部性；
像sumvec这样顺序访问一个向量中每个元素的函数，称为步长为1的引用模式，也叫做顺序引用模式；
一个连续向量中， 每隔k个元素进行访问，称为步长为k的引用模式。
步长为1的引用模式是程序中空间局部性常见和重要来源。随着步长增加， 空间局部性下降；
对于二维数组，使用下面代码，可以得到步长为1的引用；
int sumarrayrows(int a[M][N])
{
int i, j, sum = 0;
for(i = 0; i < M; i++)
for(j = 0; j < N; j++)
sum += a[i][j];
return sum;
}
6.2.2 取指令的局部性
循环体中的代码， 每次取指令都从同一个内存位置取指令；
6.2.3 局部性小结
1） 重复引用相同变量的程序有良好的时间局部性；
2） 步长为k的引用模式的程序，步长越小，空间局部性越好；在内存中以大步长跳来跳去的程序，其空间局部性会很差；
3） 对于取指令而言， 循环有很好的实践和空间局部性。循环体越小，循环迭代次数越多，局部性越好；
使用高速缓存命中率和不命中率来量化局部性的概念。
6.3 存储器层次结构
L0高速缓存一般是寄存器文件；
L1-L3高速缓存一般是SRAM；
主存一般是DRAM；
6.3.1 存储器层次结构中的缓存
高速缓存cache是一块小而快速的存储设备，作为存储在更大、也更慢的设备中的数据对象的缓冲区域；
存储器层次结构中的中心思想是：位于k层的更快更小的存储设备作为位于k+1层的更大更慢的存储设备的缓存。第k+1层的存储区被划分为连续的数据对象块， 每个块有唯一的地址可以区别其他块；块可以是固定大小的， 也可以是变大小的（HTML文件）；k层的块大小与k+1层块的大小一样， 但是块的数量不一样；数据总是以块的大小在不同缓存层中传递的；层次结构中任何一对相邻层次之间块的大小是固定的，但是其他层次对之间可以有不同的块的大小；
1） 缓存命中
当程序需要某个数据对象d， 此时d正好在缓存k中， 不需要从缓存k+1中提取数据， 就是缓存命中；
2） 缓存不命中
如果k层没有数据对象d， 就发生了缓存不命中。当发生缓存不命中，第k层的缓存从k+1层取出包含d的那个块放入缓存k中，如果缓存k已经满了， 可能需要覆盖缓存k中的某一个块；
覆盖一个现存的块的过程称为替换， 被替换的块称为牺牲块；决定替换哪一个块是由替换策略控制的。一个具有随机替换策略的缓存会随机选择一个牺牲块。一个具有最近最少使用（LRU)替换策略的缓存会选择最后被访问时间距离现在最长的块；
3） 缓存不命中的种类
冷不命中：如果第k层的缓存是空的，那么对于任何数据对象的访问都会不命中。一个空的缓存称为冷缓存，此类不命中称为强制不命中。冷不命中只是短暂的事件；
硬件缓存中执行较严格的放置策略，将k+1层的某个块限制放在第k层的一个很小的子集中，例如，k+1层的块i放到k层的（i %4）块中；块0， 4， 8， 12 映射到块0； 块1， 5， 9， 13映射到块1；
冲突不命中：上述这种策略会引起冲突不命中。例如如果请求块0， 然后块8，然后块0…, 这会导致一直不命中；
容量不命中：一个嵌套的循环可能反复访问同一个数组中的元素，程序访问的这些块的集合就是程序这个阶段的工作集。当程序的工作集大小超过缓存的大小时。缓存会经历容量不命中。此时缓存太小了，不能处理这个工作集；
4） 缓存管理
缓存管理：将缓存划分为块，在不同的层之间传递块，判定命中还是不命中，并处理。管理缓存的逻辑可以是硬件、软件或是两者的结合；
编译器管理寄存器文件， 决定当发生不命中时何时发射加载，确定哪个寄存器用来存放数据。。
L1, L2, L3层的缓存完全是由内置在缓存中的硬件逻辑来实现管理的（硬件实现的管理速度很快）；
DRAM作为主存是磁盘的缓存，其缓存管理由操作系统软件和CPU上的地址翻译硬件共同管理完成。
对于一个像AFS这样的分布式文件系统的机器而言， 本地磁盘作为缓存，其缓存管理由本地机器上的AFS客户端进程管理的。
6.3.2 存储器层次结构概念小结
利用时间局部性：同一个数据对象可能在一段时间内被多次访问；
利用空间局部性：一个块中一般有多个数据对象， 由于空间局部性，对块中的一个数据对象访问，就有可能对块中的其它对象进行访问，所以每次在不同层次之间传递数据都是以块为单位进行传递；
6.4 高速缓存存储器
L1 高速缓存：4个时钟周期
L2 高速缓存：10个时钟周期
L3 高速缓存：50个时钟周期
6.4.1 通用的高速缓存存储器组织结构
将一个存储器以字节为单位划分为S个组， E个高速缓存行， B个字节数据块；
在一个高速缓存行中，有一个有效位指明这行数据是否具有意义， 还有t = m-(b+s) 个标记位，指明当前存储在这个行中的块的身份。（例如， 上一层的块0， 4， 8， 12）都可以存在这一层的块0上，标志位指出具体是哪一块存在这里）；
高速缓存结构使用（S,E, B, m）来描述。 高速缓存的大小C是所有块的综合 = S×E×B；
当一条加载指令指示CPU从主存地址A读取一个字，他将这个地址发送给高速缓存；
参数S， B将地址分为三部分。组索引指明在哪一个组S； 然后在这个组中找寻与标记相匹配的那一个高速缓存行E，最后根据块偏移在高速缓存行中找到具体的字节；
6.4.2 直接映射高速缓存
每个组中只含有一个高速缓存行的结构， 称为直接映射高速缓存；
高速缓存确定一个请求是否命中，然后抽取出被请求的字段过程，分为三步：1） 组选择； 2） 行匹配； 3） 字抽取
（1） 直接映射高速缓存中的组选择
高速缓存从地址在抽取s个组索引位，将组索引位映射到一个对应于组号的无符号整数，根据这个整数选择具体的组；
（2） 直接映射高速缓存中的行匹配
查看高速缓存行中的有效位是否设置，如果设置了，表明当前行中的数据有效；如果有效位为0， 表明这一高速缓存行是空的， 需要从下一级存储加载数据；
然后在对标记位进行匹配；如果标记位匹配，表明当前高速缓存行上的块是目标块；如果标记位不匹配， 说明需要从下一层存储中加载数据块覆盖掉现有的块；
（3） 直接映射高速缓存中的字抽取
利用块偏移找到具体字节的位置，读出这个字节；
（4） 直接映射高速缓存中的行替换
当发生缓存不命中的时候， 需要从下一层加载块并替换现有的高速缓存行（组中只有一行高速缓存行）；
（5） 综合：运行中的直接映射高速缓存
假设高速缓存有4个组， 每个组一行，每个块有两个字节，总共能缓存8个字节；
该高速缓存读取的地址是四位的，也就是16个字节；
（S, E, B, m) = (4, 1, 2, 4);
- 标记为和索引为组合起来唯一标记了高速缓存中的一个块；
2） 存在多个块被映射到itongyige高速缓存组， 例如块0和块4都会被映射到组1；
3） 映射到同一个高速缓存组的块由标记位唯一标记。例如， 块0 的标记位是0， 块4的标记位是1；
（6） 直接映射高速缓存中的冲突不命中
当程序访问大小为2的幂的数组时候， 直接映射高速缓存中通常会发生冲突不命中。
考虑下面程序：
float dotprod（float x[8], float y[8]）{
float sum = 0.0;
int i;
for(i = 0; i < 8; i++)
sum += x[i] * y[i];
return sum;
}
浮点数是4个字节，假设x的地址是0-31， y的地址是32-63；
高速缓存大小是32个字节分为两个组，组0的块是16字节，能存4个浮点数；组1的块是16字节，能存4个浮点数；
现在缓存分配策略是这样的， x数组的前四个数据分配到组0， 后四个数据分配到组1； y数组的前4个数据分配到组0， 后4个数据分配到组1；
程序运行时候， 每次循环的时候， 第一次引用x[0],缓存不命中导致x[0]-x[3] 加载到组0； 之后引用y[0], 缓存不命中导致y[0]-y[3] 被加载到组0；之后每一次的循环都在组0中发生缓存不命中；发生抖动；导致程序性能很差；
一个简单的修复抖动的办法是：将数组定义成float[8];这样x数组的前四个元素被分配到组0，y数组的前四个元素被分配到组1. 消除了缓存抖动现象；
为什么使用地址中间的位来作为组索引， 使用地址的高位做标记位？
使用高位索引， 连续的地址空间会被分配同一个块中。 例如0000-0011这四个地址都被分配到组0，如果访问0000后访问0001，就会发生不命中，产生冲突不命中；
使用中间位索引，能最大限度地降低冲突不命中；
6.4.3 组相联高速缓存
直接映射高速缓存中的冲突不命中的原因是每个组只有一行，组相连高速缓存放松了这个限制，每个组都保存有多余一个的高速缓存，成为E路组相联高速缓存；
（1） 组相连高速缓存中的组选择
与直接映射高速缓存中的组选择一样，通过组索引识别标志组；
（2） 组相连高速缓存中的行匹配和字选择
组相连高速缓存中的行匹配更加复杂，在选定了组之后， 需要检查组内多个行的有效位和标志位，以确定所请求的字是否在组内；这样有一个重要的思想：组中的任何一行都可以包含任何映射到这个组中的内存块， 所以高速缓存必须搜索组内的每一个行；
（3）组相连高速缓存中不命中时的行替换
如果发生不命中， 高速缓存必须从下一层的存储中取出包含这个字节的块，然后在组内选择一行替换掉，这里就涉及到替换策略；
简单的替换策略：随机替换
复杂的替换策略：利用局部性原理， 替换掉将来不太会被使用的行，
LFU：最不常使用策略，替换掉过去某个时间窗口引用次数最少的那一行；
LRU：最近最少使用策略， 替换掉最后一次访问时间最久远的那一行；
6.4.4 全相联高速缓存
全相联高速缓存只有一个组；
（1） 全相联高速缓存中的组选择
只有一个组，不需要进行组选择， 地址被划分为标记和块偏移，没有组索引
（2） 全相联高速缓存中的行匹配和字选择
全相联高速缓存中的行匹配和字选择与组相连高速缓存中是一样的，主要区别在于规模大小；全相联高速缓存只适合做小的高速缓存，例如虚拟内存系统中翻译备用TLB,用于缓存页表项；
6.4.5 有关写的问题
假设我们写一个已经缓存过的字，当写完成，高速缓存中更新了这个字之后， 如何在下一层次的存储中更新这个字呢？
1） 直写：立即将w的高速缓存块写回到下一层此的存储中去；
2） 写回：尽可能的推迟更新，只有当替换算法要驱逐这个更新过的块的时候，才将这个块写回到下一层此的存储中；写回需要增加一个脏位（dirty bit),表明这个块是否被修改过；
如果处理写不命中的情况：
写分配：加载相应的低层次的块到高速缓存中，然后更新这个高速缓存块；
非写分配：避开高速缓存，直接将这个字写到低一层次；
直写高速缓存通常是非写分配到；
写回高速缓存通常是写分配到；
一般而言， 默认处理器采用写回和写分配的高速缓存模型；
6.4.6 一个真实的高速缓存层次结构的解剖
高速缓存即保存数据， 也保存指令：
i-cache:只保存指令的高速缓存
d-cache:只保存数据的高速缓存
unified cache：既保存指令又保存数据的高速缓存
6.4.7 高速缓存参数的性能影响
衡量高速缓存的性能；
1） 不命中率 = 不命中数量/引用数量
2） 命中率 = 1- 不命中率
3） 命中时间从高速缓存传送一个字到CPU所需的时间，包括组选择、行确认、字选择的时间；
4） 不命中处罚，由于不命中所需要的额外时间，L1不命中需要从L2得到服务的块，几十个周期；
从L3处得到的处罚， 50个周期； 从主存中得到服务的处罚，200个周期；
（1） 高速缓存大小的影响
较大的高速缓存可以提高命中率， 但是存储器大的时候起运行速度就慢；综合起来较大的高速缓存反而增加了命中时间；
（2） 块大小的影响
较大的块能够更好地利用程序的空间局部性，提供命中率；
但是对于给定的高速缓存器，较大的块意味着较少的高速缓存行，影响时间局部性；
同时， 较大的块，块传送时间也越长；
（3） 相联度的影响
即高速缓存行E的大小的影响，较高的相联度（E较大），降低了冲突不命中导致的抖动现象；但是较高的相联度会造成较高的成本，使得速度很慢；
（4） 写粗略的影响
高速缓存行、组和块的区别
1） 块是一个固定大小的信息包，在高速缓存和下一层次之间来回传递；
2） 行是高速缓存的一个容器，存储块以及其他信息（有效位，标记位）
3） 组是一个或多个行的集合
6.5 编写高速缓存友好的代码
局部性较好的程序更容易有较低的不命中率，因此程序运行更快，程序员应该编写高速缓存友好的程序：
1） 让最常见的情况运行得快； 程序通常把大部分时间都花在少量的核心函数上，而这些核心函数通常将大量时间花在少量的循环上。因此，程序员的注意力应当集中在核心函数的循环体内，忽略其他代码；
2） 尽量减少每个循环内部的缓存不命中；
编写高速缓存友好代码：
1） 对局部变量的反复引用是友好的，因为编译器能够将他们缓存在寄存器文件中（时间局部性）；
2） 步长为1的引用模式是友好的，因为存储器层此结构上所有层次上的缓存都是将数据存储为连续的块；