CSAPP-存储器层次结构

编程/技术 2019-04-14 @ 20:01:46 浏览数: 437 净访问: 277 By: skyrover

本博客采用创作共用版权协议, 要求署名、非商业用途和保持一致. 转载本博客文章必须也遵循署名-非商业用途-保持一致的创作共用协议


在读第9章虚拟存储器的时候,提到了TLB(Translation Lookaside Buffer) 翻译后备缓冲器,是四路组相连的。这块在以前计算机组成原理的时候学过,但是现在基本忘得差不多了,书往前翻,果然有介绍相关概念的,就是在第6章,存储器层次结构的6.4高速缓存存储器。于是翻开来看看

6.4 高速缓存存储器

这一块容易混淆的是存储器地址与存储器实际的存储单元两者的差异,大部分讨论的是存储器地址方面的,具体数据是按照地址找到存储器单元,然后存储的,这一点理解了,后面内容也就容易了

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

这张图很好,首先高速缓存存储器被分成了S个组,每个组被分成了E行,然后每一行中的存储器中的数据位中包含以下数据:

  • 1个有效位
  • t个标记位
  • B字节的高速缓存块

所以说一行有B*8+t+1位数据,但是对于存储器来说,一个地址肯定是无法对应这么多数据的。那么对于地址来说,假设存储器地址有m位,那么如何对于上面高速缓存存储器的分组分行分块模型如何找到对应数据呢,所以一个地址分成了下面:

  • t位的标记位
  • s位的组索引
  • b位块偏移

所以对于某个组,某行,某个块的数据,我们就可以通过地址来找到了,比如在组1,行1,块1的数据的地址我们就可以这样(假设地址只有4位):1011。一般是通过t标记位来标志组中哪一行包含这个数据,t是当前块的存储器地址的位的一个子集。通常会使用中间的位做组索引,如果使用高位的话,那么连续的存储器块就会映射到相同的高速缓存块,但是如果一个程序有比较好的空间局部性,顺序扫描数组元素,就会导致高速缓存中只保存一个块大小的数组内容。而使用中间位做索引,那么相邻的块会映射到不同的高速缓存行,这样可以提高使用效率。

6.4.2 直接映射高速缓存

它的每个组只有一行。高速缓存确定一个请求是否命中,然后抽取出被请求的字的过程,分为三步:组选择,行匹配,字抽取

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

通过s位的组索引进行选择,比如0001代表第2个组

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

每个组中只有一行,所以只要该行设置了数据有效位,并且该行的标记位与地址的标记位相同,则该行中包含要提取数据的一个拷贝。

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

通过块偏移来得到所需要字的第一个字节的偏移

  • 直接映射高速缓存中不命中的行替换

根据地址中的组索引存到对应组中,因为只有一个行,所以用新取出的行替换当前的行

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

冲突失效 (Conflict miss): 在组相联或直接映射 Cache 中, 若太多的块映射到同一组(块)中,则会出现该组中某个块被别的块替换、然后又被重新访问的情况。这就是发生了冲突失效。这种失效也称为碰撞失效 (collision) 或干扰失效 (interference)。(提高相联度)组相联高速缓存和直接映射缓存相比,该处理器可以把更多的工作集保持在缓存中。

书上关于冲突不命中有一个例子,可以看到在访问大小为2的幂的数组的时候,因为x,y对应索引访问的数组刚好都映射在高速缓存存储器的同一个组,但是这个组又只有一行,所以导致高速缓存反复的加载和驱逐相同的高速缓存块的组。

首先列举出整个地址空间的划分:

黄色区域是y数组开始的地方,可以看到,如果访问x[0],即地址0的数据,那么高速缓存需要加载块0放到组0,接下来访问y[0],同样需要加载块2到组0,将x的数据驱逐出去,这样就会导致高速缓存的抖动。

假设我们提高相联度:变成全相联,那么索引位就为0,只剩下标记位和偏移位组成,高速缓存将有一个组,一个组有两行,假设需要读取x[0],将会加载块0到高速缓存,接下来需要y[0],需要加载块2到缓存,但是两者的标记位不同,因为会分别加载到组的两行中,这样同样大小的高速缓存,利用率更高,虽然最终结果也是导致了经常性的换入换出,但是明显可以看出来,增加相联度是可以降低高速缓存由于冲突不命中导致抖动的可能性。

6.4.3 组相连高速缓存

  • 组相连高速缓存中的组选择

和直接映射高速缓存的组选择一样

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

在这里需要检查一个组的多个行的标记位和有效位,以确定请求的字是否在集合中。一个相联的存储器是一个(key, value)对的数组,可以把组相联高速缓存中的每个组都看成一个小的相联存储器。

高速缓存必须搜索组中的每一行,寻找一个有效的行,其标记和地址中的标记相匹配,如果找到则命中。

  • 组相连高速缓存中不命中时的行替换

在组相联或者全相联中,行替换是一个值得深入思考的问题,因为替换策略很大程度影响了替换效率,较为复杂的算法使用了局部性原理,比如最不常使用(LFU)或者最近最少使用(LRU)策略。越往存储器层次结构下面走,远离CPU,一次不命中的开销会更昂贵,因此用更好的替换策略使得不命中最少也变得更加值得了。

6.4.4 全相联高速缓存

只有一个组,组中包含了所有的行。

  • 组选择
  • 行匹配与字选择

原理都是一样,只不过规模大小。高速缓存电路必须并行的搜索许多相匹配的标记,构造一个又大又快的全相联高速缓存比较困难,因此只适合用作小的缓存,比如TLB,缓存页表项。

6.4.5 有关写的问题

  • 直写:在高速缓存更新数据之后,直接写入下一层存储器中
    • 非写分配:如果要写的内容没有在高速缓存,那么直接写入下一级存储器
  • 写回:高速缓存更新数据之后,在要将该块驱逐的时候,才写入下一级存储器中
    • 写分配:首先读入高速缓存,然后更新高速缓存块


点赞走一波😏


评论

提交评论