计算机体系结构

流水线

• 核心思想： 提升指令吞吐量，不是单个指令执行时间
• 将指令执行划分多个阶段，相比单周期CPU,指令进入/离开的频率更快

关于流水线的时钟周期

为什么流水线的时钟周期 > （单周期的时钟周期）/ （流水段个数）？ 三个原因：

1. 每个流水段都增加了寄存器，增加了延迟 墙
2. 每个流水段的时间长度不同，时钟周期按照最长的计算
3. 流水线还增加了其它线路（前地旁路等） 这些因素对于理想的流水线阶段数量有重要影响，随着流水段的级数增加，时钟频率的增益会减少

关于流水线的CPI

为什么流水线的CPI>1?

• 对于简单流水线，CPI=1+stall惩罚
• Stalls是为了解决流水线中的危害 - Hazard:影响流水线正确执行的一些危害（数据相关或控制相关）; - Stall: 为了让流水线正确执行引发的停顿. 流水线会停顿，阻塞

指令相关性及危害

• 指令相关性:两条指令之间存在关联关系。
  • 数据相关：两条指令使用相同的存储位置
  • 控制相关：一条指令影响另一条指令是否能够执行 分支/中断
  • 结构相关： 两条指令使用同一种流水线资源
• 危害：有些相关性会导致指令执行错误
• 哪些数据相关性会导致流水线停顿？
  • 写后读 是对某个值的真正依赖，必须解决
  • 写后写和读后写是因为寄存器数量不够引起的，它们依赖某个寄存器名字，而不是一个值。
• 解决写后读（RAW）
  • 暂停流水线，直到计算出结果 stall
  • 一旦数据计算完成，尽快将数据前递到先前的流水线阶段 bypass

Cache

主要参数的影响

1. Capacity
   1. 总容量 更大缓存可以更好利用时间局部性
   2. Cache增大会增加访问延迟
      1. 越小越快⇒ 越大越慢
      2. 访问延迟可能会增加关键路径的延迟
   3. Cache太小
      1. 无法有效利用时间局部性
      2. 有用的数据频繁被替换
2. 关联度
   1. 每个组里能放几个Blocks
   2. 关联度更高
      1. 命中率越高
      2. 访问时间更长
      3. 硬件更复杂 （更多比较器）
   3. 随着关联度增加，命中率增长趋缓
3. Block Size
   1. 增大block size有正反两方面影响
      1. 空间预取
         1. 地指相邻的blocks被提前预取
         2. 有利于降低miss rate
      2. 产生干扰
         1. 能放入cache的blocks变少了 数量
         2. 可能增加miss rate
         3. 特殊情况 全局只有一个block
   2. 两方面影响同时存在
      1. 具体哪个影响大取决于workload

VM

• 程序使用虚拟地址，内存使用物理地址，虚拟地址到物理地址的转换以page为粒度。映射不需要保持物理页连续，虚拟页可能没有映射到任何物理页；没有映射的虚拟页可能在磁盘上或者还未被使用过。

虚拟内存的好处

• 多程序之间隔离
  • 每个程序以为自己有2的N次方大小的内存空间
  • 防止程序互相访问彼此的内存空间
• 安全保护
  • 每个页有读/写/执行的权限 os设置
  • 由硬件保证
• 进程间之间通信
  • 将同一个物理页映射到多个虚拟地址空间
  • 或者通过unix mmap()共享文件

大页的优缺点

• 减少页表空间 ： 表项变少了；
• 页表层数更少：查找速度快；
• 页内空间浪费更严重 分配2MB 的页但只使用了 5KB
• 实现更复杂：os会寻求其他措施提高page利用率

页表大小计算

地址转换

• 概念上
  • 地址转换需要在每一次内存(cache)访问之前进行
  • 每次转换都要访问页表
  • 效率低
• 现实中
  • Translation Lookaside Buffer 缓存转换结果
  • 只有在TLB未命中的时候才去访问页表

TLB miss

• TLB miss: 地址转换结果不在TLB 在页表
  • 两种处理方式 都相对比较快
• 基于硬件
  • 页表的基地址由寄存器保存，硬件负责遍历页表取回数据
  • 优点：延迟：避免了操作系统程序 avoids pipeline flush 硬件访问速度快
  • 缺点： 页表格式必须是硬编码的
• 基于软件
  • 采用简短的操作系统程序遍历页表并更新TLB，os参与，中断的方式，给硬件发一个消息
  • 页表格式可以灵活定义
  • 缺点：读了1-2次内存访问+os call(pipeline flush) 上下文切换
• 当前基于硬件的方式更受欢迎

乱序执行

out of order execution.

• 也称为指令动态调度：由硬件在运行时完成
• 简单描述
  • 指令译码完成后，放入保留站 （指令缓存空间）
  • 每个周期，检测保留站中每条指令的源操作数
  • 如果指令的源操作数都准备好了，发送指令到执行单元（如果有空闲）
  • 指令完成后，从保留站删除
• 好处
  • 当某条指令的执行时间很长时，允许后面的不相关指令先执行
  • 有相关性的指令给无相关性的指令让路
• 条件
  • 需要为数据的生产和消费方建立关联关系 ：寄存器重命名，每个数据都和一个tag关联
  • 需要缓存那些操作数还没有准备好的指令：放到保留站
  • 指令需要检测其操作数状态（是否准备好）：当数据准备好时，会广播其tag;所有指令将其tag与广播的tag进行比较，如果相同，表明数据准备好；
  • 当所有数据都准备好时，需要将指令发送到执行单元：所有操作数都准备好时，指令会被唤醒；如果多条指令同时被唤醒，需要选择一条发送到执行单元

Tomasulo 算法

• 核心思想

  • 每个计算单元维护一个保留站（一组物理寄存器）：用于缓存操作数还没有准备好的指令
  • 通过寄存器重命名消除WAW and WAR相关性 ：将寄存器ID重命名为保留站ID
  • 乱序发送指令

• 硬件结构：

  • 保留站
  • 寄存器组
  • Bus 广播结果 带上提供该结果的保留站ID

• 具体做法

  • 如果保留站仍有空余表项，将指令送入保留站，并进行寄存器重命名；
  • 否则 stall
  • 对于在保留站中的每一条指令：
    • 监听总线
    • 当发现操作数的tag时，获取数据并保存在保留站中
    • 当所有操作数都准备好了，指令变为可发送
  • 发送指令到运算单元
  • 当指令运算结束
    • 将计算结果在总线上广播
    • 寄存器文件连接着总线
      • 寄存器增加了一个tag,记录该寄存器在等待哪个保留站ID的值
      • 如果寄存器的tag和总线的tag匹配上了，将值写入寄存器（同时清除tag）
    • 回收保留站表项（清除该指令）

精确异常

当异常发生时，异常之前的指令应该执行完，异常之后的指令不应该执行。 非精确异常：乱序执行，后面的指令比前面的指令先执行完，修改了系统状态（寄存器或者内存） ：Tomasulo算法不能保证精确异常

• 乱序执行如何保证精确异常？
  • 思路：利用缓存(ROB)临时记录执行结果，等到前面所有指令提交(commit 阶段)之后，再提交该指令结果。
  • 总结：乱序执行，但顺序提交。

Reorder Buffer

每一项内容：目标寄存器ID、指令结果、指令op

• 指令进入保留站的同时，也进入ROB (两个cache
• 寄存器ID重命名为ROB ID ，不是保留站ID
• 指令在写回阶段将结果写入ROB，而不是寄存器/内存 后面的指令可以从ROB读取这些结果
• 当指令commit 才将结果写到寄存器/内存，commit后 将指令从ROB删除

只要指令尚未commit 就不会修改系统状态，这样就很容易取消指令（比如遇到异常）

带ROB的乱序执行 总结

• Issue:发送指令到保留站 （若保留站和ROB都空余），用一个ROB表项存储结果；读操作数 检查是否READY
• Execute: 若所有操作数都已经准备好，执行指令；否则监听总线，若发现操作数就读取 并保存在保留站
• write back:发送结果到总线，释放保留站表项；ROB更新结果
• Commit:若前面指令都已将commit,且没有发生异常，将结果从ROB写入register/memory,释放ROB表项；若发生异常 清空指令列表和ROB等

指令并行高级技术 （多发射）

方案：

• 超标量（superscalar）:每周期发射多条指令（个数不固定），由编译器或硬件调度
• 超长指令字（very long instruction words） 将多条指令打包成一条固定格式的长指令，由编译器静态完成 两者对比

Superscalar	VLIW
在一个时钟周期内发射多条指令，多个执行单元并行处理这些指令	将多条指令打包成一个超长指令字
动态调度：硬件在运行时进行指令的调度和重排，提高指令级并行性。	静态调度：编译器负责指令打包和调度，硬件设计简化
复杂的硬件设计	复杂的编译器设计
较高的功耗和热量	低功耗和高效性

指令并行高级技术（多线程）

细粒度多线程

在简单流水线上交错执行不同线程的指令，单核多线程（一个alu）

• 优点：
  • 能掩盖短时间和长时间 流水线停顿，（一直有其他进程切换pc） 例如 内存操作 有依赖关系的指令 分支指令等；因为线程切换足够频繁，所以每次切换不需要刷新流水线。
  • 更能充分利用硬件资源
• 缺点：
  • 单个线程执行时间变长
    • 一个没有stall的线程可能频繁被切换出去，被来自其他线程的指令拖慢。
  • 必须有足够多的线程，否则无法填满流水线

粗粒度多线程

• 仅当遇到stall时间较长的事件时才切换线程
  • 例如cache miss;
  • 一个线程可以在连续多个周期使用流水线
  • 可以掩盖长停顿
• 可能的stall事件
  • cache misses
  • synchronization events 读取空的队列等待数据而阻塞 同步事件
  • 浮点运算
• 同一时间流水线只能被一个线程占用，不允许多个线程的指令共同在流水线中
• 只有发生cache miss时才切换线程
• 发生线程切换时，被换出线程未完成的指令将被清除，换入线程将占用流水线
• 优点：
  • 线程切换不用那么频繁
  • 不会拖慢线程，因为线程只有stall时才会被切换出去
  • 关键线程需要优先级
• 缺点
  • 发生切换时，指令必须排空并重新填充；流水线较深时影响较大，适合stall时间很长的情况；
  • 公平性：stall较少的线程占用流水线时间较长，其他线程可能饿死
    • 解决方案：占用时间超过一定额度强制切换

缓存一致性

中心化共享内存架构 问题：如果多个处理器同时拥有同一个cache block,如何保证一致性？ 本地更新会导致cache状态不一致，cache的写策略

• 一致性定义：对于相同的内存位置，所有处理器看到的值是一致的
• 基本策略：将最新值（写操作）及时更新到所有cache copy
• 写操作的两种处理方式
  • update protocol 将新数据广播给所有cache copy
  • invalidate protocol 让所有其他copy 无效，只保留一份有效的本地copy,并更新它，没有了这个数据，下一次从内存中读

消息如何传播？

• snoopy bus 侦听式
  • 处理器在总线上 广播数据更新
  • 每个处理器都侦听其他处理器的动向
  • 所有请求通过总线实现序列化 完全按顺序
• 总线侦听的作用
  • 当处理器写本地copy时，会广播到所有其他cache,所有cache将看到相同的更新：写传播；
  • 当两个处理器几乎同时向各地的本地copy写入相同数据时，一个处理器会赢得总线，并向所有其他缓存广播其更新信息，另一个处理器必须等待直到它能够获取总线
    • 这保证了所有其他缓存看到相同的顺序
    • write serialization

Write-back Cache :MSI 协议

• 每个cache block有3种状态：
  • Invalid:本地没有copy
  • Shared:本地有一个只读copy,该copy有最新的数据
  • Modified:本地有全局唯一的valid copy(其他cache无copy),该copy处于dirty状态（可能内存不一致），本地可写（不需要通知他人）
• 表格
• 存在的问题
  • 如果本地有全局唯一copy,处于shared状态
    • 此时发生本地write,会在总线上广播BusRdX,自己升级为modified,然后再写
    • 因为全局只有一个copy,所以没有必要广播消息

解决方案：MESI

• 想法：增加一个状态 Exclusive,表明该copy是全局唯一并且值是最新的 clean
  • exclusive状态：可以直接变为M状态，不需要广播信息
• 如何变成E状态？全局仅有一个clean的copy时
  • 如果read一个block的时候其他cache中都没有，那么该block直接为E状态
  • 系统中原本有多个S状态的copy,但是因为cache替换，全局仅剩一个S状态的copy,该copy也应该变为E状态
• 存在的问题
  • shared状态要求数据总是最新的clean
    • 所有shared copy都有最新的数据，包括内存
  • 问题：一个block处于M状态（表面数据脏的），如果其他cache读该block,那么需要将data先写回内存，否则大家都变为shared状态时，数据都是dirty的，
  • 为什么这是一个问题？
    • 如果每次从M→S都将数据写回内存，其实很多都是没必要的 →因为很快别的处理器可能又更新了数据。

内存一致性

顺序一致性 最严格

• 一个多处理器系统被称为sequentially consistent SC ，如果满足下面两个条件：
  • 所有处理器的操作按照某种顺序执行
  • 来自同一个处理器的操作按照指令顺序执行
• 这是一种内存顺序模型，或内存模型
  • 所有处理器看到的内存指令执行顺序相同，例如 所有内存操作按照某种顺序执行（global total order）
  • 在这个执行顺序中，每个处理器的操作按照指令顺序执行
• 优缺点
  • 简单、直观
    • 与程序员直觉一致
    • 容易解释程序行为
  • 在同一次执行中，所有处理器看到相同的内存指令执行顺序
    • 无正确性问题
  • 如果多次执行，每次执行可以观察到不同的执行顺序（每次都是sequentially consistent）
    • 调试仍然很困难，每次执行指令顺序不一样
• 缓存一致性和内存一致性区别
  • coherence仅关注一个内存地址的值
  • consistency关注所有内存地址的访问顺序

GPU

设计思路

1. 简化流水线，增加核数
   1. 对流水线进行瘦身，去掉乱序执行，分支预测等复杂逻辑，节省的空间用来增加大量核心
2. 单指令多线程
   1. 多个核心共用一条指令，将管理指令流的成本/复杂性分摊到多个运算单元
3. 同时驻留大量线程
   1. 在单核心上维护远多于执行单元的线程数，以实现细粒度线程调度掩盖高延迟操作