处理器体系结构

前言

了解了程序在机器级的表示方式和运作原理后，我们将进一步的研究处理器是如何实现指令集架构的，我们将从硬件电路开始，研究指令集架构在 cpu 内部是如何实现的。但是现在现代微处理器的体系结构是如此的精细复杂，可以称得上是人类创造出的最复杂的系统之一了，如果我们从相对熟悉的 x86-64 架构开始实现的话，可能会花上相当长的一段时间，所以我们将会实现一个受 x86-64 启发的架构，Y86-64，它是 x86-64 架构的精简版，可以让我们在实现上省去一些复杂精细的结构，在总体上对 cpu 的体系结构有个大致的了解。

Y86-64

定义一个指令集体系架构（例如 Y86-64）包括定义各种状态单元、指令集和它们得编码、一组编程规范和异常事件处理体系。

状态

在 Y86-64 中有几个可见状态，分别为：

RF：程序寄存器
CC：条件码
PC：程序计数器
Stat：程序状态
DMEM：内存

RF 中有 15 个程序寄存器：%rax、%rcx、%rdx、%rbx、%rsp、%rbp、%rsi、%rdi 和%r8 到%r14（省略了 x86-64 中的%r15 来简化指令编码）每个寄存器存储一个 64 位的字。寄存器%rsp 被入栈、出栈、调用和返回指令作为栈指针使用，除此之外其他寄存器没有固定的含义或固定值。

CC 中有 3 个一位的条件码：ZF、OF 和 SF。

PC 中存放当前正在执行的指令地址。

Stat 中的状态码表明程序执行的总体状态，它会指示程序是正常运行还是出现了某种异常。

DMEM 看作是虚拟内存系统提供的一个单一的字节数组映射，先不考虑虚拟内存的具体实现。

指令

Y86-64 中只有 8 字节整数的操作，内存引用方式也只有简单的基址加偏移量的形式，也不支持任何寄存器值的伸缩，下面是 Y86-64 中的所有指令：

4 个数据传送指令。Y86-64 将 x86-64 的 movq 分成四条指令，分别为 irmovq、rrmovq、mrmovq 和 rmmovq，在 Y86-64 中需要在前缀中显式指定源和目的的类型，i 指代立即数（immediate）、r 指代寄存器（register）、m 指代内存（memory）。
4 个整数操作指令，OPq。OP（operation）代表操作类型，分别为：addq、subq、andq 和 xorq，这些指令会设置 3 个条件码 ZF、OF 和 SF。
7 个跳转指令，jXX。jmp、je、jne、jl、jle、jg、jge。
6 个条件传送指令，cmovXX。cmovle、cmovl、cmove、cmovne、cmovge、comvg，这些指令只能从寄存器传送到寄存器。
call 指令将返回地址入栈，然后跳转到目的地址。ret 指令从调用中返回。
pushq 指令入栈。popq 指令出栈。
halt 指令停止指令运行。Y86-64 中和 halt 和 x86-64 中的 hlt 相似。x86-64 应用不允许使用 hlt，因为会使得整个系统停止运行，对于 Y86-64 来说，halt 会使得处理器停止运行，并设置状态码为 HLT。

指令编码

以下为 Y86-64 指令集字节级编码：

字节	0	1	2	3	4	5	6	7	8	9
halt	00
nop	10
rrmovq rA, rB	20	rArB
irmovq V, rB	30	FrB	V
rmmovq rA, D(rB)	40	rArB	D
mrmovq D(rB), rA	50	rArB	D
OPq rA, rB	6fn	rArB
jXX Dest	7fn	Dest
cmovXX rA, rB	2fn	rArB
call Dest	80	Dest
ret	90
pushq rA	A0	rAF
popq rA	B0	rAF

每条指令的第一个字节表明指令的类型，这个字节分为两部分：高四位为代码（code）部分，第四位为功能（function）部分。
其中功能部分 fn 的具体编码为：

整数操作指令：
- addq：60
- subq：61
- andq：62
- xorq：63
分支指令：
- jmp：70
- jle：71
- jl：72
- je：73
- jne：74
- jge：75
- jg：76
传送指令：
- rrmovq：20
- cmovle：21
- comvl：22
- cmove：23
- cmovne：24
- cmovge：25
- cmovg：26

rA，rB 为寄存器，每个寄存器使用 4 个位来编码，具体如下：

rax：0
rcx：1
rdx：2
rbx：3
rsp：4
rbp：5
rsi：6
rdi：7
r8 ：8
r9 ：9
r10：A
r11：B
r12：C
r13：D
r14：E
无寄存器：F

跳转指令使用绝对寻址的方式，不使用 PC 相对寻址。

有些指令需要一个附加的 8 字节常数，我们默认是在小端法机器上实现，所以这个常数需要按字节反序，0x0123456789abcdef 反序后为ef cd ab 89 67 45 23 01，比如：rmmovq %rsp, 0x123456789abcd(%rdx)的编码为40 42 cd ab 89 67 45 23 01 00。

异常

Y86-64 中有几个异常，如下：

值	名字	含义
1	AOK	正常操作
2	HLT	遇到 halt 指令
3	ADR	遇到非法地址
4	INS	遇到非法指令

逻辑设计和硬件控制语言（HCL）

指令集架构是通过处理器内部的数字电路实现的，我们在这里将会简单的介绍一些数字电路的知识和 HCL 来描述不同部件的设计逻辑。

逻辑门

所有数字电路都是由一个个逻辑门组成的，逻辑门可以实现单个位的逻辑判断，有以下 3 种逻辑门：

与门（AND）
或门（OR）
非门（NOT）

与门可以实现 a&&b，或门实现 a||b，非门实现!a。

组合逻辑电路和 hcl 布尔表达式

通过逻辑门的组合，我们可以实现更多复杂的逻辑判断，这些组合逻辑电路的硬件结构会非常庞大和复杂，所以我们会使用 hcl 布尔表达式来简化它的描述和表达，比如一个判断位级相等的电路为：bool eq = (a && b) || (!a && !b)，还有一个位级的多路复用器为：bool out = (s && a) || (!s && b)，hcl 表达式类似 c 语言中的函数，bool为返回值类型，其中bool表示单个位，如果是字级的返回值会使用word。

将位级逻辑判断的电路进行组合我们可以实现字级逻辑判断的电路，比如 64 位字的判断相等电路就是由 64 个位级判断相等的电路组成的，表达式为：bool Eq = (A == B)，字级的多路复用器为：

word Out = [
    s: A;
    1: B;
]

这个语句的判断顺序类似于 c 语言的 switch 语言，从上到下依次判断冒号前的布尔表达式是否为真，若为真则输出为冒号后的表达式，否则继续向下执行。

还有更多的例子，如果是一个字级的四路复用器，有两个控制信号 s0、s1，四个字级的输入 A、B、C、D，它的表达式为：

word Out4 = [
    !s1 && !s0: A; # 00
    !s1: B; # 01
    !s0: C; # 10
    1: D; # 11
]

如果是一个字级选 3 个数中最小的数的电路，它的表达式为：

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

除此之外，我们定义一个简单的 ALU（算术\逻辑单元），有两个字级的输入 X、Y，当控制信号的输入为 0 时，输出为 X+Y，输入为 1 时，输出为 X-Y，输入为 2 时，输出为 X&Y，输入为 3 时，输出为 X^Y，表达式为：

word ALU = [
    !s1 && !s0: X + Y; # 00 0
    !s1: X - Y; # 01 1
    !s0: X & Y; # 10 2
    1: X ^ Y; # 11 3
]

以上的控制信号表达有些繁琐，我们可以使用 hcl 中的集合关系表达式来简化，假设一个 2 位的 code 信号，将其译码成两条电路 s0、s1，在之前我们这样写：

1 2	bool s1 = code == 2 \|\| code == 3; bool s2 = code == 1 \|\| code == 2;

使用集合关系简化：

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

存储器和时钟

数字电路有两大类，组合逻辑电路和时序逻辑电路，以上的数字电路为前者，时序逻辑电路可以根据电路的输入和原有状态来改变输出，而组合逻辑电路只能根据电路的输入来改变输出，所以通过时序逻辑电路我们可以实现寄存器和存储器。
时序逻辑电路需要时钟来驱动，当时钟的上升沿或者下降沿到来时，电路的输出就会根据输入和原有状态来改变。由于时序逻辑电路的底层比较复杂，我们不会去研究它的具体电路结构，因为这要涉及到数电中大量的触发器等知识，我们会直接使用它们的抽象，我们统一规定后续抽象依赖时钟的使用都是当时钟的上升沿到来时触发。

寄存器文件，它实现了寄存器，它有两个读端口，A、B，每个读端口有一个输入 src(source，代表寄存器 ID)和一个输出 val(value，输出值)，还有一个写端口，有两个输入 valW（value write，写入值）、dstW（destination write，写入的寄存器 ID），最后还有时钟信号，寄存器文件的读不需要依赖时钟，而写需要依赖时钟的上升沿，以下是它的工作过程：

读出
1. 更新 srcA 或 srcB
2. valA 或 valB 更新为对应 src 中寄存器的值
写入
1. 更新 valW 和 dstW
2. 等待时钟上升沿到来
3. 对应寄存器更新成输入值

数据存储器，它实现了存储器，他有一个读\写信号，一个数据输出，一个数据输入，一个地址信号，一个异常输出以及时钟信号，它同寄存器文件一样，读不依赖时钟，写依赖时钟，以下是它的工作过程：

读出
1. 读写信号设置为 0
2. 更新地址信号为期望读出数据的地址
3. 如果地址超出范围，异常输出 1，否则数据输出更新为对应地址数据，异常输出 0
写入
1. 读写信号设置为 1
2. 更新地址信号为期望写入数据的地址
3. 等待时钟上升沿到来
4. 如果地址超出范围，异常输出 1，否则对应地址数据更新为输入数据，异常输出 0

Y86-64 的顺序实现

我们现在已经有了实现 Y86-64 处理器所需的部件了，我们将会描述一个 SEQ（sequential，顺序的）的处理器。SEQ 处理器会在一个时钟周期中会执行一条完整指令所需的所有步骤，这样的处理器的 IPC 会非常低，十分低效，不过开发 SEQ 只是第一步，我们最终会实现一个高效的、流水线化的处理器。

将处理组织成阶段

通常多数指令的部分操作都存在相似性，如果每个指令都是用一套独立的电路来实现那么成本将是高昂的，虽然指令的动作差异很大，但是都是按照遵循统一的序列的，我们可以创建一套执行指令的框架来设计一个充分利用硬件的处理器。下面是关于各个阶段和阶段内部执行操作的描述：

取指（fetch）：取指阶段将从内存中读取指令字节，地址为 PC 的值。从指令字节中抽出两个四位的部分，称为 icode（指令代码）和 ifun（指令功能）。它还可能读出一个寄存器指示符字节，指明一个或两个寄存器 rA 和 rB。除此之外，他还可能取出一个 8 字节的常数 valC。然后计算出下一条指令的地址 valP，也就是说 valP 为 PC 的值加上已取出的指令长度。
译码（decode）：译码阶段从寄存器文件读入最多两个操作数，得到 valA 和 valB。它通常读入寄存器指示符字段指明的寄存器，而有些指令可能是读入%rsp 的值。
执行（execute）：执行阶段，ALU 要么执行 ifun 指明的操作，计算内存引用的有效地址，要么增加和减少栈指针。得到的值为 valE。除此之外，它还可能设置条件码。如果是条件传送指令，它会检验条件码和传送条件，如果条件成立则更新目标寄存器。同样的，如果是条件跳转指令，它会判断是否选择分支。
访存（memory）：访存阶段可以将数据写入内存或者通过内存读出数据。读出的值为 valM。
写回（write back）：写回阶段最多可以写两个结果到寄存器文件。
更新 PC（PC update）：将 PC 设置为下一条指令的地址。

处理器会无限循环的执行这些阶段，在我们简化的处理器中，如果发生了任何的异常，处理器就会停止。在完整的设计中，处理器会进入异常处理模式，开始执行由异常类型指定的代码。

以下是一些不涉及到访存的指令所需的通用执行过程：

阶段	OPq rA, rB	rrmovq rA, rB	irmovq V, rB
取指	icode:ifun <- M1[PC] rA:rB <- M1[PC+1] valP <- PC+2	icode:ifun <- M1[PC] rA:rB <- M1[PC+1] valP <- PC+2	icode:ifun <- M1[PC] rA:rB <- M1[PC+1] valC <- M8[PC+2] valP <- PC+10
译码	valA <- R[rA] valB <- R[rB]	valA <- R[rA]
执行	valE <- valB OP valA Set CC	valE <- 0+valA	valE <- 0+valC
访存
写回	R[rB] <- valE	R[rB] <- valE	R[rB] <- valE
更新 PC	PC <- valP	PC <- valP	PC <- valP

以下是涉及到访存的指令所需的通用执行过程：

阶段	rmmovq rA, D(rB)	mrmovq D(rB), rA
取指	icode:ifun <- M1[PC] rA:rB <- M1[PC+1] valC <- M8[PC+2] valP <- PC+10	icode:ifun <- M1[PC] rA:rB <- M1[PC+1] valC <- M8[PC+2] valP <- PC+10
译码	valA <- R[rA] valB <- R[rB]	valB <- R[rB]
执行	valE <- valB+valC	valE <- valB+valC
访存	M8[valE] <- valA	valM <- M8[valE]
写回		R[rA] <- valM
更新 PC	PC <- valP	PC <- valP

以下是 pushq 和 popq 的通用执行过程：

阶段	pushq rA	popq rA
取指	icode:ifun <- M1[PC] rA:rB <- M1[PC+1] valP <- PC+2	icode:ifun <- M1[PC] rA:rB <- M1[PC+1] valP <- PC+2
译码	valA <- R[rA] valB <- R[%rsp]	valA <- R[%rsp] valB <- R[%rsp]
执行	valE <- valB+(-8)	valE <- valB+8
访存	M8[valE] <- valA	valM <- M8[valA]
写回	R[%rsp] <- valE	R[%rsp] <- valE R[rA] <- valM
更新 PC	PC <- valP	PC <- valP

以下是 jXX 和 cmovXX 的通用执行过程：

阶段	jXX Dest	cmovXX rA, rB
取指	icode:ifun <- M1[PC] valC <- M8[PC+1] valP <- PC+9	icode:ifun <- M1[PC] rA:rB <- PC+1 valP <- PC+2
译码		valA <- R[rA]
执行	Cnd <- Cond(CC, ifun)	valE <- 0+valA Cnd <- Cond(CC, ifun)
访存
写回		if(Cnd) R[rB] <- valE
更新 PC	PC <- Cnd?valC:valP	PC <- valP

以下是 call 和 ret 的通用执行过程：

阶段	call Dest	ret
取指	icode:ifun <- M1[PC] valC <- M8[PC+1] valP <- PC+9	icode:ifun <- M1[PC] valP <- PC+1
译码	valB <- R[%rsp]	valA <- R[%rsp] valB <- R[%rsp]
执行	valE <- valB+(-8)	valE <- valB+8
访存	M8[valE] <- valP	valM <- M8[valA]
写回	R[%rsp] <- valE	R[%rsp] <- valE
更新 PC	PC <- valC	PC <- valM

SEQ 硬件结构

介绍完指令执行的框架后，我们将介绍如何从硬件上实现这个框架，下面先总结一下这个框架中每个阶段会使用到的信息：

阶段	指令
取指	icode:ifun rA,rB valC valP
译码	valA,srcA valB,srcB
执行	valE Cond.codes
访存	Read/Write
写回	E port,dstE M port,dstM
更新 PC	PC

下图是以上阶段的硬件实现，正如我们设想的那样，SEQ 会在一个周期中运行完整个指令的所有阶段，为了简化线路设计方便理解，我们先不标明信息传递的源和目的，而是将信息放入信息流中，各部件按需从流中取出信息处理并放回流中。

取指：将 PC 的值作为地址，指令内存读取指令的字节。PC 增加器（使用单独一套电路不使用 ALU）计算 valP。
译码：从寄存器文件的 A、B 端口同时读取寄存器值 valA 和 valB。
执行：根据指令类型设置 ALU 的模式然后设置好 aluA 和 aluB 操作数，计算出 valE 并更新条件码。根据条件码和指令条件和类型来计算分支信号 Cnd。
访存：从数据内存读出或写入一个内存字。指令和数据内存访问的是同一块内存，只是用于不同的目的。
写回：寄存器文件有两个写端口。端口 E 用来写 ALU 计算出来的新值，端口 M 用来写从数据内存中读出的值。
更新 PC：根据指令内存，将 PC 的值更新为 valP（下一条指令的地址），valC（调用指令或跳转指令的目标地址），valM（从内存中读取的返回地址）。

下图给出了更详细的硬件实现，包括了异常处理和 Stat 的更新：

SEQ 时序

以上硬件结构中使用到了组合逻辑电路和时序逻辑电路，组合逻辑电路在输入后即可得到输出，而时序逻辑电路在输入后还需等待时钟上升沿的到来才能改变输出，下图给出一个示例有助于理解这一点：

SEQ 阶段的实现

下面将会深入分析各个阶段并使用 HCL 来详细详细描述各个部件的硬件实现，我们先回顾一下 Y86-64 中指令的常数值：

这其中包含了 nop 指令和 halt 指令。nop 指令只是简单的经过各个阶段，除了要将 PC 加 1，不进行任何处理。halt 指令使得处理器状态设置为 HLT，使得处理器停止运行。

取指阶段

取指阶段将 PC 的值作为地址从内存中一次读出 10 个字节。然后将字节 0 作为指令字节放入 Split 单元分割成两个 4 位的 icode 和 ifun，若 icode 和 ifun 不合法，或者指令内存地址不合法时，会设置 imem_error 信号指明状态，并将 icode 和 ifun 设置成 nop 指令对应的值来跳过这个字节。字节 1 作为寄存器标识字节设置 rA，rB 信号。字节 2-9 设置 valC。根据 icode 的值可以计算 instr_valid，need_regids，need_valC 信号，以下是它们的意义：

instr_valid：这个字节是否对应为一个合法的 Y86-64 指令，可用于发现不合法的指令。
need_regids：这个指令是否包含寄存器标识字节。
need_valC：这个指令是否包含一个常数字。

下面是 need_regids 和 need_valC 信号的 HCL 表达式：

1 2	bool need_regids = icode in {IRRMOVQ, IOPQ, IPUSHQ, IIRMOVQ, IRMMOVQ, IMRMOVQ}; bool need_valC = icode in {IIRMOVQ, IRMMOVQ, IMRMOVQ, IJXX, ICALL};

通过 need_regids 和 need_valC 信号 PC 增加器可以计算出 valP。对于 PC 的值为 p，need_regids 为 r，need_valC 为 i，则valP = p + 1 + r + 8i。

译码和写回阶段

寄存器文件有两个读端口（A 和 B）和两个写端口（E 和 M）。每个端口都有一个地址连接和数据连接，地址连接为寄存器 ID，数据连接为一组 64 位信号，对于读口来说是输出字，对于写口来说是输入字。两个读口的地址输入为 srcA 和 srcB，两个写口的地址输入为 dstE 和 dstM。四个地址的输入是根据 icode，rA，rB，Cnd 信号设置的。

以下是 srcA 和 srcB 的 hcl 表达式：

word srcA = [
    icode in {IRRMOVQ, IRMMOVQ, IOPQ, IPUSHQ} : rA;
    icode in {IPOPQ, IRET} : RRSP; # RRSP为寄存器%rsp的id
    1 : RNONE; # 不需要寄存器
];
word srcB = [
    icode in {IOPQ, IRMMOVQ, IMRMOVQ} : rB;
    icode in {IPUSHQ, IPOPQ, ICALL, IRET} : RRSP;
    1 : RNONE;
];

以下是 dstE 和 dstM 的 hcl 表达式：

word dstE = [
    icode in {IRRMOVQ} && Cnd : rB; # 实现条件传送
    icode in {IIRMOVQ, IOPQ} : rB;
    icode in {IPUSHQ, IPOPQ, ICALL, IRET} : RRSP;
    1 : RNONE;
];
word dstM = [
    icode in {IMRMOVQ, IPOPQ} : rA;
    1 : RNONE;
];

执行阶段

根据 icode 和 ifun 设置 alufun 信号来设置 ALU 的计算模式，alufun 的 hcl 表达式为：

word alufun = [
    icode == IOPQ : ifun;
    1 : ALUADD;
];

根据 icode 设置 aluA 为 valA、valC 或者是-8、+8，aluB 为 valB 或者 0，以下是两者的 hcl 表达式：

word aluA = [
    icode in {IRRMOVQ, IOPQ} : valA;
    icode in {IIRMOVQ, IMRMOVQ, IRMMOVQ} : valC;
    icode in {IPUSHQ, ICALL} : -8;
    icode in {IPOPQ, IRET} : +8;
    # 其他指令不需要ALU
];
word aluBB = [
    icode in {IMRMOVQ, IRMMOVQ, IOPQ, IPUSHQ, IPOPQ, ICALL, IRET} : valB;
    icode in {IRRMOVQ, IIRMOVQ} : 0;
    # 其他指令不需要ALU
];

最后还有一个 set_cc 信号来控制是否要更新条件码寄存器：

1	bool set_cc = icode in {IOPQ};

访存阶段

两个控制块产生内存地址和输入数据，两个控制块控制是执行读操作还是写操作，以下是读写信号的 hcl 代码：

1 2	bool mem_read = icode in {IMRMOVQ, IPOPQ, IRET}; bool mem_write = icode in {IRMMOVQ, IPUSHQ, ICALL};

以下是内存地址和输入数据的 hcl 代码：

word mem_addr = [
    icode in {IRMMOVQ, IPUSHQ, ICALL, IMRMOVQ} : valE;
    icode in {IPOPQ, IRET} : valA;
    # 其他指令不需要产生内存地址
];

word mem_data = [
    icode in {IRMMOVQ, IPUSHQ} : valA;
    icode in {ICALL} : valP;
    # 其他指令不需要产生内存输入数据
];

如果内存地址不合法将会设置 dmem_error 信号，最后 Stat 将会根据 icode、imem_error、instr_valid 和 dmem_error 计算出状态码 Stat，以下是 Stat 的 hcl 代码：

word Stat = [
    imem_error || dmem_error : SADR;
    !instr_valid: SINS;
    icode == IHALT : SHLT;
    1 : SAOK;
];

更新 PC 阶段

最后一个阶段会产生 PC 的新值。根据 icode 和 Cnd，new_pc 可能为 valC，valM 或 valP，以下是 hcl 代码：

word new_pc = [
    icode == ICALL : valC;
    icode == IJXX && Cnd : valC;
    icode == IRET : valM;
    1 : valP;
];

SEQ 小结

现在我们已经浏览了 Y86-64 处理器的一个完整设计。可以看到，通过将执行每条指令所需的步骤组织成一个统一的流程，就可以用少量的各种硬件单元以及一个时钟来控制计算的顺序，从而实现整个处理器。SEQ 的唯一问题就是太慢了，时钟必须非常慢才能使信号在一个周期中传输完所有阶段。这种实现方式不能充分利用硬件单元，因为每个硬件单元只在整个时钟周期的一部分时间中被使用到。后续我们将会引进流水线设计来获得更好的性能。

流水线的通用原理

流水线（pipeline）是一项提高系统吞吐量的重要技术。它的基本思想是将一个任务分解为多个连续的步骤或阶段，每个阶段由专门的硬件电路来执行。通过这种方式，我们可以同时处理多条指令，每条指令处于执行的不同阶段。
为了理解流水线的原理，我们可以通过一个简单的例子来说明：
现在假设洗一批衣服需要三个步骤：洗、漂洗和烘干，每个步骤需要 30 分钟。如果采用顺序处理的方式，处理 3 批衣服就需要 270 分钟（每批 90 分钟）。如果采用流水线的方式，第二批衣服就可以在第一批衣服进行漂洗的时候开始洗，第三批可以在第一批进行烘干，第二批进行漂洗的时候进行洗，那么处理完 3 批衣服就只需要 150 分钟，因为我们可以同时进行漂洗和烘干。

计算流水线

通过流水线技术我们可以将一个组合逻辑电路进行拆分，在拆分的电路之间插入寄存器，用来存储中间结果，从而提高电路的吞吐量。
下面给出一个简单的例子：

未流水线化前：

未流水线化前，一组指令进入系统（I1,I2,I3），系统将会执行完一个指令之后再进行下一个指令，所以在流水线图中三个指令在垂直上并没有重叠，系统的延迟为 300+20=320ps，最大吞吐量计算如下：

$$ \text{最大吞吐量} = \frac{1}{(300+20)ps} \times \frac{1s}{1ps} \approx 3.125 GIPS $$

$ 1s = 10^{12}ps $

流水线化后：

流水线化后，我们将系统拆分成三个阶段（A,B,C），一组指令进入系统（I1,I2,I3），系统会在开始的 120ps 时，开始执行 I2，在 240ps 时开始执行 I3，三个指令在垂直上有了重叠，系统的延迟为 3(100+20)=360ps，最大吞吐量计算如下：

$$ \text{最大吞吐量} = \frac{1}{(100+20)ps} \times \frac{1s}{1ps} \approx 8.333 GIPS $$

$ 1s = 10^{12}ps $

流水线化后，系统的吞吐量提高到了原来的 8.333/3.125=2.667 倍，而代价是延迟小幅提升到了 360/320=1.125 倍。
流水线化中，我们会将系统的时钟周期设置为最长的那个阶段，这样可以保证每个阶段都能在时钟周期结束时完成，不会出现数据冲突。

流水线的局限性

上述的流水线设计是在理想情况下，能将每个部分都均匀划分，但实际中流水线设计会遇到以下问题：

不一致的划分：
假如我们将系统仍然划分成 3 个阶段，但每个阶段的延迟从 50ps 到 150ps 不等，A 阶段为 50ps，B 阶段为 150ps，C 阶段为 100ps，那么流水线化后，系统的延迟将会变成 3(150+20)=510ps，吞吐量为 5.882 GIPS，当系统运行时 A 和 C 阶段会存在空闲，这样就无法充分利用硬件资源。
流水线过深，收益反而下降：
假如我们将系统划分为 6 个阶段，每个阶段需要 50ps，那么流水线化后，系统的延迟将会变成 6(50+20)=420ps，吞吐量为 14.286 GIPS，我们将性能提高了 14.286/8.333=1.713 倍，没有阶段的时钟周期缩短到了原来的两倍，但是由于流水线寄存器的存在，吞吐量并没有加倍，流水线寄存器的延迟成为了系统提升吞吐量的一个制约因素，在我们的新的设计中，这个延迟占到了整个时钟周期的 28.6%。

带反馈的流水线设计

目前为止，我们只考虑了单独执行的指令，但实际中，指令之间可能存在依赖关系，例如：

1
2
3

irmovq $100, %rax
addq %rax, %rbx
mrmovq 50(%rbx), %rdx

在上述指令中，第二条指令需要使用第一条指令存入的值，第三条指令需要第二条指令中计算出的值，这些相邻的指令之间都存在数据相关（data dependency）。

另外一种相关是控制相关，例如：

loop:
  subq %rdx, %rax
  jne targ
  irmovq $100, %rdx
  jmp loop
targ:
  halt

上述指令中使用到了 jne 指令，产生了一个控制相关（control dependency）。

如果我们仍然使用之前的 3 阶段流水线设计，那 I2 将无法获取 I1 的反馈，只能等到 I1 执行完后续的指令才能获取反馈，之将会导致系统执行错误，所以我们将流水线设计引入 Y86-64 处理器时，必须要能正确处理反馈的影响。

Y86-64 的流水线实现

在设计流水线化的 Y86-64 处理器之前，我们需要先对原先的 SEQ 处理器进行一些修改，以适应流水线的设计。

SEQ+

SEQ+ 处理器在原有的 SEQ 处理器基础上，将 PC 更新阶段移动到取值阶段前，来适应流水线化的改造，同时我们也将 PC 选择器的输入信号进行重新标号。

插入流水线寄存器

在创建一个流水线化的 Y86-64 处理器的最初尝试中，我们要在 SEQ+处理器的基础上插入流水线寄存器，并对信号重新排列，得到 PIPE-处理器。

流水线寄存器按如下方式进行标号：

F 保存 PC 的预测值
D 保存取指阶段后取出的指令的信息，用于译码阶段
E 保存译码阶段后的指令的信息以及从寄存器中取出的值，用于执行阶段
M 保存执行阶段后的指令的信息以及 ALU 计算结果和条件码，用于访存阶段
W 保存访存阶段后的指令的信息以及从内存中读取的值，用于写回阶段和更新 PC

预测下一个 PC

在 PIPE-处理器中，我们采取了一些措施来正确处理控制相关。
对于 call 和 jmp 指令来说，下一条指令的地址就是当前指令中的 valC，所以我们就可以将 valC 作为下一个 PC 的预测值。
对于条件分支指令来说，我们将会使用分支预测技术，分支预测策略的不同会影响到预测的准确性，进而影响到流水线的性能。分支预测策略大致可以分为静态预测和动态预测，静态预测策略是根据当前指令的类型来预测，动态预测策略是根据历史执行情况来预测。现代处理器基本都采用动态预测策略。我们在这里就采用简单的静态预测策略的设计，静态预测策略有以下几种：

总是选择：总是预测分支指令会跳转，成功率大约为 60%
总是不选择：总是预测分支指令不会跳转，成功率大约为 40%
反向选择：当分支地址比下一条地址低时，预测分支指令会跳转，否则预测不会跳转，成功率大约为 65%
正向选择：当分支地址比下一条地址高时，预测分支指令会跳转，否则预测不会跳转，成功率大约为 45%

正向选择和反向选择的实现难度较为复杂，我们在这里采用总是选择策略。

对于 ret 指令，它的新 PC 值并不能从指令中获取，而是要通过访问栈帧才能得知，所以我就为了简化设计就不会对返回地址进行预测，而是简单的暂停处理新的指令，直到 ret 指令执行完成。

对于大多数程序来说，预测返回地址是很容易的，因为过程调用和过程返回是成对出现，大多数函数的返回地址就是调用函数指令的下一条指令，现代处理器会在取指单元中放入一个硬件栈，保存过程调用指令产生的返回地址，当取出一个 ret 指令时就从这个栈中弹出顶部的值作为预测的返回地址。但是有的时候这样的预测不一定会成功，所以我们仍然需要提供一个恢复机制来处理预测失败的情况。

流水线冒险

流水线冒险（pipeline hazard）是指流水线中指令的执行顺序与预期顺序不一致的情况。流水线冒险可以分为数据冒险（data hazard）和控制冒险（control hazard）。

在刚才的 PIPE-设计中，我们并没有对数据冒险进行处理，所以当一条指令需要使用到上一条指令的计算结果时，流水线就会发生数据冒险。

以下有几个措施来解决数据冒险问题：

用暂停来避免数据冒险
用转发来避免数据冒险
加载/使用数据冒险

后面将会使用以下指令作为示例：

irmovq $10, %rdx
irmovq $3, %rax
addlq %rdx, %rax
halt

每条指令分别有以下几个阶段：

F(fetch)：取指
D(decode)：解码
E(execute)：执行
M(memory)：访存
W(write back)：写回

如果我们没有引入一个带反馈的流水线设计，那么以上指令就会出现如下问题：

指令	1	2	3	4	5	6	7	8
irmovq $10, %rdx	F	D	E	M	W
irmovq $3, %rax		F	D	E	M	W
addlq %rdx, %rax			F	D	E	M	W
halt				F	D	E	M	W

在第 4 周期时，addlq 进行译码时读取到的%rdx 和%rax 的值仍然是 0，因为前两条 irmovq 指令还没有完成 W 阶段，寄存器中的值还没有更新

使用暂停来避免数据冒险

最简单的解决方法就是在 addlq 和 irmovq 之间添加 nop 指令，使得 addlq 的 D 阶段在 irmovq 的 W 阶段之后，所以改造后的代码为：

指令	1	2	3	4	5	6	7	8	9	10	11
irmovq $10, %rdx	F	D	E	M	W
irmovq $3, %rax		F	D	E	M	W
nop			F	D	E	M	W
nop				F	D	E	M	W
nop					F	D	E	M	W
addlq %rdx, %rax						F	D	E	M	W
halt							F	D	E	M	W

这样 addlq 阶段的 D 阶段就会变道第 7 周期，此时两个 irmovq 的 W 阶段都已经完成，这样 addlq 就能取到更新后的值了，解决了数据冒险问题，我们实际上并不会真的在两条指令中添加 3 个 nop 指令而是使用阻塞
我们会在 addlq 和 irmovq 指令之间添加 3 个 bubble，使得后续的指令阻塞在当前阶段，如图：

指令	1	2	3	4	5	6	7	8	9	10	11
irmovq $10, %rdx	F	D	E	M	W
irmovq $3, %rax		F	D	E	M	W
bubble
bubble
bubble
addlq %rdx, %rax			F	D	D	D	D	E	M	W
halt				F	F	F	F	D	E	M	W

这样虽然能解决问题，但是这样会使得流水线暂停长达 3 个周期，严重降低了整体的吞吐量

使用转发来避免数据冒险

当流水线进行到第 4 个周期的时候，addlq 正处在 D 阶段中，此时第一条 irmovq 指令正在 M 阶段，它的 M_valE 的值是 10，第二条 irmovq 指令正在 E 阶段，它的 e_valE 的值是 3，所以我们可以在这两个信号处搭建旁路将信号转发到 D 阶段中，这样 D 阶段就能将正确的值写入流水线寄存器中，所以我们需要一个控制器来发现数据冒险然后选择使用转发过来的信号，解决数据冒险，同时为了保证泛用性，我们会将更多的信号进行转发，最后我们会将 e_valE、m_valM、M_valE、W_valM、W_valE 这五个信号进行转发，所以最后的设计如下：

加载/使用数据冒险

有一类数据冒险不能单纯用转发来解决，因为内存读在流水线发生的时候比较晚，所以我们无法将访存后才能得到的值转发到过去的过去发生的阶段中，因此我们只能使用暂停的方式在处理这个问题，比如以下例子：

指令	1	2	3	4	5	6	7	8	9	10	11
irmovq $128, %rdx	F	D	E	M	W
irmovq $3, %rcx		F	D	E	M	W
rmmovq %rcx, 0(%rdx)			F	D	E	M	W
irmovq $10, %rbx				F	D	E	M	W
mrmovq 0(%rdx), %rax					F	D	E	M	W
addlq %ebx, %eax						F	D	E	M	W
halt							F	D	E	M	W

mrmovq 指令在内存中的值需要到 M 阶段后才能得到，无法通过转发来解决，所以我们会在 mrmovq 和 addlq 之间加入一条 bubble，这样就能在 mrmovq 的 W 阶段将值转发到 addlq 指令的 D 阶段
这种用暂停来处理加载/使用数据冒险的方法称为加载互锁，使用加载互锁和转发技术结合起来足以处理所有可能的数据冒险。因为只有加载互锁才会降低流水线的吞吐量，所以我们几乎可以实现每一个周期都发射一条新指令的目标

避免控制冒险

当处理器没有办法根据处于取指阶段的当前指令来确定下一条指令的地址时，就会出现控制冒险。在前面我们的处理器设计中，控制冒险只会发生在 ret 指令和跳转指令。
对于 ret 指令，我们必须要通过访问栈帧才能知道具体的返回地址，所以当我们遇到了 ret 指令就会往后面插入 3 个 bubble 来暂停流水线，等到 ret 进行到 W 阶段时 PC 选择器就能知道下一条指令的地址，例如以下：

指令	1	2	3	4	5	6	7	8	9	10	11
irmovq Stack, %rsp	F	D	E	M	W
call proc		F	D	E	M	W
ret			F	D	E	M	W
bubble				F	D	E	M	W
bubble					F	D	E	M	W
bubble						F	D	E	M	W
irmovq $10, %rdx							F	D	E	M	W

对于跳转指令，我们采用总是选择策略，预测跳转指令会选择分支，对于以下例子，当 jne 指令到 E 阶段也就是第 4 周期时，分支逻辑发现不应该选择分支，但是此时已经选择我们已经取出了两条指令，它们不应该执行下去了，所以我们会为已经进入流水线的两条指令都给一个 bubble 来阻塞住它们，这样它们就不会进行到 E 阶段，影响程序员可见的状态。

  xorq %rax, %rax
  jne target      # not taken
  irmovq $1, %rax # fall through
  halt
target:
  irmovq $2, %rdx # target
  irmovq $3, %rbx # target + 1
  halt

指令	1	2	3	4	5	6	7	8	9
xorq %rax, %rax	F	D	E	M	W
jne target		F	D	E	M	W
irmovl $2, %rdx			F	D	E	M	W
bubble					D	E	M	W
irmovq $3, %rbx				F	D	E	M	W
bubble					F	D	E	M	W
irmovq $1, %rax					F	D	E	M	W

异常处理

处理器中很多事情都会导致异常控制流，此时，程序执行的正常流程就会被破坏掉。异常可以由程序执行从内部产生，也可以由某个外部信号从外部产生。在我们的 ISA 中包括三种不同的内部产生的异常：

halt 指令
非法指令和功能码组合的指令
取指或数据读写尝试访问一个非法地址

除此之外，还有三个细节问题：

流水线中可能会同时有多条指令导致异常，比如处在取指阶段中有 halt 指令，而数据内存报告访存阶段的阶段出现了指令地址越界的问题。我们处理这个问题的原则是：有流水线中最深的指令引起的异常的优先级最高。
取出了一条指令进入流水线中，但是由于分支预测失败取消了这条指令，也就说这条指令本不会实际影响执行结果但是去导致了异常。所以我们需要避免出现这个异常。
当一条指令导致了一个异常，而后面的指令已经更新了处理器的状态，比如 pushq %rax，此时的 %rsp 为 0x0000000000000000，那么 pushq 指令就会向 0xfffffffffffffff8 中插入数据，但是这会在访存阶段导致一个异常，如果后面紧跟着一条 addq 指令，那么指令就会在执行阶段更新 CC，但实际上并不应该对 CC 进行更改。所以我们应该要能够发现出现了这个异常然后停止执行。