Skip to content

Chapter 04 Processor Architecture

4.1 Y86-64 指令集体系结构

4.1.1 程序员可见状态

"程序员" 指写程序的人, 也可以是产生机器代码的编译器.

  • 15 个程序寄存器: 省略了 x86-64 中的 %r15 (用作无寄存器)
  • 3 个 1 位条件码: ZF, SF, OF (没有 CF)
  • PC: 存放当前正在执行指令的地址.
  • 内存: 抽象成一个很大的字节数组
  • 状态码 stat.

4.1.2 Y86-64 指令

只包含 8 字节整数操作.

  • halt: 停机指令. 代码 00
  • nop: 无操作. 代码 10
  • mov 操作
    • rrmovq: 从寄存器到寄存器. icode = 2. 第二个字节为 rA|rB 指示了两个寄存器, 因为一共就 15 个寄存器(加上1个空寄存器是16个), 所以可以用一个一位十六进制数编码, 两位十六进制数刚好是一个字节. 根据 ifun 表示传送条件. 特别地, ifun=0 表示无条件传送
    • irmovq: 从立即数到寄存器. icode = 3, ifun = 0. rA=F(空寄存器), 后面还有一个 8 字节立即数 V.
    • rmmovq: 从寄存器到内存. icode = 4, ifun = 0. 后面还有一个立即数表示内存偏移量. 注意无论是 rmmovq 还是 mrmovq 偏移量都是加在 rB 上.
    • mrmovq: 从内存到寄存器. icode = 5, ifun = 0.
  • OPq: 两个寄存器的整数操作, 结果存放在 rB 中, 会设置条件码. icode=6, 根据 ifun 表示是哪一种操作
  • jXX: 跳转指令. icode = 7, 根据 ifun 表示跳转条件.
  • cmovXX: 就是上面所说的 rrmovq 的 ifun != 0 的时候.
  • call: 无寄存器指示符. 将返回地址入栈, 然后跳转到 Dest
  • ret: 无寄存器指示符. 从栈中读出返回地址, 出栈并返回.
  • pushq: 将 rA 中的内容入栈. rB=F
  • popq: 将 rA 中的内容入栈. rB=F

4.1.3 指令编码

OP 中的 ifun:

  • 0: addq
  • 1: subq
  • 2: andq
  • 3: xorq

条件传送和跳转中的 ifun:

  • 0: 无条件
  • 1: 小于等于 (le)
  • 2: 小于 (l)
  • 3: 等于 (e)
  • 4: 不等于 (ne)
  • 5: 大于等于 (ge)
  • 6: 大于 (g)

注意条件中加起来是 7 的刚好是相互取反. 比如 1 是小于等于, 6 就是不小于等于即大于.

寄存器标识符对应:

记忆方法:

  • 8-F 刚好对应 r8-无寄存器(原来的 r15)
  • 0-7 的寄存器末尾按照字典序逆序排列, x->p->i.
  • x 的中间字母是 acdb, p 的中间字母是 sb, i 的中间字母是 sd.

所有分支指令和调用指令的目的都是绝对地址, 整数采用小端法编码, 当指令书写时, 立即数的字节要以相反的顺序出现

CISC vs 早期 RISC

  • 指令数量: CISC 较多
  • 指令延迟: CISC 较长
  • 编码: CISC 可变长度编码, 1-15字节. RISC 固定长度编码, 通常都编码为 4 字节
  • 寻址: CISC 有变址寄存器和伸缩因子, RISC 只有基址和偏移量寻址
  • 内存与寄存器: RISC 只能对寄存器进行算术和逻辑运算, 允许使用内存的只有 load/store, 因此也被称为 load/store 体系结构
  • 可见性: CISC 对机器级程序来说实现细节不可见, RIS 可见.
  • 条件码: CISC 有条件码, RISC 无条件码
  • 密集: CISC 栈密集, RISC 寄存器密集, 因此 RISC 通常有更多寄存器.

4.1.4 Y86-64 异常

状态码 Stat 描述了程序运行的总体状态.
- Stat=1: AOK (ALL OK) 正常操作
- Stat=2: HLT (Halt) 遇到 halt 指令
- Stat=3: ADR (Address) 遇到非法地址
- Stat=4: INS (Instruction) 遇到非法指令

4.1.5 Y86-64 程序

Y86-64 汇编代码完整程序实例:

以 . 开头的是汇编器伪指令, 告诉汇编器调整地址. 比如 .pos 0x200 告诉汇编器从 0x200 地址开始以便插入数据或代码. 注意如果是在机器代码中, array 里面的元素也是按小端法书写的.

pushq %rsp 和 popq %rsp

pushq %rsp 会将 rsp 的原始值存入栈中, 再将 rsp-8. popq %rsp 会令 rsp = 栈顶元素, 并且不再 +8.

4.2 HCL

4.2.1 组合电路

逻辑门: AND门, OR 门, NOT 门

逻辑门只对单个位的数进行操作, 而不是整个字.

HCL 中, bool 表示一位数据, 所有字级信号都声明为 int 而不指定字大小.

组合逻辑电路表达式

Terraform
1
bool eq = (expr);

选择表达式:

Terraform
1
2
3
4
5
6
[
    select1 : expr1;
    select2 : expr2;
    ...
    selectk : exprk;
]

每种情况都有一个布尔表达式 select_i 和整数表达式 expr_i, 第一个求值为 1 的情况会被选中. 因此几乎所有情况表达式最后一个 select 都是 1, 表示前面都未发生的默认情况.

通过逻辑门和选择表达式的组合, 可以构造 ALU. 具体实现超出了我们的讨论范围.

集合关系表达式

Terraform
1
bool s = code in {1, 2}

这个代码的意思就是 s = code == 1 || code == 2

4.2.2 存储器和时钟

组合电路本质上来讲不存储任何信息, 因为它们只是简单地响应输入信号, 产生输出.

为了产生时序电路, 我们必须引入按位存储信息的设备, 它们都是由同一个时钟控制的, 时钟是一个周期性信号, 决定什么时候把新值加载到设备中, 有两类存储设备:
- 时钟寄存器(简称寄存器)存储单个位或者字.
- 随机访问存储器(简称内存)存储多个字. 用地址来选择该读哪个字. 这里包括 1) 处理器的虚拟内存系统.(它可以看作一个巨大字节数组) 2) 寄存器文件 (标号0-14), 用 rA rB 作为地址访问.

可以看到硬件和机器级编程的"寄存器"是有细微差别的. 硬件中的寄存器可以理解成只存储一个信息(直接把输入和输出连接到其他地方). 机器级寄存器是存放在寄存器文件中的. 为了区分我们称他们为 硬件寄存器 和 程序寄存器.

一些单独的信息比如状态码, PC, 条件码就会使用硬件寄存器来存储. 一些多个信息的聚合比如寄存器文件就会用随机访问存储器来存储.

寄存器文件有两个读端口, 一个写端口. srcA, srcB 指明要读哪个寄存器, valA, valB 是读出来的值. dstW, valW 分别代表要写哪个寄存器和写入的值.

读是不需要时钟的, 可以看成是一个组合电路, 寄存器文件响应 srcA, srcB 的输入并输出 valA, valB. 可能一开始的信号并不稳定, 但经过一段时间的延迟后输出最终会稳定下来.

写是需要时钟的, 因为电路的信息一直在变化, 我们不可能在还未稳定的时候就写入信息(比如说可能由于电路还未稳定 dstW 一开始还是一个奇怪的值), 这样会破坏数据. 通过在时钟上升沿写入我们保证写入的信号是一个稳定的信号. 这样就不会破坏数据了.

4.3 Y86-64 的顺序实现

按顺序执行, 是流水线化的第一步.

4.3.1 将处理组织成阶段

处理一条指令包含很多操作, 我们将它们划分为统一的几个阶段.
- 取指 (fetch): 从内存地址为PC处读取指令字节, 得到 icode, ifun. 如果需要可能还会读出寄存器指示符字节 rA|rB. 常数字 valC. 读取后计算出下一条指令地址 valP. valP = PC + 当前指令的长度
- 译码 (decode): 从寄存器文件读入最多两个操作数, 得到 valA和/或 valB. 通常是读入 rA, rB 指明的寄存器, 不过有时候读寄存器 %rsp (4)
- 执行 (execute): ALU 要么执行指令指明的操作, 要么增加和减少栈指针. 得到的值称为 valE. 在这里可能设置条件码. 对条件传送指令, 会在这个阶段检查条件码和传送条件. 同样跳转指令是否跳转也是在这个阶段检查.
- 访存 (memory): 可以将数据写入内存, 或者从内存读出数据. 读出的值称为 valM.
- 写回 (write back): 最多可以写两个结果到寄存器文件.
- 更新PC (PC update): 将 PC 设置成下一条指令地址.

Warning

ALU 的第一个输入和第二个输入最后得到的结果是 第二个输入 OP 第一个输入. 所以我们书写的时候将 valB 写在前面

可以看到, 对内存的操作我们一般都在执行阶段算出内存地址 valE. 在访存阶段读或写 valE 处的内容.

(这里书上 popq 访存阶段 valM<-M_8[valA] 又写成 valE 了...)

注意, 在这里对栈的操作中, 译码阶段我们需要读 %rsp 处的内容以便在执行阶段计算出栈地址.

因为我们都是对 valB 来作为地址偏移的基址, 所以 valB 肯定是读 %rsp 的内容, 注意在 popq 的指令中, 我们要读两遍 rsp 的内容. 因为在访存的阶段我们要读的是还未 +8 的 %rsp 的内容. 为什么不继续使用 valB? 可能是为了兼容吧.

注意这里 popq 有两个写寄存器操作, 执行顺序是先写 valE, 再写 valM. 这一点在后面非常重要.

从这两个操作的具体执行阶段我们也可以看出为什么 pushq %rsp, popq %rsp 的行为是那样的.

4.3.2 SEQ 硬件结构


- 白色方框表示时钟寄存器: PC 是 SEQ 中唯一的时钟寄存器
- 浅灰色表示硬件单元, 如内存, ALU, 我们将它们看成黑盒子.
- 控制逻辑用灰色圆角矩形表示.
- 白色圆圈是信号的名字
- 宽度为字长的数据用中等粗度的线表示
- 宽度为字节或更窄的数据用细线表示
- 单个位的连接用虚线表示.

4.3.3 SEQ 的时序

每个周期开始时, 状态单元是根据前一条指令设置的. (上一个周期前一条指令产生出要写入的值, 这个周期的时钟上升沿写入)

4.3.4 SEQ 的实现

参见 seq_std.rs

本质上是理解前面各个指令的各个阶段的实现方式.

4.4 流水线通用原理

4.4.1 计算流水线

吞吐量: 每秒执行的指令数

延迟: 执行一条指令所需要的时间


这个未流水线化的设计
- 吞吐量为 1/320ps = 3.12GIPS (GIPS是每秒千兆条指令, 即10^9)
- 延迟为 320ps.


通过流水线化
- 吞吐量为 1/120ps=8.33GIPS
- 延迟为 3*120ps=360ps

可以看到, 吞吐量增加, 延迟也稍微增加, 这是因为我们每划分出一个阶段都需要有一个流水线寄存器来保存这个阶段计算出的值.

4.4.2 流水线的局限性

  • 时钟周期必须设置为延迟最高的那个阶段.
  • 流水线过深, 延迟过高.

4.5 Y86-64 的流水线实现

4.5.1 SEQ+: 重新安排计算阶段

移动 PC 更新阶段, 使它在一个时钟周期开始时执行, 这样方便我们进行流水线化, 因为流水线要一直取出新的指令.

SEQ -> SEQ+ 是一个很通用的改进的例子, 这种改进称为电路重定时. 重定时改变了一个系统的状态表示但不改变它的逻辑行为, 通常用它来平衡一个流水线系统中各个阶段之间的延迟.

4.5.2 插入流水线寄存器

PIPE-

这里黑色的方框代表流水线寄存器, 每个寄存器有多个字段, 用白色方框表示.

流水线寄存器按如下方式编号:
- F: 保存PC的预测值
- D: 位于取指和译码之间, 保存最新取出的指令信息, 即将由译码阶段处理.
- E: 译码和执行之间.
- M: 执行和访存之间.
- W: 访存和反馈路径之间. 反馈路径执行寄存器写, ret 操作还要为 PC 提供返回地址.

4.5.3 对信号重新排列和标号

使用大写字母开头代表流水线寄存器内的内容, 小写字母表示每个阶段刚计算出来的信号

因为只有 call 和跳转指令需要 valP 的值, 这些指令又都不需要 valA 的值, 所以可以吧 valP 合并到 valA 信号中.

4.5.4 预测 PC

对于会实现控制转移的指令, 我们有如下方式预测:
- call: 总是 valC
- jmp: 总是 valC
- jXX: 总是预测选择分支, 即 valC
- ret: 我们无法预测, 所以我们简单的将流水线暂停处理新指令, 直到我们从栈中取出了下一条指令的地址.

4.5.5 流水线冒险

当相邻的指令出现一些相关时, 由于流水线化的设计导致我们无法提前得知某些数据的信息或者对某些数据进行更改, 就会出现冒险. 冒险分为数据冒险和控制冒险.

数据冒险:

在 0x017 addq 命令进入D阶段时, 我们需要读入 %rdx 和 %rax 的数据, 在这个例子中 %rdx 和 %rax 已经执行完了写回(W) 阶段, 所以不会造成数据冒险.

在这个只有 2 个 nop 指令的示例中, 0x016 处的 addq 在 D 阶段准备读入 %rax 数据的时候, %rax 的新内容还未写入寄存器中(因为要等 W 阶段执行完的下一个周期的上升沿才会写入), 这就造成了我们读出的是 %rax 的旧值.

这个例子说明, 如果一条指令的操作数被它前面三条指令的任意一条修改的话, 就会出现数据冒险.

Note

通过对数据冒险类型的列举, 假设程序不会自我修改代码, 我们可以得出我们只需要处理寄存器数据冒险, 控制冒险, 以及正确处理异常.

用暂停避免数据冒险:

暂停和气泡是配合使用的. 最后一个暂停的阶段后面的指令不能继续执行, 所以我们要插入气泡 bubble 实现 nop(不修改程序员可见状态)

这里 F, D 阶段 stall, E 阶段插入一个 bubble

用转发避免数据冒险:

暂停的代价太大, 我们发现其实 %rax, %rdx 的新值在 E 阶段已经被计算出来了, 但是到 W 阶段才写回. 所以不如在 E 阶段直接将计算出来的值转发到 addq 的 D 阶段.

通过转发
- e_valE: E阶段刚计算出来的寄存器值
- m_valM: M阶段刚从内存中读出的寄存器值
- M_valE: M阶段保存的E阶段还未写入寄存器的值
- W_valM: W阶段还未写入寄存器的内存中的值
- W_valE: W阶段还未写入寄存器的 E 阶段计算出来的值.

因此, 对于刚刚那个例子. 如果没有 nop, 我们可以直接转发 e_valE 计算出的新 %rax 到 addq 的 valA 中. 如果有一个 nop, 对 %rax 的更新来到了 M 阶段, M_valE 保存了 %rax 的新值, 可以转发. 如果有两个 nop, 对 %rax 的更新来到了 W 阶段, W_valE 保存了 %rax 的新值, 可以转发. 这样我们正确处理了数据冒险.

加载/使用数据冒险:

有一类数据冒险不能单纯使用转发来解决, 因为这类数据的新值不是在 E 阶段而是到 M 阶段才从内存中被读出. 这样我们就不能利用 e_valE 实现相邻指令之间没有 nop 的数据转发了.

所以对于上一条指令从内存中读数据到寄存器中, 下一条指令立刻使用该寄存器值作为源操作数的指令, 我们需要插入一个 bubble. 这样到 M 阶段内存里的值就会被读出来然后可以转发到 D 阶段中.

避免控制冒险:

当处理器无法根据取指阶段的当前指令来确定下一条指令的地址时, 就会出现控制冒险. 控制冒险只会发生在条件跳转指令和 ret 指令.

对于 ret 指令, 我们只能等待它到达 W 阶段使用 W_valM 更新 PC. 因此中间要插入三个 bubble.

Note

虽然让后面的指令继续执行到 D 阶段不会改变程序员可见状态, 但是最后我们还是要通过 bubble 取消这些指令(可以参见分支预测错误的处理方式), 所以不如直接不取这些指令, 在 F 阶段插入 bubble.

为什么不在 m_valM 计算出来的时候就转发到 PC 中?

内存取数是一个非常耗时的过程, 如果我们在计算出来的时候就转发到 select PC 模块, select PC 模块就必须等待内存取出数后才能计算出正确的 PC, 然后才能继续进行取指阶段的后续操作. 这就导致取指阶段的时间过长.

那么为什么寄存器数据冒险就可以直接使用 ALU 计算出来的 e_valE 呢, 这是因为我们转发到 valA 的时候其实已经进行到了 D 阶段的末尾, 后面没有耗时的操作了(D 阶段真正耗时的操作是从寄存器文件读出数据, 而这不需要等待转发的数据).

总而言之, 转发什么数据到哪里, 关键还是要看 PIPE 实现的硬件结构图, 看哪里有信号指向前面的模块.

对于分支预测错误, 首先我们要明白发现分支选择错误的时机是在 jXX 的 E 阶段访问条件码寄存器的时候, 这时候我们的流水线取出了两条错误的指令, 分别正在执行 F 和 D 阶段.

幸运的是, 由于错误的指令还未执行到 E 阶段, 我们还未对任何程序员可见状态造成影响, 所以我们可以简单的取消这两条错误指令, 并修改 PC 为真正的指令地址. 取消指令可以通过在 D 和 E 阶段加入 bubble, 这样它们就不会继续执行了.

暂停和气泡

对于执行到某个阶段一条指令, 如果现在不是它执行的时机, 但是我们希望它后面重新执行, 我们就需要暂停这个阶段和它前面的阶段, 这样就不会有新的指令进来覆盖掉我们的指令. 后面的一个阶段要插入 bubble, 这样后面的阶段就不会被执行. (load/use hazard)

对于我们希望丢弃的指令, 我们就可以不需要暂停前面的阶段, 只要在后面插入 bubble 就行了. (wrong branch prediction)

4.5.6 异常处理

回顾异常的三种情况:
- halt
- 非法指令
- 非法地址

第一个细节问题, 对于一个流水线内, 可能有多个指令导致异常, 例如 F 阶段的非法指令, M 阶段的非法地址, 这时候我们应该报告 M 阶段的异常, 因为它是比 F 阶段先执行的.

第二个细节问题, 一个异常可能由于分支预测错误被取消, 因此, 我们不能一旦发现异常就立刻停止.

第三个细节问题, 发生异常我们不希望后面的指令执行, 所以也要求后面的指令不能对任何程序员可见状态造成影响. 例如, 一个 M 阶段才被发现的异常, 同一周期 E 阶段可能会更改条件码寄存器, 这是我们不希望的.

为了避免上面这三个细节问题, 我们让异常状态随着流水线一直延续. 当我们在 M 阶段或 W 阶段发现异常的时候, 我们可以肯定它们不会由于分支预测错误被取消了 (因为它们肯定执行完了 E 阶段), 所以我们可以断定程序出现了异常, 这时候我们就要禁止任何对程序员可见状态(条件码寄存器, 内存)的更改.

4.5.7 PIPE 各阶段的实现

参见 pipe_std.rs

4.5.8 流水线控制逻辑

对于 ret 指令, 实际上我们无法在 F 阶段插入 bubble, 所以我们需要暂停 F 阶段, 并在 D 阶段插入 bubble

对于异常指令到达访存阶段, 我们会:
- 禁止执行阶段指令设置条件码
- 向 M 阶段插入 bubble, 避免下一条指令数据写入
- 当写回有异常指令, 暂停写回阶段, 因而暂停了整个流水线.

每个流水线寄存器有两个控制输入暂停和气泡. 正常下都设置为 0, 如果暂停设置为 1. 寄存器保持它的状态. 如果气泡设置为 1, 寄存器状态变为某个复位配置. 两个都设置为 1 被认为是一种错误.

控制条件的组合

在实际中, 有可能出现多种冒险组合的情况.

图中只有组合 A 和 B 可能同时出现, 其他都是互斥的.

观察组合导致的暂停气泡结果, 我们认为暂停或气泡会覆盖正常状态.

对于组合A, 是预测错误+ret, 我们发现这样会导致 F 暂停, D,E 气泡. 这其实相当于本来预测错误会继续取出两条指令但是现在少取了一条, 这也没关系, 因为后面我们的 E 阶段气泡会取消掉 ret 指令, 这样下一个周期 F 还是可以使用正确的地址而不会被暂停.

对于组合B, 是加载使用+ret, 发生的情况是加载指令设置 %rsp, 然后 ret 指令使用 rsp. 我们希望 ret 指令阻塞在 D 阶段. 但是我们发现这两者组合会导致 D 阶段出现气泡+暂停. 因此这种情况需要特殊处理.

4.5.9 性能分析

由于气泡的存在, 流水线不能每个时钟周期发射一条新指令的目标, 可以通过插入气泡的数量衡量效率的损失. 一个 load/use 冒险会产生一个气泡, 一个返回指令会产生三个气泡, 一个预测错误会产生两个气泡

CPI: 每指令周期数. 1.0+C_b/C_i