CS:APP第四章复习

其实第四章一开始感觉不是我该学的，但是想想自己也要考研，计组也会讲这些，而这本书应该是会比计组讲的好的，所以还是硬着头皮学吧。

• 2022-12-27 UPDATE:完成了这一章

每天 % 一遍：CSAPP 永远的神！！！计算机的教科书我愿称他为最好！

计算机体系结构图

Y86-64指令集体系结构

我们知道，x86-64 指令集体系结构的电脑是很经典的 CISC（complex instruction set computer）。这里方便学习就定义一个精简指令集 Y86-64 结构。

程序员可见的状态

• Y86-64程序中的每条指令都会读取或修改处理器状态的某些部分，这称为程序员可见的状态。
• 这里的“程序员”既可以是用汇编代码写程序的人，也可以是产生机器级代码的编译器

Y86-64 的状态类似 x86-64。有 15 个寄存器：%rax，%rcx，%rdx，%rbx，%rsp，%rbp，%rsi，%rdi 以及 %r8-%r14。为了方便指令编码，少了一个 %r15 寄存器。

其中，%rsp 被用于入栈出栈，程序计数器（PC，也就是%rip）存放当前指令执行的地址，还包含了 3 位的条件码用于条件跳转，程序状态的最后一个部分是状态码（Stat），表明了程序正常运行或者是出现了某种异常。

程序员可见的状态：各类通用寄存器，PC，条件码，Stat。

程序员不可见的状态：指令寄存器（Instrument Register），主存数据寄存器（Memory Data Register），主存地址寄存器（Memory Address Register）。这些都是辅助 CPU 执行的寄存器，对我们来说不知道也没必要知道，我们只需要知道通用寄存器里面有什么就可以了。

Y86-64指令

数据传送指令

x86-64 的 movq 指令被分为了 4 个不同的指令。就是对应了源目的的种类数：立即数-寄存器，寄存器-寄存器，内存-寄存器，寄存器-内存，与 x86-64 相同，不允许直接从内存地址传送到另一个内存地址，必须通过寄存器传送。

整数操作指令

有四种类型的整数操作（addq，subq，andq，xorq），它们的代码部分（code）相同，功能不同，功能用于选择是对两个数进行加法，减法，按位与还是按位或运算。

跳转指令

有七个跳转指令，与前面介绍的类似，一个无条件跳转和六个条件跳转（jle，jl，je，jne，jge，jg）。

条件传送指令

有六个条件传送指令，与条件跳转类似。

调用函数

call指令，与 x86-64 类似

栈操作指令

也与 x86-64 类似，有入栈（push）和出栈（pop）的操作。

指令编码

参考书上这个图

因为我们有 15 个寄存器，所以 0-E 刚好表示 15 个寄存器，剩下一个 F 表示该操作数不为寄存器，可能为一个立即数。例如 irmovq 指令的源操作数是立即数，因此源操作数这一位用 F 替代。

再比如，pushq 和 popq 指令是单操作数，因此第二个字节后八位默认也是 F。

分支指令调用的地址是绝对地址而不是 PC 寻址，指令集一个比较重要的是字节编码必须有唯一的解释，不能产生歧义。

Y86-64异常

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

Y86-64在遇到异常的时候只会简单地停止处理器的运行，但是完整的设计应该需要让处理器调用一个异常处理程序（exception handler）。

Y86-64程序

这里需要注意，add 指令不能直接加一个常数，Opq指令只能对两个寄存器做运算，因此要对立即数运算需要先把立即数加载到寄存器当中才可以。

subq 指令可以直接设置条件码，而在 x86-64 架构下，我们需要再多一个 test 命令才能实现设置条件码。

demo

.pos 0
irmovq stack,%rsp
call main
halt

array:
	.quad 0x000d000d000d
	.quad 0x00c000c000c0
	.quad 0x0b000b000b00
	.quad 0xa000a000a000
	
main:
	irmovq array,%rdi
	irmovq $4,%rsi
	call sum;sum(array,4)
	ret

sum:
	irmovq $8,%r8
	irmovq $1,%r9
	xorq %rax,%rax;set %rax=0
	andq %rsi,%rsi;test rsi
	jmp test

loop:
	mrmovq (%rdi),%r10;get (%rdi) save in %r10
	addq %r10,%rax;%rax+=%r10
	addq %r8,%rdi;%rdi+=8
	subq %r9,%rsi;%rsi-=1

test:
	jne loop;not equal == not zero simple to while(rsi!=0)
	ret
	
	.pos 0x200
stack:

以 . 开头的词是汇编器伪指令，.pos 他告诉汇编器调整地址，从那里开始产生数据或者汇编代码。

其实逐行分析逻辑我们不难得到 sum 函数的一个定义：WORD sum(WORD *array,WORD length)，而该函数会求出 array[0]~array[length] 的和返回。

再上面的程序中，最终 sum 会返回 0xabcdabcdabcd。

一些 Y86-64 指令的详情

有些指令会更改指定寄存器的状态，比如 pushq 指令会令 %rsp 减去 8，将值放入该栈空间。当我们执行 pushq %rsp 时，处理器的行为是不确定的，因为入栈的寄存器会在这条指令中被更改状态，这种情况下就会存在两种不同的结果：

• 压入 %rsp 的原始值（x86-64采用的约定）
• 压入减去 8 的 %rsp 的值

经过一个测试程序，我们发现，pushq 指令并不按照我们常规的理解，先减后放，而是先放后减。

其实在我看来，如果以流水线执行指令的方式去理解这个问题会好理解的多，这个在后面具体讲讲自己的看法吧。

对于 popq %rsp 指令，书中给了一个练习，有如下的测试程序：

movq %rsp,%rdi
pushq $0xabcd
popq %rsp
movq %rsp,%rax
movq %rdi,%rsp
ret

发现这个函数的结果总是会返回 0xabcd，说明 pop %rsp 是先减去了 %rsp 再赋的值，这个略微有点复杂，在讲指令流水的时候也会讲这个情况的处理方式。

不过现在这个阶段，我们照着上面的理解即可，是先移动指针再取出来。

push 和 pop 两个指令在对 %rsp 寄存器本身操作时，都会尽量保证得到的值是原始值。

pushq %rsp 一定会压最初的 %rsp。

popq %rsp 一定是把那个值正确地给到了 %rsp。

跳转链接：push 的理解

跳转链接：pop 的理解

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

逻辑门

这个就是数电的知识复习了，常见的逻辑门就是 and or not，并且 and or 常见为两输入，但是可以扩展到 n 输入的状态，比如三输入的与门用 HCL 表示就为 a&&b&&c，逻辑门总是活动的，一旦一个门的输入发生变化，在很短的时间内输出也会相应变化。

组合电路和HCL布尔表达式

用很多逻辑门相互连接形成一张网，就能构建计算块，称为组合逻辑电路，构建这个网有以下限制

• 每个逻辑门的输入必须连接到一下三个选项之一：系统输入，某逻辑单元的输出，某逻辑门的输出
• 两个或多个逻辑门的输出不能连接在一起
• 网必须无环

多路复用器（MUX）根据输入控制信号的值，从一组不同的数据信号中选择一个作为输出。

HCL表达式和C表达式会有以下区别：

• C表达式的参数允许是任意整数，非 0 的值均被视为 1，而 HCL 的输入只允许 1 或 0
• C逻辑表达式可能会出现部分求值的特性，如果一个 and 或者 or 运算只对第一个参数求值之后就能确定，那么就不会对第二个参数求值了，而组合逻辑电路没有这种规则。

字级的组合电路和HCL整数表达式

处理器中会遇到很多多路复用器，我们用情况表达式来描述，通用格式为

[
select1:expr1;
select2:expr2;
select3:expr3;
...
selectk:exprk;
]

这个表达式包含了一系列情况，表明了什么时候选择这种情况，后者是指得到的值。

同 switch 不同，不要求选择表达式之间互吃，从逻辑上来讲，它们会被顺序求值，且第一额为 1 的情况会被选中。

有一个比较有意思的例子

如果需要寻找 A，B，C 中的最小值输出，用一般的HCL可以这么描述

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

这个比较经典，但是下面会让我们用三个比较来实现功能，其实不难得出，如果上述条件不满足，那么A肯定不是最小的，如果A都不是最小的了，我也没必要拿它来比了，所以我们的 HCL就可以简化：

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

集合关系

用于匹配多个值中的其中一个，可以理解为集合中的属于。

常用格式就是

iexpr in {iexpr1,iexpr2...,iexprk};

存储器和时钟

• 时钟寄存器（简称寄存器）：存储单个位或字，时钟信号控制加载输入值。
• 随机访问存储器（简称内存，Random Access Memory）：存储多个字，通过地址选择该读或该写哪些字。

这里注意一个概念就是关于寄存器，在硬件中，寄存器就是一个电子器件，在机器级编程时它是一个寄存器文件，我们把这两类概念分别称为硬件寄存器和程序寄存器。

在每个时钟信号上升沿时，值才会从寄存器输入给到输出。

如上图所示，对于整个寄存器文件，有两个读端口，一个写端口，每个端口都有一个地址输入，这里的地址表明该选哪个寄存器进行读或者是写。

因为允许同时读写，因此可能会发生冲突，如果发生了冲突，肯定会按照固定的逻辑去执行操作的。

这个内存有一个地址输人，一个写的数据输入，以及一个读的数据输出。同寄存器文件 一样，从内存中读的操作方式类似于组合逻辑：如果我们在输入 address 上提供一个地址, 并将 write 控制信号设置为 0, 那么在经过一些延迟之后，存储在那个地址上的值会出现在 输出 data 上。如果地址超出了范围，error 信号会设置为 1，否则就设置为 0。写内存是由 时钟控制的：我们将 address 设置为期望的地址，将 data in 设置为期望的值，而 write 设 置为 1。然后当我们控制时钟时，只要地址是合法的，就会更新内存中指定的位置。对于读 操作来说，如果地址是不合法的，error 信号会被设置为 1。这个信号是由组合逻辑产生的， 因为所需要的边界检查纯粹就是地址输人的函数，不涉及保存任何状态。

这里其实可以这么看，地址就是主存地址寄存器（Memory Address Register），数据输入就是 主存数据寄存器（Memory Data Register），数据输出应该也是会输出到主存数据寄存器中。

Y86-64 的顺序实现

首先，我们描述一个称为 SEQ 的处理器。每个时钟周期上，SEQ 执行处理一条完整指令所需的所有步骤。不过如果是这样一条指令的执行就会显得时间很慢，我们需要降低时钟周期以便于适配所有指令。开发 SEQ 的目标就是提供实现最终目的的第一步：是实现一个高效的、流水线化的处理器。

将处理组织成阶段

处理一条指令包括很多操作，通常我们分为以下6个步骤。

• 取指（fetch）：取指阶段从内存读取指令字节，地址为程序计数器（PC）的值。从指令中抽取出指令指示符字节的两个四位部分，称为icode（指令代码）和ifun（指令功能）。它可能取出一个寄存器指示符字节，指明一个或两个寄存器操作数指示符rA和rB。它还可能取出一个四字节常数字valc。它按顺序方式计算当前指令的下一条指令的地址valP。也就是说，valP等于PC的值加上已取出指令的长度。
• 译码（decode）：译码阶段从寄存器文件读入最多两个操作数，得到值va1A和/或valB。通常，它读入指令rA和rB字段指明的寄存器，不过有些指令是读寄存器rsp的。
• 执行（execute）：在执行阶段，算术/逻辑单元（ALU）要么执行指令指明的操作（根据ifun的值），计算内存引用的有效地址，要么增加或减少栈指针。得到的值我们称为valE。在此，也可能设置条件码。对一条条件传送指令来说，这个阶段会检验条件码和传送条件（由ifun给出），如果条件成立，则更新目标寄存器。同样，对一条跳转指令来说，这个阶段会决定是不是应该选择分支。
• 访存（memory）：访存阶段可以将数据写入内存，或者从内存读出数据。读出的值为valM，这一步理解为读写内存数据。
• 写回（write back）：写回阶段最多可以写两个结果到寄存器文件，这一步可以理解为更新寄存器。
• 更新PC（PC update）：将PC设置成下一条指令的地址，更新 %rip 寄存器。

通用指令的指令执行步骤：

这里需要注意，OPq 操作会设置条件码，用于条件跳转和条件传送指令。

因为它是按照这个顺序执行的，所以也可以理解一点前面 pushq %rsp 的问题了，因为在访存阶段会把地址和数据分别放到 MAR 和 MDR 中，因此当我更新 %rsp 寄存器的时候，访存已经完成，此时 %rsp 的原石值在 MDR 当中，因此就会显得是先把数据放入栈中再移动栈指针的感觉，实际上是由这样流水作业的顺序完成的。

比如下面的 demo

跟踪第六行代码的执行情况可以得到以下结果

不难看出，译码阶段如果 valA 取出 %rsp 寄存器的值，那么得到的一定是 %rsp 的原始值，因为 %rsp 在写回阶段才会更新。

所以顺序一定是先更新内存，再更新寄存器，popq %rsp 也是同理，首先读内存，然后再增加栈指针。

最后我们看看 ret 指令的执行并跟踪上面 demo 的第 13 行。

访存阶段读取了栈顶内存并将此设为了新的 PC。

SEQ 硬件结构

SEQ 的硬件结构如下图所示

从下网上看这张图，可以看到指令的一个执行过程以及硬件连接的情况。

• 取指（Fetch）阶段：根据 PC 的值从内存中读取指令，计算指令长度并将新的 PC 暂时放入值 valP 当中。
• 译码（Decode）阶段：会根据指令中需要的寄存器从寄存器文件中读取对应寄存器的值，得到两个操作数。
• 执行（Execute）阶段：将操作数送入 ALU 中计算得到 valE，可能会写回寄存器，从端口 E 中写回，这一步会更新标志寄存器。
• 访存（Memory）阶段：根据 MAR 和 MDR 对内存进行访问（读/写），读出的结果若要写寄存器则会从端口 M 写寄存器文件。
• 写回（Write Back）阶段：将新的寄存器值更新到寄存器文件中，这里有两个更新端口，一个是 E 用于接收 ALU 计算的结果，一个是 valM 用于接收读取内存的结果。
• 更新PC（PC update）阶段：根据预先保存的地址或者是之前计算的指令预计的下一步位置去更新 PC。

SEQ的时序

SEQ 的实现包括组合逻辑和两种存储器设备：时钟寄存器（程序计数器和条件码寄存 器），随机访问存储器（寄存器文件、指令内存和数据内存）。组合逻辑不需要任何时序或 控制—只要输人变化了，值就通过逻辑门网络传播。我们也将读随 机访问存储器看成和组合逻辑一样的操作，根据地址输人产生输出字。对于较小的存储器 来说(例如寄存器文件），这是一个合理的假设，而对于较大的电路来说，可以用特殊的时 钟电路来模拟这个效果。由于指令内存只用来读指令，因此我们可以将这个单元看成是组合逻辑。

现在还有四个硬件单元需要对他们的时序进行明确的控制——程序计数器、 条件码寄存器、数据内存和寄存器文件，这些单元通过一个时钟信号来控制，它触发将新值装载到寄存器以及将值写到随机访问存储器。每个时钟周期，程序计数器都会装载新的指令地址。因为只有在 OPq 操作时才会改变操作码，在执行数据传送指令（mov），push，call 的时候才会进行写数据内存，所以我们只需要控制内存和寄存器的时钟控制信号即可实现一模一样的效果，即使所有的状态更新实际上同时发生， 且只在时钟上升开始下一个周期时。之所以能保持这样的等价性，是由于 Y86-64 指令集 的本质，因为我们遵循以下原则组织计算 ：

• 原则：从不回读

处理器从来不需要为了完成一条指令的执行而去读由该指令更新了的状态。

SEQ阶段的实现

首先给出如下常数定义

取指阶段

就像这个图所示，首先取出 PC 所指示的内存的第一个字节分割得到高四位的 icode 和低四位的 ifun，然后会判断该指令是否合法，由图示信号 Instr valid 得到，同时也可以计算得到该指令是否包含常数（Need valC）以及寄存器（Need regids）。

这里的 Instr valid 可以用 HCL 描述为

Instr_valid=
icode in{
	0xC,0xD,0xE,0xF
}

同样 Need_regids 也可以用 HCL 描述为

Need_regids =
icode in { 
    IRRMOVQ,IOPQ,IPUSHQ,IPOPQ,
    IIRMOVQ,IRMMOVQ,IMRMOVQ
};

Need_valC 用 HCL 描述为

Need_valC=
icode in{
	IIRMOVQ,IMRMOVQ,IRMMOVQ,
	IJXX,ICALL
}

译码和写回阶段

译码

图 4-28 给出了 SEQ 中实现译码和写回阶段的逻辑的详细情况。把这两个阶段联系在 一起是因为它们都要访问寄存器文件。

每个端口都有一个地址连接和一个数据连接，地址连接是一个寄存器 ID, 而数据连接是一组 64 根线路，既可以作为寄存器文件的输出字（对读 端口来说），也可以作为它的输人字（对写端口来说）。 两个读端口的地址输人为 srcA 和 srcB，而两个写端 口的地址输人为 dstE 和 dstM。如果某个地址端口上 的值为特殊标识符 OxF( RNONE)，则表明不需要访问 寄存器。

就是说， srcA 和 srcB 决定我从哪个寄存器读数据，对应从 valA 和 valB 中读出。同理 destE 和 destM 决定我要去写哪个寄存器，对应数据从 valE 和 valM 中写入。

下面两题比较有意思：

第一个是取 srcA 的一个信号。

word srcA = [
    icode in {IRRMOVQ, IRMMOVQ, IOPQ, IPUSHQ } : rA;
    icode in {IPOPQ, IRET } : RRSP;
    1 : RNONE; # Don't need register
}

这里需要注意的是， srcA 是用于读的一个寄存器，因此只有在 rrmovq，rmmovq，OPq，pushq 指令需要读取操作数所包含的寄存器。这里只有两个数据传送指令，其余的指令，比如说 mrmovq，这个可能需要看看之前那个大表了，它的源操作数在 rB，目的操作数在 rA，所以 rA 没必要被读取。再比如说 irmovq，源操作数为立即数 rA 为 0xF，也就是 RNONE。

然后第二个条件，也就是说在 popq 和 ret 两个指令执行的时候，我们需要额外读取一个 rsp 寄存器，

第二个是取 srcB 的信号，先给出答案吧

word srcB = [
    icode in {IRMMOVQ, IMRMOVQ, IOPQ  } : rB;
    icode in {IPOPQ, IRET, ICALL, IPUSHQ } : RRSP;
    1 : RNONE; # Don't need register
}

寄存器→内存 的一个过程，内存我们需要读取寄存器与一个偏移的立即数相加，因此需要读取 rB 寄存器的值算出地址得到目的操作数的具体地址。而 内存→寄存器 的一个过程，前面说过了，因为它的寄存器反了，源操作数那边的寄存器为 rB，所以为了计算内存地址我们依然要读取这个寄存器。

这里多了的 pushq 指令，除了源操作数 rA 以外，需要额外读取一个 rsp 寄存器以方便我们放入栈中，call 指令其实就是 push rip + jmp 指令，因此同理，只是不太清楚这个 popq 和 ret 怎么来的。

写回

其实就是对寄存器文件的写，其实很简单，想想对目的操作数为寄存器的几个指令即可。

那么很容易写出 dstE 的 HCL 描述

word dstE = [
    icode in { IRRMOVQ } : rB;
    icode in { IIRMOVQ, I0PQ} : rB;
    icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
    1 : RNONE; # Don't write any register
];

首先我们需要清楚，dstE 是从 ALU 中计算得到的结果，rrmovq 相当于是从 rA 中取出值 +0 写回 rB，因此写回的值是从 ALU中出来的，OPq 指令也一样，结果是从 ALU 取得写回目的寄存器，以及 irmovq同理。

特别的，pushq，popq，call，ret指令会改变 rsp，rsp是会通过 ALU 进行 +8 -8的，这四个指令都会更新 rsp。

dstM 的 HCL 描述如下

word dstM = [
	icode in {IMRMOVQ,POPQ}:rA;
	1 : RNONE;
];

这个可以参考前面的各个指令的执行阶段，mrmovq 很好理解，就是从内存中读出的值写到了目的寄存器， 也就是valM。popq也一样，从栈中取得值放到目的寄存器中。这里再提一下，就是 rmmovq 的目的寄存器是 rA。

练习4.22 只有popq指令会同时用到寄存器文件的两个写端口。对于指令popq %rsp，E和M两个写端口会用到同一个地址，但是写入的数据不同。为了解决这个冲突，必须对两个写端口设立一个优先级，这样一来，当同一个周期内两个写端口都试图对一个寄存器进行写时，只有较高优先级端口上的写才会发生。那么要实现练习题4.8中确定的行为，哪个端口该具有较高的优先级呢？

那么这里也描述的很清楚了，当读写端口的两个写操作指向了同一个寄存器，那么会设置优先级来确保其唯一，根据之前的一个特性观察我们会发现 pop %rsp 执行完成之后总是会使用栈（内存）中的数据给到 %rsp。那么不难得出 dstM 的优先级会高于 dstE。

执行

执行阶段的逻辑图如下图所示

执行阶段包括算术/逻辑单元（ALU)。这个单 元根据 alufun 信号的设置，对输人 aluA 和 aluB 执行 ADD、SUBTRACT、 AND 或 EXCLUSIVEOR 运算。如图 4-29 所示，这些数据和控制信号 是由三个控制块产生的。ALU 的输出就是 valE 信号。

数据输入

执行阶段的第一步就 是每条指令的 ALU 计算。列出的操作数 aluB 在 前面，后面是 aluA，这样是为了保证 subq 指令 是 valB 减去 valA。可以看到，根据指令的类型， aluA 的值可以是 valA、valC, 或者是 -8 或+8。 因此可以用如下的 HCL 表达式来描述 aluA 的行为

word aluA=[
    icode in { IRRMOVQ,IOPQ}:valA; 
    icode in { IIRMOVQ,IRMMOVQ,IMRMOVQ}:valC; 
    icode in { ICALL,IPUSHQ}:-8; 
    icode in { IRET,IPOPQ}:8;
    #Other instructions don't need ALU
];

来解释一波：

• OPq 指令就不用说了，本身就会用到 ALU 的，aluA 的输入就是源操作数，也就是 rA 寄存器读出的 valA。
• rrmovq 指令是把源寄存器的值赋值给目的寄存器，虽然只是简单的数据传送，但是写寄存器只有两个端口：要么是内存里来的从 dstM 出，要么是 ALU 来的，从 dstE 中出。这里显然我们还是要经过 ALU，那么目的操作数可以直接给 0 然后作个加法输出，所以它的源操作数也是从 rA 寄存器读出的 valA。
• irmovq 指令是将立即数赋值给目的寄存器，我们需要从指令中取出这个立即数经过算术逻辑单元 +0 之后写寄存器，因此它的输入就是 valC
• rmmovq 和 mrmovq 同理，因为它们都有一个偏移量要和目的寄存器相加，也得从指令中取出立即数经过 ALU 与寄存器的值相加。因此这两个指令的 aluA 输入都是 valC。
• call 和 push 基本一致，只是 call 指令比 push 多了一个 jmp 而已，这个指令需要我们对 %rsp 寄存器操作，而 %rsp 是目的操作数，而源操作数自然是 -8 让栈顶抬高 8 个字节。
• ret 和 popq 同理，就是让栈降低 8 个字节，源操作数为 +8。

下面有一个练习让我们写出 aluB 的 HCL 描述，其实比较简单，甚至比上面的简单。指令肯定还是那些指令，不同的就是 跟栈操作相关的目的操作数皆为 %rsp 也就是从 valB 中读出来的值，因此这四个指令都是 valB。除此之外，OPq，mrmovq，rmmovq 的目的操作数皆为目的寄存器 rB，因此从中读出来的 valB 也就是 aluB 的输入。

但是之前还提到了，有两个只是数据传送的指令，相当于是要 +0，那么那两个指令的目的操作数就是 0，那我们很容易写出它的 HCL 描述了。

word aluB=[
    icode in { IRMMOVQ,IMRMOVQ,IOPQ,ICALL,IPUSHQ,IRET,IPOPQ} : valB; 
    icode in { IRRMOVQ,IIRMOVQ}:0;
    # Other instructions don't need ALU
];

行为控制

ALU（Arithmetic logic unit） 叫 《算数逻辑单元》，肯定不能只会简单的加法，还得实现 Y86-64 架构下面的其它运算，减法，异或，按位与。

因此这里有一个信号 ALUfun 用于控制 ALU 让它对操作数执行什么运算。

对于这个信号我们也很好写出它的 HCL 描述：只在执行 OPq 指令的时候根据 func 功能位去选择运算种类。其它情况都使用加法即可。

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

特别地，在 ALU 执行 OPq 指令的时候会设置条件寄存器（CC），那么有一个信号 setCC 就是告诉 ALU 是否对执行结果设置 CC。它的 HCL 可以描述为：

bool set_cc = icode in {IOPQ};

标号为 cond 的硬件单元会根据条件码和功能码来确定是否进行条件分支或者条件 数据传送。它产生信号 Cnd, 用于设置条件传送的 dstE，也用在条件分支的下 个 PC 逻辑中。对于其他指令，取决于指令的功能码和条件码的设置，Cnd 信号可以被设置为 1 或者 0，这里我们不管它如何实现条件判断，只给一个简单的设定：Cnd 信号为 1 表示条件满足，为 0 表示不满足。

这里还有一个 练习24 让我们修改 dstE 的 HCL 描述让它可以实现条件传送，也很简单：我们只需要在进行 rrmovq 的时候判断一下 Cnd 信号是否有效即可，如果不满足则将 dstE 设置为 RNONE 表示不需要写回任何寄存器。

word dstE = [
    icode in { IRRMOVQ } : rB;
    icode in { IIRMOVQ, I0PQ} : rB;
    icode in { IPUSHQ, IPOPQ, ICALL, IRET } : RRSP;
    1 : RNONE; # Don't write any register
];

访存

逻辑如图所示

访存阶段的任务就是读或者写程序数据。如图 4-30 所示，两个控制块产生内存地址和内存输入数据（为写操作）的值。另外两个块产生表明应该执行读操作还是写操作的控制信号。当执行读操作时， 数据内存产生值 valM。

图 4-1 8 图 4-2 1 的访存阶段给出了每个指令 类型所需要的内存操作。可以看到内存读和写的 地址总是 valE 或 valA。 这个块用 HCL 描述 就是：

word mem_addr=[
    icode in{IRMMOVQ,IPUSHQ,ICALL,IMRMOVQ} : valE;
    icode in{IPOPQ,IRET} : valA;
    #Other instructions don't need address
]

也来解释一下这个例子吧

访存不论是读还是写，都需要指明读写的地址，所以我们要观察地址怎么得出的，是 ALU 计算过了（valE），还是直接寄存器取出（valA）。

• 对于 rmmovq 指令，我们的内存地址需要经过一个寄存器和一个加法运算，得到的才是最终访问的地址，所以是 valE，mrmovq 同理，只不过前者是写，后者是读。
• pushq 和 call 一样，都是有一个入栈操作。我们来想想入栈是需要写的，写的内存在哪？ %rsp - 8 的位置上，而这个 -8 就不是从寄存器来的，也是 ALU 中来的，因此这两个指令也是 valE 作为地址访问。
• popq 和 ret 指令都包含出栈操作，出栈是读操作，读的其实就是 %rsp 所指示的地址的值，因此它不需要经过 ALU 计算，直接从 valA 中取值即可。

来看看练习 25：

观察图 4-18 图 4-21 所示的不同指令的访存操作 ，我们可以看到内存 写的数据总是 valA 或 valP。写出 SEQ 中信号 mem_data 的 HCL 代码。 我们希望只为从内存读数据的指令设置控制信号 mem_read，用 HCL 代码表示就是：bool mem_read = icode in { IMRMOVQ, IPOPQ, IRET };

其实这里大部分都是 valA 要被写入内存，valP 就是下一条指令的地址，这个我们只会在 call 指令中遇到，会把这个值保存在栈中，其它要写内存的指令大部分都是直接给源操作数 valA。

所以 HCL 代码就很好写出来：

word mem_data = [
	icode in {IPUSHQ,IRMMOVQ} : valA;
	icode in {ICALL} : valP;
	#other instructions don't need mem_data
]

再来看看练习 26：

我们希望只为向内存写数据的指令设置控制信号 mem_write。写出 SEQ 中信号 mem_write 的 HCL 代码 。

就上面那三个指令需要写，判断是否在执行那三个指令即可了。

bool mem_write = icode in {IPUSHQ,IRMMOVQ,ICALL}

练习27 倒是没啥，用它自带的信号发生器，给 Stat 设置就好了，如果某个异常信号为 1 了就直接设置 Stat。

更新 PC

最后一个阶段，更新PC，比较简单，因为 PC 要么就是用 valP 赋值，要么是 ret 了从 valM 中赋值，要么是 call 或者是 jmp，从 valC 中读取值过来作为新的 PC，但是还有条件跳转，这里就需要用 Cnd 信号了。

用 HCL 描述：

word new_pc = [
    # Call. Use instruction constant
    icode == ICALL : valC;
    # Taken branch. Use instruction con
    icode == IJXX && Cnd : valC;
    # Completion of RET instruction. Use value from stack
    icode == IRET : valM;
    # Default: Use incremented PC
    1 : valP;
];

SEQ小结

可以看到，通过将执行每条 不同指令所需的步骤组织成一个统一的流程，就可以用很少量的各种硬件单元以及一个时 钟来控制计算的顺序，从而实现整个处理器。不过这样一来，控制逻辑就必须要在这些单 元之间路由信号，并根据指令类型和分支条件产生适当的控制信号。

SEQ 唯一的问题就是它太慢了。时钟必须非常慢，以使信号能在一个周期内传播所 有的阶段。让我们来看看处理一条 ret 指令的例子。在时钟周期起始时，从更新过的 PC 开始，要从指令内存中读出指令，从寄存器文件中读出栈指针，ALU 将栈指针加 8, 为了 得到程序计数器的下一个值，还要从内存中读出返回地址。所有这一切都必须在这个周期 结束之前完成。

这种实现方法不能充分利用硬件单元，因为每个单元只在整个时钟周期的一部分时间 内才被使用。我们会看到引入流水线能获得更好的性能。

流水线设计的通用原理

流水线字面意思来讲可以指一些工厂，比如生产一个零件，如果我让一个工人从锻造铁开始，然后一直到打磨成可以用的零件都让一个人来完成的话，可能生产一颗螺丝钉都要一天。但是如果我多安排几个工人，一个工人只干生产中的一件事，那么工人干重复的事效率就会大大提高。

计算流水线

下图给出了一个很简单的非流水线化的硬件系统的例子，就是由一些执行计算的逻辑以及一个保存结果的寄存器组成的，时钟信号会在每个特定的时间间隔去保存寄存器。图中的计算块是用组合逻辑来实现的，意味着信号会穿过一系列逻辑门，在一定时间的延迟之后，输出就成为了输入的某个函数。

ps（皮秒，10e-12S） 是时间单位。在这个例子中，我们假设运算逻辑需要 300ps，加载寄存器需要 20ps，那么整个指令周期就是 320ps。

吞吐量就是十亿条指令/S（GIPS）作为单位，在上面的例子中，这个系统的吞吐量就是 \(\frac{1}{320\times 10^{-12}}=3.12GIPS\)，这么说我突然想到了寄组里面的 MIPS，因为这个跟一个指令集名字是一样的，就记住了，它是每秒百万条指令，这个 M 理解为 mega 而不是 million 会比较好，因为和这里的 GIPS 相对应嘛，而书上写的好像是 million。

那么假设将系统执行的计算分成三个阶段（A、B和C），每个阶段需要100ps。然后在各个阶段之间放上流水线寄存器，这样每条指令都会按照这三步经过这个系统，从头到尾完成一次就需要三个完整的时钟周期。

就像刚刚举的例子，这样就可以让三个阶段同时在工作，增加效率，但是执行单条指令所需时间增加。类比一下出来就是说，我一个人生产，因为零件一直在我的手上，我让零件进入新的阶段生产时，不需要重新了解这个零件，而在流水线中，因为不同阶段是不同的人在操作，因此一个人拿到上一个阶段的产物时，需要花少量时间去了解这个零件然后再操作，这在时间上面就会有开销，在上图中的形象的理解就是每经过一个阶段都需要花一定时间去读寄存器。

流水线操作的详细说明

把指令分为三个阶段，同一时间可能就会有三条指令经过不同的阶段，如图中的 240-360 这个阶段。

那么在下图中我们就跟踪了 240-360 这个时间段的电路活动。

指令I1经过阶段C，12经过阶段B，而13经过阶段A。就在时刻240（点1）时钟上升之前，阶段A中计算的指令I2的值已经到达第一个流水线寄存器的输入，但是该寄存器的状态和输出还保持为指令Il在阶段A中计算的值。指令Il在阶段B中计算的值已经到达第二个流水线寄存器的输入。当时钟上升时，这些输入被加载到流水线寄存器中，成为寄存器的输出（点2）。另外，阶段A的输入被设置成发起指令I3的计算。然后信号传播通过各个阶段的组合逻辑（点3）。就像图中点3处的曲线化的波阵面（curved wavefront）表明的那样，信号可能以不同的速率通过各个不同的部分。在时刻360之前，结果值到达流水线寄存器的输入（点4）。当时刻360时钟上升时，各条指令会前进经过一个流水线阶段。

从这个对流水线操作详细的描述中，我们可以看到减缓时钟不会影响流水线的行为。信号传播到流水线寄存器的输入，但是直到时钟上升时才会改变寄存器的状态。另一方面，如果时钟运行得太快，就会有灾难性的后果。值可能会来不及通过组合逻辑，因此当时钟上升时，寄存器的输入还不是合法的值。

如果时钟减缓运行，只不过是组合逻辑运行完成之后，不能够及时更新寄存器，但是也不会影响最终结果，但是如果加快时钟的话，如果某条指令某个阶段运行超出时钟周期，就会导致后面的指令取出一个不合法的值，出现严重错误。

流水线的局限性

4-33 的图给出的例子就是比较礼箱的流水线化的系统，在这个系统当中可以分成三个相互独立的阶段，每个阶段所需时间都是一模一样的，但是会出现一些其它的因素降低流水线的效率。

不一致的划分

实际情况不可能刚刚好，我们指令分出来的三个阶段刚好所需时间相等，当我们把时钟周期设置为 120ps 的时候，每一时刻，指令没有空闲。但是实际情况往往不能等分时间

图4-36展示的系统中和前面一样，我们将计算划分为了三个阶段，但是通过这些阶段的延迟从50ps到150ps不等。通过所有阶段的延迟和仍然为300ps。不过，运行时钟的速率是由最慢的阶段的延迟限制的。流水线图表明，每个时钟周期，阶段A都会空闲（用白色方框表示）100ps，而阶段C会空闲50ps。只有阶段B会一直处于活动状态。我们必须将时钟周期设 为150+20=170ps，得到吞吐量为5.88GIPS。另外，由于时钟周期减慢，延迟增加到了 510ps。

对硬件设计者来说，将指令过程进行等分是很困难的，通常，处理器中的某些硬件单元，如ALU和内存，是不能被划分成多个延迟较小的单元的。这就使得创建一组平衡的阶段非常困难。在设计流水线化的Y86-64处理器中，我们不会过于关注这一层次的细节，但是理解时序优化在实际系统设计中的重要性还是非常重要的。

吞吐量为流水线单阶段最高的延时的倒数，延迟为完整执行一条指令所需的时间。

流水线过深，收益反而下降

如图所示

我们在这里划分了 50ps 一个阶段，那么我们所需最小时钟周期为 70ps，比起划分为 100ps 一个阶段，性能提高了 120/70=1.71 倍的效率，虽然我们将划分的阶段时长减小到了二分之一，但是效率确没有提高 2 倍，主要是流水线寄存器产生的延迟。如图这种情况，流水线寄存器的延迟占到了 28.6%。

现代的处理器采用了很深的流水线（15或者更多），它们把一条指令的执行分成很多简单的步骤，这样一来，每个阶段的延迟就很小。

带反馈的流水线

如果考虑上一条指令和下一条的指令没有任何关系，那么我们设计的流水线便畅通无阻，然而事实往往没那么简单，比如下面这个例子。

在第一条指令的执行阶段，可能第二条指令正在译码，甚至没有执行完毕等到 %rax 的最终结果，直到第一条指令写回才更新 %rax 寄存器，此时第二条指令已经过了执行阶段了，那么我的流水线就改变了这一整个代码的行为。

第二个例子是一个控制相关的例子：

通过流水线技术的加速，我们改变了整个系统的行为

当我们将流水线技术引入Y86-64处理器时，必须正确处理反馈的影响。很明显，像图4-38中的例子那样改变系统的行为是不可接受的。我们必须以某种方式来处理指令间的数据和控制相关，以使得到的行为与ISA定义的模型相符。

Y86-64的流水线实现

我们终于准备好要开始本章的主要任务——设计一个流水线化的Y86-64处理器。首先，对顺序的SEQ处理器做一点小的改动，将PC的计算挪到取指阶段。然后，在各个阶段之间加上流水线寄存器。到这个时候，我们的尝试还不能正确处理各种数据和控制相关。不过，做一些修改，就能实现我们的目标——一个高效的、流水线化的实现Y86-64 ISA的处理器。

SEQ+：重新安排计算阶段

我们移动PC阶段，使得它的逻辑在时钟周期开始时活动，使它计算当前指令的PC值。图4-39给出了SEQ和SEQ+在PC计算上的不同之处。在SEQ中（图4-39a），PC计算发生在时钟周期结束的时候，根据当前时钟周期内计算出的信号值来计算PC寄存器的新值。在SEQ+中（图4-39b），我们创建状态寄存器来保存在一条指令执行过程中计算出来的信号。

SEQ+不会有硬件寄存器来存放 PC，而是根据前一条指令保存下来的一些状态信息动态地计算 PC。比如取指的第一条指令是 irmovq，那么在取完之后我马上能知道下一条指令在 +8 的位置了。

SEQ到SEQ+中对状态单元的改变是一种很通用的改进的例子，这种改进称为电路重定时（circuit retiming）。重定时改变了一个系统的状态表示，但是并不改变它的逻辑行为。通常用它来平衡一个流水线系统中各个阶段之间的延迟。

插入流水线寄存器

我们先来看一看整体的 SEQ+ 的硬件结构

可以看到取指阶段就对 PC 进行了增加，使得其更适合流水线工作。

然后我们需要用寄存器把五个阶段分隔开来。

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

• F（Fetch Code）保存程序计数器的预测值。
• D（Decode）位于取指和译码阶段之间。它保存关于最新取出的指令的信息，即将由译码阶段进行处理。
• E（Execute）位于译码和执行阶段之间。它保存关于最新译码的指令和从寄存器文件读出的值的信息，即将由执行阶段进行处理。
• M（Memory Access）位于执行和访存阶段之间。它保存最新执行的指令的结果，即将由访存阶段进行处理。它还保存关于用于处理条件转移的分支条件和分支目标的信息。
• W（Write Back）位于访存阶段和反馈路径之间，反馈路径将计算出来的值提供给寄存器文件写，而当完成ret指令时，它还要向PC选择逻辑提供返回地址。

于是我们得到了 PIPE- 架构

下面我们用一个五个指令的执行流程图来解释一下流水线的步骤。

这里给的图中，在第一个周期，I1 取指阶段，在第五个周期结束，I2 在第2个周期取指，第六个周期结束……

我们取出第五个周期的情况可以看看， I1 处于写回阶段，I2 处于访存解读那，I3 处于执行阶段，I4 处于译码阶段，I5 处于取指阶段，从下往上画的原因是为了让流水线看起来是自底向上流动的。

对信号进行重新排列和标号

顺序实现SEQ和SEQ+在一个时刻只处理一条指令，因此诸如 valC、srcA和valE这样的信号值有唯一的值。在流水线化的设计中，与各个指令相关联的这些值有多个版本，会随着指令一起流过系统。

例如，在PIPE一的详细结构中，有4个标号为“Stat”的白色方框，保存着4条不同指令的状态码（参见图4-41）。我们需要很小心以确保使用的是正确版本的信号，否则会有很严重的错误，例如将一条指令计算出的结果存放到了另一条指令指定的目的寄存器。我们采用的命名机制，通过在信号名前面加上大写的流水线寄存器名字作为前缀，存储在流水线寄存器中的信号可以唯一地被标识。

例如，4个状态码可以被命名为D_stat、E_stat、M_stat和W_stat。我们还需要引用某些在一个阶段内刚刚计算出来的信号。它们的命名是在信号名前面加上小写的阶段名的第一个字母作为前缀。以状态码为例，可以看到在取指和访存阶段中标号为“Stat”的控制逻辑块。因而，这些块的输出被命名为f_stat和m_stat。

我们还可以看到整个处理器的实际状态Stat是根据流水线寄存器 W 中的状态值，由写回阶段中的块计算出来的。

在命名系统中，大与的丽级“D、“上"、“M和“W指的走流水线奇仔器，所以M_stat指的是流水线寄存器M的状态码字段。小写的前缓“f”、“d”、“e”、“m”和“w”指的是流水线阶段，所以mstat指的是在访存阶段中由控制逻辑块产生出的状态信号。

后面这里提到的一个问题是，我们的寄存器 id 取自指令，它在译码阶段被取出，在写回阶段可能也会用到，就是说，我在译码阶段读出的 rA，rB 可能在写回阶段都要用，如果什么措施都不采取，就直接上流水线的话，我再写回阶段可能写到的是此时正在执行译码阶段的那个寄存器，这显然就改变了它指令的行为，因此我们中间需要插入流水线寄存器确保信息是正确的。

PIPE一中有一个块在相同表示形式的SEQ+中是没有的，那就是译码阶段中标号为“SelectA”的块。我们可以看出，这个块会从来自流水线寄存器D的valP或从寄存器文件A端口中读出的值中选择一个，作为流水线寄存器E的值valA。

包括这个块是为了减少要携带给流水线寄存器E和M的状态数量。在所有的指令中，只有ca11在访存阶段需要valP的值（压入下一个PC）。只有跳转指令在执行阶段（当不需要进行跳转时）需要valp的值。而这些指令又都不需要从寄存器文件中读出的值。因此我们合并这两个信号，将它们作为信号va1A携带穿过流水线，从而可以减少流水线寄存器的状态数量。这样做就消除了SEQ（图4-23）和SEQ+（图4-40）中标号为“Data”的块，这个块完成的是类似的功能。在硬件设计中，像这样仔细确认信号是如何使用的，然后通过合并信号来减少寄存器状态和线路的数量，是很常见的。

预测下一个PC

在PIPE-设计中，我们采取了一些措施来正确处理控制相关。流水线化设计的目的就是每个时钟周期都发射一条新指令，也就是说每个时钟周期都有一条新指令进入执行阶段并最终完成。要是达到这个目的也就意味着吞吐量是每个时钟周期一条指令。要做到这一点，我们必须在取出当前指令之后，马上确定下一条指令的位置。不幸的是，如果取出的指令是条件分支指令，要到几个周期后，也就是指令通过执行阶段之后，我们才能知道是否要选择分支。类似地，如果取出的指令是ret，要到指令通过访存阶段，才能确定返回地址。

但是除此之外，我们都能在取指阶段结束后马上知道下一跳指令的地址，对于无条件跳转来说，下一条指令的地址是指令中的一个常数 valC，对于其他指令来说就是 valP。对于条件跳转指令来说，如果选择了跳转，那么 PC 新的值应当是 valC，如果选择不跳转，那么 PC 新的值应当是 valP。我们既可以预测选择了分支，也可以预测没有选择分支，既然预测能解决以上流水线的问题，我们还必须解决预测错误带来的麻烦，因为发现预测错误的时候往往已经执行了部分我们预测的指令，在之后我们会讨论这个错误处理。

流水线冒险

我们需要在流水线中引入反馈系统，因为当相邻指令有关联的时候，前一条指令并不能和后一条指令并行执行。这个关联有两种形式

• 数据相关：后一条指令需要读取前一条指令执行的结果
• 控制相关：后一条指令为条件跳转，条件取决于当前语句的执行状态。

这些相关有可能会导致指令执行得到错误的结果，称为冒险。同相关一样，冒险也可以氛围数据冒险和控制冒险。我们先考虑数据冒险。

数据冒险的解决方案

暂停

我们可以使用空指令（NOP）来避免冒险，只要我们在译码阶段保证上一条可能会影响我的指令已经完成了写回即可。在中间插入三条 NOP 指令，这样就可以在前一条指令的写回阶段我们再译码，确保不出问题。 当然这是宏观上面我们最容易理解的思路，实际上处理器会自己处理自动阻塞可能会发生冒险的指令，直到冒险条件去除才会继续执行而不是真的插入 NOP 指令，但是实际上执行起来就像插入了 NOP 指令一样。 缺点我们都看得出来，会严重降低整体的吞吐量。

转发

其实很简单，因为译码阶段已经可以确定寄存器和立即数，如果在 irmovq 的译码阶段我直接取出这个数，给较早的流水线阶段，这样甚至能避免下一条指令译码取数，这样就能避免暂停，这种技术称为数据转发（简称转发或者旁路（bypassing））。 有时候，值可能是在执行阶段得到的，我们在这个阶段得到的值同样可以给到下一条指令，但是需要硬件提供点小小的支持。

加载/使用冒险

转发操作不能解决这种冒险，如果有一个指令是访存得到寄存器的值（Load），它将在访存阶段才能拿到，而紧接着的下一条指令会使用这个寄存器，那么此时转发就不能解决了，因为下一条指令已经进入了执行阶段。

因此我们可以使用暂停+转发两种思想结合的方式解决冒险，如果发现访存得到的结果需要在下一条指令马上被访问，那么我就暂停一个指令周期等到访存结束之后马上转发给下一条指令，此时下一条指令正在译码阶段，还能来得及。

避免控制冒险

当遇到条件跳转语句或 ret 指令的时候，处理器无法仅仅通过 PC 来预测下一条指令的地址。

不难发现，当执行 ret 的时候，我们需要等到 ret 访存完毕的时候才可以预测到下一条指令的地址，因此我们需要在中间插入三个 bubble。

而条件跳转指令预测错误的后果就是会多处理两条不该执行的指令，好在它们执行的指令只是到了译码阶段，并没有对实际的寄存器和内存做出什么变动，唯一的后果就是浪费了两条指令的处理能力。

---

这一章彻底结束吧，把最基本的冒险，和解决方案了解完真的感觉差不多了，后面基本都是硬件部分，正式进入第五章了！