csapp_6_存储器层次结构2

存储器层次结构
高速缓存存储器：直接映射、组相联映射、全相连映射
缓存的行替换策略
缓存的写问题：写命中/不命中，以及策略
存储器山
小结

存储器层次结构

层次结构

• 重点图
• 高速缓存（cache）：小而快的存储设备。使用高速缓存的过程称为缓存。
• 存储器层次结构中心思想：对于每个k，位于第k层的更小更快的存储设备作为位于第k+1层的更大更慢的存储设备的缓存。即，层次结构中的每一层都缓存来自较低一层的数据对象。
• 数据以块为传送单元在第k层和第k+1层之间来回赋值。
  
  • 任何一对相邻层次之间块的大小是一致的固定的，但其他层次对之间块的大小可以与本层次对不同。
    • 如L0和L1的块大小为1个word；L2和L1、L3和L2、L4和L3是几十bytes；L5和L4之间的块是几百/几千bytes。
    • 距离cpu越远的层次，访问设备时间越长。为了弥补这些时间，块也相应大。

缓存

缓存命中

• 缓存命中：如果第k+1层的数据对象d，刚好缓存在第k层中，那么就是缓存命中（程序需要第k+1层的数据对象d时，会现在第k层的一个块中查找d）

缓存不命中

• 缓存不命中：如果第k+1层的数据对象d，没有缓存在第k层中，那么就是缓存不命中。

• 此时第k层会从第k+1层取出包含d的块，将其存入第k层。此时可能会发生覆盖第k层现存的块。

  • 覆盖的过程称为 替换/驱逐 块。被驱逐的块称为牺牲块。决定哪个块被替换由缓存的替换策略控制（如LRU，LFU等）

• 缓存不命中种类

  • 冷不命中 / 强制不命中
    • 对于冷缓存，任何数据对象的访问都不命中。（第k层为冷缓存即第k层为空）
    • 冷不命中短暂。暖身之后就不会出现。
  • 冲突不命中
    • 为了速度更快，硬件会使用更严格的放置策略，但这种放置策略会引起冲突不命中。
    • 有足够的高速缓存空间，却交替的引用映射到同一个组的块。
  • 容量不命中
    • 程序通常是按照一系列阶段（循环）来运行的，每个极端访问缓存块的某个相对稳定不变的集合。
    • 感觉就是最一般的不命中吧，缓存不够大，不能一次就将工作集放入缓存，若当工作集的大小超过缓存大小时，当需要用到没放入缓存中的工作集数据时，缓存会经历容量不命中。（如访问一个大数组，其块的集合就被称为该阶段的工作集）

• 放置策略：决定第k+1层取出的块放在第k层哪个组
  • Placement policy: determines where b goes
• 替换策略：决定哪个块被驱逐
  • Replacement policy:
    determines which block
    gets evicted (victim)

缓存管理

• 管理缓存的逻辑可以是硬件、软件或两者结合
  • 需要由某种形式的逻辑管理缓存，也即如何将某个对象划分成块，如何传递块，是否命中，并如何放置，替换等处理他们。如
  • 寄存器文件 由 编译器管理
  • L1 L2 L3 由内置在缓存中的硬件逻辑管理
  • 在有虚拟内存的系统中，DRAM作为存储在磁盘上的数据块的缓存，由os和cpu上的地址翻译硬件共同管理
  • 本地磁盘作为AFS分布式文件系统的缓存，由运行在本地机器的AFS客户端进程管理
• 缓存常自动运行，无需用户程序采取特殊或显式的行为。
  

高速缓存存储器

• 架构图
  

结构（高速缓存和主存地址）

• 高速缓存和主存地址图
  
  

• 高速缓存是一个高速缓存组的数组（S=2^s个高速缓存组）

  • 每个组包含E（E>=1）行
  • 每行包含一个有效位，t位标记为，一个数据块，且数据块大小为Bbytes（B=2^b）

• 高速缓存的结构可以用(S,E,B,m)来描述。高速缓存的大小C = S*E*B，m表示主存地址的位数

• 高速缓存的结构将m个地址位划分为t位标记位，s位组索引位，b位块偏移。

• 注意S=2^s,B=2^b,但E!=2^t，因为t位标记位只是作为标记位，通过比较是否相等来标记该行缓存的是否是我所请求的地址的块内容，不时用来指示组中的哪一个行。

• 当CPU要从主存地址A读一个字时，降低至A发送给高速缓存，如果缓存命中，那么就将该字A发送给CPU。那么如何判断缓存是否命中（在缓存找找到请求的字）？如下，利用主存的目的地址

  • 地址中s位组索引：指明该地址起始的块应该缓存在哪一组。
  • 地址中t位标记：定位到正确的组之后，遍历该缓存组的行，将每行的t位标记与该地址的t位标记比较，相同，则表明改行缓存的就是该地址起始的块。
  • 地址中b位偏移量：指出请求的字在相应行的数据块中的字节偏移量。
  • 除此外，还有高速缓存行中的有效位：如果该行的有效位为0，则无效。1则有效

• 主存和缓存之间的数据交换，一般是以块为单元，即以Bbytes为单元。

• 缓存和cpu之间的数据交换，一般是以字，字节，双字等为单元。

• 根据每个组的高速缓存行数E，高速缓存被分为不同的类。

直接映射高速缓存

• 直接映射高速缓存：E=1，即每个组只有一行。
  
• 缓存命中：高速缓存很快地抽取字w，返回给cpu
• 缓存不命中：
  • 高速缓存向主存（下一层结构）请求包含w的块的一个副本，在这个过程中，cpu必须等待。
  • 当被请求的块从主存中到达时，高速缓存根据组索引位的指示将该块放在它某组中的一个高速缓存行里。
    • 可能会需要驱逐一个缓存中现存的行
      • 对于直接映射来说，替换策略很简单，就是用新取出的行替换当前的行。
  • 然后从被存储的块中抽出字w，然后将它返回给cpu。

请求过程

• 高速缓存判断一个请求是否命中，然后抽取出被请求的字的过程，分为
  • 1. 组选择
  • 2. 行匹配
  • 3. 字抽取

组选择

• 组索引位：s位标记位被解释为无符号整数，是一个到高速缓存数组的索引。

行匹配

• 行匹配：选择了组i之后需要进一步确认组中是否有字w的一个副本
• 缓存命中条件：有效位设置 && 标记匹配
  • 有效位设置：缓存行中标记和块中的位是有意义的。
  • 标记匹配：高速缓存行中的标记与w的地址中的标记相同，此时行中包含w的一个副本

字选择

• 一旦缓存命中，我们就知道w就在该行的块中的某个地方，接下来最后一步确定所需的字在块中从哪里开始即可。利用b位的块偏移。
  • b位二进制表示偏移的字节数。

行替换

• 用新取出的行替换当前的行。

例子

• (S,E,B,m) = (4,1,2,4)
  
• 标记位和索引位连起来唯一的标识了主存中的每个块。
• 映射到同一个高速缓存组的块由标记位唯一的标识。
• 见csapp_430

直接映射的冲突不命中

• 抖动：高速缓存反复的加载和驱逐相同的高速缓存块的组。 （因为不同块被映射到同一组）
  • 即便程序有良好的空间局部性，高速缓存空间也够，但由于抖动，程序速度也会下降。
• 修正抖动问题：在每个数组的结尾放B字节的填充。
  • B字节，正好错开一组。
    

• 为什么用中间的位作为组索引，而不是用高位
  • 因为用高位做索引，那么一些连续的内存块就会被映射到相同的高速缓存行。
  • 那么，如果一个程序有良好的空间局部性，顺序扫描数组时，在任意时刻，高速缓存块中只保留一个块大小的数组内容。因为相邻的块都被映射到同一组了。效率低下，

组相联高速缓存

• E路组相联：一组里面有E行
  • 一个1<E<C/B的高速缓存（C=E*S*B && 1<E<C/B –> S > 1）
    
• 一个组中的任何一行都可以包含任何映射到这个组的内存块

组选择

• 组索引标识组，同直接映射的组选择。
  

行选择

• 比直接映射的组选择复杂。
• 高速缓存必须搜索一个组中的所有行，若行的标记和主存地址的标记匹配，即命中。
  

字偏移

• 还是b位二进制表示偏移的字节数。

行替换

• 在不命中时，如果定位到的组中有空行，那么直接放入；如果没有空行，即会发生行替换。（尽量使得这个牺牲行之后不会很快被cpu引用）
• 行替换策略
  • 随机选择要替换的行（简单）
  • LRU（Least-Recently-Used）：最近最少使用策略
    • 替换最后一次访问时间最久远的那一行
  • LFU（Least——Frequently-Used）：最不常使用策略
    • 替换在过去某个时间窗口引用次数最少的那一行
  • 这些策略需要额外的硬件和事件，但是，存储层次越向下，越远离cpu，一次不命中的开销越大，因此，用更好的替换策略使得不命中最少也变得更加值得了。

全相联高速缓存

• 只有一个组，也即S = 2^0 = 0。也即主存地址中的s组索引部分的位数为0。
• 比前两种都复杂和昂贵，全相联只适合做小的高速存储，如虚拟内存系统中的翻译备用缓冲器TLB，用于缓存页表项（cy，还没学啊）

组选择

• 组索引位数为0
  

行匹配

字偏移

• m = t+b
  

读概要

• 之前探讨的都是读的问题。关于读命中和读不命中。

  读命中

• 缓存命中则直接将字返回给cpu；

  读不命中

• 不命中的话
  • 高速缓存向主存（下一层结构）请求包含w的块的一个副本，在这个过程中，cpu必须等待。
  • 当被请求的块从主存中到达时，高速缓存根据组索引位的指示将该块放在它某组中的一个高速缓存行里。
    • 可能会需要驱逐一个缓存中现存的行
      • 对于直接映射来说，替换策略很简单，就是用新取出的行替换当前的行。
  • 然后从被存储的块中抽出字w，然后将它返回给cpu。

写

写命中

• 要写一个已经缓存了的字w
• 1. 先在高速缓存更新w的副本
• 2. 然后更新w在层次结构中紧挨着的下一层的副本，有两种方案。write-through 和 write back
  • write-through ：直写
    • 立即将w的高速缓存块写回紧挨着的低一层中
    • 优点：实现简单
    • 缺点：每次写都会引起总线流量
  • write-back：写回
    • 尽可能推迟更新，只有当替换算法要驱逐这个更新过的块时，才把它写道紧接着的低一层中。
    • 优点：利用局部性，写回策略可以显著减少总线流量
    • 缺点：增加复杂性。高速缓存必须维护一个额外的修改为（dirty-bit），表明这个高速缓存块是否修改过。

写不命中

• 要写一个还没被缓存的块。
• write-allocate：写分配
  • 加载相应的低一层中的块到高速缓存中，然后更新这个告诉缓存块。
  • 优点：利用了空间局部性
  • 缺点：每次不命中都会导致一个块从低一层传送到高速缓存。
  • 写分配策略提问
    • 为什么写不命中需要将原内存内容先加载入cache，再更新这行cache。为啥不直接根据主存地址在cache里的相应位置写入要写的新内容。之后这个块需要被驱逐时再紧接着的下一层？
    • 因为写分配是一个写不命中时的策略，这是高速缓存中相应的行不是主存相应地址的内容。主存和缓存交换的单元是数据块，缓存和cpu交换的单元是字/字节等。缓存行的数据块除了你写入修改的bytes，还会有其他bytes不是主存相应地址的内容，怎么办？你只写入了几个有效的bytes，那行里的把其他无效bytes呢？岂不是会破坏主存里的内容
    • 所以，写分配应当先讲下一层的该地址的块加载到本层内存中，然后更新这个告诉缓存块。
• not-write-allocate 非写分配
  • 避开高速缓存，直接把这个字写入低一层中。
• 直接写高速缓存通常是非写分配的。
  • write-through && not-write-allocate
• 写回高速缓存一般是写分配的
  • write-back && write-allocate
• 但是读都是一样的。

• 写程序时一般认为os和机器使用写回写分配的高速缓存模型
  • 由于较长的传送时间，因而采用写回
  • 策略实现的复杂性不再是阻碍
  • 现在所有层次上都能看到写回缓存
  • 与处理读的方式相对称，都利用了局部性
  • 基于这种假设，我们可以在高层次上写程序，而不用去试图优化一个存储器系统

真实结构

• unified-cache：统一的高速缓存：既保存指令又保存数据
• i-cache：只保存指令的高速缓存
• d-cache：只保存数据的高速缓存
  • 两个独立的高速缓存的优点
  • 处理器可以同时访问这俩
  • 可以针对不同访问模式优化
  • 确保数据访问不会和指令访问形成冲突不命中（代价：可能会引起容量不命中up）
• L3所有核共享；L1、L2每个核私有

性能

• 衡量性能

  • 不命中率（miss rate）：不命中数量 / 引用数量
  • 命中率（hit rate）
  • 命中时间（hit time）：从高速缓存中传送一个字到cpu的时间：
    • 组选择、行确认、字偏移的时间。
    • 对L1来说，命中时间的数量级为几个时钟周期。
  • 不命中处罚（miss penalty）：由于不命中所需的额外时间
    • L1不命中后
    • 从L2得到服务的处罚：10个时钟周期
    • 从L3得到服务的处罚：50个时钟周期
    • 从主存得到服务的处罚：200个时钟周期

• 影响因素

  • 高速缓存大小
    • 较大的高速缓存：
      • 提高命中率，
      • 但也会增加命中时间。（使大存储器运行更快比较难）
    • 所以L1比L2小，L2比L3小
  • 块大小
    • 较大的块
      • 更能利用程序中可能存在的空间局部性，帮助提高命中率
      • 但对于给定的高速缓存大小，块越大意味着高速缓存行数越少（我感觉容易发生抖动，可能会多个块映射到同一行），会降低时间局部性比空间局部性更好的程序的命中率。
      • 对不命中处罚也有不利影响：块越大，传送时间越长，不命中处罚也就越大。
  • 相联度
    • 每组行数E即相联度。
    • 较大的E
      • 降低了由于冲突不命中而出现抖动的可能
      • 但是复杂，昂贵，增加命中时间（因为行的复杂性增加了)，增加不命中处罚（因为选择牺牲行的复杂性增加了）。
    • E的选择是命中时间和不命中处罚的折中。
      • L1：E较小（因为不命中处罚只是几个clk）
      • 而较低层则E较大（因为不命中处罚很大）
  • 写策略
    • …
    • 越向下，越可能使用写回而不是直写。

• 组包含行，行包含块
  

编写高速缓存友好的代码

• 基本方法

  • 让最常见的情况运行的快
  • 尽量减小每个循环内部的缓存不命中数量

• 对局部变量的反复吟咏是好的，因为编译器能将他们缓存在Register File中（时间局部性）

• 步长为1的引用模式是好的，因为存储器层次结构中所有层次上的缓存都是讲数据存储为连续的块。

  • 步长为k（字）的引用模式：平均每次循环迭代会有min(1,(wordsize*k)/B)次缓存不命中

• 二维数组遍历 行优先 / 列优先。（假设1字4bytes，高速缓存4个字，初始为空）

  • 行优先：不命中率1/4
    
    
  • 列优先。可以自己对着地址和程序看一眼。会出现抖动。
    
    
    • 数组地址

      t s  b
      0 00 0000   // (0,0)
      ...
      0 01 0000   // (0,4)
      ...
      0 10 0000   // (1,0)
      ...
      0 11 0000   // (1,4)
      ...
      1 00 0000   // (2,0)
      ...
      1 01 0000   // (2,4)
      ...
      1 10 0000   // (3,0)
      ...
      1 11 0000   // (3,4)

• 例题
  

• 关键点：

  • 直接映射，直写（写命中），写分配（写不命中）
    • 写分配：需要将下一层的块加载入高速缓存中，又因为直接映射，因此会发生替换。
    • 直接映射：E=1
  • 块大小B=8bytes，故b=3。
  • 组数S = C / (E*B) = 16/8 = 2 = 2^s 。故s=1
  • 标记位t多少位无所谓，就是个标记。

• 逻辑

  dst[0][0] = src[0][0]
  dst[1][0] = src[0][1]
  dst[0][1] = src[1][0]
  dst[1][1] = src[1][1]

• 地址

  src     
           0         1
  0     0 0 000   0 0 100
  1     0 1 000   0 1 100
  
  dst
           0          1
  0     1 0 000   1 0 100
  1     1 1 000   1 1 100

存储器山

• 读吞吐量(read throughput)/读带宽(read handwidth)：一个程序从存储系统中读数据的速率。(n/s ：s秒内读n字节；通常以MB/s为单位)

• 存储器山：读吞吐量的时间局部性和空间局部性二维函数。
  

• 大小是指工作集大小：工作集越小，时间局部性越好。

• 步长stride：步长越小，空间局部性越好。

• 橘色：四条山脊对应的工作集完全在L1、L2、L3、主存内的时间局部性区域

• 粉色：空间局部性好可以补救时间局部性差

• 固定步长为常数，观察吞吐量与时间局部性（工作集）关系
  

• 固定工作集大小，观察吞吐量和空间局部性（步长）关系(csapp447.其实没太看懂，这步长的单位到底是啥。)
  

• 码农尽可能利用时间局部性和空间局部性，去访问存储器山的左上角。

在程序中利用局部性

• 正如我们看到的，存储系统被组织成一个存储设备的层次结构，较小、较快的设备靠近顶部，较大、较慢的设备靠近底部。由于采用了这种层次结构，程序访问存储位置的实际速率不是一个数字能描述的。相反，它是一个变化很大的程序局部性的函数（我们称之为存储器山）， 变化可以有几个数量级。有良好局部性的程序从快速的高速缓存存储器中访问它的大部分数据。局部性差的程序从相对慢速的 DRAM 主存中访问它的大部分数据。
• 理解存储器层次结构本质的程序员能够利用这些知识编写出更有效的程序，无论具体
  的存储系统结构是怎样的。特别地，我们推荐下列技术
• 将你的注意力集中在内循环上，大部分计算和内存访问都发生在这里。
• 通过按照数据对象存储在内存中的顺序、以步长为 1 的来读数据，从而使得你程序中的空间局部性最大。
• 一旦从存睹器中读入了一个数据对象，就尽可能多地使用它，从而使得程序中的时间局部性最大。