CS:APP 第四章学习笔记

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: ZFSFOF
  • 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,且只设置 ZFSFOF 三个 status flag
  • jmp/jle/jl/je/jne/jge/jg,包括 jmp 在内都只能跳转到固定的地址,不接受寄存器作为 operand,且这个地址是绝对地址而非相对于 PC 的地址
  • cmovle/cmovl/cmove/cmovne/cmovge/cmovg,它们只接受寄存器作为 operand
  • call: 地址是绝对地址
  • retpushqpopqnop: 与 x86-64 基本相同
  • halt: 停止运行,将 status code 设为 HLT

Y86-64 指令编码

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

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

Y86-64 指令编码示意图

指令类型的编码

指令编码的第一个 byte 表示指令的类型。这个 byte 的高位叫做 code,低位叫做 function,其中 function 只在某几个指令有用。特别地,rrmovqcmovXX 的 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

除了 jXXcall,指令编码的第二个 byte(如果有)的高低位分别表示一个 register identifier。

register identifier 从 %rax0%r14EF 表示不是寄存器。

Constant Word

irmovqrmmovq/mrmovqjXX/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 %rsppopq %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) 表示计算 ab 是否相等的电路。因为它表示的是电路而不是计算,在这条语句之后,一旦 ab 的值发生改变,eq 的输出也会改变(和 Vue 的 computed 类似)。

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

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

在 HCL 中,一般使用大写的名称表示 word,例如: bool Eq = (A == B) 表示计算 word AB 是否相等的电路,可以实现为判断每个 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;
]

表示一个由 s0s1 控制的、在 ABCD 中选一个作为输出的 MUX。

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

下面的 HCL 代码表示计算 ABC 中的最小值:

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 用来读取指令,而在真实的处理器中这是和内存一体的。

data memory 的 read 信号

383 页的图中 data memory 还有一个 read 信号,但在文字说明中没有提到它的作用,而对 write 信号的说明似乎使得 read 信号无用 🤔

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 的具体实现

WIP

未完待续…… 🕊️