系统结构第七章 | 存储系统

1.  人们对存储系统往往希望容量大、速度快、价格低，但是很遗憾这三点通常是矛盾的，于是采用的解决方案是采用多种存储器技术，构成多级的存储层次结构。由程序访问的局部性原理，程序所访问的指令和数据在地址上往往是相对聚簇的。
   

2. 越靠近CPU访问速度越快，容量越小，每位价格越高。

3. 性能参数：

   （仅考虑两级存储器）

   

   存储容量S=S2，一般来说，整个存储系统的容量即是第二级存储器M2的容量。

   每位价格C=(C1*S1+C2*S2)/(S1+S2);当S1<<S2时，C≈C2

   命中率（对M1而言）H=N1/(N1+N2) Nx为访问Mx的次数。

   不命中率=1-H;

   平均访存时间=HT1+(1-H)(T1+T2)

4. cache-主存层次弥补了主存速度的不足，主存-辅存层次弥补了主存容量的不足。

   

5. 映像规则，全相联映像（放哪都行，空间利用率最高冲突概率最低实现最复杂）、直接映像（只能固定放在一个地方，空间利用率最低冲突概率最高实现最简单，通过一个取模换算关系就能确定）、组相联映像（主存中的每一块可以放置到Cache中一个组的任意位置，直接映像到组，组内全相联（用低g位用于选组），每组中的块数称为相联度，相联度n=总块数M/组数G。

6. 查找算法，CPU访问cache时如何确定cache中是否有要访问的块，如果有如何确定其位置？通过目录表，目录表中记录了当前cache块中存放了哪个主存块，主存块地址的高位部分称为标识，标识加上cache块地址就是主存块地址。目录表存放于标识存储器中，每一项设置一个有效位指出cache中的块是否包含有效信息，当一个主存块调入cache中某个位置时，其标识被填入目录表中与cache块相对应的项中，置有效位为1。当cpu访问主存块时只需查找候选位置所对应的目录表项，如有标识匹配且有效位为1，则它所对应的cache块即是所要找的块，对候选项的标识检查应并行进行。假设cache能存放M块，则全相联映像候选位置有M个，直接映像候选位置有1个，n路组相联候选位置有n个。

   

   先选组，再选路。

7. Cache的容量=2^索引位数*相联度*块大小。

8. 替换算法：直接映像不需要算法，在组相联和全相联cache中，需要设计算法尽可能避免替换掉马上就要用到的信息。a.随机法：随机选择被替换的块，优点是简单，缺点是没有考虑cache块使用情况，反映不出程序的局部性原理，命中率低。b.FIFO法，优点是容易实现，缺点是最先进入的也有可能最近使用。c.LRU最近最少使用法，选择近期最少被访问的块作替换，优点是反映了程序局部性原理所以命中率较高，缺点是复杂，硬件实现成本高。LRU和随机法分别因为命中率较高和容易实现而被广泛采用，模拟数据表明，对于容量很大的Cache，LRU和随机法的命中率差别不大。

9. LRU可以使用堆栈法实现，将最近访问的压入栈顶，未命中替换栈底同时压入栈顶。需要为每一组都设置一个小堆栈，每一项的位数为log2(n)，n为相联度，而且这个堆栈要能够相联比较，能全部下移、部分下移取出中间项，实际上不是算法中狭义的堆栈。速度较低成本较高。

10. LRU也可以使用比较对法实现，假设有abc三个块，可以组成ab、ac、bc三对，每一对中块的访问次序用“对触发器”Tab，Tac，Tbc表示，如果为1表示前面一个比后面一个最近被访问，为0反之，显然当Tac、Tbc都为1时，c就是最久没有被访问过的了，C=Tac*Tbc，A=~Tab*~Tac，B=Tab*~Tbc（在前面就取反在后面就不变），使用如下电路图就可以实现：

    

    然后我们可以计算一下所需的硬件数量，对于与门，每块就需要一个，但是对于触发器，是一个排列组合问题：

    

    在块数少时，比较对法比堆栈法容易实现但随着块数的增加，所需触发器会以平方关系增加，导致硬件实现的成本很高。

11. 写策略。

    

    写操作必须在确认是命中后才可以写入cache，写访问有可能导致cache和主存内容的不一致，为了保证正确性，主存内容也必须更新，于是什么时候写回去就存在两种写策略。

    a.写直达

    执行写操作时不仅写入cache也写入下一级存储器，保证下一级存储器中的数据都是最新的。

    采用写直达法时，若在进行写操作的过程中，CPU必须等待，直到写操作结束，称为CPU写停顿，可以采用写缓冲器来减少写停顿，CPU只需要把数据写入写缓冲器就可以去看别的事儿了，将下一级缓冲器的更新和CPU的执行重叠起来。

    优点：易于实现，一致性好

    b.写回法

    执行写操作时只写入cache，不写入下一级存储器。有些数据的最新版本在cache中，仅当cache中相应的块被替换才写回主存。

    需要设置一个修改位，如果没修改过可以不必写回，尽可能减少存储器访问。

    优点：速度快，使用的存储器带宽较低

12. 当发生写不命中时，是否需要调入相应的块？如果需要调入相应的块则为按写分配，不需要调入直接写入下一级存储器为不按写分配，写回法——按写分配，写直达法——不按写分配。

13. CPU时间=（CPU执行周期数+存储器停顿周期数）*时钟周期时间

14. 存储器停顿周期数=读的次数*读不命中率*读不命中开销+写的次数*写不命中率*写不命中开销=访存次数*平均不命中率*平均不命中开销

15. p205、p206例题，206中需要注意题目中限制了两种结构cache的不命中开销都是70ns，那么告诉我们不命中开销（单位为指令数）*时钟周期时间已经是70ns了，不能把1.1乘在外面。

16. 下面将围绕改进cache性能展开，可以从三个方面17种方法改进cache的性能，分别为降低不命中率8种，减少不命中开销5种，减少cache命中时间4种继续讨论。

降低不命中率

首先介绍三种类型的不命中。

a.强制性不命中

当第一次访问一个块时，该块不在cache中，需要调块，这就是强制性不命中，也称冷启动不命中或首次访问不命中。

b.容量不命中

如果程序执行时所需的块不能全部调入cache中，则当某些块被替换后，若又重新访问就会发生容量不命中。
c.冲突不命中

在组相联或直接映像cache中（全相联不存在该不命中，但是全相联的硬件成本昂贵），若太多的块映像到同一组（块）中，则会出现该组中某个块被别的块替换，然后又被重新访问，就是发生了冲突不命中。（被替换后再访问），也称碰撞不命中或干扰不命中。

上图中橙色为强制性不命中是任何cache结构共有的，粉色为全相联模式下的不命中率，由于全相联模式下不存在冲突不命中，所以全部为容量不命中，粉色之上部分则为各个结构cache的冲突不命中，可以观察出，相联度越低，冲突更易发生，冲突不命中率越高。

要减少强制性不命中，可以通过增加块大小（也就减少了块数目，每个块也就那么一次，就能减少）、预取。

要减少容量不命中可以增加容量（废话）。

要减少冲突不命中可以提高相联度（理想情况是全相联，因为冲突最少）

毕竟世界上很少能有两全其美的东西，许多降低不命中率的方法可能会增加命中时间或不命中开销。

这是在实验中曾经得出的结论，可以通过适度的想象分析，如果块大小适度增大，那确实有利于降低不命中率，由程序的局部性原理，但是如果块一直增大，那么能放的块数减少，由于程序也不是完全的局部性，就会起反作用。

降低cache不命中率的最直接方法就是增加cache容量，你有本事把cache搞得和主存一样大那就不存在不命中的问题了，只不过很显然，这会带来高昂的成本同时增加命中时间（相联比较的位数增加了）。

提高相联度也可以降低不命中率。采用8路以上相联的实际意义不大在降低组相联上与全相联一样。存在一个2:1 cache经验规则（容量为n的直接映像cache的不命中率与容量为n/2的2路组相联cache差不多）。但是提高相联度是以增加命中时间为代价的，因为比较的逻辑更加复杂了。

采用伪相联，伪相联结合了多路组相联的低不命中率和直接映像的命中速度优势，伪相联可以看作特殊的二路组相联，它通过索引最高位进行分割，首先将索引按照直接相联的方式去匹配标识，如果成功匹配，则与直接匹配完全相同，若未成功匹配，则将最高位取反再次匹配，如果还没有匹配才去寻找下一级存储器。

这样显然在第一次匹配时具有较高的速度，同时由于存在两次匹配的机会，不命中率相较于直接匹配也会降低，不过如果有某一种情况，在第二次匹配到的机会更多，那么，可能伪相联就还不如直接映像，但是可以优化，当每一次在第二次匹配到时，我们就将一二次块中的内容进行互换，这样下一次就能快速命中。

缺点也很明显，多种命中时间使得CPU流水线设计复杂化，这种设计常常运用于离处理器较远的cache上，如二级cache。

硬件预取，编译器控制的预取，预取可以预先将指令和数据取入快速存储器，所以可以减少cache的不命中率，但是设计预取时有一个前提是不能影响程序的正常工作，在预取数据的同时，处理器应能继续进行或者硬件应该占用空闲的带宽，否则反而可能做了无用功降低效率。

编译器进行优化，通过对软件进行优化来降低不命中率，这种方法不需要对硬件进行改动，编译器可以通过重新组织程序却不影响程序的正确性的方式，对一个程序中的过程重新排序，减少冲突发生。

如果编译器在编译时能够知道一个分支很可能会成功转移，那么它就可以通过将转移目标处的基本块紧跟着分支指令后的基本块，以提高空间局部性，或者直接修改分支条件取反再进行安排，从而使得跳转较小发生，程序顺序进行。

对数组的运算可以转移到同一cache块中，从而降低不命中率。

编译优化可以进行数组合并、循环融合、内外循环交换（提高空间局部性）、分块等来降低cache的不命中率。

牺牲cache，在cache和它从下一级存储器调数据的通路之间设置一个全相联的小cache，用于存放因冲突而被替换出去的块，以备重用，发生不命中时先不急着调下一级存储器而是看看牺牲cache里面有没有所需块，如果有就将牺牲cache中的内容根据替换规则与cache交换后使用，就像是“回收站”，其实某种意义上也是扩大了cache的容量。

总结：以上提到的通过降低cache不命中率优化cache的方法有：

增大块大小（但不能一直增大）、增大cache容量、（硬件、编译器）预取、编译器优化、提高相联度、采用伪相联、采用牺牲cache。

减少cache不命中开销

采用两级cache，采用两级cache主要是考虑到应该把cache做大还是做快这一冲突，想要尽可能的把cache做得又大又快，所以把第一级cache做得小而快，第二级cache做得大以捕获更多访问，平均访存时间可以通过条件概率进行计算=命中一级缓存的时间+不命中一级缓存的概率*（命中二级缓存的时间+不命中二级缓存的概率*不命中二级缓存的开销）

不命中率可以通过概率学的公式计算，局部不命中率=该级cache不命中次数/到达该级的访问次数，全局的不命中率=该级cache的不命中次数/cpu发出的访存总次数=一级不命中率*二级不命中率，在评价第二级cache应该使用全局不命中率，它表示有多大比例是穿过了前面的cache到达二级后还不命中的，比较有道理。注意，在计算cache的开销的时候，命中的时间不需要乘命中率，因为无论命不命中，时间都是需要消耗的。

平均停顿时间也等于平均访存时间-访问第一层cache的命中时间。

第二级cache的容量往往比第一级cache大许多，也就意味着第二级cache可能实际上就没有容量不命中，只剩下强制性不命中和冲突不命中，减少第二级cache的不命中率可以使得第一级cache的不命中开销减少从而使得整体的访存时间减少，第一级cache可能会对CPU的时钟频率产生影响。

在计算时钟周期的问题时，如果时钟周期存在小数，往往需要将时钟周期进行取整。因为时钟周期一定是一个整型单位的。

两级cache的设计本质就是要快速命中、减少不命中次数（第二级）

让读不命中优先于写

在写直达cache中为了提升写性能，需要添加一个写缓冲器，而cache中的写缓冲器导致对存储器访问的复杂化，当发生读不命中时，所读单元可能不是最新的，有可能在写缓冲器中还没有写入主存。所以我们需要额外设计读不命中的处理。

最简单的方法是推迟对读不命中的处理，直到写缓冲器清空，但是这样会增加读不命中的开销；所以我们可以额外增加一道检查手续，检查写缓存器中的内容与我读不命中要调块的内容是不是有冲突（地址是不是相同）而且存储器是否可访问，如果各不影响，那么可以继续处理读不命中，而不一定在写之后，这就是让读不命中优先于写

在写回法的cache中，也可以采用增加一个写缓冲器来处理，原来是将脏块写入存储器后再从存储器读块，现在新增一个写缓冲器，将脏块临时复制到写缓冲器中（速度快于存储器操作），然后从存储器调块（1次存储器访问），之后再将脏块写入存储器，由写回法的特性，调入cache的块一定是最新的。

写缓冲合并

在写直达策略的cache中，依靠写缓冲减少了对下一级存储器写操作的时间，这里依旧有优化的空间，有的时候写缓冲还没有来得及写进去，又再写了，那就不需要两次访存，可以将修改合并为一次，这就是写缓冲合并的想法。CPU写入写缓冲后就完事了，那么CPU就只需要在写缓冲满而且写缓冲中没有当前写的东西（无法合并）的时候需要等待。

这个方式提高了写缓冲器的空间利用率，减少了因写缓冲满而等待的时间。

请求字处理技术

利用存储器向CPU调入一块时，块中只有请求字是CPU立即需要的其他字可以暂缓，从而更快促进CPU重启这一性质：

1）尽早重启动，当CPU收到请求字之后，就立即重启CPU，继续执行。

2）请求字优先，调块时，让存储器首先提供CPU所要求的请求字，请求字一旦到达立刻送CPU。

以上技术往往在cache很大时才有效，因为在cache较小时用不用这些技术命中率差别不大。但是，若下一条指令就需要访问数据，该方法只能节省一个时钟周期，因为下一条指令依旧需要数据才能正常进行。

非阻塞cache技术

cache不命中时依旧运行CPU进行其他的命中访问，也就是允许“不命中下的命中”存在，减少实际不命中的开销。在cache不命中时，不完全拒绝CPU的访问，能处理部分访问，从而减少实际不命中的开销。能让cache允许多个不命中重叠，提高效率。

总结：为了减少cache不命中开销，可以通过采用两级cache、让读不命中优先于写、写缓冲合并、请求字处理技术、非阻塞cache技术来实现。

减少命中时间

前述有提及，第一级cache的命中时间直接影响到处理器的时钟频率，而且在现代计算机中，cache的访问时间限制了处理器的时钟频率，所以减少命中时间是优化cache性能的一个重要方向。

采用容量小、结构简单的cache，这个方案实际上是废话，硬件越简单速度就越快，应该使得cache足够小，以便可以与CPU一起放在一块芯片内，减少片外访问开销，这一点非常重要，某些设计采用一种折中方案进行，将cache的标识部分放在片内，把cache的存储器放在片外，这样既可以快速识别标识，也能用独立存储芯片提供更大的容量。此外还需要保持cache结构的简单性，采用直接映像cache让标识检测和数据传送同时进行，有效减少命中时间。

虚拟cache，按照访问cache的地址是物理地址还是虚拟地址可以把cache细分为物理cache和虚拟cache，我们CPU在对存储器访问时，需要存在一个虚实地址的转换，虚地址总是需要先转换为实地址，才能进行访存操作。

这就导致了地址转换和访问cache是串行进行的，访问速度慢。那有没有可能直接用虚拟地址就能一步到位的访问cache呢，于是就引入了虚拟cache的概念。

虚拟cache也就是可以直接用虚拟地址进行访问的cache，标识存储器中存放的也是虚拟地址，在命中时无需地址转换，省去了地址转换的时间，即使不命中，地址转换和访问cache也是并行进行的，速度较物理cache快很多。

由操作系统的知识我们可以知道，虚拟地址是有可能相同的，但物理地址是唯一的，所以虚拟cache里面一定要能够分离开各个进程的虚拟地址（当然，最摆烂的解决方案是每次切换进程都清空cache），比较好的解决方案是在地址标识中增加一个PID进程标识符字段，然后虚拟地址们就可混合存放于cache中。由于PID也可能被重用，有时也需要清空cache。

以下为三个方案的比较（单进程无切换、用PID切换、清空切换）

可以发现PID方式还是相当优异的。

为了结合虚拟cache和物理cache的好处，人们继续发明了一种虚拟索引-物理标识的方法，兼得虚拟cache和物理cache的好处，直接使用虚地址中的页内位移（因为页内位移在进行虚实变换的时候保持不变）作为访问cache的索引和块内位移，但标识却是物理地址，这样在转换的时候就能并行读出标识，完成地址转换后把得到的物理地址与标识进行比较。

但这使得cache容量受到限制，因为直接映像cache的容量不能超过页面大小（索引+块内位移的长度小于或等于页内位移长度）。

cache访问流水化

对第一级cache的访问按照流水方式进行组织，访问cache需要多个时钟周期完成，这样可以提高时钟频率，但是并不能真正减少cache的命中时间，but可以提高访问cache的带宽。

踪迹cache

当每个时钟周期流出超过4条指令时，要提供足够多条彼此互不相关的指令是很困难的，采用踪迹cache存放CPU所执行过的动态指令序列，其中包含分支预测展开了的指令，由于指令流被动态保存，踪迹cache可以跳过一些不会执行的语句，因而可以提高它的空间利用率。

总结：为了减少命中时间，我们可以采用容量小结构简单的cache、使用虚拟cache、将cache访问流水化、使用踪迹cache。

大总结：Cache优化技术总结

增加块大小可以增大不命中率但是当不命中时拉入的东西变多会导致不命中开销增大，增加cache容量可以降低不命中率，提高相联度可以降低不命中率因为存放更加自由了但是会导致比较逻辑更复杂而使得命中时间增大，牺牲cache相当于增大了cache的容量所以它和增大cache容量是一样的，采用伪相联cache实质上相当于使用了2组相联，提高了相联度，同时命中时间分为快慢，快的和直接相联一样快，慢的要慢一些，所以通过交换快慢来尽可能保持程序的局部性，硬件预取指令和数据同样可以降低不命中率，实质上也像是增大了cache的容量，编译器控制的预取和硬件预取是类似的，需要采用非阻塞的cache才能起到较好的效果，使读不命中优先于写能够让读不命中发生时，更快的响应，写缓冲合并，是通过比较写缓冲器是否已有待写，将待写二合一，减少一次写操作同时尽可能利用了写缓冲器的容量，尽早重启动和请求字优先，通过提早向CPU返回请求字提前让CPU启动从而加快速度，但是如果下一条指令需要用数据，就还得等，非阻塞cache允许不命中下的命中存在，对不命中发生的时候不完全拒绝CPU响应，两级cache是为了使得第一级能更快第二级能更大，满足人们对快和大的要求，小而简单的cache可以大大减小命中时间但是由于cache变小了也会使得不命中率增大，对cache进行索引时无需转换使用了虚拟cache，减少了真实地址转换的步骤会提高响应速度，采用流水化的cache访问已经被广泛采用，因为采用这样的方法可以提高CPU的主频还可以提高cache的带宽，采用踪迹cache可以跳过不会使用到的代码部分，提高空间利用率。

虚拟存储器

虚拟存储器可以分为段式和页式两类，页式虚存把空间划分为大小相同的页，段式虚存把空间划分为可变长的块（段），段页式结合两者，把每段划分为若干个段，既保持了段作为逻辑单位的优点，又简化了替换的实现，段不必作为整体一次调入，可以以页面为单位调入。

虚拟地址通过页表映射为物理地址，结合偏移地址一起访问内存空间，由于页表很大放在主存中按页存储访问比较慢，所以又引入了地址变换缓冲器TLB存放近期经常使用的页表项，是页表的cache，TLB中的项由标识和数据构成，标识是虚地址的一部分，因为页表是按顺序存放的，所以不需要标识，但是TLB只有一部分就必须指出这是页表哪一行的内容，数据则是物理页的帧号有效位使用位修改位等信息。

为了使得TLB中的内容与页表保持一致，当修改页表中的某一项时，操作系统必须保证TLB中没有，否则需要把TLB中的页表项作废。

使用多级页表可以有效的缩小页表大小，首先从第一个字段和基址寄存器获得第一级页表基址再把下一级偏移量加到新基址上再次访存获得第二级页表基址，如此往复获取最后一次访存获取到物理页号再进行拼接得到完整的物理地址。

所有和cache有关的优化也可以类似的运用到TLB上，比如多级TLB。