计算机体系结构

导航

• 导航
• 成绩构成
• Fundamentals of Computer Design
  • Introduction
• chpater2–Memory Hierarchy
  • Introduction of memory
  • Technology Trend and Memory Hierarchy
    • Memory Hierarchy
      • Inclusive Hierarchy
      • Exclusive Hierarchy
  • four questions for cache design
    • Block replacement
    • write policy
  • Memory system performance
  • Virtual Memory
    • TLB
• chapter3–Instruction Level Parallelism
  • dynamic vs static
    • 1-bit predictor
    • 2-bit predictor
    • generalized to local history
    • correlating predictor
    • tournament predictor
  • dynamic sheduling overcome datahazard
    • 动态调度的思想
    • Tomasulo Algorithm
  • Hardware-Based speculation
    • Tomasulo and extended to handle speculation
  • exploiting ILP using Multiple Issue and static scheduling
    • purpose of multiple-issue processors
    • two types of multiple-issue processors
• chapter4–Data-Level Parallelism Architecture
  • 4.1 SIMD:vector processor
    • RISV-V指令
    • vector processor
    • Vector processor example- Cray-1
    • memory:bank
    • improve the performance of vector process
  • 4.2 SIMD Instruction set extension for multimedia
  • 4.3 GPU
  • 4.4 Loop-Level parallelism
• chapter 5–TLP
  • 5.1 Multiprocessor
    • introduction
    • the catagory of multiprocessor
    • 编程模型
    • 多处理器带来的问题
  • 5.2 Cache Coherency
    • condition of coherency
    • how to achieve coherency
    • snooping protocol
    • MESI protocol
    • cache coherency distributed shared memory

成绩构成

1. 作业加实验加考试。
2. 实验尽早完成（三周以后得分可能会下降，两周内完成较好），可能会有bonus。

Fundamentals of Computer Design

Introduction

• 体系结构=指令集+实现指令集

chpater2–Memory Hierarchy

Introduction of memory

• 存储器层次结构：
  • register->cache->main memory->disk
  • 离cpu越近，越小，访问速度越快
• 两个设计关键点：
  • 时间局部性
  • 空间局部性

Technology Trend and Memory Hierarchy

Memory Hierarchy

Inclusive Hierarchy

• 定义：上级缓存包含所有下级缓存的数据副本（如 L3 包含 L2 和 L1 的数据）。

• 特点：

  • 数据冗余：L3 是 L1/L2 的超集。
  • 一致性维护：通过监听 L3 即可判断数据是否存在（简化多核一致性协议如 MESI）。
  • 替换开销：L3 替换时需失效所有下级副本。

• 优点：

  • 简化多核一致性管理（如 Intel CPU 的 L3 缓存）。
  • 快速失效（Invalidation）广播。

• 缺点：

  • 存储容量浪费（L3 部分空间用于备份）。

• 示例：

1
2
3
4

L1: [Data A]
L2: [Data A]
L3: [Data A, B, C]  # 必须包含 L1/L2 的所有数据

Exclusive Hierarchy

• 定义：上级缓存与下级缓存数据互斥（如 L2 不包含 L1 的数据）。

• 特点：

  • 无冗余：数据仅存在于某一级缓存。
  • 高利用率：有效缓存总容量 = L1 + L2 + L3。
  • 一致性复杂：需跨多级缓存查询数据状态。

• 优点：
  最大化存储利用率（适合容量敏感场景）。

• 缺点：
  一致性协议复杂（如 AMD 早期 CPU

four questions for cache design

• 见计组笔记

Block replacement

• Lru本质上是stack replacement algorithm
  • $B_t(n)$ represents the set of access sequences contained in a cache block of size n at time t.
  • $B_t(n)$ 是 $B_t(n+1)$的集合，也就是n增大，命中的块一定包含原来的块，也就是说命中率会上升。
• FIFO本质上是队列replacement algorithm

解释：我感觉这张ppt的图很棒，很巧妙地使不同大小的block对于同一个sequence采用lru策略的结果放在了同一张图中。用栈来模拟LRU，栈顶是最近访问的，栈底是最久未访问的。

• 使用门和触发器实现LRU算法
  • 让任何两个cache块之间两两结对，用一个触发器的状态来代表两个块的先后访问顺序（比如1表示A刚被访问，0表示B刚被访问）。通过门电路对触发器的状态进行逻辑组合找到LRU块。
  • 假设有p个cache blocks,我们需要$\binom{p}{2}=p * (p-1)/2$

write policy

• 对于write miss
  • write around(no write allocate)
    • 直接在内存中写
  • write allocate
    • 将写的块读在缓存中再写
• 对于write hit
  • write through（通常和write around搭配）
    • 同时写回cache和内存
  • write back（通常和write allocate搭配）
    • 直接在cache中写，并标记为赃块

Memory system performance

Virtual Memory

TLB

• 本质上就是对page table做一次cache
• 而page table本质就是一个哈希表，从虚拟地址映射到物理地址

chapter3–Instruction Level Parallelism

dynamic vs static

• 根据branch的历史数据来预测
  • 使用branch prediction buffer indexed by lower portion of branch address and 使用一位来表示taken/untaken status(bit 1 for taken,bit 0 for untaken)

1-bit predictor

• 状态机如下(利用历史数据来预测)
  
• 在循环中使用1-bit predictor时，因为在循环中我们的选择肯定是连续相同的，则预测会非常准确。
• 然而如果是摇摆的，有可能会导致预测率相当低，远不如静态预测。

2-bit predictor

• 状态机如下(利用历史数据来预测)
  
• 在摇摆情况下，预测率会更高，达到50%。
• 我们可以再进行泛化到n-bit，只是存储开销更大

generalized to local history

• 前面提到的predictor其实都是在考虑前一天的预测，我们可以考虑更多的天数

correlating predictor

• 这也叫做二级预测器，例如(1,2)预测器在预测一个分支时，利用最近一个分支的行为在一对二位分支预测器中选择。一般情况下(m,n)预测器利用最近m个分支行为在$2^m$个分支预测器中选择，其中每一个分支预测器都是n位。
• 一个(m,n)预测器的位数:$2^mn$由分支地址选中的预测项的数量
• 相关预测器的一个著名例子就是gshare预测器，
  

tournament predictor

• 通常使用一个全局预测器和一个局部预测器。全局预测器使用最近的分支历史作为预测器的索引，局部预测器使用分支地址作为索引。
• 一个例子
  

dynamic sheduling overcome datahazard

动态调度的思想

• 想要成功实现动态调度，我们仍然使用顺序指令发射，但我们希望一条指令能够在其数据操作数可用时立即开始执行，这样的流水线实际是乱序执行(out-of-order execution)
• 但是乱序执行可能导致WAR冒险和WAW冒险：(利用寄存器重命名可以解决)

1
2
3

fdiv.d f0,f2,f4
fmul.d f6,f0,f8
fadd.d f0,f10,f14

• 为了能够乱序执行，我们将简单的五级流水线ID分成两个阶段(发射、读取操作数)。

• 记分牌技术：

  • 结构（注意有两个乘法部件）:
    
  • 例子:

  1 2 3 4 5 6

  FLD F6, 34(R2) FLD F2, 45(R3) FMUL.D F0, F2, F4 FSUB.D F8, F2, F6 FDIV.D F10, F0, F6 FADD.D F6, F8, F2

  • instruction status
    
    解释：指令1已经执行完成，scoreboard没有其信息。指令2没有完成WB，后面的指令要使用指令2的结果，由于数据冒险所以还没有进行读取操作数阶段。指令6是加法操作，此时存在结构冒险还没有进入发射阶段。
  • Function Component status
    
    解释：busy代表当前这个单元是否有指令正在使用，op表示这个单元正在被哪类指令使用。Fi,Fj,Fk代表源操作数和目的操作数(Fi为目的操作数)。Qj，Qk表示表示源操作数来自哪个部件。Rj，Rk表示源操作数的状态（注意当指令正在执行时，源操作数的状态为no）。
  • 在scoreboard算法中，只要我们成功过了op阶段，那么多条成功经过op阶段的指令都能并行执行，这样相比较传统的流水线也有大幅度提升。
  • 总结工作要点：
    • 一条指令能否发射，一看是否有功能部件空闲可用，这个信息包含在功能状态中；二看指令要写的寄存器是否正要被别的指令写，这个信息包含在寄存器状态中，观察这个信息是为了解决 WAW 冒险。
    • 一条指令能否读数，要看记分牌是否提示源寄存器不可读，如果不可读，就说明该寄存器将要被别的前序指令改写，现在的指令要等待前序指令写回，观察这个信息是为了解决 RAW 冒险。
    • 一条指令能否写回，要看是否有指令需要读即将被改写的这个寄存器，具体一点来说，就是要观察标记 Yes 的Rj、Rk 对应的寄存器里是否有当前指令的目的寄存器，如果有，就说明有指令需要读取寄存器的旧值，这样一来我们就要等指令读完旧值之后再写回，观察这个信息是为了解决 WAR 冒险。
    • 所以本质上以上三种数据冒险，记分牌的策略都是通过阻塞解决。

Tomasulo Algorithm

• scoreboard并不能解决WAR和WAW这两个冒险(源于名称依赖)，只是单纯的通过阻塞解决。

• 理解寄存器重命名如何消除冒险

  • 代码示例

  1 2 3 4 5

  fdiv.d f0,f2,f4 fadd.d f6,f0,f8 fsd f6,0(x1) fsub.d f8,f10,f14 fmul.d f6,f10,f8

  • 我们现在考虑三个名称依赖：fadd.d使用f8时的WAR冒险，fsub.d使用f8时的WAR冒险（写后读，反依赖:两条指令共享同一个存储位置），fadd.d可能在fmul.d之后完成导致的WAW冒险（输出依赖）。
  • 这三个名称依赖都可以通过寄存器重命名消除。假定存在两个临时寄存器:S和T。

  1 2 3 4 5

  fdiv.d f0,f2,f4 fadd.d S,f0,f8 fsd S,0(x1) fsub.d T,f10,f14 fmul.d f6,f10,T

• 保留站

  • 保留站在一个操作数可用时马上提取并缓冲它，这样就不需要从寄存器中获取操作数，这也就意味着我们的相应的数据进入保留站后数据直接拷贝而不依赖于寄存器（因为记分牌的数据还一直依赖于寄存器），这样tomasulo利用保留站就能很好地避免因为“假依赖”导致阻塞，从而提高效率。
  • 发射指令时，会重命名待用操作数的寄存器说明符，改为提供寄存器重命名功能的保留站的名字。

• 寄存器状态表

  • 指令在发射的时候会更新寄存器状态表，如果后序指令和前序指令的目的寄存器重合了，就用后序指令的写信息标志寄存器，表示只会把后序指令的计算结果写进寄存器，这样可以解决写后写冒险；

• 使用Tomasulo算法的浮点单元基本结构
  

• 每一条指令经历的步骤

  • 发射阶段：从指令队列的头部获取下一条指令，如果有一个匹配的保留站为空则将这条指令发射到这个站中。如果没有空闲保留站则说明存在结构冒险，该指令停顿。如果操作数不在寄存器中，则一直跟踪将生成这些操作数的功能单元。并且在这一阶段对寄存器进行重命名。
  • 执行：如果还有一个或多个操作数不可用，则在等待计算的同时观察公共数据总线。当一个操作数变为可用时，就将它放到任何一个正在等待它的保留站中。当所有操作数可用时，则在功能单元执行运算。
  • 写结果：在计算出结果后，将其写到CDB上，再从CDB传送到寄存器和所有等待这一结果的保留站。存储指令一直缓存在存储缓冲区中，直到待存储值和存储地址可用为止，然后在有空闲存储器单元时立即写入结果。

• tomasulo算法的实例

  • cycle1:
    
    解释：在第一个周期，第一条指令发射到保留站中，并且保留站的信息更新（注意此时的Vk与记分牌不同，直接从寄存器堆中拷贝数据，A是地址偏移立即数）.寄存器结果状态也相应地更新。
  • cycle2:
    
    解释：第二个周期，第二条指令发送到保留站，此时第一条指令刚刚执行完偏移量的计算并更新相应的A.
  • cycle3:
    
    解释：第三个周期。第三条指令发送到保留站中。第一条指令执行完毕执行过程。第二条指令完成偏移量的计算并更新相应的A。寄存器结果状态完成相应的更新。
  • cycle4:
    
    解释：第四个周期结束。第一条指令完成写回阶段，此时结果立马传递到CDB，然后CDB立马传递到相应的寄存器中。第二条指令执行完毕执行过程。第三条指令因为还需要第二条指令的结果所以被阻塞。第四条指令发送到保留站，此时发现第四条指令的相应的保留站中的寄存器的值已经是最新的值。
  • cycle5:
    
    解释：第五个周期结束。第二条指令完成写回阶段。此时第三条指令和第四条指令都同时从CDB中获取到寄存器的值。并且更新这两条指令需要执行的周期数（更新在Time中，从下一周期开始执行阶段）。第五条指令因为保留站有空余于是发射到保留站中。

• 常瑞老师的例子:
  
  解释：从这个例子中我们更能看清楚Tomasulo算法的执行过程，因为我们的保留站很充足，所以我们的指令都顺利发射。同时对于load和store指令因为我们还需要计算存储位置，所以我们在第三个周期才开始执行EX阶段。在写回阶段，因为我们在CDB上传递需要时间，相当于在第四周期结束时我们的值可以传递给保留站，从下一个周期开始进行执行阶段。

Hardware-Based speculation

• 因为前面的无论是scoreboard还是tomasulo算法，我们得到结果以后都直接将最终结果写入了寄存器，所以是乱序提交的。
• 但是我们从动态调度中延伸到推测，因为使用旁路值类似于执行一次推测寄存器读操作，所以我们现在的寄存器的值必须确保是正确的值，所以有了我们接下来的操作。
• 我们使用Reorder Buffer来使指令执行完成的顺序也是顺序的。结果先写到reorder buffer中，再从reorder buffer中取到结果，写入到寄存器中。我们将每条指令加上一个commit状态，对于某条指令，只有它前面的指令都commit，它才能commit。
• Hardware-based speculation combines three key ideas:
  • dynamic branch prediction to choose which instructions to execute
  • speculation to allow the execution of instructions before the control dependences are resolved (with the ability to undo the effects of an incorrectly speculated sequence)
  • dynamic scheduling to deal with the scheduling of different combinations of basic blocks

Tomasulo and extended to handle speculation

• Issue:get instruction from FP Op Queue
• Execution
• Write result
  • 在与该指令相关的操作完成到该指令提交之间，ROB保存该指令的结果。
  • ROB是指令的操作数来源，就像Tomasulo算法中的保留站提供操作数一样。
• Commit:update register with reorder result
  • 实现speculation背后的关键思想是允许指令乱序执行，但强制它们按顺序提交，并防止任何不可撤销的操作（如更新状态或获取异常），直到指令提交。
  • 重新排序缓冲区（ROB）以与Tomasulo算法中的保留站扩展寄存器集相同的方式提供额外的寄存器。
• 在这种进化版的tomasulo，保留站也发生了变化(Qj,Qk字段以及寄存器状态字段中的保留站编号被ROB条目编号代替，以及将Dest字段加到保留站中，Dest指定的是保留站条目产生的结果在ROB中的目的地)

ROM与保留站:

exploiting ILP using Multiple Issue and static scheduling

purpose of multiple-issue processors

• 之前做的工作都是为了减小cpi，使其接近理想cpi
• 允许多条指令在一个周期发射，能够使理想cpi的下限降低小于1

two types of multiple-issue processors

• Superscalar（超标量）–硬件方法
  • 定义：处理器在同一个周期内同时发射n条指令(n:1-8)
  • 最好让所有的功能单元都能同时工作
  • 静态调度的superscalar
    • 处理器通过硬件实现在发射指令时已经知道指令之间的依赖关系，并将指令打包
    • 发射过程分为两个阶段：决定打包的packet中的指令；并观察packet中指令之间的冲突。（这个issue check过程需要在一个周期内完成，所以clock cycle time不可能很小）
    • 面临的问题:
      • 发射阶段完成所有冲突检查：
      • 相应的寄存器读写口、result buses等硬件都需要提升
  • 动态调度的superscalar

chapter4–Data-Level Parallelism Architecture

4.1 SIMD:vector processor

• 向量处理器是SIMD的一种实现:单独的一条指令能够对一串数据（向量）进行操作
• 两种类型:
  • memory-memory:直接操作内存中的数据，这需要比较高的内存带宽，检查memory的依赖也较为复杂
  • vector register:先将数据加载到寄存器中再进行操作，其实就和我们以前了解到的架构一样，后面我们讨论的都默认是vector register

RISV-V指令

• 规则:当两个操作数都是向量时，后缀使用.VV;当第二个操作数为标量时，后缀使用.VS;当第一个操作数为标量时后缀使用.SV
• 一个例子（双精度a x X加Y）

1
2
3
4
5
6
7
8

vsetdcfg 4*FP64  #启用四个双精度浮点向量寄存器
fld f0,a
fld v0,x5
vmul v1,v0,f0
vld v2,x6
vadd v3,v1,v2
vst v3,x6
vdisable #禁用向量寄存器

vector processor

• 结构：

  • vector register
  • vector functional units
  • vector load-store units
  • scalar registers:single element for FP scalar or address

• 处理方式

  • Horizontal processing method

    • vector的处理对于每一行从左到右处理，逐个计算出后再进行下一行。
    • Problems with horizontal processing:
      • When calculating each component, RAW correlation occurs, and the pipeline efficiency is low.
      • If a static multi-functional pipeline is used, the pipeline must be switched frequently; the throughput of the pipeline is lower than that of sequential serial execution.如果是静态的多功能流水线，我们每次都要排空才能进行下一次运算，这样的效率很低。
      • The horizontal processing method is not suitable for vector processors.

  • vertical processing method(全向量并行)
    

    • 如上图所示：The vector calculation is performed vertically from top to bottom in a column manner.要等加法全部都做完才能做乘法。只存在一个数据相关，执行两次功能切换。

  • vertical and horizontal processing method

    • 分组计算，组内采用纵向计算，组间采用横向计算
    • 核心思想：当我们的N大于硬件最大向量长度(MVL)时进行分组处理（也就是strip mining）。$N=S * n + r$
    • 伪代码:

    1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18

    # 处理完整段 for s from 0 to S-1: start = s × n end = start + n - 1 # 段内垂直处理 K[start:end] = B[start:end] + C[start:end] D[start:end] = A[start:end] × K[start:end] # 处理剩余元素 if r > 0: start = S × n end = start + r - 1 # 剩余元素水平处理 for i from start to end: K[i] = B[i] + C[i] D[i] = A[i] × K[i]

    • Data related:S+1,Function Switch:2(S+1)

Vector processor example- Cray-1

• 结构：有 8 个向量寄存器，每组向量寄存器有 64 位。有 12 条单功能流水线，可以并行工作。Each vector register Vi has a separate bus connected to 6 vector functional units。不同的功能需要的周期不同。
• 特点：
  • Vi conflict: The source vector or result vector of each vector instruction working in parallel uses the same Vi.也就是说：当向量寄存器有依赖的时候，后续指令要在前面指令的结果出来之后再执行。这里并不是等前面的向量的每一个元素都计算完，而是等前面的向量的第一个元素计算完就开始计算第一个元素的后续指令，等第二个元素计算完就开始计算第二个元素的后续指令，以此类推。其实也是一个流水线的思想。
  • functional conflict：Each vector instruction working in parallel must use the same functional unit.如果我们的相关功能部件被占用，我们只能等待前面指令全部完成，才能开始下面的指令。
• instruction types of CRAY-1

memory:bank

• bank(存储体)：为向量载入/存储单元提供带宽。通常存储器系统在开始运行时存在总存储器延迟。
• 存储体基本定义:将物理存储器划分为多个独立的逻辑单元。这些单元能够：独立地进行读写操作、并行地响应多个访问请求、减少访问冲突。
• 当处理向量体系结构中的多维数组时需要引入步幅(stride)的概念:对于要收集到一个寄存器中的元素之间的距离，因为在RV64V中可寻址单位为1字节，所以步幅的单位也是字节。
• 理解了步幅的概念后我们就可以明白非单位步长可能带来的冲突：因为我们可能频繁访问同一个存储体，所以当满足以下公式时就可能造成冲突:$\frac{number of bank}{least common multiple of bank and stride} \lq bank busy time$

improve the performance of vector process

• optimzation 1:vector chaining
  • 流水线中forwarding的思想迁移到了向量计算中，我们在得到结果后便可以将数据通过chain给到需要用到该数据的功能单元。如果没有链接技术，前一条指令要等到最后一个分量完成才能进行下一条指令，现在我们第一个分量完成就可以开始下一条指令的第一个分量的运算。
  • 有了chaining，我们便能提高计算效率
  • convey:set of vector instructions that could potentially execute together(对于一个指令序列，如果存在结构冲突则不能放在一个convey中，数据依赖可以通过vector chaining实现)
  • chimes:sequences with read-after-write dependency hazards placed in same convey via chaining.chimes 是指在一个 convey 中，由于读后写（RAW）依赖而必须按顺序执行的指令序列。
  • chime:执行一个convey需要的时间单元
• optimization 2:conditional execution
  • 如果我们在向量运算中引入了conditional execution，显而易见地提高效率。否则的话存在条件分支，可能产生完全不同的执行路径，但是引入控制语句后，所有的元素都执行相同的指令，保证了向量化的进行。(控制流转化为数据流)
  • how to implement conditional execution?:引入masked register and masked vector instructions.先对每个向量判断是否满足条件，将结果保留在掩码寄存器中。实际操作时再带上掩码进行向量计算。
• optimization 3:sparce matrices
  • 核心技术：vector scatter/gather.gather:从内存中将元素收集到向量寄存器中。scatter:将向量寄存器中的元素写入内存中。通过这两个操作，向量处理器就可以访问稀疏矩阵中的数据。
• optimization 4:Multi-lane implementation
  • 核心思想:每个时钟周期处理多个元素
  • RV64V指令集的特性：所有向量算术指令只允许向量寄存器的第N个元素与其他向量寄存器的第N个元素进行运算。根据这一个特性可以简化并行向量单元的设计：我们可以在单元构造多个multi-lane,其中每一条通道对应一条流水线。每一条通道保存所有向量寄存器的固定位置的元素，这种分配方式也就使某个通道内部的计算不需要和其他通道完成通信。
  • 包含四条通道的向量单元的结构
    

4.2 SIMD Instruction set extension for multimedia

4.3 GPU

4.4 Loop-Level parallelism

• 这一节主要研究基于循环的并行性
• 主要看循环的迭代之间是否有数据依赖(Loop-carried dependence)
• 如果循环间存在依赖，我们可以通过改写来解决

1
2
3
4
5
6
7
8
9
10
11
12
13
14

for(i=0;i<100;i++)
{
  A[i] = A[i]+B[i];
  B[i+1] = C[i]+D[i];
}
//上面的语句存在循环依赖，因为我们的第一条语句需要用到上一个循环的第二条语句的内容
//为了将数据依赖删除，我们可以进行下面的改写
A[0] = A[0]+B[0];
for(i=0;i<99;i++)
{
  B[i+1] = C[i]+D[i];
  A[i+1] = A[i+1]+B[i+1];
}
B[100] = C[99]+D[99];

chapter 5–TLP

• 线程级并行(更大的颗粒度并行)，在软件的层次上面下功夫。

5.1 Multiprocessor

introduction

• 为什么使用多处理器
  • 提升性能
  • 单处理器性能瓶颈
  • 多处理器属于MIMD架构

the catagory of multiprocessor

• 对称多处理器(SMP):处理器数目较少，所以处理器可以共享一个集中式存储器并且平等的访问它。（我们这种处理器在物理上是一个连续的存储器，只是逻辑上通过interconnect使得访问对应的存储器的位置）同样这种处理器可以被称为UMA(uniform memory access)一致存储器访问:所有处理器访问存储器的延迟都是一致的。
• 分布式共享处理器(DSM)也叫做NUMA:我们的处理器更多，为了支持更多的处理器，存储器必须分散在处理器之间（和UMA相比我们在物理上就已经将存储器进行分割，如果要访问需要通过interconnect来访问其他存储器，显而易见访问存储器的延迟不一致）。

编程模型

• multiprogramming:无交流
• shared address space:通过内存共享
• Message Passing:通过消息传递
• Data Parallellel:通过数据并行

多处理器带来的问题

• 有限的程序并行性：重新写代码
• 处理器之间的通信延迟
  • 硬件解决办法:缓存共享数据（带来了缓存一致性的问题）
  • 软件解决办法：同步

5.2 Cache Coherency

• 在体系结构中cache coherency更多地关注一个位置上的不同处理器观测值的一致性。
• memory consistency model：，它定义了在并发系统中，内存操作（读和写）对于不同处理器而言，它们被看到（观察到）的顺序。

condition of coherency

• 处理器P对位置X的读操作跟在P对X的写操作之后，并且在P的写操作和读操作之间没有其他处理器对X执行写操作
• 一个处理器对于位置X的读操作紧跟在另一个处理器对X的写操作之后，并且在两个处理器对X的访问之间没有其他处理器对X执行写操作。
• 对于同一位置的写操作是被串行化的

how to achieve coherency

• 为多个处理器保持缓存一致性的协议成为缓存一致性协议(cache coherency protocol)
  • 监听策略(snooping)，通常运用在共享存储器
  • 目录策略(directory-based)

snooping protocol

• 概述
  • 处理器之间可以通信，通过总线进行监听
  • 如果某个处理器写入X，需要通知其他的处理器
  • 其他处理器监听通知，并作出相应操作
    • 如果自己的cache也存在X，根据以下策略进行处理:
      • write invalidate:将X的副本置为无效，做一个无效化操作，把包含X的block踢出cache。
      • write Broadcast:通过正在写入X的处理器将X的副本更新，这也就说明其他处理器能够更快的响应，因为数据还是在cache里面。
• 具体实现协议–利用状态机(针对每一个cache block)
  • 每一个cache存在三种状态:
    • invalid:无效(valid=0)，数据无效，当前处理器不能对该缓存块进行读写操作。
    • shared:共享(dirty=0,valid=1)，说明数据是干净的，与主内存中的对应数据一致。
    • exclusive:独占(dirty=1,valid=1)，说明数据是脏的且只有当前处理器的缓存中持有该数据的有效副本。
  • 每块缓存会接受两种信号
    • 来自自己处理器的信号(cpu read,cpu write)
    • 来自其他处理器的信号，也就是从bus获取的信号(bus read,bus write)，注意只有总线上的事务地址 ​​与本地Cache Line的地址完全匹配​​ 时，才会触发一致性动作。
  • 当接收到自己处理器的信号的状态机:
    
    解释：我觉得想要了解状态机的工作原理最重要的是理解三个状态的具体含义。
    在invalid状态没有数据，如果要读数据就说明我们要进行同步操作转移到shared操作，写操作对于这个cache而言都会进入独占状态，并且还需要通知总线(释放write miss on bus)。
    在shared状态同理，只是如果进行读操作就没有必要状态转移。
    在exclusive状态，说明此时我们独占这个数据，如果发生read miss，说明这个cache line中没有我们想要的数据，我们需要替换这个赃块(write back)，并且需要通知总线(释放read miss on bus)，转移状态到shared。如果发生write miss，需要通知总线(释放write miss on bus)，然后进入exclusive状态。
  • 当接收到总线的信号的状态机:
    
  • 例子
    
    解释：前面是P1处理器对于写的相关反馈，当P2处理器read miss之后，P1处理器监听到总线上的信息进行write back操作然后进入shared状态，此时P2处理器再从内存中顺利读取。再在P2处理器上执行写操作，进入exclusive状态，然后通知总线(释放write miss on bus)，P1处理器监听到总线信息以后转移状态到Invalid。最后在P2处理器执行写操作但是write miss，于是执行写回操作，内存中A1值得到更新。

MESI protocol

• 与传统的 Snooping Protocol不同，增加了一个exclusive状态。这会在一定程度上减少总线事务：当处理器首次读取一个cache block时如果其他处理器都没有缓存它，那么状态是Exclusive，此时写入时无需广播invalidate，直接升级为modified即可。
• 四个状态
  • Modified(private ,!=Memory)
  • exclusive(private ,==Memory)
  • shared(shared ,==Memory)
  • Invalid
• 相应的状态机
  

cache coherency distributed shared memory

• 使用目录协议
• 概述
  • directory:记录memory中每一个block的状态
  • information in directory
    • status of every block:shared/unncached/exclusive
      • 我们需要明白这个状态和cache block自己维护的状态的差异，directory的状态记录每个cache block的全局共享情况。
      • shared: cache block被多个处理器共享
      • uncached: cache block没有被缓存
      • exclusive: cache block被一个处理器独占
    • which processors have copies of the block:bit vector（sharers List）
    • 这个block是否是脏的
• 原理
  • 没有总线也没有广播
  • 三种处理器
    • Local node where a request originates
    • Home node where the memory location of an address is located
    • Remote node has a copy of a cache block,whether exclusive or shared
  • 在目录协议中涉及的消息
    
    解释：
    前面三个消息是缓存发布的请求，与snooping协议相比，增加了 一个消息，即invalidate。
    中间几个请求是目录向cache发送的请求，所以在我们下面的状态机中会出现这几个请求。
    最后的请求是remote cache向目录发送的请求。
  • 具体状态转化
    • 这个体系架构中cache line也同前面的snooping协议一样维护三种状态，当我们的cache接收到cpu的信息或者目录发送的信息以后会根据下面的状态机进行状态的变化。其实最主要的差异就是从shared到exclusive的write hit的情况下向home directory发送invalidate消息。
      
    • 目录也要进行相应的元信息的更新。
      
      • 对于read miss：家节点接收到信息开始查看目录，可能会存在uncached(Send Rp;转化为shared状态，更新sharers={p})/shared(Send Rp;sharers+={p})/exclusive(先向远程node发送Fetch请,get reply back from R.N.,Send RP,->Shared,更新sharers+={p})三种情况
      • 对于write miss:Uncached(Send Rp;S->Exclusive;sharers = {p}),Shared(Send Invalidate;Send Rp;S->Exclusive;sharers = {p}),Exclusive(Send Fetch/invalidate to R.N. get reply back from R.N. Send RP to P;S->Exclusive;sharers = {p})