第4章 指令级并行

4.1 指令级并行的概念

4.2 指令的动态调度

4.3 控制相关的动态解决技术

4.4 多指令流出技术

目录列出来了，却没复习完，只看了部分循环展开、记分牌和 Tomasulo 。

记分牌：

https://www.bilibili.com/video/BV1JM4y1f7UP/?spm_id_from=333.999.0.0&vd_source=e7300d5accad8932a257efb8871bb9ee

Tomasulo:

https://www.bilibili.com/video/BV1xe4y1c7AK/?spm_id_from=333.999.0.0&vd_source=e7300d5accad8932a257efb8871bb9ee

第5章 存储层次

在冯·诺依曼体系结构下，绝大多数程序访问的指令和数据是相对聚簇的，符合局部性原理。

这一本质特征使得 CPU 近期使用的程序和数据可放在离 CPU 较近的、容量小而速度快的存储器中来满足性能要求，而其他程序和数据可放在离 CPU 较远的、容量大而速度慢的存储器中来满足容量要求，从而构成多级存储层次。

5.1 存储器的层次结构

5.1.1 多级存储层次

多级存储层次的设计目标：从 CPU 来看，该存储系统的速度接近于 M1M_1 的速度，而容量和每位价格接近于 MnM_n 的容量和价格。

在存储层次中，每一层存储器中的数据一般都是其下一级（离 CPU 更远的一级）存储器中数据的子集。CPU 在访存时，首先是访问靠近它的那个存储层次，若找不到所要的数据，则访问其相邻的下级存储层次，若找到所要的数据，则则将包含所需数据的块或页面调入上级存储层次；若还找不到，则继续依次访问更下级的存储层次。

5.1.2 存储层次的性能参数

简单起见，考虑两级存储层次结构

存储器层次 容量 访问时间 每位价格
M1M_1 S1S_1 TA1T_{A1} C1C_1
M2M_2 S2S_2 TA2T_{A2} C2C_2

1. 存储层次的每位价格

C=C1S1+C2S2S1+S2C=\frac{C_1S_1+C_2S_2}{S_1+S_2}

为了让价格和容量接近 M2M_2 ，可以看到，S1≪S2S_1 \ll S_2 时，C≈C2C \approx C_2 。

2. 命中率 HH

执行一组有代表性的程序时，访问 M1M_1 和 M2M_2 的次数分别为 N1N_1 和 N2N_2 ，则

命中率 HH ：

H=N1N1+N2H = \frac{N_1}{N_1+N_2}

失效率 FF ：

F=1−HF = 1 - H

3. 平均访问时间 TAT_A

  • 访问 M1M_1 时命中，访问时间为 TAT_A
  • 访问 M1M_1 时未命中（TA1T_{A1}），需要访问 M2M_2 ，大部分情况下会命中（TA2T_{A2}），再将访问到的数据块从 M2M_2 整个调入 M1M_1 中（TBT_B）。所以不命中的访问时间是 TA1+TA2+TB=TA1+TMT_{A1}+T_{A2}+T_{B}=T_{A1}+T_{M} 。记 TM=TA2+TBT_M = T_{A2}+T_B 为失效开销（Miss Penalty）。

根据上述分析，平均访问时间如下：

TA=HTA1+(1−H)(TA1+TM)=TA1+(1−H)TM=TA1+FTMT_A = HT_{A1}+(1-H)(T_{A1}+T_M)=T_{A1} + (1-H)T_M = T_{A1}+FT_M

5.1.3 两种存储层次关系

  1. “Cache—主存”层次

    CPU 的性能增长速度比主存快，在 CPU 和主存之间增加一个高速缓冲存储器（Cache）来弥补主存速度的不足。

  2. “主存—辅存”层次

    在主存外面增加一个容量更大、每位价格更低，但速度更慢的存储器（称为辅存，一般是硬盘）。常被用来实现虚拟存储器，给程序员提供大量的程序空间。

5.1.4 存储层次的 4 个问题

  1. 映像规则： 当把一个块调入高一层存储器时，可以放到哪些位置上？
  2. 查找算法： 当所要访问的块在高一层存储器中时，如何找到该块？
  3. 替换算法： 当发生失效时，应替换哪一块?
  4. 写策略： 当进行写访问时，应进行哪些操作？

5.2 Cache 基本知识

Cache：现代计算机在 CPU 和主存之间设置的一个高速、小容量的缓冲存储器。

Cache 技术：被广泛用于指代利用缓冲技术来实现局部数据再利用的技术，例如，文件 Cache、踪迹 Cache 等。

本章中的 Cache 是其中的一种，专指 CPU 和主存之间的 Cache。

Cache 和主存之间信息的交互按块来组织。

Cache和主存均被分割成大小相同的块，信息以块为单位调入 Cache，块大小常为 2 的幂次方字节 。

Cache 由硬件寻址，对程序员是透明的（CPU 中给出的是主存地址）。

主存地址：

块地址 块内位移

5.2.1 映像规则

将一个块从主存中调入 Cache 时，首先要确定这个块可以放在 Cache 的哪个块位置上，映射方法主要有以下三种：

设块的数量为 MM

  1. 直接映像（Direct Mapping）

    主存块只能被放置到唯一的一个 Cache 块位置的方法。按取模的余数分配块的位置。

  2. 全相联映像（Fully Associative Mapping）

    主存块可以被放置到任意一个 Cache 块位置的方法。

  3. 组相联映像（Set Associative Mapping）

    Cache 被等分为若干组，每组由若干个块构成，主存块可以被放置到 Cache 中唯一的一个组中的任何一个位置的方法。按取模的余数分配组。

    如果组相联 Cache 中每组有 n 个块，则称该映像为 n 路组相联（n-way Set Associative）。直接映像实际上为 1 路组相联。全相联为 M 路组相联。

直接相联和组相联中采用循环分配方法使得相对簇聚的数据被分配到不同的 Cache 块（组）位置，相对其他对应关系，这种分配方法更符合局部性原理。

相联度越高（即 n 的值越大），Cache 空间的利用率就越高，块冲突就越低，因而 Cache 的失效率就越低。

块冲突： 一个主存块要进入已被占用的 Cache 块位置。

5.2.2 查找方法

tag index
唯一标识每个主存块 指定了主存块在 Cache 中的块号或组号（全相联索引位数为0，表示查找所有块的位置）

目录表： 无论采用哪种映像规则，多个主存块都可能映像到同一个 Cache 块的位置，目录表是用于区分当前某 Cache 位置保存的是哪一个主存块，记录唯一标识此主存块的信息的硬件结构。目录表中还会给每个 Cache 中的块设置一个有效位。

  • 直接映像 Cache

    主存块地址： |tag|%%%块索引（Index）|

    1）利用块索引找到这个位置对应的目录表项

    2）如果对应表项中的保存的标识与主存块 tag 相同

    3）且其有效位为 1 ，则该位置上的 Cache 块即是所要找的块

  • 组相联 Cache

    主存块地址： |tag%%%|组索引（Index）|

    1）利用组索引查找对应组的目录表项（标识）

    2）如果该组中有一个标识与所访问的主存块 tag 相同

    3）且其有效位为 1，则它对应的 Cache 块即是要找的块

  • 全相联 Cache

    主存块地址： |tag %%%%%%%%%%%%|

    由于主存块可能放在 Cache 的任意位置，所以 CPU 访问该主存块时

    1）该 tag 需要和 Cache 所有块对应的标识比较

    2）若有一个标识与所访问的主存块的 tag 相同

    3）且其有效位为 1 ，则它所对应的 Cache 块即是要找的块

下面是一个四路组相联查找的例子：

CPU 访存时，用主存块地址中的组索引 Index 从标识存储器中选取一行，并行读出 4 个标识，然后通过 4 个比较器将它们与主存块地址中的 tag 进行并行比较，如果有一个 tag 能够匹配且有效位为 1 ，则命中。

可以从上面的例子中看出，查找时只需要比较 tag ，如果 Cache 容量不变，提高相联度会增加每一组中的块数，从而减少 Index 的位数而增加 tag 的位数。tag 的位数变大， 当采用类似上图的并行比较方案时，所需比较器的个数和位数都会随之增大。

5.2.3 替换算法

当要调入的主存块的 Cache 块位置已被占用时，需要进行替换，直接映射只能在此位置上替换，而其他的映射方法还可以有别的选择，主要的替换算法有以下 4 种：

  1. 随机法

  2. 先进先出法（First In First Out, FIFO）

    用到了同一组中各块进入 Cache 的顺序这一”历史“信息

  3. 最近最少使用法（Least Recently Used, LRU）

    用到了数据局部性

  4. 最不常使用法（Least Frequently Used, LFU）

    既充分利用了历史信息，又反映了程序的局部性

LRU 和随机法分别因其失效率低或实现简单而被广泛采用。

5.2.4 写策略

优化读访问的常用方法是：访问 Cache 时，在读出标识进行比较的同时，可以把相应的 Cache 块也读出来

  • 命中：则把该块中的所请求得数据立即发送给 CPU
  • 失效：对所读出的块处理器置之不理

写和读不同，”写“一般比”读“要花费更多的时间，原因如下：

  • 由于检查标识符和写入 Cache 块不能并行进行，只有在读出标识并进行比较，确定命中后，才能对 Cache 块进行写入
  • 处理器要写入的数据宽度不是定长的（通常为1~8字节），写入时只能修改 Cache 块中相应的部分，而”读“可以多读几个字节也没关系，所以在实现时，写访问可能是”读—修改—写“的硬件操作，比较费时

被写的块不在 Cache 中（写失效）

1）按写分配（Write Allocate），又叫写时取（Fetch On Write）：先把所写单元所在的块调入 Cache ，然后再进行更新。这与读失效类似。

2）不按写分配（No Write Allocate），又叫绕写（Write Around）：直接写入下一级存储器而不将相应的块调入 Cache 。

待写的块在 Cache 中（命中或写失效时按写分配）

1）写直达法（Write Through）：不仅把信息写入 Cache 中相应的块，而且也写入下一级存储器中相应的块。

2）写回法（Write Back）：只把信息写入 Cache 中相应的块。该块只有在被替换时，才被写回下一级存储器，判断是否做了 Cache 中数据的修改，利用目录表中的”脏位“是否置 1 来判定。

例题：

写时取法和绕写法可与写直达法和写回法形成不同的组合：

采取写直达法时，若写操作过程中 CPU 必须等待该操作结束，则称 CPU 写停顿（Write Stall）。

减少写停顿时间的一种常用优化技术是采用写缓冲器（Write Buffer），写访问数据一旦写入该缓冲器，CPU 就可以继续执行，从而使下一级存储器的更新和 CPU 的执行重叠起来。

5.2.5 Cache 结构

5.2.6 性能分析

5.2.7 改进 Cache 性能

5.3 降低 Cache 失效率的方法

5.3.1 调节Cache块的大小

5.3.2 提高相联度

5.3.3 Victim Cache

5.3.4 硬件预取

5.3.5 编译器控制的预取

来不及了，看不完了。

5.3.6 编译器优化

来不及了，看不完了。

5.4 减少 Cache 失效开销的方法

来不及了，看不完了。

5.5 减少命中时间

来不及了，看不完了。

5.6 主存

5.7 虚拟存储器

这里我没学好，回头有机会重学一次。

ps：不知道什么时候才有机会，事实证明第一次就应该学好，人生很难给你第二次机会，每次都应该好好把握！

第6章 I/O

反思与感想

考完啦。心情并不激动，甚至有些担忧，希望没挂科。考的非常细节，第四章我只复习了循环展开（粗略）、记分牌和 Tomasulo ，但是还考了向量流水线和超长指令字，可以说完全不会，全部胡画了。这次期末在开学考，希望自己能吸取教训，重要的课学习时，一定要把每个知识点的逻辑都理解了，计算方法手推几遍。平时不努力注定考前面向考试突击，几乎一无所获。

怎么说呢，这门课算是草草了事，除了认真写了个单周期非流水 CPU 外，可能没学到太多，以后不知道有没有机会重学一次（千万别挂科，求求了）。

深表遗憾与惋惜。