盐析白兔

这个屌丝很懒，什么也没留下！

热门标签

系统结构期末复习（五）存储系统_多级包容性:

作者：盐析白兔 | 2024-03-20 07:59:30

踩

多级包容性:

1. 存储系统的层次结构

1.1 存储系统的层次结构

走出容量价格和速度三者困境的唯一方法是采用多种存储器技术，构成多级存储层次结构。

程序访问的局部性原理
时间局部性和空间局部性：对于绝大多数程序来说，程序所访问的指令和数据在地址上不是均匀分布的，而是相对簇聚的。时间：现在用到的是将来用到的，如循环；空间：将来用到的在现在的附近，如顺序执行。
存储系统的多层次结构
在存储层次中，各存储器之间一般满足包容关系，即任何一层存储器中的内容都是其下一期（离CPU更远一层）存储器中内容的子集。CPU与M1之间传送信息一般以字为单位，M1以外（含M1）的相邻存储器之间一般以块或页面为单位传送信息。

1.2 存储系统的性能参数

前提：
在这里插入图片描述

1. 存储容量

一般来说，整个存储系统的容量即是第二级存储器M2的容量，例如在由高速缓冲存储器Cache和主存组成的系统中，存储系统的容量就是主存的容量。

2. 存储系统的平均每位价格C

在这里插入图片描述

3. 命中率H

在这里插入图片描述

4. 平均访存时间

在这里插入图片描述
不命中开销是在M1中没有找到，然后到M2中去找找到了，再传回M1，CPU必须从M1中取得数据。

1.3 三级存储结构

在这里插入图片描述
虚拟存储器主要是为了解决扩大存储器容量的问题

1.4 存储层次的4个问题

当把一个块（页）调入高一层（靠近CPU）存储器时，可以放到哪些位置上（映像规则）
当所要访问的块（页）在高一层存储器中时，如何找到该块（查找算法）
当发生不命中而且高一层存储器已经满时，应该替换哪一块。（替换算法）
当进行写访问时，应进行哪些操作（写策略）

2. Cache基本知识

2.1 基本结构和原理

要点：
1. 主存和Cache被分成大小相同的块，Cache是按块进行管理的
2. 主存信息以块为单位调入Cache
3. 块大小放几十字节
4. Cache中的数据是主存中的副本
5. 全相联和直接映像都是特殊的组相联，全相联的组数就等于1，直接映像的组数就等于块数
6. 一定要注意一个概念，所谓的 n路组相联，指的是组相联中，每组里的块数，而不是组数
1
2
3
4
5
6
7

在这里插入图片描述

2.2 映像规则

解决问题：把一个块从主存调入Cache时可以放置到哪些位置

1. 全相联映像

主存中的任一块可以被放置到Cache中的任意一个位置。
特点：空间利用率最高，冲突概率最低，实现最复杂

2. 直接映像

主存中的每一个块只能被放到Cache中唯一一个位置。
特点：空间利用率最低，冲突概率最高，实现最简单
在这里插入图片描述

3. 组相联映像

Cache被等分成若干组，每组由若干个块构成。主存中的每一块可被放到Cache中唯一一个组的任何一个位置。组的选择常采用位选择算法：
在这里插入图片描述

n路组相联：如果每组中有n个块（n=M/G）
绝大多数计算机都采用直接映像、两路组相联、四路组相联，特别是直接相联应用的最多。

⚠️⚠️⚠️索引的划分是在块地址的部分进行划分，和块内位移无关。

例题：
设cache共有8块，每块大小为4B,主存共有64块，请给出直接映像、2路组相联映像、4路组相联映像和全相联映像时的访存地址格式和具体分析过程

cache每块大小位4B，则偏移为2位。总位数为2+6=8位
直接映像：（分成8组，每组1块）index=3位；tag=6-3=3位
2路组相联：（分成4组，每组2块）index=2位；tag=6-2=4位
4路组相联：（分成2组，每组4块）index=1位；tag=6-1=5位
1
2
3
4

【根据主存大小确定地址长度】

2.3 查找方法

查找算法是干啥的？
当CPU给出一个内存地址时，找一找Cache中有没有该内存单元的副本，也就是看看是“命中”，还是“不命中”。
怎么知道“命中”还是“不命中”？
假设，Cache的块数为4，主存的块数为8，直接映像，也就是主存的块地址划分为1位标识位，2位索引，如下图所示。凡是内存地址索引位为“00”的，映像到Cache的“00”块上，以此类推。

从图上可以看出，多个内存块可以映射到同一Cache块上。也就是，如图示，块地址为“001”和块地址为“101”的内存块，都可以映像到“01”Cache块上。那么，当CPU给出一个内存地址，怎么判断该地址对应的内存块是否在Cache中呢？相信大家也观察到了，虽然映像到同一个Cache块的内存块地址的索引位是相同的，但是标识位必定不相同。比如说图中的“001”和“101”，前者的标识为“0”，后者的标识为“1”。如此，在Cache块对应的位置记录下来当前在该块中的内存块的标识，就能表示清楚，当前时刻，在Cache块中保存的是内存那一块的副本。
查找目录表：Cache中有一个目录表，每一个Cache在该表中都有唯一的一项，用于指出当前该块中的信息是哪个主存块的。实际上记录的就是tag，存放目录表的存储器又叫做标识存储器。目录表中给每一项设置一个有效位，用于指出Cache中的块是否包含有效信息。
候选位置：一个主存块可能映像到Cache中的一个或多个Cache块位置。
当CPU访问主存块时，必须且只需查找它的候选位置的tag，如果tag匹配且有效项为1，则为要找的块。为了保证速度，对各候选位置的检查应该并行进行。
原理上先进行“主存到Cache”地址变换，得到Cache地址后再去访问Cache存储体，而且对于全相联必须如此，但实际上，在采用直接映像或组相联映像的情况下，为了提高访问速度，把==“主存到Cache”地址变换和访问Cache存储体安排成同时进行。同时，不知道哪个位置上有所要访问的数据，所以要把所有候选位置中的相应信息都读出来==，在“主存到Cache”地址变换完成后，再根据其结果从这些信息中选一个，发送给CPU。
实现并行查找的方法：用相联存储器实现；用单体多字的按地址访问的存储器和比较器来实现
相联存储器是一种按照内容访问的存储器。

单体多字节存储器是一次能够取出多个存储字的存储器。

所需硬件：大小为2^gxnxh位的存储器和n个h位的比较器。相联度n增加，比较器的个数和位数都会增加。
无论是直接映像还是组映像，查找时只需要比较tag，index无须参加比较：因为索引已被用来选择要查找的组（或块），而所有index相同且只有index相同的块才被映像到该组中。

2.4 Cache的工作过程

在这里插入图片描述
【分析】
容量是8KB的Cache
块大小 32B ：块内偏移 5 位
（写缓冲器和相联度无关，而且题目中已经告知是直接映像）~~写缓冲器大小是 4 个块：（4-路组相联）组内偏移 2 位~~
共有 256 个块：索引 8 位
tag = 34-5-8=21位
在这里插入图片描述
写缓冲器的介绍：
为了提高写访问的速度，才设置了一个写缓冲器。这个写缓冲器是按字寻址的，含有4个块，每块大小4个字。当要进行写入操作时，如果写缓冲器不满，那么就把数据和完整的地址写入缓冲器。对CPU而言，本次写访问已经完成，CPU可以继续往下执行，由写缓冲器负责把该数据写入主存。
⚠️在写入缓冲器时，要进行写合并检查。即检查本次写入数据的地址是否与缓冲期内某个有效块的地址匹配。如果匹配，就把新数据与该块合并。

由于21064的数据Cache是直接映像的，所以当发生调块时必然引起替换，因为该Cache使用写直达法，所以替换时不必把被替换块写回主存。当发生不命中时，21064将使数据绕过Cache，直接写入主存。
在这里插入图片描述

Cache相关问题的解题方法：

整个内存数据块大小，确认主存地址位数，即CPU发送过来的地址位数
然后根据每块大小和组数，确认块内偏移和索引
目录项中第一位为有效位，剩余位为标识。有多少个取决于组数（每组设1个，所以换索引即直接对应同组位置一样的地址）
同时去存储数据的地方找数据
进行标识比对（相联存储器、单字多节的按地址访问的存储器和比较器）

some ideas：

写缓冲器就类似于在输出和外设之间的输出井，CPU只需要关注把数据输出就可以去做其他的事情了，而后续的数据选择输出都不需要CPU关注，这样可以节省时间，提升访问速度，缓冲CPU和设备之间速度不匹配的问题
写入时，都进行一个检查，涉及到写操作、替换操作都可以进行一个和当前合并内容是否有相同的部分进行比较。

2.5 替换算法

数据块调入内存时发生冲突，需要将Cache中的块替换出，尽量避免替换掉马上就要用到的信息。

2.5.1 替换算法

1. 随机法

随机选择被调出的块，不能正确的反应程序的局部性

2. 先进先出法

最早调入最先被替换，不能正确的反应程序的局部性。

3. 最近最少使用法（LRU）

本来是选择近期使用次数最少的块作为被替换的块，但实际上是只选择最久没有被访问的块。能较好地反应程序的局部性原理，命中率在三种策略中最高，硬件实现成本较高。

2.5.2 LRU算法的硬件实现

1. 堆栈法

基本思想：使用一个堆栈来记录相联Cache的同一组中各块被访问的先后次序（这个先后次序是用堆栈元素的物理位置来反映的，从栈底到栈顶的先后顺序一起记录了该组中各块被访问的先后次序）
所需硬件：每组设置一个项数与相联度相同的小堆栈（每一项位数：log₂n位）；对硬件堆栈的要求——相联比较、能全部下移、部分下移、从中间取出一项；只适用于相联度较小的LRU算法。

2. 比较对法

不用相邻比较，仅仅使用一般的门、触发器来实现LRU替换算法。

基本思路：让各块两两组合，构成比较对。每一个比较对用一个触发器的状态来表示它所相关的两个块最近一次被访问的远近次序，再经过门电路就可找到LRU块。
T_AB：表示A比B更近被访问过
硬件：多少个块就需要多少个门；每个门的输入端要连接所有与之相关的触发器

当组内块数较多时，可以使用多级状态位技术来减少所需的硬件量：

2.6 写策略

在这里插入图片描述

2.7 Cache性能分析

两个重要公式：

平均访存时间＝命中时间＋不命中率×不命中开销
两个组成部分既可以使用绝对时间也可以使用时钟周期数来衡量。执行一个程序所需的CPU时间能更好地反应存储系统的性能。
CPU时间＝（CPU执行周期数+访存次数×不命中率×不命中开销）× 时钟周期时间
其中，不命中开销是指不命中、访存所需要的周期数。

⚠️在计算最终的性能时，要把所有的存储器停顿都考虑进去，

问题：Cache命中所用的时钟周期数（⚠️是命中所用，还未命中到命中的时间）被看作是CPU执行的时钟周期数的一部分还是存储器停顿时钟周期数的一部分。两种说法都合理，但是广泛使用的是第一种。

CPI_execution越低，代表执行部分占比越小，不命中部分占比越大，相对影响越大。

2.8 改进Cache性能

Cache的作用是弥补主存在速度上的不足，因此Cache的性能重点关注的是它对访存时间的提升。【在提升和改进某个部件的性能时要考虑这个部件存在的意义是什么，这个部件有什么作用，再去考虑如何提升性能】

平均访存时间=命中时间+不命中率x不命中时间
所以可以从三个方面来改进Cache的性能：降低不命中率、减少不命中开销、减少命中时间

3. 降低Cache不命中率（8‘）

3.1 三种类型的不命中

在这里插入图片描述

3.2 增加Cache块的大小

问题1：不命中率为什么会降低？
首次访问，Cache是空的，所以发生强制失效。发生失效只有要从主存调入一块。块越大，调入的字节越多，下次访存的时候不失效的可能性就越大。所以强制性不命中率降低。

问题2：不命中率为什么后来又升高了？
块大了，块数少了。所以带来强制性不命中降低的同时，带来了冲突不命中的增加。两者共同作用，导致总的不命中率增加。看来，块大小设置多大，是需要好好设置一下的。

问题3：增加块大小，会不会对其他性能参数有影响？
当然有影响，块大了，调块的时间长，所以会增加不命中的开销。
在这里插入图片描述

3.3 增加Cache的容量

在这里插入图片描述

3.4 提高相联度

2条经验规则：

采用相联度超过8的方案的实际意义不大
2:1Cache经验规则——容量为N的直接映像Cache的不命中率和容量为N/2的两路组相联Cache的不命中率差不多相同。

3.5 伪相联Cache

又称列相联，既能获得多路组相联的低不命中率又能保持直接映像Cache的命中速度。
基本思想：首先按与直接映像相同的方式访问，如果命中直接给CPU；如果不命中，检查将索引字段的最高位取反的位置去寻找另一个位置（块），如果这一块的标识匹配，称发生伪命中。
伪相联Cache有两种访问时间，分别对应于正常命中和伪命中。要能够指出在同一组的两个块中访问哪个块才更可能是快速命中。解决方法：当出现伪命中时交换两个块的内容，把最近刚访问过的块放到第一位置（直接映像所对应的块上）【因为局部性原理，刚访问过的块很可能就是下一次要访问的块】

多种命中时间会使CPU流水线的设计复杂化，因此伪相联技术往往是应用于离处理器较远的Cache上，例如第二级Cache。

3.6 硬件预取

指令和数据都可以在处理器提出访问请求之前进行预取
预取内容可以直接放入Cache，也可以放在一个访问速度比主存快的外部缓冲器中
指令预取通常由Cache之外的硬件完成
预取建立在利用存储器的空闲带宽（若不采用预取，这些带宽将浪费掉）的基础上，但是如果它影响了对正常不命中的处理，就可能会降低性能
利用编译器的支持可以减少不必要的预取

3.7 编译器控制的预取

在这里插入图片描述

非阻塞Cache：只有在预取数据的同时处理器还能继续执行的情况下，预取才有意义。要求Cache在等待预取数据返回的同时，还能继续提供指令和数据。
编译器控制预取的目的也是要使执行指令和读取数据能重叠执行。循环是预取指令的主要对象。
每次预取指令需要花费一条指令的开销，因此要保证这种开销不超过预取所带来的收益。编译器可以通过把重点放在那些可能会导致不命中的访问上，使程序避免不必要的预取，从而较大程度地减少平均访存时间。

3.8 编译优化

通过软件的方法进行优化来降低不命中率，这种方法的特色是无须对硬件做任何改动。分为减少指令不命中和减少数据不命中两个方面。

3.8.1 程序代码和数据重组

重新组织程序而不影响程序的正确性很容易。
书中简介两种：
a. 把一个程序中的过程重新排序，就可能会减少冲突不命中，从而降低不命中率
b. 为了提高大Cache块的效率，把基本块堆砌，使得程序的入口点与Cache块的起始位置对齐就可以减少顺序代码执行所发生的Cache不命中的可能性
如果知道分支指令很可能成功转移，可以通过以下两点改善空间局部性：
数据对存储位置的限制更少，便于调整顺序。目的是改善空间局部性和时间局部性。
编译优化技术包括数组合并、内外循环交换、循环融合、分块等。数组合并是将本来相互独立的多个数组合并成一个复合数组，以提高它们的局部性。循环融合是将若干个独立的循环融合为单个的循环，这些学换访问同样的数组，对相同的数据作不同的运算，这样能使读入Cache的数据在被替换出去之前得到反复使用。

3.8.2 内外循环交换

在这里插入图片描述

3.8.3 分块

在这里插入图片描述

3.9 牺牲Cache

定义：在Cache和其下一级存储器的数据通路上增设一个全相联的小Cache，称为“牺牲Cache”，其中存放因冲突而被替换出去的那些块。
基本思想：当发生不命中时，在访问下一级存储器之前，先检查“牺牲cache”中是否有所需的快，如果有直接和Cache中的块进行交换。
采用命中率较高的全相联映像，而且仅在替换时发生作用。（而且从降低不命中率的角度单独看牺牲Cache，采用全相联也是不命中率最低的）
这里把该方法归为减少不命中率的方法。因为把“牺牲Cache”看成是Cache的向下扩展，在“牺牲Cache“上命中也算命中。但是归到减少不命中开销的方法也是可以的，站在”Cache和牺牲Cache之间看问题”。前面的伪相联和预取也是。

4. 减少Cache不命中开销（5‘）

4.1 采用两级Cache（采用比较多的方法）

在CPU和主存之间增加Cache的原因就是弥补主存与CPU的速度差异。那为什么不把Cache做的很大呢？原因很简单，太贵，而且CPU直接访问的Cache一般是在CPU片上，占用CPU的芯片面积。那么为了进一步弥补主存和Cache速度上的差异，一般的处理器都使用多级Cache，有片上的，也有片下的。
两级Cache的平均访问时间分析

对于二级Cache有以下结论：

在第二级Cache比第一级Cache之间的首要区别是：第一级Cache的速度会影响CPU的是时钟频率，而第二级Cache的速度只影响第一级Cache的不命中开销。（许多不适合第一级的设计方案可能适合第二级）
设计第二级Cache只有两个问题需要权衡：能否降低CPI中的平均访存时间部分；成本是多少
在第二级Cache比第一级Cache大的多的情况下，两级Cache的全局不命中率的容量与第二集Cache相同的单级Cache的不命中率非常接近。
可以使用上一节的技术来减少第二级Cache的不命中率，从而达到减少不命中开销的目的（提高相联度和伪相联的方法都值得考虑）
采用增加块大小的方法来减少不命中率。由于前面有结论：Cache块增加到一定程度后反而可能导致不命中率上升。但是对于第二级Cache来说，容量大，使不命中率达到最低的块的大小也比较大。
多级包容性：如果第一级的数据总是同时存在于第二级Cache中，则称第二级Cache有多级包容性。（有利于I/O于Cache之间内容一致性的检测）
为了减少平均访存时间，让容量较小的第一级采用较小的块，而让容量较大的第二级Cache采用较大的块。仍可实现包容性，但是在处理第二级Cache不命中时要做更多的工作：替换第二级Cache中的块时，必须作废所有对应于该块的第一级Cache中的块。
10.

4.2 让读不命中优先于写

设置一个大小适中的写缓冲器

读不命中，需要访存时，可能存储器还未更新，要读的内容还在写缓冲区中，若推迟访问，直到写缓冲的数据都写入主存，会增加命中时间。
不等写缓冲器清空，直接在写缓冲区的数据里面找是否有需哟啊的数据

4.3 写缓冲合并

写缓冲合并：为了减少写访问所花的时间，写直达Cache一般都采用一个写缓冲器。如果该缓冲器不满，就可以把数据和相应地址写入该缓冲器。从CPU的角度来看，这个写操作就算完成了。CPU可以继续执行后面的指令，而写缓冲器继续负责将之写入存储器。在写缓冲器不为空的情况下，则需要把这次的写入地址与写缓冲器中已有的所有地址进行比较，看是否有匹配的项。如果有地址匹配而对应的位置又是空闲的，就把这次要写入的数据与该项合并。

写缓冲区有四项，每项四个64位的字。
如果一次写操作，不合并，每次写操作使用缓冲区一项，使用了一个64位的字。四个字就得用四项，启动四次写主存操作。
如果写缓冲合并，最好的情况下，四个字地址是连续的，写入了写缓冲区一项中。也就是启动一次写操作，连续写了4个字，节省了很多时间。也就是节省了写不命中的开销。

4.4 请求字处理技术（不用增加硬件）

请求字：当从存储器向CPU调入一块时，块中往往只有一个字时CPU立即需要的，这个字称为请求字【请求字到达后，不等整个块都调入Cache，就可以把该字发送给CPU并重启CPU继续执行】

4.5 非阻塞Cache技术

采用尽早重启动技术时，在请求字到达之前，CPU还是要处于等待状态。有些流水方式的计算机采用==记分牌或Tomasulo类控制方法，允许指令乱序执行（后面的指令可以跨越前面的指令先执行），CPU无须在Cache不命中时停顿。
不命中发生后，CPU在等待数据Cache给出数据的同时，有可能继续执行后面的指令，如果采用非阻塞Cache或非锁定Cache技术，则可以将CPU性能提高更多。（不命中时不完全拒绝CPU的访问，而是能处理部分访问，从而减少了实际不命中的开销。
支持多重不命中下的命中和不命中下的不命中，则可进一步减少实际不命中开销。
但是不是可以同时处理的不命中次数越多越好，对于整数程序来说，重叠次数对性能提高影响不大，简单的一次不命中下命中就几乎可以得到所有好处。

5. 减少命中时间

5.1 容量小、结构简单的Cache

硬件越简单，速度就越快
应使Cache容量足够小，以便可以与处理器做在同一芯片上
折中方案：把Cache的标识放在片内，而把Cache的数据存储体放在片外，这样既可以实现快速标识检测，又能利用独立的存储芯片来提供更大的容量。
还要保持Cache结构的简单性，例如采用直接映像

5.2 虚拟Cache

一般由存储管理部分MMU完成，按照访问地址是物理地址还是虚拟地址，把Cache分成物理Cache和虚拟Cache。

5.2.1 物理Cache

物理Cache：使用物理地址进行访问传统的Cache，其标识存储器中存放的是物理地址，进行地址检测也是用的物理地址。

5.2.2 虚拟Cache

虚拟Cache：可以直接用虚拟地址进行访问的Cache，其标识存储器中存放的是虚拟地址，进行地址检测用的也是虚拟地址。
优点：在命中时不需要地址转换，节省了地址转换的时间，不命中时地址转换和访问Cache时并行进行的，速度比物理Cache快很多。
并非所有计算机都采用虚拟Cache的原因：每当进行进程切换时需要清空Cache，由于新进程的虚拟地址可能与原进程的相同，但它们所指向的物理空间确是不同的。
解决方法：增加一个进程标识符字段（PID），这样多个进程的数据可以混放在Cache中，由PID指出Cache中的各块是属于哪个程序的，PID经常是由操作系统指定。【对于每一个进程，操作系统从循环使用的几个数字中指定一个作为其PID】不过，这种方法有时也需要清空Cache，这种情况仅发生在当某个进程的PID被重用的时候，即该PID以前已被分配给了某个进程，现在又把它分配给另外一个进程的时候。
虚拟Cache没有流行起来的另一个原因？
操作系统和用户程序对同一个物理地址可能采用两种以上不同形式的虚拟地址来访问，这些地址称为同义或别名。它们可能会导致同一个数据在虚拟Cache中存在两个副本。而这是不允许的，否则会发生错误，这种情况在物理Cache中不会发生，因为物理Cache会首先把虚拟地址转换到同一物理地址，从而找到同一个物理Cache块。
用软件的方法解决alias很容易，只要要求alias相同的某些地址位相同。
对于虚拟地址，最后还应该考虑I/O。I/O通常使用物理地址，所以为了与虚拟Cache打交道，需要把物理地址映像为虚拟地址。

5.2.3 虚拟索引-物理标识方法

直接用虚地址中的页内位移，作为访问Cache的索引，但标识却是物理地址。
局限性：直接映像Cache的容量不能超过页面大小。
为了既能实现大容量Cache，又能使索引位数比较少，可以采用提高相联度的方法：
在这里插入图片描述
另一种方法：硬件散列变换

5.3 Cache访问流水化

把对第一级Cache的访问按流水方式组织，使得访问Cache需要多个时钟周期才能完成。实际上它并不能真正减少Cache的命中时间，但可以提高访问Cache的带宽。

5.4 踪迹Cache

开发指令级并行性所遇到的一个挑战：当要每个时钟周期流出超过4条指令时，要提供足够多条彼此互不相关的指令是很困难的。
解决方法：踪迹Cache，存放的是CPU所执行过的动态指令序列，其中包含了由分支预测展开了的指令，该分支预测是否正确要在取到该分支指令时进行确认。
在这里插入图片描述

5.5 Cache优化技术总结

在这里插入图片描述

6. 并行主存系统

主存的性能主要由带宽和延迟来衡量。
延迟：存储器的访问时间，也就是启动1次存储器操作到完成该操作时所需要的时间
带宽：单位时间内存储器存取的信息量
以往Cache主要关心的是主存的延迟（影响Cache的不命中开销），而I/O主要关心的是主存的带宽。随着第二级Cache的广泛使用，主存带宽对于Cache来说也重要，因为第二级Cache的块比较大。实际上，Cache可以通过增加Cache块的大小来利用主存带宽的增加，因为==在高带宽的情况下，块大小增大并不会使不命中开销增加多少。
并行存储系统：在一个访存周期内能并行访问多个存储字的存储器，它能有效地提高存储器的带宽。
在这里插入图片描述

在相同器件条件下（T_M相同），如果要提高主存的带宽，可以采用以下两种并行存储器结构：单体多字存储器和多体交叉存储器。