CSAPP 第四章 Y86-64的顺序实现与流水线处理器

CSAPP 第四章 Y86-64的顺序实现与流水线处理器

将处理指令的过程抽象为阶段 OPq系列指令和 rrmovq ,irmovq指令 rmmovq 和 mrmovq 指令 pushq 和 popq 指令 跳转指令 call 和 ret 条件传送系列指令 流水线 将处理抽象为阶段 要设计一个处理器, 需要将指令分为不同的阶段, 根据不同的阶段来优化. 各

  1. 将处理指令的过程抽象为阶段
  2. OPq系列指令和 rrmovq ,irmovq指令
  3. rmmovq 和 mrmovq 指令
  4. pushq 和 popq 指令
  5. 跳转指令 call 和 ret
  6. 条件传送系列指令
  7. 流水线

将处理抽象为阶段

要设计一个处理器, 需要将指令分为不同的阶段, 根据不同的阶段来优化. 各个阶段有:
  1. 取指令 fetch. 即读取指令字节, 地址为程序计数器的值. 读取的指令, 根据之前的指令集, 可以知道, 取出的指令从1-10字节不等. 这里把指令字节的前四位叫做icode, 后四位叫做ifun. 将之后的寄存器指示字节的高四位叫做rA, 低四位叫做rB. 根据具体指令的不同, 也可能取的是一个8字节的值, 叫做valC. 只要取了指令, 根据指令的长度, 会计算出下一条指令的长度等于PC的值加上当前指令的长度, 这个新地址叫做valP.
  2. 译码 decode, 根据 rA 和 rB 指明的寄存器, 从寄存器文件中读取最多两个操作数, 对应rA的叫做valA, 对应rB的叫做valB
  3. 执行 execute, 在这个阶段之前, valA, valB, icode, ifun, valC都必须准备好. 然后会将这些值送入ALU. ALU根据送入的内容, 会产生输出, 叫做valE. 看指令可以知道, 除了产生一个值之外, 还可能决定跳转, 更新条件码, 等等. 更新寄存器也在这个阶段.
  4. 访存 memory, ALU及寄存器电路更新完毕之后, 这个阶段可以将数据写入内存, 或者从内存读出数据, 读出的值叫做valM.
  5. 写回, 这个阶段指的是写寄存器, 而不是写内存. 最多写两个结果到寄存器.
  6. 更新程序计数器 PC update, 将PC设置成下一条指令的地址.

OPq系列指令和 rrmovq ,irmovq指令

这一系列指令无需操作内存, 来看一看三者的执行过程:
阶段 Opq rA, rB rrmovq rA, rB irmovq V, rB
取指令 从程序计数器的地址中取出icode:ifun, 由于是单字节, 下一条程序计数器的地址 +1: M1[PC] => icode:ifun 取单字节, 表示两个寄存器, 下一条程序计数器的地址 +1: M1[PC+1] => rA : rB 取完了两字节的指令, 得到下一条程序计数器的地址是 PC + 2, 此时知道了valP的值: PC + 2 => valP 由于rrmovq和OPq操作的都是两个寄存器, 因此这一阶段和OPq相同. irmovq相比前两个操作, 除了读入之前两个操作的两字节之外, 还需要读入额外的8字节操作数valC: M8[PC+2] => valC valP => PC + 10
译码 从寄存器中读出valA和valB: R[rA] => valA R[rB] => valB 由于rrmovq只需要知道rA的值,因此只取rA的值: R[rA] => valA 由于valA是不用操作的, valB是目标, 所以无需译码
执行 将valB 和 valA 送入ALU进行操作, 得到 valE: valA OP valB => valE 同时我们的Y86还会在此时设定条件码: Set CC 此时由于无需计算valA, 实际的操作就是valA + 0, 不改变valA: valA + 0 => valE 无需记性计算, 只是把valC 放入 valB, 所以valE就是valC: valC + 0 => valE
访存 仅操作寄存器, 无需访存 仅操作寄存器, 无需访存 这个也无需访存
写回 要把valE写入到 rB中: valE => R[rB] 要把valE写入到 rB中: valE => R[rB] 要把valE写入到 rB中: valE => R[rB], 这三条操作都是对rB操作, 所以是一样的
更新PC 更新程序计数器: valP => PC 更新程序计数器: valP => PC 同样需要更新程序计数器: valP => PC, 这条指令长度是10字节

练习 4.13 描述irmovq指令的具体执行过程

阶段 通用 具体
irmovq V, rB irmovq $128, %rsp
取指令 icode:ifun <- M1[PC] rA:rB <- M1[PC+1] valP <- PC + 2 icode:ifun <- M1[0x016] = 3:0 rA:rB <- M1[0x016+1] = f:4 valC <- M8[0x016+2] = 0x80 valP <- 0x016+A = 0x020
译码 这个是从立即数传送到寄存器, 无需取寄存器值
执行 valE <- 0 + valC valE <- 128 = 128
访存 立即数和寄存器操作, 无需访问内存
写回 R[rB] <- valE R[%rsp] <- valE = 128 ZF = 0, SF = 0, OF = 0
更新PC PC <- valP PC <- valP = 0x20
执行完该指令的效果是, PC加上10, %rsp 的值变成128.

rmmovq 和 mrmovq 指令

这两个指令相比前边的指令, 最大的特点的带上了内存读写, 也就是存在访存操作. 因为有了访存操作, 在之前需要计算出内存地址, 这个是在执行阶段计算的. 其他的步骤基本上相同.
阶段 rmmovq rA, D(rB) mrmovq D(rB), rA
取指令 两个取指令都是一样的: 取指令: icode:ifun <= M1[PC] 取寄存器: rA:rB <= M1[PC+1], 注意mrmovq解释寄存器的顺序相反 取偏移量常数: valC <= M1[PC+2] 指令是10字节长度, 计算出新的PC地址: valP = PC + 10
译码 取出valA和valB, 因为valA是要写入的值, valB是基地址, 都要用到 只要取出valB即可, 因为valB的值是基地址, 要计算出实际的内存地址. rA则是目标对象 ,无需取出valA.
执行 两者这里是一样的, 都需要通过valC和valB计算出实际内存地址: valE = valB + valC
访存 这条指令需要把valA写入valE对应的内存地址: valA => M8[valE] 这条指令先要从计算出的内存地址中取出valM M8[valE] => valM
写回 这个指令无需写回寄存器 将刚刚取出的valM写入寄存器: valM => R[rA]
更新PC PC <= valP
根据265页第5行的rmmovq 的指令跟踪如下:
阶段 具体
rmmovq %rsp, 100(%rbx)
取指令 指令是4043, icode:ifun = 4:0 寄存器是 rA : rB = 4:3, 分别是%rsp, %rbx 取常数 valC = 100 10字节长度指令: valP = PC + 10 = 0x02a
译码 这个阶段需要两个码都译出来: R[rA] => valA R[rB] => valB
执行 valA无需再计算, 关键是计算地址: valE = valB + valC
访存 要把valA写入到valE地址内: valA => M8[valE]
写回 无需写回寄存器操作
更新PC 0x02a => PC
现在已经把我们指令集中的无条件传送的系列和OPq系列都看完了, 基本上差异不大, 主要是在访存阶段.

pushq 和 popq 指令

这两个指令相比之前的, 就有一些复杂了, 因为相比上边的指令, 还多了要操作%rsp寄存器的过程. 这里要注意X86-64, 也是我们的Y86-64遵循的惯例, 先读内存, 再更新%rsp.
阶段 pushq popq
取指令 两个取指令都是一样的: 取指令: icode:ifun <= M1[PC] 取寄存器: rA:rB <= M1[PC+1], 注意mrmovq解释寄存器的顺序相反 指令是2字节长度, 计算出新的PC地址: valP = PC + 2
译码 pushq的译码要注意, 在指令里取出来的rB是F, 但是这里实际操作需要从rA中取到valA, 因为这是要压栈的数据. 此外还自动从当前的%rsp中取出当前的栈地址, 当做valB M8[rA] => valA M8[%rsp] => valB popq这里更特别, 由于是从栈里取数, 现在寄存器中的值是什么无需关心, 这里取两次%rsp的值分别放入valA和valB: R[%rsp] => valA R[%rsp] => valB
执行 想一想之前的要求, 在写入内存之后, 更新栈指针. 要先计算出来写入内存之后新的栈顶指针. 由于栈顶指向的是第一个元素, 所以要算出来新的栈顶地址: valB - 8 => valE 对比一下pushq, 当前的%rsp指向的是当前的栈顶, 要先计算出来弹栈之后的下一个栈顶地址: valB + 8 => valE
访存 访存对于两个指令来说很关键, 压栈就是将valA压入新的栈顶对应的地址: valA => M8[valE] 弹栈这里要注意, 是从原来的栈顶, 也就是valA中读出数据, 不是valE M8[valA] => valM
写回 这里要注意, 写回的时候写哪个? 显然是更新过的栈指针valE valE => R[%rsp] 这里要注意, 写回栈指针用的也是更新过的栈指针valE valE => R[%rsp] 此外由于是弹栈, 还需要将读取的valM写入到rA寄存器中来: valM => R[rA] 注意这是有顺序的, valM后发生
更新PC 这2个指令都是2字节, 所以 newPC <= PC + 2
对比了这两个指令的时候, 注意两个指令在valA和valB上的操作, 将没有使用到的值都载入了%rsp的值, 然后通过valE计算出新的栈顶. 在具体操作内存的时候, 压栈是直接用新的栈顶压栈, 再将新栈顶写回寄存器. 弹栈则是用老栈顶读数据, 将新栈顶和读出的数据写回寄存器. 从两者整体来看, 都是先操作内存, 再操作%rsp. 符合一开始说的惯例要求.

练习4.14 popq 指令的处理情况:

在popq之前, 可以发现已经执行过一次pushq, 则当前的栈顶地址是第4条指令设置的%rsp 128 - 8 = 120
阶段 具体
popq %rax
取指令 指令是b00f, icode:ifun = b:0 寄存器是 rA : rB = 0:f, 分别是%rax, 无寄存器 2字节长度指令: valP = 0x02A + 2 = 0x02C
译码 注意没有使用到的valA和valB: R[%rsp] => valA = 120 R[%rsp] => valB = 120
执行 计算弹栈后的栈顶指针 valE = valB + 8 = 120 + 8 = 128
访存 要从原来的栈顶地址120中读出valM: M8[120] => valM = 9, valM实际上是上一条压入的%rdx的值, 就是9
写回 需要两个写回, 写栈指针和数据: 9 => R[%rax] 128 => R[%rsp], 向%rsp中写入128
更新PC 0x02E => PC

练习题 4.15 如果第6行指令改成pushq %rsp会如何呢?

也来按照逻辑跟踪一下:
阶段 具体
pushq %rsp
取指令 指令是a04f, icode:ifun = b:0 寄存器是 rA : rB = 4:f, 分别是%rsp, 无寄存器 2字节长度指令: valP = 0x02a + 2 = 0x02c
译码 注意此时的%rsp中是128, 两个数都取到, 但是一个是用来压入栈, 一个去计算新的栈顶地址: R[%rsp] => valA = 128 R[%rsp] => valB = 128
执行 计算压后的栈顶指针 valE = valB - 8 = 120
访存 注意压入栈的是valA的值128: M8[120] <= 128
写回 压栈需要写回新的栈地址 120(valE) => R[%rsp], 向%rsp中写入120
更新PC 0x02C => PC
可以看到, 压入栈的是128(valA), 也即%rsp的原来地址, 与4.7的结果是一致的.

练习题 4.15 如果第6行指令改成pushq %rsp, 然后第7行指令改成 popq %rsp 会如何呢?

在执行完第6条指令的时候, %rsp中的值是120, 而栈顶中的值是128. 然后继续看popq指令:
阶段 具体
popq %rsp
取指令 指令是b04f, icode:ifun = b:0 寄存器是 rA : rB = 0:f, 分别是%rsp, 无寄存器 2字节长度指令: valP = 0x02C + 2 = 0x02E
译码 注意没有使用到的valA和valB: R[%rsp] => valA = 120 R[%rsp] => valB = 120
执行 计算弹栈后的栈顶指针 valE = valB + 8 = 120 + 8 = 128
访存 要从原来的栈顶地址120中读出valM: M8[120] => valM = 128
写回 需要两个写回, 写栈指针和数据: 128(valE) => R[%rsp], 向%rsp中写入128 128(valM) => R[%rsp] 这里注意, 写valM的是后发生的, 所以最终执行完, 就是将%rsp设置成从内存读出的值
更新PC 0x02E => PC
可见由于valM最后执行, 所以最终就是直接将%rsp设置成读出的值. 和4.7 中的结论是一致的.

跳转指令 call 和 ret

跳转指令以及call和ret指令的特点是无需寄存器指令字节. 跳转指令比较特别的地方在于会在执行阶段更新一个Cnd信号, 用于表示跳转判断的结果. 由于跳转的本质就是更新程序计数器, 所以在更新PC的阶段, 会根据CC码来判断要将跳转的地址写入PC, 还是仅仅更新PC到下一条指令的地址. call 和 ret 则是包含了操作栈的指令, 实际上整个指令的后半段都是在操作栈, 所以要在学了push和pop之后再来看这两个指令.
阶段 jxx Dest call Dest ret
取指令 M1[PC] => icode:ifun valC => M8[PC+1] 取跳转地址 valP = PC +9, 9字节长的指令 与jxx 指令完全相同: M1[PC] => icode:ifun valC => M8[PC+1] valP = PC +9, 9字节长的指令 ret指令是1字节指令, 无需取常数: M1[PC] => icode:ifun valP = PC +1
译码 jxx无需译码, 因为不需要操作寄存器和内存, 要跳转的地址valC和下一条指令地址valP均已知 call包含了压栈操作, 按照压栈的流程, valA由于没有, 就用不到, 但是要把当前栈地址取出来: R[%rsp] => valB ret包含了弹栈操作, 所以是valA和valB都要设置成%rsp R[%rsp] => valA R[%rsp] => valB
执行 jxx的执行阶段会根据跳转功能, 检测对应的条件码, 然后更新Cnd码 Cond(CC, ifun) => Cnd 信号 压栈, 所以栈指针-8 valE = valB - 8 弹栈, 栈指针+8 valE = valB + 8
访存 完全不需要访存 压栈, 将下一条地址压入栈中, 下一条地址是已经计算出的valP valP => M8[%rsp] 弹栈, 用原始的栈指针去读valM, valM就是将跳转的地址 valM = M8[valA]
写回 也无需写回 更新%rsp 为 -8 之后的数字 valE => R[%rsp] 将栈地址更新到 +8 的地址, 由于不涉及其他寄存器, 无需将值写入其他寄存器, 只更新栈指针寄存器: valE => R[%rsp]
写回 这里很关键, 根据Cnd信号, 决定是把下一条地址写入PC(即不跳转), 还是把常数地址valC写入PC(即执行跳转): Cnd? valC: valP => PC 由于压完了当前下一条地址, 下边就要跳转了, 所以是把常数valC 写入 PC: valC => PC 从内存中读取了要跳转的地址 valM, 很显然要把valM 写入 PC: valM => PC
可以看到, 上边这个几个指令的精髓操作PC. jxx利用了条件判断来写PC, call 和 ret 则是将压栈弹栈与更新PC结合起来.

条件传送系列指令

条件传送这里是用一个练习题来做的, 相比rrmovq来说, 条件传送其实就是加上一个判断, 然后用判断来决定是否更新寄存器的值. 练习 4.17 用rrmovq修改成cmovXX的阶段
阶段 rrmovq rA, rB cmovXX rA, rB
取指令 icode:ifun <= M1[PC] rA: rB <= M1[PC+1] valP <= PC+2 这个阶段是一样的,是2字节指令
译码 valA => R[rA] 这里要把两个码都译出来, 决定用哪一个进行传送
执行 valE = 0 + valA valE = 0 + valA 除了计算valE之外, 条件传送的关键在于根据条件码来设置Cnd: Cnd = Cond(CC, ifun)
访存 无需访存 无需访存
写回 R[rB] => valE 这里的关键是要根据Cnd来决定用valE写回rB, 还是不做操作: Cnd? valE => R[rB]
更新PC valP => PC valP => PC

练习 4.18 跟踪call 指令的具体阶段

在执行call指令之前, %rsp依然是128.
阶段 call 0x041
取指令 icode:ifun = M1[0x037] = 8:0 valC = M8[0x038] = 0x41 valP = 0x037+9 = 0x040
译码 valB = R[%rsp] = 128
执行 valE = valB - 8 = 120
访存 0x040(valP) => M[120]
写回 120(valE) => R[%rsp]
更新PC 0x41(valC) => PC
这条指令执行完之后, 就是把0x040压入栈, 栈指针更新到120, 然后将PC的值设置成0x41. 目前已经把指令集中的所有指令都分解成了阶段.

流水线

简单的说, 就是有一块不由时钟控制的逻辑电路, 我管这个叫处理电路, 还有由时钟控制的存储电路. 还需要保证, 处理电路不会因为执行指令要去重复读自己计算的结果. 因此要将处理电路的输入都接在存储电路的输出上, 将处理电路的输出,都接入到存储电路的输入上. 这样形成一个闭环, 只需要控制存储电路的时钟, 就能够在一个周期内, 改变处理电路的状态. 每个周期里时钟信号为高的时候, 上一条指令的状态会被写入到各个存储器和程序计数器中, 然后存储器中的值就会更新到输出端. 然后连在输出端的处理电路整个的状态就会更新, 但是还没有来的及写入, 时钟就变为低信号. 此时存储器中的结果就是上一条指令的执行结果, 而当前指令的执行结果就是处理电路当前的状态. 然后到了下一个周期, 存储器中的内容会改成当前上一个周期的处理结果, 新的指令的执行结果又会反映在处理电路的当前状态上. 关键是理解每次时钟由低变高的瞬间, 也就是上升沿, 会写入存储电路. 之前一直理解成高位可以写入. 其实就那么一瞬间而已. 在分阶段的时候, 我们可以发现所有指令都需要的数据不外乎rA, rB, valA, valB, valC, valM, valP, 条件码, Cnd, ifun, icode等等.... 如果在不同的阶段的电路中间, 插入流水线寄存器, 保存这些所有需要的数据, 会是什么样子呢? 实际上, 指令在每次时钟改变的时候, 只会改变部分电路的状态. 而已经使用过的电路, 又可以执行新的指令, 这就像水面扔了一个石头, 某一个时刻看, 两个波之间始终有波在前进, 指令是一段一段的流过所有圆圈, 这就是流水线的原理. 流水线会增加单条指令的延迟, 但是可以极大的提高吞吐量. 流水线的各个阶段如果延迟能一致,那是很好的, 但是现实中很难做到, 流水线的时钟周期取决于总时间最长的一个处理过程. 流水线后边的部分, 原理基本上懂了, 控制电路的部分就不一一看了. 继续进行第五章吧.
LICENSED UNDER CC BY-NC-SA 4.0
Comment