ouuan’s blog

CS:APP 第四章学习笔记

创建于修改于访问量169标签csapp标签学习笔记标签WIP

CS:APP 第四章 “Processor Architecture” 的学习笔记。

这章的主要内容为一个简化的指令集 Y86-64 的设计以及 Y86-64 处理器的实现（顺序实现和 pipeline 实现）。

The Y86-64 Instruction Set Architecture

这部分定义了在这一章中用作演示的名为 “Y86-64” 的玩具 ISA。

Y86-64 程序状态

  • 15 个寄存器（x86-64 的寄存器除去 %r15，为了简化编码）
  • 3 个 status flag: ZF、SF、OF
  • program counter: PC
  • memory
  • status code: Stat，用来表示程序正常运行或发生了异常

Y86-64 指令

Y86-64 指令大致上是 x86-64 的一个子集，但在 operand 等方面有一些简化或区别。

operand 与 x86-64 的区别是：

  • Immediate、Register、Memory 都只有 64 位的版本
  • Register 只有 15 个
  • Memory 不支持 (, ri, s) 的部分，只能是 Imm/(rb)/Imm(rb)

condition code 只有六个，即 signed compare: le/l/e/ne/ge/g

指令列表，以及与 x86-64 的区别：

  • irmovq/rrmovq/mrmovq/rmmovq，即将 movq 按 operand 类型拆成了四个指令
  • addq/subq/andq/xorq，它们只接受寄存器作为 operand，且只设置 ZF、SF、OF 三个 status flag
  • jmp/jle/jl/je/jne/jge/jg，包括 jmp 在内都只能跳转到固定的地址，不接受寄存器作为 operand，且这个地址是绝对地址而非相对于 PC 的地址
  • cmovle/cmovl/cmove/cmovne/cmovge/cmovg，它们只接受寄存器作为 operand
  • call: 地址是绝对地址
  • ret、pushq、popq、nop: 与 x86-64 基本相同
  • halt: 停止运行，将 status code 设为 HLT

Y86-64 指令编码

Y86-64 通过对指令的简化，同时也使编码得到了简化，但相应地使得编码不紧凑，会有浪费。

CS:APP Figure 4.2 简明地展示了 Y86-64 的指令编码：

Y86-64 指令编码示意图

指令类型的编码

指令编码的第一个 byte 表示指令的类型。这个 byte 的高位叫做 code，低位叫做 function，其中 function 只在某几个指令有用。特别地，rrmovq 和 cmovXX 的 code 是相同的，这表示 rrmovq 可以看作一种特殊的 cmovXX。

算术运算的 function: add 0, sub 1, and 2, xor 3

condition code 的 function: le 1, l 2, e 3, ne 4, ge 5, g 6；jmp 的 function 为 0

Register Specifier Byte

除了 jXX 和 call，指令编码的第二个 byte（如果有）的高低位分别表示一个 register identifier。

register identifier 从 %rax 为 0 到 %r14 为 E；F 表示不是寄存器。

Constant Word

在 irmovq、rmmovq/mrmovq、jXX/call 中，分别有一个 8-byte 的 constant word，用来表示 immediate value 或地址，byte ordering 是 little endian。

Y86-64 异常

status code Stat 有四种可能的取值：

  • AOK: 正常
  • HLT: 执行了 halt 指令
  • ADR: 访问了不合法的地址
  • INS: 指令编码不合法

在 Y86-64 中，遇到异常后处理器会立即停止运行。

Y86-64 程序

CS:APP Figure 4.8 展示了一个完整的 Y86-64 程序：

完整 Y86-64 程序的汇编与机器码

可以下载 Y86-64 tools 并使用 yas 进行汇编，使用 yis 模拟运行。编译 yas 时 需要添加 -fcommon 编译选项。

对 %rsp 进行 push/pop

pushq %rsp、popq %rsp 这两条指令虽然没什么用，但它们的行为可能有歧义，所以在设计 ISA 时明确规定它们的行为是有必要的。

Y86-64 遵循和 x86-64 相同的规则：pushq %rsp 会将旧的（没有减 8 的）%rsp 的值入栈，popq %rsp 相当于 mrmovq (%rsp), %rsp。

Logic Design and the Hardware Control Language HCL

这一章中使用玩具语言 HCL (hardware control language) 来描述 Y86-64 处理器的逻辑设计。（与之类似但不是玩具的语言，例如 VHDL、Verilog 等，叫做 “hardware description language (HDL)”。）

逻辑门

CSAPP Figure 4.9:

与或非逻辑门

  • 图中只展示了输入个数为 2 的 AND 和 OR，但可以有更多输入
  • 一旦输入改变，逻辑门的输出很快就会随之改变

组合逻辑电路

组合逻辑电路即由若干逻辑门组合而成的电路，它的特点是无状态，输出仅与输入有关，输入改变后输出很快就会随之改变。

在 HCL 中，用逻辑表达式来表示组合逻辑电路，例如 bool eq = (a && b) || (!a && !b) 表示计算 a、b 是否相等的电路。因为它表示的是电路而不是计算，在这条语句之后，一旦 a、b 的值发生改变，eq 的输出也会改变（和 Vue 的 computed 类似）。

以 word 为单位进行操作的电路

在处理器的设计中，经常需要对一个 word 而非单个 bit 进行操作。

在 HCL 中，一般使用大写的名称表示 word，例如: bool Eq = (A == B) 表示计算 word A、B 是否相等的电路，可以实现为判断每个 bit 是否相等再 AND。

Multiplexor (MUX)

multiplexor (MUX) 的功能是通过信号输入的值来在其它输入中选择一个作为输出，word-level 的 MUX 电路如图 (CSAPP Figure 4.13)：

word-level MUX 电路

在 HCL 中，使用 case expressions 表示 MUX，例如

word Mux = [
    !s1 && !s0: A;
    !s1: B;
    !s0: C;
    1: D;
];

表示一个由 s0 和 s1 控制的、在 A、B、C、D 中选一个作为输出的 MUX。

case expression 在逻辑上的语义是依次判断每个条件，以第一个满足的条件作为输出，类似于 Rust 的 match。

下面的 HCL 代码表示计算 A、B、C 中的最小值：

word Min3 = [
    A <= B && A <= C: A;
    B <= C: B;
    1: C;
];

Arithmetic/logic unit (ALU)

ALU 是用来进行算术/逻辑运算的组合逻辑电路元件，它接收两个 data input 以及一个表示进行何种运算的 control input，输出运算的结果。

测试值是否属于集合

在 HCL 中，可以使用 in 来表示测试值是否属于集合的电路，例如:

bool s1 = code in { 2, 3 };
bool s0 = code in { 1, 3 };

Memory and Clocking

组合逻辑电路是无状态且实时更新的；与之相对，memory 可以存储状态，但更新由 clock 控制。

这一章中会用到的 memory 有两大种三小种：

  • clocked register: 存储一个值，有一个输入和一个输出。输出即存储的值，而每次 clock rise 时会将存储的值修改为输入。
  • random access memory:
    • register file: 存储 15 个值（在 Y86-64 处理器中），有两个 read port 和一个 write port：
      • 每个 read port 有一个输入 src 表示 register identifier，有一个输出 val 表示这个 register 存储的值，且 src 改变后 val 会立刻改变。
      • write port 有一个输入 dst 表示 register identifier，另有一个输入 val 用于写入。每次 clock rise 时，如果 dst 不是 F 就会将 val 写入相应的 register。
    • data memory: 存储很多个值，用地址进行索引。
      • 有一个地址输入 address。
      • 有一个信号输入 write 表示进行写入而非读取。
      • 有一个数据输出 data out。若 write 为 0，data out 会立刻输出 address 处存储的值。
      • 有一个数据输入 data in。若 write 为 1，在 clock rise 时会将 data in 写入 address 处。
      • 有一个信号输出 error，在 address 不是合法地址时输出 1。

可以看到，这几种 memory 的共同点是读取是实时的，但写入由 clock 控制。

在 Y86-64 的程序状态中，寄存器存在 register file 中，status flags、program counter、status code 存在 clocked register 中，memory 存在 data memory 中。

Y86-64 处理器还有一个额外的 read-only instruction memory 用来读取指令，而在真实的处理器中这是和内存一体的。

Sequential Y86-64 Implementations

这一节会实现一个名为 SEQ 的顺序执行的处理器。在这个处理器中，指令是按顺序一条接着一条执行的，且每条指令都会在一个 clock cycle 内执行完毕，这要求 clock cycle 很长，会导致处理器的执行很慢，下两节将对此进行优化。

指令执行的阶段划分与具体操作

将指令的执行划分为多个阶段，可以使行为有很大差别的不同指令有一定的统一性，方便硬件实现。

本节会将指令执行划分为六个阶段：

  1. Fetch: 将指令编码中不同部分的值读取出来
  2. Decode: 读取寄存器的值（我感觉 fetch 和 decode 这两个名字互换一下才比较对 🤔）
  3. Execute: 执行运算
  4. Memory: 写入或读取内存
  5. Write back: 写入寄存器
  6. PC update: 更新 program counter

每个指令每阶段的具体操作如图（CS:APP Figure 4.18~4.21、Solution 4.17）：

OPq, rrmovq, irmovq

rmmovq, mrmovq

pushq, popq

jXX, call, ret

cmovXX

SEQ 的主体电路

CS:APP Figure 4.23 大致展示了 SEQ 的主体电路：

SEQ 主体电路

其中蓝色的元件是 black box，灰色的元件会在后面进行设计，还有部分电路连接没有画出来。

这个电路大概看着有个印象即可，细节会在后面说明。

SEQ 的时序控制

在 SEQ 中，每个时钟周期执行一条指令，而时钟控制的只有各种 memory 的写入，memory 的读取和运算都是用组合逻辑电路实现的，虽然在逻辑上有执行顺序，在电路上却是同时执行的，可以看成一个关于 memory 的函数。

也就是说，整个执行过程是：读取 memory 并计算出需要写入 memory 的值，然后在 clock rise 时执行写入，从而读取到新的 memory 的值而执行下一条指令。

为了这个设计能够实现，一条重要的原则是 “No reading back”，即一条指令不能先更新再读取同一个值。例如，在 pushq 中，不是先更新 R[%rsp] 再写入 M[R[%rsp]]，而是先算出 valE，再写入 M[valE]，最后将 valE 写入 R[%rsp]。又例如，有的指令会修改 status flags，有的会读取，但没有指令既修改又读取。

因为运算都是同时进行的，执行的六个阶段实际上是六个部分。

SEQ 的具体实现