计算机体系结构

Chapter 1：Introduction

1.1 Current computer

1. 什么是CA(Computer Architecture)

   1. 计算机架构是：选择和连接硬件组件以创建满足功能、性能、成本和功率目标的计算机的科学和艺术

   2. 它是计算机各个部分的需求和设计实现的蓝图和功能描述，主要关注中央处理单元（CPU）内部执行和访问内存地址的方式

   3. Tradeoff取舍

      

2. Computer Architecture包含了三个主要的方面

   1. ISA，七个维度如下：
      1. Class of ISA
      2. Memory addressing
      3. Addressing modes
      4. Types and sizes of operands
      5. Operations
      6. Control flow instructions
      7. Encoding an ISA
   2. Microarchitecture：也叫Computer organization，是对系统的较低层次、更具体和更详细的描述，涉及系统的组成部分如何互连以及它们如何互操作以实现ISA
   3. System Design：包括计算系统中所有其他硬件组件的系统设计，如：逻辑实现

   

3. 处理器芯片的发展趋势

   1. 工艺、主频遇到瓶颈后，开始通过增加核数的方式来提升性能；
   2. 芯片的物理尺寸有限制，不能无限制的增加；
   3. ARM的众核横向扩展空间优势明显

4. SoC：System of Chips，芯片上的系统

5. CPU发展的三个挑战

   1. ILP：指令集之间的并行
   2. Memory：内存到CPU之间的时间开销
   3. Power：功耗

6. Bandwidth和Latency

   1. Bandwidth带宽/throughput吞吐率：单位时间内能够完成的任务
   2. Latency延迟/response time反应时间：完成单个任务所需的时间
   3. 有时候不一定Latency降低，Bandwidth就提高了

7. 降低能耗：

   1. 休眠：在没有core运行时就休眠
   2. 动态调压：降低电压/频率
      1. 频率：开关晶体管的次数
   3. 为典型的情况做设计
   4. 超频Overlocking
   5. 尽快将所有的任务完成Race-to-halt

8. 功耗

   1. 动态功耗Dynamic power：由于开关晶体管导致的功耗
      1. \(Power_{dynamic}=\frac{1}{2}*电容负载*电压^2\)
      2. \(Energy_{dynamic}=电容负载*电压^2\)
   2. 静态功耗Static power：即便不导通，晶体管也会有电压泄露
      1. \(Power_{dynamic}=静态电流*电压\)
   3. 一般来说，电压降低10%，功率降低30%

1.2 Dependability(需要计算)

1. Availability：可用性，一定时间内有多长时间是可以正常工作的

   1. 也是某个时间，不可用的几率

   

2. Reliability：可靠性

   1. 指一个人或系统在日常环境以及敌对或意外环境中执行和维护其功能的能力
   2. IEEE将其定义为：“某个系统或组件在规定条件下，在规定时间内执行其所需功能的能力。”

3. Maintainability：可维护性

4. Dependability：可信性，所提供服务的质量，以便可以合理地依赖此服务

   1. MTTF：Mean Time To Failure，从开始工作到失效的平均时间
   2. MTTR：Mean Time To Repair，从失效到再次重新工作的平均时间
   3. MTBF：Mean Time Between Failure，两次失效之间的平均时间
      1. MTBF = MTTF + MTTR
   4. FIT：Failure In Time，失败出现的机会
      1. FIT = 1 / MTTF
   5. Module Availability：模块可用的时间
      1. \(\frac{MTTF}{MTTF+MTTR}=\frac{MTTF}{MTBF}\)

5. 已知每个部分的MTTF，求整个系统的MTTF：

   1. 求出各个部分的FIT_i = 1 / MTTF_i
   2. 求出整个系统的FIT = FIT₁+FIT₂+…+FIT_n
   3. 求出整个系统的MTTF = 1 / FIT

   

6. 应对failure：Redundancy冗余

   1. Time Redundancy：重复做一遍
   2. Resource Redundancy：用另一个部件替换坏掉的部件

1.3 测量/报告/总结 性能(需要计算)

1. 比较两个计算机的性能

   1. Execution time：计算的速度
   2. Throught：吞吐率
   3. MIPS：millions of instructions per second每秒多少百万条指令
   4. 使用Benchmark进行测量

2. Wall-clock Time：一个程序从开始到结束所需时间(包含中间停顿所需的时间)

3. CPU Time：一个程序实际在CPU上所需的时间

   1. User Time：在user mode下使用的时间
   2. System Time：在operating system中使用的时间

4. MIPS：每秒钟计算的多少百万条指令

   1. MIPS = benchmark中的指令数 / (benchmark运行的时间 * 1,000,000)
   2. 指令集中的每条指令，权重不一定一样，且已经包含在了benchmark中

5. Benchmark的种类

   1. Real applications：一个真实的程序
   2. Modified (or scripted) applications：对程序进行一些修改，关注于其中的一些点
   3. Kernels：程序的最主要的部分
   4. Toy：只关注一些部分
   5. Synthetic：创建来表示程序的某些方面

6. 计算A比B快多少：A所需的时间 / B所需的时间，得到一个>1的数字

   

Chapter 3：Memory hierarchy

3.1 Introduction

1. DRAM：Dynamic Random Access Memory

   1. 高密度、低功耗、便宜、速度慢
   2. 不能放在CPU里面，因为有电容，有充放电(交流信号 )，会影响CPU的计算
   3. Dynamic动态：需要定期“刷新”，刷新时不能进行读写

2. SRAM：Static Random Access Memory

   1. 低密度、高功率、昂贵、快速
   2. 唯一可以放在CPU里面的，因为没有电容
   3. Static静态：内容将“永远”保存（直到失去动力）

   

3.2 Cache

3.2.1 组相联计算

1. 4G：地址为32位
2. Cache 8K，Block-offset为5位：共2⁸个block
3. 2-way组相联：index= 8-1=7位

3.2.2 block的替换策略

只有在全关联/组关联的时候，会有替换策略

1. Random replacement：随机选择一个块替换

   1. 随机数的硬件实现：
      1. 设计一个专门的组件
      2. 用一根电线什么也不接，然后读取这个引脚的电压，理论上是白噪声，电压是随机分布的

2. LRU：选择最近最少访问的块替换

   1. 伪LRU算法(体系不考察LRU)

   

3. FIFO：选择第一个进入cache的块替换

3.2.3 写策略

1. write-through：同时修改cache和memory
   1. cache的控制位：valid bit
   2. 始终保证memory中的数据是最新的
   3. 通常会写入buffer，从而让cache不用等待memory
2. write-back：只修改cache，block被替换时写入memory
   1. cache的控制位：valid bit，dirty bit
   2. 带宽更小，因为重复访问时不需要写memory

选择write-through时，会有两种更新策略

1. write-stall：CPU等待write-through完成
2. write-buffer：写入buffer，CPU不用等待write-through完成
   1. buffer的大小不是无限的，buffer满时需要stall

miss时的写策略：(读策略肯定是将block放入cache)

1. write-allocate：将对应的block放入cache（通常是write-back对应的策略，write-through也可以用）
2. write-around：直接写memory，不取对应的cache（通常是write-through对应的策略）

3.2.4 数据和指令的cache是否分离

1. average miss rate = 指令占比% × 指令的miss rate + 数据占比% × 数据的miss rate

3.2.5 Supervisor cache / User cache

1. Supervisor 和 User 所要访问的空间肯定有很大的区别，可以将它们两个分别赋予一个cache
2. 指令cache
3. Supervisor / User Space Bit
   1. 1：Supervisor access only
   2. 0：Supervisor / User access

3.2.6 Cache Performance (计算)

3.2.6.1 CPU Time

1. CPU时间 = (CPU时钟周期 + Memory-Stall周期) × 一个周期的时间
2. Memory-Stall周期 = 指令数量IC × 平均每条指令访问内存的次数 × Miss-Rate × Miss惩罚

3.2.6.2 AMAT：平均内存访问时间

1. AMAT = 命中时间 + Miss率 × Miss惩罚

   ​ = (命中时间_指令 + Miss率_指令 × Miss惩罚_指令) + 命中时间_数据 + Miss率_数据 × Miss惩罚_数据)

3.2.6.3 Cache性能的测试指标

1. Miss Rate
   1. 与硬件的速度无关
2. Average Memory Access Time
   1. 是性能的间接表现
3. CPU time

3.2.6.4 示例

1. 例1：

   

2. 例2：

   1. 1 + 0.5：每条指令在取指令的时候都可能miss(1) + 这些指令中的50%是访问数据，也会miss(0.5)

   

   

3. 例3：

   

   

   

   

   

4. 例4：

   

   

   

5. 例5：

   

   

   

   

Chapter 4：How to improve memory performance

\[ AMAT = hit\_time + miss\_rate × miss\_penalty \]

1. 降低hit time
   1. 更小的一级cache，路径预测
   2. 避免地址转换，Trace cache
2. 增加bandwidth
   1. 流水线cache，multibanked cache，non-blocking caches
3. 降低miss penalty
   1. 多级cache
   2. 读miss优先于写miss
   3. Critical word first，merging write buffers，victim caches
4. 降低miss rate
   1. 更大的block size，更大的cache size，更高的关联度(2路组相联 => 4路组相联)
   2. 编译器优化
5. 通过并行，降低miss_penalty 或 miss_rate
   1. 硬件/编译器预取

4.1 降低hit time

4.1.1 小而简单的cache

使用小型，直接映射cache

1. 实现缓存所需的硬件越少，通过硬件的关键路径就越短
2. 无论是读还是写，直接映射都比组关联快
3. 将cache安装进CPU芯片上，也可以提高访问速度

一级cache和关联度对性能的影响

4.1.2 Way Prediction

1. 额外的位保存在缓存中以预测下一次缓存访问的方式或块
2. 如果预测是正确的，指令缓存延迟是1个时钟周期
3. 如果不是，它尝试另一个块，改变方式预测，并有一个额外的1个时钟周期的延迟
4. 使用SPEC95进行仿真表明，集预测精度超过85%，因此预测方式节省了流水线阶段85%以上的指令读取

4.1.3 在cache上做索引时避免Address Translation

1. 每个进程都有一个页表
2. 页表是内存中的一个巨大的数据结构
3. 每次load/store/instruction_fetch都需要2次内存访问
4. 解决方法：
   1. 方法1：如果cache中的index+offset均在页表中的page-offset中，那么可以先将页表中的page-offset送入cache进行搜索，然后再将MMU翻译出的tag送入cache进行比对
   2. 方法2：cache中的内容可以是虚地址，但是换进程/进内核的时候需要清空cache
   3. 方法3：对页表建立一个cache

4.1.3.1 TLB：Translation Lookat Buffer

1. 实际上就是将页表放入cache
2. TLB的大小通常是128~256个entry，通常使用全相联

Fast hits by Avoiding Address Translation

4.1.3.2 Virtual Cache

1. cache中的内容可以是虚地址
2. 但是换进程/进内核的时候需要清空cache，因为不同的进程使用的虚页号可能相同，但对应的物理地址是不同的地址

4.1.4 Trace Caches

1. 找到一个动态序列的指令，序列包含采取分支加载到缓存块

2. 由CPU而不是内存布局决定block的边界

   1. 例如有一个循环跨越了两个block，可以将这个循环访问到的数据放到trace cache中的一个block

3. 需要复杂的地址映射机制

4. 使用trace cache后，如果每个循环有N个指令

   1. 没有 I-cache miss
   2. 没有 prediction miss
   3. 没有 packet breaks

5. Trace：dynamic instruction sequence

   1. 当指令(操作)退出管道时，将指令段打包到trace中，并将它们存储在trace cache中，包括分支指令
   2. 虽然分支指令可能会去不同的目标，但大多数情况下，下一个操作顺序将与上一个顺序相同(locality)

6. 优点：引入一个额外的cache，可以突破block的边界

7. Trace in CPU：

   

8. Instruction segment：

   

4.2 增加bandwidth

4.2.1 Pipelined Cache

4.2.2 Nonblocking Caches

1. 一个Nonblocking(Lookup-free) Caches，允许cache在处理read miss时继续提供hit
   1. “Hit under miss” ， “Hit under multiple miss”
2. 复杂的cache甚至可能有多个未执行的miss(miss under miss)
3. Nonblocking与乱序执行相结合，可以让CPU在数据cache miss后继续执行之后的指令
   1. 之后的指令与当前指令不能有依赖关系

4.2.3 Multibanked Caches

1. 将cache分成几个独立的bank，它们可以同时被访问
2. 可以让多条指令同时进cache，但是WB阶段还是要排队
3. 需要编译器的支持，实现对内存的交错访问

4.3 降低miss penalty

4.3.1 Multilevel Caches

1. 一级cache较小，二级cache较大
2. 如果一级cache miss，二级cache hit，此时会降低miss penalty
3. AMAT = Hit_Time_L1 + Miss_Rate_L1 × (Hit_Time_L2 + Miss_Rate_L2 × Miss_Penalty_L2)
4. 两个概念：
   1. Local miss rate：当前cache miss的次数 / 访问当前cache的指令数
   2. Global miss rate：当前cache miss的次数 / 总指令数

4.3.2 Critical Word First & Early Restart

1. 不要等到加载满块后才重新启动CPU：

   1. Critical Word First：一旦发生miss，立即将请求的word从内存中取出并发送给CPU，让CPU继续执行，之后再慢慢填充block。也叫wrapped fetch / requested word first
   2. Early restart：还是从内存中取出一个block，但是一旦当请求的word到达，就把它发送给CPU，让CPU继续执行

2. 通常在block比较大的时候比较有用

3. 示例：

   

4.3.3 Giving Priority to Read Misses over Writes

1. 读miss优先于写miss执行

   

4.3.4 Merging write Buffer

1. 用 multiword writes 替代 one word writes
2. 在write-througe策略中：
   1. 当写入失败时，如果缓冲区包含其他修改的块，则可以检查地址，以查看这个新数据的地址是否与有效的写入缓冲区项的地址匹配
   2. 如果是，则将新数据与该条目合并
3. 降低了同一个地址被多次写时的开销，也可以降低write buffer full的次数

4.3.5 Victim Caches

1. Victim Caches：是一个小的、全关联的cache
2. 当cache中的块被替换时，可以将其先放入 Victim Caches
   1. 如果下一次的miss仍在该块中，可以直接将其拿回来 / 直接修改 Victim Caches 中的块

4.4 降低miss rate

miss的来源：

1. Compulsory：由于cache为空而导致的miss
   1. Misses in even an Infinite Cache
2. Capacity：由于cache容量已满而导致的miss
   1. Misses in Fully Associative Size X Cache
3. Conflict：由于当前block应当放到的cache中的位置已经有block而导致的miss
   1. Misses in N-way Associative, Size X Cache
4. Coherence：由于cache一致性问题导致的miss

以下策略均在cache size不变的情况下讨论

4.4.1 更大的Block Size

1. 优点：

   1. 利用空间局部性降低了compulsory miss rate

2. 缺点：

   1. 会提高miss penalty：因为每次miss需要取更多的数据
   2. 会提高conflict miss rate：因为cache中的块数降低了
   3. 会提高capacity miss rate：因为小的cache中包含的块数变少了，就更容易满了

3. 权衡：

   1. 尽可能最小化 miss rate 和 miss penalty
   2. block size的选择取决于memory的延迟和带宽

4. 示例：

   

4.4.2 更大的cache

1. thumb定律：2倍的size => miss rate降低25%
2. 优点：
   1. 降低了capacity miss rate
3. 缺点：
   1. 会提高hit time
   2. 会提高cost
   3. AMAT曲线是U型的

4.4.3 更高的Associativity

1. 2:1 rule of thumb：

   1. 大小为N的直接映射的cache 与 大小为N/2的2-way组相联的cache 的miss rate相同
   2. 8-way组相联在降低miss rate方面，与提高8倍的cache size效果相同

2. 优点：

   1. 降低了conflict miss rate

3. 缺点：

   1. 会提高hit time

4. AMAT vs. Miss Rate

   

4.4.4 编译器优化

1. 指令
   1. 重新排列内存中的程序，以减少冲突、未命中
   2. 分析冲突（使用他们开发的工具）
2. 数据
   1. 合并数组Merging Arrays：通过单个数组提高空间局部性
   2. 循环交换Loop Interchange：修改循环访问数据的嵌套次序
   3. 循环融合Loop Fusion：将两个有相同循环、类似变量的循环合并为一个
   4. 阻塞Blocking：重复数据与向下移动整列或整行

4.4.4.1 Merging Arrays

1. 将两个独立的数组合并到一起
2. 这样使用的时候，可以在一个block中读取到
3. 提高空间局部性

4.4.4.2 Loop Interchange

1. 遍历矩阵时，修改遍历的顺序，保证内层循环在列上

4.4.4.3 Loop fusion

1. 将两个独立的循环合并为一个
2. 两个循环中使用了相同的变量，合并之后可以减少miss

image-20221214113143734

4.4.4.4 Blocking optimized Matrix Multiplication

1. 将大矩阵分为小矩阵，使得小矩阵的每一列可以存进cache中

4.4.4.5 示例

4.5 硬件相关知识

4.5.1 DRAM & SRAM

SRAM：

1. 6个晶体管，表示1个bit
2. 不需要刷新

DRAM：

1. 1个电容，表示1个bit

2. 电容越大，积累的电荷越多，自放电越慢，刷新的频率越低；但每一次写入的时间越长，单位面积存放的电容越少，存储容量越少

3. DRAM的周期性刷新，会产生一个大的交流信号，导致DRAM不能与CPU做在一起

4. 通常会做成矩阵形式

   

4.5.2 SDRAM：Synchronous DRAM

1. 在DRAM的基础上增加了clock，达到同步效果
2. 可以有burst mode，让关键字先写

4.5.3 DDR：Double data rate

1. 在上升沿和下降沿各做依次写

4.5.4 flash

1. flash在读上比DRAM慢

习题

选A：cost尽可能便宜，speed尽可能快

image-20221214124711597

选B：两级cache时，一级cache不需要很大

选A

1. B：I/O不仅指与人的交互，还有CPU与内存的交互
2. C：I/O性能很重要

image-20221214125100925

选C：直接映射时block conflict的概率最高

image-20221214174637040

选D：当进程工作时，并不是程序访问的所有内容都会被放到主存。如果电脑有虚拟内存，一些内容会仍停留在磁盘。地址空间会被划分成固定大小的block，称为pages。任何时候，每一个page会停留在主存或磁盘中。

选A：

1. Write through 与 Write back 对比，对虚拟内存没有影响
2. full-associative map 与 其它映射方法 对比
3. TLB cache 与 no cache 对比
4. LRU replacement 与 其它替换策略 对比

image-20221214175356757

选A

image-20221214175804610

选B：

1. 内存为256MB：28bit
2. 4KB cache：2¹²
3. block size 32B：5bit
4. 2-way associative：1bit
5. index的长度：12-5-1=6bit

image-20221214175819564

选B：把1个bank替换为多个banks，有哪些好处–提高了带宽

image-20221214180148625

选D：

1. AMAT = Hit Time + Miss Rate * Miss Penalty
2. IC * CC * IPC
3. 改进的程度 = Told / Tnew
4. CPU Time = IC * CC * CPI

image-20221214180335701

选B：当程序运行的时候，使用的内存地址为逻辑地址

image-20221214180527597

选A：对于全关联来说，组关联的优点在于–tag更小，占用的芯片面积更少

image-20221214180639388

选D：假设cache中有M个block，每K个block分为一个组，则它是一个K-way组关联

image-20221214180841186

选A：增强了空间局部性--访问了x，x的附近也会被访问

image-20221214181048556

1. cache大小：64KB--2¹⁶
2. 每一行大小：128B--2⁷
3. 4-way组关联：2²

image-20221214181405480

选B：如果block size增大了，miss rate可能会降低，正确的表述为：在一定范围内，block size增大，miss rate降低

image-20221214181455496

选D：二级cache的AMAT = Hit time_L1 + Miss rate_L1 * (Hit time_L2 + Miss rate_L2 * Miss penalty_L2)

image-20221214181556596

在一个2-way组关联的cache中，假设cache有4个block，每个block有1word，每个set有2个block。对于指令LOAD R1, 0x18，这次访问miss了，不需要replacement，新的block会放在Set 0 Block 0

image-20221214181716064

memory的表现为：

1. 送地址：4 clock
2. 访问每个word：56 clock
3. 传输数据：4 clock

假设一个block有4 word，一个word有8 byte，那么miss penalty为(4 + 56 + 4) × 4 = 256 clock，bandwidth为\(\frac{4 * 8}{256}=\frac{1}{8}\)

image-20221214182030080

1. miss rate = 50%
   1. 每次访问数组时，偶数次miss，然后装入2 word，从而奇数次hit
2. AMAT = 8 + 50% * 70 = 43 ns
3. CPI计算：
   1. 先用AMAT与频率换算成clock cycle
   2. 然后再计算平均每条指令需要的clock cycle

image-20221214182448100

假设cache的其它参数(容量、关联性、block大小)都不变，对于下列三个问题：

1. block size翻倍，block数量降低，index变小，tag变大，但不是翻倍的关系
2. 直接映射的cache，容量翻倍，block数量翻倍，会降低conflict miss
3. 直接映射的cache，容量翻倍，强制miss的次数倍增

什么是virtual indexed和physical tagged cache？

1. virtual indexed：index部分在page-offset中，因此不需要经过MMU翻译
2. physical tagged：tag在page number中，需要经过MMU翻译

通过index在cache中找对应的block 与 MMU翻译page number并行进行，降低了时间消耗

image-20221214183259142

假设一个cache使用write-back策略，被交换的block有20%的几率为dirty，cache miss的概率为10%。假设hit time为1 cycle，miss penalty为20 cycle，写回dirty block为20 cycle

image-20221214184127692

第3问需要：图+语言描述

image-20221214184359869

image-20221214184439146

Chapter 5：Extend 2 Supporting M Coperation

5.1 之前的流水线CPU

1. ALU部分是一个门电路，只需要1个cycle就可以完成计算

5.2 扩展流水线CPU，支持多周期运算

5.2.1 包含FP运算单元的5阶段流水线

5.2.2 两个指标：Latency和Initiation interval

1. Latency：指令开始到结束所需的时间
2. Initiation interval：指令开始后，再经过多长时间，可以重新开始

流水级

新的情况

5.2.3 按序发射，乱序完成

结构冲突：

1. WB阶段要写寄存器，ID阶段要读寄存器：double bump，上升沿写，下降沿读

2. IF和MEM都要访问存储器：将存储器分为指令存储器、数据存储器

3. 同一个周期有多个WB

   1. 多端口读写，但成本太高
   2. 阻塞stall
      1. 在ID阶段stall：多增加一些判断逻辑，但是与原来的CPU是统一的

5.2.4 如何解决write port conflict

image-20221214191641942

5.3 data hazard的种类

1. RAW true dependence：A写Rx，B读Rx
2. WAW output dependence：A写Rx，B写Rx
3. WAR anti-dependence：A读Rx，B写Rx

5.3.1 RAW依赖

1. B在A写寄存器之前，就读了寄存器的值，可能导致B得到了一个旧的value
2. 解决方法：forwarding

填写技巧：

1. 一旦有一行stall，下面都是stall
2. stall一定出现在ID的后面
3. stall结束时，与上一行的stage之间一定有一个forward

5.3.2 WAW依赖

1. B在A写寄存器之前，就写了寄存器的值，可能导致A再次写寄存器，从而使寄存器保存了一个旧的value
2. 解决方法：
   1. 阻塞A
   2. 直接扔掉A这条指令

1. 在WB之前检测是否需要stall
2. 注意：整数指令，MEM=>WB；浮点指令，没有MEM阶段

5.3.3 WAR依赖

1. B在A读寄存器之前，就写了寄存器的值，可能导致A读寄存器时，读到了一个新的不正确的value

5.3.4 在ID阶段需要检查的内容

1. 结构冲突
   1. 除法、寄存器写端口
2. RAW冲突
   1. 如果有RAW冲突，则直接stall，直到
      1. 源寄存器不再是其它指令的目标寄存器
      2. 源寄存器不再是EX/MEM阶段load指令的目标寄存器
3. WAW冲突
   1. 如果有WAW冲突，则直接stall / cancel

Chpater 7：Dynamic Schedule--Scoreboard

统计数据表明，每5条指令，大概率就有一条跳转指令

7.1 指令级并行ILP

7.1.1 指令级并行的目标：最小化CPI

CPI = 理想CPI + 结构冲突导致的stall + 数据冲突导致的stall + 控制冲突导致的stall

1. 理想CPI：实现某个算法的最优表现
2. 结构冲突：HW不能支持这种指令的组合
3. 数据冲突：当前指令依赖于之前指令的结果
4. 控制冲突：由获取指令和决定控制流更改(分支和跳转)之间的延迟引起冲突

7.1.2 如何实现ILP

1. 基于硬件的动态解决方案
2. 基于编译优化的静态解决方案

7.1.3 降低stall的方法

7.1.4 Instruction-Level Parallelism ILP

1. 为了获得实质性的性能增强，我们必须跨多个基本块利用ILP
2. 最简单：循环级并行性，利用循环迭代之间的并行性
   1. 使用Vector(SIMD) & GPU
   2. Vector：如将多个寄存器与多个寄存器相加，结果保存到多个寄存器中–即同时处理多个寄存器
   3. 如果不是Vector，则通过分支预测进行动态ILP，或通过编译器展开循环进行静态ILP

7.2 数据依赖

7.2.1 真实数据依赖：RAW 写后读

7.2.2 命名依赖

1. 命名依赖：后面要写的寄存器，出现在了前面的源/目的寄存器中

   1. 可以通过寄存器重命名解决
      1. 编译器解决：更容易知道重命名到什么时候
      2. 硬件解决：需要考虑重命名到什么时候、CPU是否支持多个重命名同时存在

2. WAR 读后写--anti-dependence

   

3. WAW 写后写–output dependence

   

7.2.3 控制依赖

1. 一般情况下，CPU的指令重排只在两个跳转之间进行，不会跨越跳转

Example 1：由于beq的存在，or指令可能与add有依赖，也可能与sub有依赖

Example 2：x4在skip后没有使用，sub指令可能可以被移动到beq之前

7.2.4 异常

1. 指令重排不能影响异常的精确性

7.3 ILP：软件方法--静态调度

7.3.1 相关技术

1. 实现ILP的基本编译器技术
   1. 循环展开
2. 静态分支预测
3. 静态多重问题：VLIW
4. 实现ILP的高级编译器支持
   1. 软件流水线
   2. 全局代码调度
5. 在编译时实现更高ILP的硬件支持
   1. 硬件为编译器提供更多指令级
   2. 条件或谓词指令
   3. 具有硬件支持的编译器推测

7.3.2 示例

指令没有重排：

指令重排后：

7.3.3 跳转指令的delay slot

1. 跳转指令后面的一条指令，不论跳转是否成功，都可以执行完成
2. 可以把一条指令(不论跳还是不跳都要执行)放在branch的后面，就可以充分利用branch的delay slot
3. 一般是从跳转前拿一条指令放在后面，这条指令的执行不影响跳转的结果

7.4 ILP：硬件方法--动态调度

7.4.1 为什么需要动态调度

1. 某个被stall的指令，与之前的指令没有依赖关系，但由于之前的指令stall了，它也不得不stall
2. 可以通过动态调度，让后面的指令先执行
3. 也成为指令重排

7.4.2 基本思路

1. 将指令的ID阶段分为两个阶段
   1. Issue(发射)：译码指令，判断是否有结构冲突
   2. Read Operands：等待，直到没有数据冲突，然后读寄存器，这里要有能够支持等待的存储单元

7.5 Scoreboard 计分板

1. 当资源充足且无数据依赖性时，允许指令无序执行
2. 顺序issue
3. 乱序EXE
4. 乱序completion

7.5.1 基本结构

7.5.2 计分板的流水级

1. 发出（Issue）：在以下情况下发出指令
   1. 功能单元可用
   2. 没有其他活动指令具有相同的目标寄存器。
   3. 没有structural冲突、WAW冲突
2. 读取操作数（RO）
   1. 两个操作数都可用，才能进入EX阶段，否则一直在RO阶段
   2. 这意味着以前发出但未完成的指令都没有将操作数作为目标
   3. 这可动态解决RAW冲突
3. 执行（EX）
   1. 完成后通知记分板，以便重新使用功能单元
4. 写入结果（WB）
   1. 记分板检查WAR冲突，如果有则stall

7.5.3 计分板算法

1. 记分板全权负责指令发布和执行

   1. 创建相关性记录
   2. 决定何时获取操作数
   3. 决定何时开始执行
   4. 决定何时可以将结果写入寄存器

2. 三种数据结构

   1. Instruction status

      1. 指令在四个步骤中的哪一个

   2. Functional unit status

      状态	解释
      Busy	表示当前单元是否被占用
      Op	当前单元正在执行的指令(如add or subtract)
      Fi	目标寄存器
      Fj, Fk	源寄存器
      Qj, Qk	生成源寄存器Fj, Fk的功能单元
      Rj, Rk	判断源寄存器Fj, Fk是否已经ready；当操作数被读取之后，设为NO

   3. Register result status

      1. 哪个功能单元将写入该寄存器

7.5.4 记分牌算法的具体运行方式

指令的等待：Function Unit，每个Function Unit最多有1条指令等待执行

1. Issue：
   1. 如果对应功能部件被占用，则stall：防止结构冲突
   2. 计算完成后，更新记分牌
      1. Function Unit Status：
         1. Busy：设置为Yes
         2. Op：设置为对应的操作
         3. Fi：设置为目标寄存器
         4. Fj,Fk：设置为源寄存器
         5. Qj,Qk：如果源寄存器被占用，则设置为对应的功能部件
         6. Rj,Rk：如果源寄存器未被占用，则为Yes；否则为No
      2. Register Result Statue：
         1. Fi对应的位置：设置为当前部件
2. RO：
   1. 如果Rj,Rk不全为Yes，则stall：防止RAW冲突
   2. 读取源寄存器
3. EXE：
   1. 功能部件计算结果
   2. 计算完成后，更新记分牌
      1. Function Unit Status：
         1. Rj,Rk：设置为No，表示释放对应的寄存器
4. WB：
   1. 将计算结果写入目标寄存器
   2. 计算完成后，更新记分牌：
      1. Function Unit Status：
         1. 清空当前功能部件
         2. 如果其它功能部件中，Qj,Qk对应的部件为当前部件，则将其清除，并将Rj,Rk设置为Yes
      2. Register Result Statue：
         1. 清空Fi对应的位置

7.5.5 示例

详见视频讲解

image-20221224132827051

7.5.6 Scoreboard的局限性

1. 如果后面的每一条指令都依赖前面的指令，则Scoreboard用处不大
2. issue queue的大小问题：
   1. window：CPU有多少指令可以处于等待状态，一般不能超出一个branch的范围
3. 放弃了功能部件的流水性
4. 存在WAR和WAW冲突，但Scoreboard选择stall解决

7.6 寄存器重命名

1. 任何指令的写，都不写入寄存器，而是写入换名寄存器中
2. 之后对该寄存器的读，直接读取换名寄存器

7.7 Scoreboard vs. Tomasulo

Chapter 8：Dynamic Schedule--Tomasulo

8.1 Tomasulo算法

8.1.1 基础思想

1. 指令&缓存 被分布在每个功能单元(FU，Function Units)中
   1. FU buffer被称作保留站(RS，reservation stations)，具有挂起的操作数
2. 指令中的寄存器被替换为 具体的值 / 指向保留站的指针，被称为register renaming
   1. 避免了WAR、WAW冲突
   2. 保留站比寄存器多，因此可以进行一些编译器不能进行的优化
3. 当指令要进行计算时，操作数 从保留站中通过CDB(Common Data Bus)广播获取，而不是寄存器
   1. 寄存器进保留站只有一个时刻：指令进入保留站的时候
4. Load、Store也被视为FU，也拥有RS
5. 整数指令可以穿过branch使用，如循环中下一次的指令可以直接使用上一次计算出来的值

8.1.2 保留站的内容

状态	解释
Busy	表示当前行是否有指令
Op	当前行的指令(如add or subtract)
Vj, Vk	源寄存器能读取到的数据
Qj, Qk	尚不能读取到的数据将由哪条指令算出
A	指令的地址，用于存放立即数和计算得到的地址数据

8.1.3 三个阶段

Tomasulo算法的调度分为三个步骤：发射、执行、写回

1. 发射Issue：
   1. Tomasulo算法是顺序发射的，即指令按照程序中的顺序一条接一条被发射到保留站
   2. 判断能否发射的唯一标准是指令对应通路的保留站是否有空余位置，只要保留站有空余，就可以把指令发射到保留站中
   3. 周期结束时会更新保留站和寄存器结果状态表，如果指令有可以读取的数据，就会立刻拷贝到保留站中
   4. 寄存器结果状态表中总是存有最新的值，即如果后序指令的目的寄存器和前序指令的目的寄存器重合，那就只保留后序指令的写信息
2. 执行EXE：
   1. 指令通过拷贝数据和监听CDB获得源数据，然后开始执行
   2. 执行可能是多周期的，在执行过程中不改变处理器状态
3. 写回WB：
   1. 指令在写回阶段通过CDB总线将数据直通到寄存器堆和各个保留站
   2. 周期结束时，根据寄存器结果状态表来更新寄存器堆，并且清除保留站和寄存器结果状态表的信息

8.1.4 Data Path

1. Normal Data Bus：数据 + 目标地址
2. Common Data Bus：数据 + 源地址
   1. 64-bit数据 + 4-bit 功能单元的源地址
   2. 如果与期望的功能单元地址匹配，则写入

8.1.5 具体运行方式

1. Issue：
   1. 如果对应功能部件被占用，则stall：防止结构冲突
   2. 计算完成后，更新保留站
      1. Reservation Station：
         1. Busy：设置为Yes
         2. Op：设置为对应的操作
         3. Vj,Vk：设置为读取到的源寄存器的值
         4. Qj,Qk：如果源寄存器被占用，则设置为对应的功能部件
         5. A：如果指令为LD/ST，则设置为计算出的目标地址
      2. Register Result Statue：
         1. 目标寄存器对应的位置：设置为当前部件
2. EXE：
   1. 如果Vj,Vk没有都被填入，则stall：防止RAW冲突
   2. 功能部件计算结果
3. WB：
   1. 将计算出的结果放入CDB中进行广播，并写入寄存器堆
   2. 计算完成后，更新保留站
      1. Reservation Station：
         1. 清空当前功能部件
         2. 如果其它功能部件中，Qj,Qk对应的部件为当前部件，则读取CDB中的值，放入对应的Vj,Vk中
      2. Register Result Statue：
         1. 清空Fi对应的位置

8.1.6 示例

具体见视频

8.1.7 优缺点

Tomasulo算法记录寄存器的值，Scoreboard算法只记录寄存器的编号

优点：

1. 将hazard detection logic分散开
   1. 每个功能单元都有一个保留站，使用CDB进行广播
   2. 如果多条指令等待同一个结果，并且每条指令都有其它的操作数，当目标结果在CDB中被广播时，这些指令可以同时释放
2. 可以消除WAW、WAR冲突

缺点：

1. 需要实现一个高速CDB
2. 每一个cycle只能有一个功能部件完成，因为CDB上同时只有一个数据

8.1.8 Tomasolo算法的指令可以跨越循环的前后轮

1. Tomasolo算法可以实现事实上的动态展开循环，每一轮都可以正常进行
   1. 要求branch为预测跳转
2. 寄存器重命名
   1. 多次迭代使用不同的物理目标
3. 寄存器重命名
   1. 多次迭代使用不同的寄存器物理目的地（动态循环展开）
4. 保留站
   1. 允许发出指令以推进过去的整数控制流操作
   2. 还缓冲寄存器的旧值—完全避免了我们在记分板上看到的WAR暂停
5. 其他观点：Tomasulo动态构建数据流依赖图

示例：

1. 注意，这里直接将Load2写入了F0对应的位置
   1. 因为需要Load1结果的指令MULTD此时等待的是Load1的值，而不是F0的值

8.1.9 精确中断

1. Tomasulo算法的特点：
   1. 顺序issue
   2. 乱序execution
   3. 乱序completion
2. 需要修复乱序完成的操作，从而能在指令流中找到精确的断点
   1. Speculation
   2. Reorder buffer

8.2 Scoreboard算法：通过寄存器重命名避免WAR、WAW等待

8.2.1 Scoreboard的流水级

1. Issue：在以下情况下发出指令
   1. 功能单元可用
   2. 没有其他活动指令具有相同的目标寄存器。
   3. 解决了：structural冲突、WAW冲突
2. Read Operands（RD）
   1. 两个操作数都可用，才能进入EX阶段，否则一直在RO阶段
   2. 这意味着以前发出但未完成的指令都没有将操作数作为目标
   3. 解决了：RAW冲突
3. Execution（EX）
   1. 完成后通知记分板，以便重新使用功能单元
4. Write Result（WB）
   1. 记分板检查WAR冲突，如果有则stall

8.2.2 Scoreboard算法

1. 记分板全权负责指令发布和执行

   1. 创建相关性记录
   2. 决定何时获取操作数
   3. 决定何时开始执行
   4. 决定何时可以将结果写入寄存器

2. 三种数据结构

   1. Instruction status

      1. 指令在四个步骤中的哪一个

   2. Functional unit status

      1. buzy，op，Fi，Fj，Fk，Qj，Qk，Rj，Rk

   3. Register result status

      1. 哪个功能单元将写入该寄存器

8.2.3 Explicit Renaming 显式寄存器重命名

8.2.3.1 前提

1. 物理寄存器 > 逻辑寄存器

8.2.3.2 核心思路

对每一条需要写寄存器的指令，分配一个新的物理目标寄存器

1. 与编译器优化方式(SSA, Static Single Assignment)类似，但是是硬件实现
2. 消除了WAR和WAW冲突
3. 与Tomasulo类似，更加容易支持全乱序完成
4. 类似于基于硬件的动态编译

8.2.3.3 实现机制

维护一个translation table

1. 映射：ISA寄存器 => 物理寄存器
2. 写寄存器时：从freelist中得到一个新的寄存器，替换原有项
3. 释放物理寄存器的时机：所有使用该物理寄存器的指令均已执行完成
   1. 由于第二次写同一个逻辑寄存器时，该逻辑寄存器会被分配另一个物理寄存器
   2. 因此，只有两次写同一个逻辑寄存器之间的指令，有可能使用同一个物理寄存器

8.2.3.4 优点

1. 将renaming与scheduling分离
   1. 流水线可以更贴近于标准MIPS流水线，只是每个周期可能会发射多条指令
   2. 否则的话，流水线更类似于Tomasulo或Scoreboard
   3. 可以使用标准的forwarding、bypassing
2. 允许数据从单个寄存器组中读取
   1. 不需要从reservation stations或reorder buffer中获取数据
   2. 对平衡流水线来说，很重要
3. 是另一种获取精确断点的方式：
   1. 要获得精确的断点，所有需要“撤消”的操作就是撤消表映射
   2. 在reorder buffer和future file之间提供有趣的混合
      1. 结果立即写回寄存器文件
      2. 寄存器名称按程序顺序“释放”（通过ROB）

8.2.3.5 需要的支持

1. 快速访问翻译表
2. 一种物理寄存器文件，其寄存器数超过ISA指定的寄存器数
3. 能够找出哪些物理寄存器是free的
   1. 没有free的寄存器 ⇒ issue会被stall
4. 寄存器重命名不需要保留站，然而：
   1. 许多现代体系结构使用explicit register renaming + Tomasulo-like reservation stations来控制执行流程
5. 两个问题：
   1. 如何管理free list？
   2. 显示寄存器重命名 如何与 精确中断相结合？

8.2.3.6 示例

1. 物理寄存器表 > ISA寄存器表
2. 在issue阶段，每条指令从freelist中申请一个寄存器，作为自己的目的寄存器

1. 注意物理寄存器P0在这次load之后已经dead
   1. 当我们完成load操作后，我们释放该寄存器

8.2.3.7 在Scoreboard中使用显式重命名

1. 实现一个Rename Table：告诉Scoreboard，指令里面的哪个寄存器被换成哪个寄存器了
2. Rename Table后面是一个更大的寄存器表，该表不对ISA公开，只能由Rename Table使用

8.2.3.8 显式重命名Scoreboard的四个阶段

1. Issue：指令译码、检查是否有结构冲突、为目标寄存器申请新的物理寄存器
   1. 指令按序issue
   2. 如果没有物理寄存器，则stall
   3. 如果有结构冲突，则stall
2. Read Operands：直到没有冲突的时候，读取操作数
   1. 解决了RAW冲突，因为我们等待指令写回数据
3. Execution：计算
4. Write Result：结束计算
5. 在这个过程中，没有检查WAR、WAW冲突

示例见视频

Chapter 9 ：Branch Predictor & Speculation

9.1 Control Hazard

1. Flushing：
   1. 每次遇到跳转，直接stall，直到跳转指令完成
2. Predict-not-taken：
   1. 直接读入跳转指令的下一条指令
   2. 如果发现跳转指令为跳转，则清空流水线，此时浪费了1个周期
3. Predict-taken：
   1. 读入如果跳转时的下一条指令
   2. 如果发现跳转指令为不跳转，则清空流水线，此时浪费了1个周期
4. Delayed Branch

9.2 动态硬件预测

动态硬件预测，只有当前跳转指令被反复执行到的前提下，才有意义

预测是基于数据的预测，因此只能预测下一次遇到当前地址的跳转指令时，是否跳转

9.2.1 1-bit Branch-Prediction Buffer

1. Performance = ƒ(accuracy, cost of misprediction)
2. BHT，Branch History Table：
   1. index：PC地址的低位
   2. value：1位，记录上一次是否跳转
3. 问题：
   1. 在一个循环中，1-bit BHT会导致2次misprediction：进入循环、退出循环
   2. accurancy：(n-2)/n

9.2.2 2-bit Branch-Prediction Buffer

策略1：初始为Taken，发生2次not-taken后，才预测not-taken

策略2：进入临时状态后，如果是taken，就回到taken了

9.2.3 n-bit Branch-Prediction Buffer

与1-bit和2-bit类似，设计更加复杂的状态图

9.2.4 Branch Target Buffer

1. 在循环中，每次跳转时，跳转的目的地址都是一样的
2. 可以将跳转的目的地址缓存起来，减少一次加法

9.2.5 Integrated Instruction Fetch Units 集成指令获取单元

将IF阶段扩展，IF阶段可以实现：

1. branch predication
2. Instruction prefetch
3. Instruction memory access and buffering

9.2.6 Return Address Predictor

1. 间接跳转：目的地地址在运行时变化
   1. 如从函数返回、使用函数指针跳转、对虚函数的访问
2. 寄存器的存在，使得难以预测跳转的地址
3. SPEC89：程序返回占间接跳转的85%
4. Branch Target Buffer对return不起作用
5. LR(Link Register)寄存器：用于存储函数的返回地址，在RISCV中是ra寄存器
   1. 进入函数时，通常会先将LR寄存器保存进堆栈，然后再执行函数的逻辑

9.3 Hardware Based Speculation 投机

9.3.1 Tomasulo的缺点

1. 无法实现精确中断
   1. 精确中断：中断发生时，该指令之前的指令均执行完成，后面的指令均没有执行
2. WB阶段检测中断
   1. 外部中断：找到最后面已经完成的指令，这之前的全部完成，之后的全部没有完成
   2. 内部中断：
      1. 非法指令、除0异常：直接终止程序
      2. 缺页异常：仍需要回到产生中断的那条指令，要求必须精确中断。可以通过添加内存栅栏，让CPU强制等待到当前指令
3. 会部分overlap
   1. 整数单元先跑，浮点单元后跑
   2. 尽管可以issue，但后续基本块在分支解决之前无法开始执行

9.3.2 Hardward-based Speculation

投机：在不知道branch指令是否跳转的情况下，先去做后面的指令

1. 对branch的结果做speculation，假装预测是对的来执行程序
2. 关键点
   1. 动态分支预测，选择跳转到哪里
   2. 由于跳转指令依赖于寄存器，因此跳转指令可能也要等待其它指令的执行完成
   3. 指令可以先执行，但指令的执行结果必须等待之前的指令均执行完，才能写入内存/寄存器
   4. 乱序执行、顺序写入
3. 算法
   1. 按照预测的顺序执行，但是不commit
   2. 只有预测的结果正确时，才将其提交：写寄存器组、写内存
   3. 如果预测结果不正确，则回滚：清空Reorder Buffer

9.3.3 基于Tomasulo算法的投机执行 Speculative execution

9.3.3.1 基础思想

1. 将指令的完成、指令的提交、结果的bypass分开
   1. 如果当前指令的结果是其它指令所需要的，则仍可以给出去，即使当前指令是推测执行的
   2. 因为后面的指令也保证不会写入
2. 处于推测执行的指令，均可以正常执行，但不会写回，直到当前指令不再是speculative
   1. 按照顺序commit
   2. 当branch指令commit的时候
      1. 如果branch指令预测正确，则后续所有指令按序commit
      2. 如果branch指令预测错误，则直接舍弃后面的指令

9.3.3.2 结构

1. 指令队列Instruction queue：用于一次取值取多条指令
2. Reorder Buffer：
   1. Reorder Buffer的来源是CDB、地址单元，出口是寄存器组、内存单元
   2. 即原来的store buffer的拓展，记录哪个地址有哪个值需要写入
   3. 排序的依据：原来的指令顺序
   4. 由于要commit的指令，要么写寄存器，要么写内存，因此可以使用该模块实现顺序commit
   5. 原来CDB广播的数据是直接进寄存器组的，这里添加了一个Reorder Buffer，让其能够顺序commit

9.3.3.3 和Tomasulo算法的区别

1. 增加了Reorder Buffer，删除了Store Buffer
2. 寄存器的重命名是通过Reorder Buffer，而不是通过保留站
   1. 即，通过Reorder Buffer暂存数据
3. 保留站只用来存放：已经issue，没有execution的指令的opcode、operands
4. Reorder Buffer会保存指令的结果，并且将操作数bypass给还没有完成的指令

9.3.3.4 Reorder Buffer 的每个实例包含

1. 指令的类型
2. 目的寄存器
3. 计算出的值
4. 是否已经就绪
5. 异常向量

9.3.3.5 投机Tomasulo算法的四个步骤

1. Issue：从FP Op Queue中得到一条指令
   1. 如果保留站、Reorder Buffer均有空，则发射该指令
   2. 将该指令存入保留站，并且在Reorder Buffer中为目的寄存器分配一个空间
      1. 这一步也叫dispatch(分派)
   3. 更新该实例的控制单元为in use
2. Execution：对操作数进行计算
   1. 如果两个操作数均ready，则进行计算
   2. 否则，等待CDB广播两个操作数，直到两个操作数均在保留站中
   3. 解决RAW冲突
3. Write Result：完成计算
   1. 写入CDB进行广播
   2. 写入Reorder Buffer
   3. 标记保留站中对应的位置为free
4. Commit：使用Reorder的结果更新寄存器
   1. 当Reorder Buffer头部的指令已经有结果了，更新寄存器/写入内存，并将其从Reorder Buffer中移除
   2. 如果跳转指令预测错误，则清空Reorder Buffer
      1. 这一步也叫graduation(毕业)

9.3.3.6 commit时的操作

当一条指令变为Reorder Buffer的头部指令，并且已经计算出结果时

1. 如果当前指令不是跳转指令
   1. 更新寄存器
   2. 从ROB中删除该寄存器
   3. 如果是store指令，则更新内存
2. 如果是跳转指令，但是预测错误
   1. 清空ROB
   2. 流水线从branch的正确分支那里重新开始执行
3. 如果是跳转指令，并且预测正确
   1. branch的执行就结束了

9.3.3.7 示例

1. 使用ROB实现重命名：保留站中等待的，是ROB中的项，而不是之前的保留站的项
2. ROB保证了提交的顺序与原始指令的顺序是一样的

详细见视频

3. 跳转指令依旧需要进入ROB
4. 当后面的指令需要读寄存器时，要选择离它最近的ROB项

9.3.3.8 新问题：memory disambiguation

1. 问题：给定一个指令序列，先store后load，它们两个访问的地址是否时相同的

   1. 或者说，两条指令是否有RWA冲突
   2. 如下面的例子中，R2可能与R3的值相同，导致访问同一个地址

   

2. 我们是否能够先执行LD指令，后执行ST指令？

   1. 如果存储的是寄存器的值，可能会由于一些对于R2的操作指令，使得ST指令被delay很长时间
   2. 我们可能想要在同一个周期里，开始执行这两条指令(ST和LD可以通过double bump在同一个周期内完成)

3. 解决方法：

   1. 在进行内存操作时，要保证ROB中所有内存操作的地址均已得到，才能进行内存操作
   2. ROB需要跟踪所有修改内存的指令，按照源码的顺序
      1. 当地址已经获得的时候，记录地址、值，而不是寄存器的地址
      2. 保存先进先出的顺序：保证load和store的执行顺序没有被打乱
         1. 如下图中，LD指令必须在ST指令之后执行
   3. 硬件支持：
      1. 当我们有一个load的地址的时候，检查store队列
         1. 如果在load之前有store指令的地址于其相同，则暂停load指令
         2. 如果load指令的地址与之前的store指令的地址相同时，会有一个memory-induced RAW hazard
            1. 如果store的值已经可用，则返回该值
            2. 如果store的值不可用，则将对应ROB的序号放入load指令的source中
         3. 否则，执行load指令

   

9.3.3.9 对精确中断的硬件支持

1. 如果在某一条指令产生了中断，则将ROB中对应指令的
   1. 后面的指令全部清空
   2. 前面的指令正常运行

9.4 记分牌、Tomasulo、带投机的Tomasulo三种算法对比

三者按顺序，依次解决了更多的问题

1. 记分牌：RAW问题
2. Tomasulo：WAW、WAR问题；RAW问题
3. 带投机的Tomasulo：精确中断；WAW、WAR问题；RAW问题

Chapter 10：SuperScalar & VLIW

10.1 获取CPI<1：Multiple Issue Processor 多发处理器

CPI<1：单位时间内能够处理多条指令

1. Vector Processing：向量计算（把数据拼在一起、数据并行）
   1. 将多个数据拼成一个向量，指令对向量进行计算
   2. 在RISCV中，该指令称为vector指令
   3. 在其它处理器中，该指令称为SIMD指令
2. Superscalar：超标量
   1. 每个周期可以执行的指令数量是变化的(1~8)
   2. 可以由编译器或硬件调度(Tomasulo)
   3. 如：IBM PowerPC、Sun UltraSparc
3. Very Long Instruction Words(VLIW)：超长指令字（把指令拼在一起、指令并行）
   1. 在一个指令中，放固定数量的指令
   2. 该指令由编译器产生，将操作放到wide templates(TBD)中
   3. 编译器要保证放在一起的这几条指令之间，没有依赖关系
4. 新的性能指标：Instruction Per Clock cycle，IPC

10.2 SuperScalar

1. 每个周期尽可能发射足够多的指令，让每个功能单元均处于busy状态
   1. 静态调度：编译器优化，按序执行
   2. 动态调度：使用基于Tomasulo算法的技术，乱序执行

10.2.1 静态调度SuperScalar

1. 指令按序发射

2. 在issue的时候，会检查所有流水线冲突，会在一个周期内发射0~8条指令

3. Issue packet：fetch unit在取值的时候，会在一个周期内取多条指令，这些指令可能会在一个周期内发射

   1. 如果指令存在结构冲突/数据冲突，则指令就不会issue
   2. 如果是N-issue，则一个周期内发射0~N条指令

4. Issue阶段会被分开，并且实现流水

   1. within packet：确定当前packet中会有多少指令能够同时发射
   2. between packet：检查选中的指令中，是否与之前的packet有冲突

5. 在一个周期内执行issue check，会限制clock cycle time：需要O(n²-n)次比较

   1. 因此，将issue阶段分割，并且实现流水
      1. 第一个阶段：决定由多少指令可以同时发射
      2. 第二个阶段：检查是否与之前的指令由冲突
   2. branch penalties会更高，因此预测准确更重要

6. 多发的难点：

   1. 译码

   2. issue：难于找到一条FP和一条整数指令，两者完全没有关系

   3. 寄存器组：需要在一个周期内完成2 * N个写、 1 * N 个读

   4. Rename的逻辑：必须能够在一个周期内，对同一个寄存器，换名两次，举例如下

      

   5. Result buses：需要在一个周期内，完成多条指令

      1. 因此，需要一个multiple buses，对于每一个保留站都有一个匹配逻辑
      2. 或者，需要multiple forwarding paths

双发流水线：dual-issue pipeline

Scalar MIPS

1. 一次两条指令，一条浮点，一条整数

10.2.2 动态调度SuperScalar

1. 两种不同的方法用于解决一个周期内issue多条指令：
   1. pipeline：将两条指令分别在一个周期的上升沿、下降沿执行
   2. widen issue logic：有一个更宽的逻辑单元，同时可以处理两条指令
   3. 现在一般两种方法都用

1. 双发 ≠ 双执行，只有数据都准备好了，才能执行

2. 如果有多个整数单元，则

image-20221228165033244

3. 假设整数部分有3个单元：ALU、计算地址(ADD)、比较器(SUB)

   1. 双发，但不使用speculation

      

      image-20221228165428654

   2. 双发，使用speculation

      

      image-20221228165822014

10.2.3 ILP软件方法

1. 循环展开
2. 静态分支预测
3. 静态多发：VLIW(超长指令字)
4. 高级编译器支持：
   1. 软件流水线：software pipeline
   2. 全局代码调度：global code scheduling
5. 硬件对软件的支持
   1. 条件/预测指令，如ADDHI(前面的比较成功，则执行)、SUBLO(前面的比较s失败，则执行)
   2. 编译器投机

示例：

1. C代码：

   

2. 翻译为MIPS

   

3. 检查hazard

   

4. 利用延迟槽减少stall

   

5. 循环展开：要求循环次数必须是4的整数倍

   

从编译器角度看code movement

1. 编译器要考虑程序里面的依赖关系
2. 不管流水线是否有硬件冲突
3. 编译器要通过指令重排，避免冲突
4. 编译器主要考虑RAW(真实依赖)，通过寄存器来判断
5. 如果有RAW依赖，则不能并行
6. 编译器很难判断memory disambiguation
   1. 100(R4)与20(R6)是否相等?
   2. 在不同的循环中，100(R4)与20(R6)是否相等?

循环展开的细节

1. 通常不知道循环的具体次数
2. 假设有n次，且我们会将循环中的内容展开k遍
3. 通常不是简单展开，而是产生一个相邻循环的pair
   1. 先执行n % k遍
   2. 然后再进行n / k次展开

10.3 静态多发：VLIW

1. VLIW：Very Long Instruction Word
2. 每个超长指令字中，存储的指令的类型是固定的
3. 在指令集的设计中需要进行平衡tradeoff
   1. 超长指令字可以提供多条指令的空间
   2. 编译器放入的多条指令，相互之间是没有依赖关系的
   3. 例如：2个整数指令、2个FP指令、2个Memory访问、1个branch
   4. 需要编译技术，在多个跳转之间进行调度
4. VLIW的问题：
   1. 技术问题：
      1. 代码大小增加了
      2. 会有unused function slots
      3. 任何功能单元上的stall，会引起多条指令的stall
   2. 逻辑问题：
      1. 二进制代码的兼容性
   3. 多发处理器的主要挑战：
      1. 如何实现更大的ILP

VLIW的循环展开示例：

Chapter 11：Multithreading

11.1 多线程软件

11.1.1 进程&线程

1. 进程
   1. 每个进程有独特的地址空间unique address space
   2. 可以有多个线程
2. 线程：每个线程有它独特的执行上下文unique execution context
   1. 独立的PC、registers、stack
   2. 一个进程的所有线程，共享相同的地址空间
   3. 可以有私有的堆空间，但一般情况下，一个进程的所有线程共用一个堆

11.1.2 多线程应用：进程被划分成了线程

1. 增加并发度concurrency/并行度
   1. 并发concurrent：外面来了一件事，但手头的事不能停下，因此会被动的同时做两件事
   2. 并行parallel：主动将任务分为两部分，同时进行
2. 部分阻塞
3. 集中资源管理

11.1.3 如何保证流水线之间的指令没有依赖关系

1. 交替执行不同线程的指令
2. 寄存器组是分bank的，每个线程使用不同的bank

11.1.4 多线程体系结构

1. 如果处理器可以执行多个软件线程，则
   1. 可以同时执行：线程可以由硬件切换(交替执行interleaved)，而不是由OS控制
2. 共享资源
   1. 更好的资源利用率、更好的吞吐量
3. 可以是同一个进程，也可以不是
   1. 如果不是，问题主要是页表的切换
   2. 页表可能会有多份

11.1.5 多线程的开销

1. 对于每个软件来说，CPU更慢了
2. 每个线程需要有各自独立的user state：GPRs、PC
3. 也需要独立的OS控制状态：虚拟内存页表、异常处理寄存器

11.1.6 线程调度策略

1. Fixed interleave（CDC 6600 PPUs，1965）
   1. 每N个周期，每N个线程各自执行一条指令
   2. 如果线程没有ready，就stall
2. Software-controlled interleave（TI ASC PPUs，1971）
   1. OS在N个线程之间，分配S个流水线槽位
   2. 硬件在S个流水线槽位之间，做固定的interleave
3. Hardware-controlled thread scheduling（HEP，1982）
   1. 硬件跟踪哪个线程ready to go
   2. 根据硬件优先的模式，选择下一个要执行的线程

Denelcor HEP是一个uniform shared memory multiprocessor

1. 有多个处理器，共享一个内存uniform shared memory
2. 是一个细粒度(fine-grain)的多线程
3. 可以忍受内存的延迟、同步的延迟、功能单元的延迟
4. 每个处理器有120个线程，时钟周期频率为10MHz

11.1.7 Coarse-Grain Multithreading 粗粒度多线程

1. Tera MTA为超算应用设计
   1. 数据特点：数据集很大，局部性较低
   2. 没有data cache
   3. 有很多并行的线程，去隐藏一个large memory latency
2. 其它应用会更加cache friendly
   1. 当cache hit时，会有更少的流水线bubble
   2. 只增加一部分线程，去隐藏偶尔的cache miss latencies
   3. 当cache miss的时候，交换线程

11.2 多线程设计

1. 细粒度多线程Fine-grained multithreading
   1. 每一个时钟周期，都在不同线程间切换
   2. 多个线程的指令执行，是交织(interleave)在一起的
   3. interleave是以轮询的方式进行的：CPU认为指令序列就是交替好的
   4. 一旦发生停顿，所有线程均中断
2. 粗粒度多线程Coarse-grained multithreading
   1. 一直跑单个线程，只有在成本比较高的停顿发生时，才会进行线程切换
   2. 如：二级/三级cache miss、功能单元的数据冲突
   3. 会有线程切换的开销
   4. 在解决停顿时间较长的情况时，比较划算
3. 设计时需要考虑
   1. 上下文切换的开销
   2. 需要支持多少线程
   3. 期望的应用级并行度

11.2.1 Superscalar Machine Efficiency

1. 垂直waste：通常是cache miss

11.2.2 垂直多线程

1. 消除了垂直waste，但是会没有解决水平waste

11.2.3 芯片多线程

1. 消除了水平waste，但是还有一部分垂直waste

11.2.4 同时多线程 Out-of-Order Simultaneous Multithreading

1. 在细粒度的基础上进行改良

   

2. 基础Out-of-order流水线

   

3. SMT流水线

   

4. SMT的设计挑战

   1. 要在细粒度实现的表现与单线程的表现之间进行权衡
      1. 首选线程：可能会牺牲吞吐量
      2. 不太可能混合来自多个线程的指令
      3. 最大限度地提高单线程性能，应尽可能提前提取，并在分支预测失误或预取缓冲区中发生未命中时释放提取单元
   2. 一个较大的寄存器文件，用于保存多个上下文
   3. 不影响时钟周期，例如在指令发出时，在指令完成时
   4. 确保cache和TLB冲突不会导致性能下降

11.2.5 投机、乱序、超标量的处理器

11.2.6 芯片多线程

Chapter 12：DLP--Vector & SIMD & GPU

数据级并行

1. Vector Processor
2. GPU

线程级并行

1. SMP/DSM
2. Cache coherence
3. Synchronization

12.1 程序执行四种模式

1. SISD：单一指令、单一数据

   

2. SIMD：单一指令、多个数据

   1. SIMD必须在最小段里面执行，因为要保证指令是单一的
   2. 如果跳转的话，指令就不一样了

   

3. MIMD：多条指令、多个数据

   

4. MISD：多条指令、单一数据

   1. 比较罕见

12.2 SIMD

1. SIMD体系结构可以利用显著的数据级并行性：
   1. 面向矩阵的科学计算
   2. 面向媒体的图像和声音处理器
2. SIMD比MIMD更节能
   1. 每个数据操作只需要获取一条指令
   2. 使SIMD对个人移动设备具有吸引力
3. SIMD允许程序员继续按串行的思路思考

12.3 Vector Processing 向量计算

1. 在处理单元的个数不变的时候，相当于做了一次循环展开，节省了branch的开销

12.3.1 向量计算的特点

1. 单矢量指令意味着大量的重复工作（循环）
   1. 可以减少IF的次数
2. 每个结果独立于以前的结果
   1. 长管道，编译器确保无依赖性
   2. 提高时钟频率，因为基本上都是整数运算，可以很快完成
   3. 硬件不必检查数据危害
3. 访问存储器的向量指令具有已知的访问模式
   1. 内存是高度交错的
   2. 内存的读取延迟会被分摊(amortize)到超过64个元素
   3. 不需要（数据）缓存
4. 减少管道中的分支和分支问题
   1. 通常由回路分支引起的控制危险是不存在的

12.3.2 Vector架构的类型

1. memory-memory vector processors：
   1. 所有的向量操作，都在内存之间进行，向量存储在内存中
   2. 可以给出两个内存地址作为source，一个内存地址作为target
2. vector-register processors：
   1. 所有的向量操作，都在vector寄存器之间进行(处理load和store)
   2. vector等价于load-store架构

12.3.2.1 vector-register architecture

1. 基础想法
   1. 把一组数据读到vector register中
   2. 在寄存器上进行操作
   3. 将结果写回memory
2. 寄存器由编译器控制
   1. 用于隐藏memory latency
   2. 影响内存的带宽

12.3.2.2 Vector Memory-Memory Achitecture

1. 矢量内存结构（VMMA）需要更大的主内存带宽，为什么？
   1. 所有操作数都必须从内存中读取
2. VMMA使多个向量操作的执行难以重叠，为什么？
   1. 必须检查对内存地址的依赖关系
3. VMMA导致更大的启动延迟
   1. 在CDC Star-100上，当矢量<100个元素时，标量代码更快
   2. 对于Cray-1，向量/标量盈亏平衡点约为2个元素

12.3.2.3 Vector Processor的组件

1. Vector Register：向量寄存器，固定长度的bank，存储一个vector
   1. 至少2个读端口，1个写端口
   2. 通常有8~32个向量寄存器，每个存入64-128个64bit单元
2. Vector Functional Units(FUs)：向量功能单元，完全流水，每个周期启动一个新的计算
   1. 通常有4~8个FUs：FP add，FP mult，FP reciprocal，integer add，logical，shift
   2. 同一种功能单元可能有多个
3. Vector Load-Store Units(LSUs)
   1. 完全流水
   2. 每个周期可以读/写多个元素
   3. 可能有多个LSUs
4. Scalar register：标量寄存器，用于浮点标量/地址计算
5. Cross-bar：矩阵，将所有部件连起来

12.3.2.4 基础向量指令

12.3.2.5 向量指令的执行时间

1. 执行事件取决于三个因素
   1. 向量的长度
   2. 是否有结构冲突
   3. 数据依赖
2. RV64V功能单元每个时钟周期消耗一个element
   1. 流水计算，而不是并行计算
   2. 执行时间大约为vector的长度
3. Convey
   1. 有可能可以同时执行的向量指令的集合

12.3.2.6 Chimes 节拍

1. 在同一个convey中的指令可能有RAW依赖

2. Chaining

   1. 一旦向量操作的源向量均已可用，允许该向量操作尽早执行

   

3. Chime

   1. 执行一次传送的时间单元
   2. m个convey在m个chimes中执行，向量长度为n
   3. 对于长度为n的向量，需要m*n个时钟周期

12.3.2.7 Vector内存操作

1. load/store操作在寄存器和内存之间移动数据
2. 三种类型的寻址
   1. Unit stride：单位步幅
      1. 给出每个单元的大小，然后一个单元一个单元的读取
      2. 最快的
   2. Non-unit(constant) stride：非单位（恒定）步幅
   3. Indexed(gather-scatter)：索引（聚集-分散）
      1. 寄存器间接的矢量等效
      2. 适用于稀疏数据阵列
      3. 增加矢量化程序的数量
      4. 压缩/扩展变量
3. 支持内存中各种数据宽度的组合
   1. ｛.L、.W、.H、.B｝x｛64b、32b、16b、8b｝

Vector 内存系统

12.3.2.8 DAXPY

1. 设X、Y为向量，a为标量，则DAXPY表示的操作为：Y = a * X + Y

12.3.2.9 向量长度

1. 一个向量的具体长度是不确定的，但是有一个最大长度(MVL，maximum vector length)
2. vector-length register(VL)：控制任何矢量操作的长度，包括矢量加载或存储
   1. 例如：VL=10时，vadd.vv为
   2. for(I=0；I<10；I++) V1[I]=V2[I]+V3[I]
3. VL可以是从0到MVL的任何值

12.3.2.10 Strip Mining

1. 当向量长度 > MVL时，需要进行Strip Mining
   1. 生成一个循环计算，每个循环计算的向量长度为MVL
   2. 循环结束后，计算不足MVL的部分

12.3.3 向量操作的优化

12.3.3.1 Vector Chaining

1. 是forward在向量上的延展

12.3.3.2 条件执行

1. 假设源码如下：

   1. 由于对每个单元的操作不一样，因此需要条件执行

   

2. 解决方法：条件执行

   1. 为向量的每个单元添加一个1-bit vector flag register
   2. 使用vector compare，设置flag register
   3. 将flag register作为mask，控制向量减法

3. 示例：

   

12.3.3.3 压缩/扩展操作

1. 如果向量比较稀疏，可以通过mask做压缩
2. 然后可以将另一次向量操作，填进当前操作的空余部分

12.3.4 Vector的优点

1. 易于获得高性能；N次操作：
   1. 没有依赖关系
   2. 使用相同的功能单元
   3. 存取不相交寄存器
   4. 按照与前面指令相同的顺序访问寄存器
   5. 访问连续存储器字或已知模式
   6. 可以利用大内存带宽
   7. 隐藏内存延迟（以及任何其他延迟）
2. 可扩展：通过添加硬件资源获得更高的性能
3. 紧凑型：用一条简短的指令描述N个操作
4. 可预测：性能与统计性能（缓存）
5. 多媒体就绪：N * 64b、2N * 32b、4N * 16b、8N * 8b
6. 需要成熟的编译器技术

12.4 SIMD

1. 多媒体应用需要的时比正常word更窄的数据类型
   1. 如RGBA在做运算时，每个通道要分开计算，即一个计算单元为8-bit
2. SIMD与向量计算相比，限制在于：
   1. 数据的个数被编码进了op code中
   2. 无复杂的寻址模式（stride、scatter-gather）
   3. 无mask register

12.4.1 SIMD实现

12.4.2 SIMD代码示例

12.5 GPU：Graphical Processing Units

1. 基础思路：
   1. 异构的计算模型：Heterogeneous execution model
      1. CPU是主机，GPU是设备
   2. 为GPU开发一种类似C语言的编程代码
   3. 编程模型为SIMT：Single Instruction Multiple Thread
2. GPU单个指令的计算能力不强，但是并行度非常高，路数很多
3. GPU是一个典型的SIMD

12.5.1 Threads and Blocks

1. 一个thread与一个data element关联
2. thread组成block，block组成grid
3. GPU硬件进行thread的管理

12.5.2 NVIDIA GPU 架构

1. 与vector machines类似：
   1. 数据级并行
   2. 可以进行scatter-gather传输
   3. 有mask registers
   4. 有更大的寄存器组
2. 区别：
   1. 没有标量的处理
   2. 使用多线程去隐藏memory latency
   3. 有很多的功能单元，不再流水，而是完全的并行
      1. 4096个线程就是4096个加法器、4096个乘法器…

Chapter 13：Multiprocessors

13.1 为什么要使用多处理器

1. 应用的需求
   1. 单一处理器性能的提升，可以解决latency的问题，但不能解决单位时间内获取更多的产出的问题
2. 微处理器已经是最快的CPU了
3. 摩尔定律的失效
4. 能够使用并行的软件逐渐增多

13.1.1 多处理器的目标

1. 性能：
   1. 突破单一处理器的限制
   2. 如ILP(branch预测，RAW冲突、内存)
2. 更低的成本：
   1. 使用廉价的部分，构建一个大的系统
3. 可扩展性scalability：
   1. 只要多加处理器，就能获得更好的性能
4. 错误容忍：
   1. 如果有少量处理器失效，仍能继续进行运算

13.1.2 并行计算机

1. 定义：并行计算机是一组处理单元，相互协作、通信处理大的问题
2. 相关参数：
   1. 多少个计算机
   2. 每一个计算单元有多强大
   3. 如何进行协作、通信
   4. 数据是怎么发送的
   5. 通信的类型是什么
   6. 对程序员来说，硬件和软件的基本单元是什么
   7. 如何形成性能的

13.1.3 Catalogue the Parallel(MIMD) Processors

1. main memory的组成方式
   1. Shared：所有核共享一个内存UMA
   2. Distributed：每个核都有一个内存NUMA
2. 对硬件来说，memory的性能
   1. 如memory access latency的表现？
      1. Shared：每个核访问的不同内存的时间是一致的
      2. Distributed：每个核访问不同内存的时间是不同的
3. 对软件来说，memory的性能
   1. 处理器是否能够直接通过内存通信
      1. Shared(shared memory)：可以直接通过load/store进行通信
      2. Distributed(message passing)：通过message进行通信
4. 是否正交
   1. DSM：物理上是分布的，逻辑上是共享的

13.1.3.1 UMA

1. 理想模型：
   1. 优秀(single-cycle)的内存访问延迟
   2. 优秀(infinite)的内存访问带宽
2. 实际系统
   1. 当处理器个数上升时，latency会变长
   2. bandwidth是有限的
   3. 添加memory banks，latency也会变大
3. 也就是说，UMA做不大

13.1.3.2 UMA vs NUMA

1. UMA：uniform memory access
   1. p0访问m0~m3的延迟都是一样的
   2. 当系统变大时，延迟会增加
   3. data放在哪一块是不重要的
2. NUMA：non-uniform memory access
   1. p0访问m0会更快，m1~m3会更慢
   2. p0发送请求给m0，如果m0发现数据不在当前内存，则向Interconnect发消息，获取其它内存单元的数据
   3. data放在哪里很重要

13.1.4 主要的MIMD类型

1. 中心化的共享内存
2. 去中心化的内存：内存单元跟随CPU
   1. 内存带宽变大，但是会有更高的通信延迟
   2. 软件模型更复杂

13.1.5 并行架构

1. 并行架构拓展了传统的计算机架构，主要通过通信
   1. 抽象：在硬件和软件上有不同的接口
2. 并行的编程模型
   1. multiprogramming：有很多任务，不考虑通信问题
   2. shared address space：通过内存进行通信
   3. message passing：发送/接收消息
   4. data parallel：由代理(agents)同时操作数据集，然后全局地同时交换信息
3. 通信的抽象：
   1. 共享地址空间：load、store、原子的swap
   2. 信号传递：send、receive调用库函数

13.1.5.1 Shared Address Model

1. 每个处理器都可以访问机器上的任何一个物理地址
2. 每个进程都可以访问和别的进程共享的数据
3. 数据的传输：load、store
4. 数据的大小：byte、word、cache blocks
5. 使用虚拟内存，将虚拟空间映射到本地/远程物理空间
6. 应用memory层级模型
   1. 通信会将数据移动到本地的cache
7. 对于分布式内存架构，需要一个layer(硬件/软件)，做透明的地址映射
8. 重点是：数据的一致性、数据保护
9. 对于多机系统来说，地址的映射是由软件完成的，通常是OS的一部分
10. scalability是有限的，因为通信方式与处理器的地址空间紧密的联系在一起

13.1.5.2 Message Passing Model

1. 整个计算机（CPU、内存、I/O设备）作为显式I/O操作进行通信
   1. 本质上是NUMA，但集成在I/O设备与内存系统之间
2. 发送指定远程计算机上的本地缓冲区+接收进程
3. 接收指定远程计算机上的发送进程+放置数据的本地缓冲区
   1. 通常发送的信息包含process tag
   2. 接收在tag上有规则：match 1，match any
   3. 同步：当发送完成时，当缓冲区空闲时，当请求被接受时，接收等待发送
4. 发送+接收=>memory-memory copy
   1. 其中每个副本提供本地地址，并且执行成对同步

13.2 Cache coherence 一致性问题

SMP的特性：

1. 有限的处理器数量
2. 足够大的cache：提供更大的memory bandwidth
3. UMA：uniform memory access time

Cache coherence

Synchronization：

1. 原子的读/写操作

内存一致性模型：

1. 处理器必须以什么样的顺序观察别的处理器写的数据
2. 读和写之间的关系是什么样的

coherency的意义：

1. 严格定义：所有的read必须返回最新的write数据
2. 更优的定义：所有的write必须最终被read看到，所有的write以一种正确的顺序被看到(串行)
3. 两条规则去实现：
   1. 如果P写了x，P1要读x，只有当read和write分开足够远时，P的write才能被P1的read看到
   2. 写到同一个地方的数据必须串行起来，以一种相同的顺序被看到
      1. 只会看到最新的写

cache coherence的定义：

13.2.1 硬件Coherence协议

1. Snooping算法：Snoopy Bus
   1. 所有对数据的请求都要发给所有处理器
   2. 处理器监听是否有对数据的请求与其相关，如果于其相关，则修改自己的cache中的数据
   3. 需要广播的机制
   4. 如果有bus，则work well
   5. 适用于小规模的机器
2. Directoy-Based Scheme：discuss later
   1. 有一个中央的目录，知道哪一个处理器拥有哪一段地址
   2. 如果需要修改数据，则向中央目录发送点对点请求
   3. 中央目录将该请求发送到每个与其相关的处理器
   4. 只有当处理器不在一个bus上时，才更优

13.2.2 Snoopy协议

1. Write Invalidate协议：
   1. 多个reader，单一writer
   2. 写到shared data时，会发送一个invalidate的消息，给所有的cache
   3. 当cache读到invalidate的数据时，就会发生miss
      1. write-through：内存总是最新的
      2. write-back：先看别的cache中，是否有当前数据的最新copy
2. Write Broadcast协议：
   1. 写的时候，会将数据发送到bus上，处理器用该数据更新自己的cache
   2. 不会导致新的miss
3. 写的串行化：通过bus访问实现
4. 总结：
   1. 所有的cache会看到所有的bus事件，并进行响应
   2. 协议依赖于bus事件的全局可见性
   3. 由于bus上只能有一个数据，因此可以强制串行write

示例：write-back cache、write invalidate

1. 最后一次读X时，让其它的cache中进行一次write-back，然后从memory中读取X

示例：write-back cache、broadcast

1. 广播时，会将内存中的数据也修改了(事实上的through)