ArchLab

05 06 的实验基本相同, 本节主要介绍有关体系结构的基础知识以及 Y86-64 的设计, 所有的实验解答都一起放在下一节 06-ArchY86Lab 中

关于体系结构的实验可能做的人不会很多, 指令集/处理器对于相当一部分人来说都是很陌生的, 直接上手 Y86 汇编应该是相当吃力的, 因此建议读者先阅读一下第四章处理器体系结构, 再结合实验所提供的文档继续完成实验

笔者也对书中内容和文档资料做了一些总结

处理器体系结构

我们知道处理器必须执行一系列指令, 每条指令执行某个简单操作, 例如两个数相加. 指令被编码为由一个或多个字节序列组成的二进制格式. 一个处理器支持的指令和指令的字节集编码称为它的指令集体系结构(Instruction-Set Architecture ISA).

不同的处理器家族, 例如 X86-64, ARM 都有不同的 ISA. 一个程序编译成在一种机器上运行就不能再另一种机器上运行.

另外同一个家族里也有很多不同型号的处理器, 虽然每个厂商制造的处理器性能和复杂性不断提高, 但是不同型号在 ISA 级别上都保持着兼容. 一些常见的处理器家族,例如 x86-64 的处理器分别由多个厂商提供, 因此 ISA 在编译器编写者和处理器设计人员之间提供了一个概念抽象层, 编译器编写者只需要知道允许哪些指令以及他们是如何编码的; 而处理器设计者必须制造出执行这些指令的处理器.

Y86 指令集体系结构

本章首先定义一个简单的指令集,作为我们处理器实现的运行示例.因为受x86-64指令集的启发,它被俗称为"x86",所以我们称我们的指令集为"Y86-64"指令集.与x86-64 相比,Y86-64指令集的数据类型、指令和寻址方式都要少一些.它的字节级编码也比较简单,机器代码没有相应的x86-64 代码紧凑,不过设计它的CPU译码逻辑也要简单一些.虽然Y86-64 指令集很简单,它仍然足够完整,能让我们写一些处理整数的程序.设计实现 Y86-64的处理器要求我们解决许多处理器设计者同样会面对的问题.

想要定义一个指令集体系结构(例如 Y86-64), 那么需要定义各种状态单元、指令集和它们的编码、一组编程规范和异常事件处理.

如上图所示, Y86 的程序可见状态包括寄存器, 条件码, 内存, 程序状态. Y86 的程序可以访问和修改程序寄存器, 条件码, 状态码, 来指明程序是否正常运行, 或者发生了一些特殊事件

• Y86 具有类似 x86-64 有 15 个程序寄存器(省略了 r15). 每一个寄存器存储一个 64 位的字. 除了寄存器 rsp 被入栈/出栈/调用/返回指令作为栈指针外, 寄存器没有固定的含义或固定值

• Y86 有 3 个一位的条件码 ZF SF OF , 他们保存着最近的算术或逻辑指令所造成影响的有关信息, 程序计数器 PC 存放当前正在执行指令的地址

• 内存从概念上来说是一个很大的字节数组, 保存着程序和数据. 程序状态码 stat 表明程序执行的总体状态, 它会指示正常运行还是出现了某种异常.

  stat 的状态在 Y86-64 架构中一共有4种, 如下所示

  

  对于 Y86-64 当遇到这些异常的时候简单的让处理器停止执行指令, 在更完整的设计中,处理器通常会调用一个异常处理程序(exception handler),这个过程被指定用来处理遇到的某种类型的异常.异常处理程序可以被配置成不同的结果,例如中止程序或者调用一个用户自定义的信号处理程序(signal handler).

Y86-64 指令集

Y86-64 指令集基本上是 x86-64 的一个子集, 如下所示. 其中指令为 1-10 字节不定长编码, 仅支持对于整数的操作, 下面来详细介绍一下

这里希望读者已经对第三章x86汇编有所了解, 不然读起来会有些吃力

• halt(停止指令执行, 类似x86的hlt), nop 空指令, call ret pushq popq 和 x86 中使用方式相同

• x86 中的 movq 在 Y86 当中被拆分成了4条指令 SDmovq, 其中 S 代表源类型, 可以是立即数(i), 寄存器(r), 内存(m). D 代表目的类型, 可以是寄存器(r)和内存(m).

  同x86-64一样, Y86 不支持从一个内存地址直接传送到另一个内存地址, 也不允许将立即数传送到内存, 所以合法的movq指令剩下 32-2 = 4种, 分别是 irmovq, rrmovq, mrmovq, rmmovq*

  同时在内存传送指令的内存引用方式只支持基地址(rb)+偏移量(Imm)的方式. 例如 rmmovq rA, D(rB). 不支持像 x86-64 一样更复杂的第二变址寄存器(ri)和寄存器值的伸缩(scale), 例如 Imm(%rb, %ri, s), 这是不支持的

  上图中 irmovq 的 F 表示一个不访问任何寄存器, 即空占位(因为Y86中没有r15(0xf))

• OPq 为整数操作指令, Y86 中仅支持操作整数. OPq 有4种分别是 addq, subq, andq, xorq, 它们由图中 fn(依次顺序对应0-3)来区分, 在计算结束后还会设置 ZF SF OF 三个条件码

  x86 还支持对内存数据进行操作, 不过Y86不支持

• jXX 为跳转指令有7种, 由fn区分. jmp jle jl je jne jge jg. 同x86-64的分支条件, 根据条件码和指令类型进行跳转

• cmovxx 为条件传送指令有6种, 由fn区分, cmovle, cmovl, cmove, cmovne, cmovge, cmovg

下图为 x86 支持的内存传送指令, Y86 仅支持基地址+偏移量的方式

上面提到了 4 种整数操作指令, 7 种跳转指令和 6 种条件传送指令的 fn 对应值如下图所示

跳转的条件码判断如下图所示, 和 x86 完全相同

寄存器数字编号与名称对应值如下图所示, F 代表无寄存器

最后我们整体观察一下 Y86 指令集特点: 0 字节用于区分指令类型, 有的指令需要附加的寄存器指示符字节, 有的还需要操作数.这些寄存器字段称为rA和rB.从指令的汇编代码表示中可以看到,根据指令类型,指令可以指定用于数据源和目的的寄存器,或是用于地址计算的基址寄存器.没有寄存器操作数的指令,例如分支指令和call 指令,就没有寄存器指示符字节.那些只需要一个寄存器操作数的指令(irmovq、pushq和 popq)将另一个寄存器指示符设为0xF.这种约定在我们的处理器实现中非常有用.

有些指令需要附加一个 4 字节的常数字, 作为立即数数据/地址偏移量/目的地址, 值得注意的是作为目的地址的时候是一个绝对地址, 而不是像 IA32 一样使用 PC 相对地址. 同时对于整数使用了小端序.

例如,用十六进制来表示指令rmmovq %rsp,0x123456789abcd (%rdx)的字节编码.其中rrmmovq的第一个字节为40.源寄存器%rsp应该编码放在rA字段中,而基址寄存器%rdx应该编码放在rB字段中.查表得到寄存器指示符字节 42.最后,偏移量编码放在8字节的常数字中.首先在Ox123456789abcd的前面填充上0变成8个字节,变成字节序列00 012345 67 89 ab cd.写成按字节反序就是cd ab 89 67 45 23 01 00.将它们都连接起来就得到指令的编码 4042cdab896745230100

指令集的一个重要性质就是字节编码必须有唯一的解释.任意一个字节序列要么是一个唯一的指令序列的编码,要么就不是一个合法的字节序列.Y86-64就具有这个性质,因为每条指令的第一个字节有唯一的代码和功能组合,给定这个字节,我们就可以决定所有其他附加字节的长度和含义.

这个性质保证了处理器可以无二义性地执行目标代码程序.即使代码嵌入在程序的其他字节中,只要从序列的第一个字节开始处理,我们仍然可以很容易地确定指令序列.反过来说,如果不知道一段代码序列的起始位置,我们就不能准确地确定怎样将序列划分成单独的指令.对于试图直接从目标代码字节序列中抽取出机器级程序的反汇编程序和其他一些工具来说,这就带来了问题.

同x86-64中的指令编码相比,Y86-64的编码简单得多,但是没那么紧凑.在所有的Y86-64指令中,寄存器字段的位置都是固定的,而在不同的x86-64指令中,它们的位置是不一样的.x86-64可以将常数值编码成 1、2、4或8个字节,而Y86-64总是将常数值编码成8个字节.

另外关于 RISC CISC 指令集的讨论, 书中也给出了两段旁注, 非常值得一读.

20世纪80年代,计算机体系结构领域里关于RISC指令集和CISC 指令集优缺点的争论十分激烈.RISC的支持者声称在给定硬件数量的情况下,通过结合简约式指令集设计、高级编译器技术和流水线化的处理器实现,他们能够得到更强的计算能力.而CISC的拥趸反驳说要完成一个给定的任务只需要用较少的CISC指令,所以他们的机器能够获得更高的总体性能.

然而事实证明无论是单纯的RISC还是单纯的CISC都不如结合两者思想精华的设计.RISC机器发展进化的过程中,引入了更多的指令,而许多这样的指令都需要执行多个周期.今天的RISC机器的指令表中有几百条指令,几乎与"精简指令集机器"的名称不相符了.那种将实现细节暴露给机器级程序的思想已经被证明是目光短浅的.随着使用更加高级硬件结构的新处理器模型的开发,许多实现细节已经变得很落后了,但它们仍然是指令集的一部分.不过,作为RISC设计的核心的指令集仍然是非常适合在流水线化的机器上执行的.

比较新的CISC机器也利用了高性能流水线结构.它们读取CISC指令,并动态地翻译成比较简单的、像 RISC那样的操作的序列.例如,一条将寄存器和内存相加的指令被翻译成三个操作:一个是读原始的内存值,一个是执行加法运算,第三就是将和写回内存.由于动态翻译通常可以在实际指令执行前进行,处理器仍然可以保持很高的执行速率.

Y86-64 程序

书中给出了一个比较基础的汇编程序示例, 对照左侧 x86-64 指令集, 右侧也都是前文介绍过的汇编指令. y86-64 采用了和x86-64相同的参数传递和寄存器保存方法, 即 rdi rsi rdx rcx r8 r9 然后放在栈上

观察上面的程序, 可以注意到一些不同之处

• Y86-64 需要先将常数加载到寄存器, 因为在算数指令不能使用立即数

• 从内存中读取一个数值并于一个寄存器值相加(sum+=*start)在 Y86-64 中需要两条指令(8,9), 而 x86-64 只需要一条 addq(5)

• Y86-64 中11行使用了 subq 实现 -1 之外还设置了条件码, 可以直接进行后续的 jne 判断而不需要像 x86 一样通过 testq 判断

下面是一段比较简单但是完整的 y86-64 汇编代码, 你可以在 y86-code/asum.ys 中找到这段代码. 这段代码就是利用上面的 sum 函数, 对于 array 数组中的元素求和

# Execution begins at address 0 
    .pos 0
    irmovq stack, %rsp      # Set up stack pointer
    call main       # Execute main program
    halt            # Terminate program
# Array of 4 elements
    .align 8
array:
    .quad 0x000d000d000d
    .quad 0x00c000c000c0
    .quad 0x0b000b000b00
    .quad 0xa000a000a000
main:
    irmovq array,%rdi
    irmovq $4,%rsi
    call sum        # sum(array, 4)
    ret
# long sum(long *start, long count)
# start in %rdi, count in %rsi
sum:
    irmovq $8,%r8        # Constant 8
    irmovq $1,%r9        # Constant 1
    xorq %rax,%rax       # sum = 0
    andq %rsi,%rsi       # Set CC
    jmp     test         # Goto test
loop:
    mrmovq (%rdi),%r10   # Get *start
    addq %r10,%rax       # Add to sum
    addq %r8,%rdi        # start++
    subq %r9,%rsi        # count--.  Set CC
test:
    jne    loop          # Stop when 0
    ret                  # Return
# Stack starts here and grows to lower addresses
    .pos 0x200
stack:

除了我们熟悉的y86-64指令集, 汇编中还出现了#开头的注释, . 开头的汇编伪指令以及段的声明, 这部分与 x86 汇编类似, 简单解释一下.

• .pos 指的是从当前地址开始生成代码, 比如开头的 .pos 0 和结尾的 .pos 0x200

• .align 用于对齐

• .quad 用于定义一个四字(8字节)

• 声明不分前后, 比如 main stack 等段名都定义在后文, 最后生成机器码时会做一个名称到地址的翻译

可以利用 yas 汇编器先将 y86-64 的汇编代码转换为对应的机器码

# in directory y86-code
$ ../misc/yas asum.ys

得到 asum.yo 文件内容如下, 可以看到对应的汇编指令按照前文提到的指令编码方式被整齐的转换为机器码

                            | # Execution begins at address 0
0x000:                      |   .pos 0
0x000: 30f40002000000000000 |   irmovq stack, %rsp      # Set up stack pointer
0x00a: 803800000000000000   |   call main       # Execute main program
0x013: 00                   |   halt            # Terminate program
                            |
                            | # Array of 4 elements
0x018:                      |   .align 8
0x018: 0d000d000d000000     | array:    .quad 0x000d000d000d
0x020: c000c000c0000000     |   .quad 0x00c000c000c0
0x028: 000b000b000b0000     |   .quad 0x0b000b000b00
0x030: 00a000a000a00000     |   .quad 0xa000a000a000
                            |
0x038: 30f71800000000000000 | main: irmovq array,%rdi
0x042: 30f60400000000000000 |   irmovq $4,%rsi
0x04c: 805600000000000000   |   call sum        # sum(array, 4)
0x055: 90                   |   ret
                            |
                            | # long sum(long *start, long count)
                            | # start in %rdi, count in %rsi
0x056: 30f80800000000000000 | sum:  irmovq $8,%r8        # Constant 8
0x060: 30f90100000000000000 |   irmovq $1,%r9        # Constant 1
0x06a: 6300                 |   xorq %rax,%rax       # sum = 0
0x06c: 6266                 |   andq %rsi,%rsi       # Set CC
0x06e: 708700000000000000   |   jmp     test         # Goto test
0x077: 50a70000000000000000 | loop: mrmovq (%rdi),%r10   # Get *start
0x081: 60a0                 |   addq %r10,%rax       # Add to sum
0x083: 6087                 |   addq %r8,%rdi        # start++
0x085: 6196                 |   subq %r9,%rsi        # count--.  Set CC
0x087: 747700000000000000   | test: jne    loop          # Stop when 0
0x090: 90                   |   ret                  # Return
                            |
                            | # Stack starts here and grows to lower addresses
0x200:                      |   .pos 0x200
0x200:                      | stack:

最后使用 yis 执行结果如下, 可以观察到 rax 寄存器的值变为定义的四个数组元素的和 0xabcdabcdabcd. 同时由于在汇编中使用了两次call(call main, call sum), 栈rsp指针为 0x200, 所以下面的两个内存地址(0x01f0, 0x01f8) 的值也被修改了, 不过好在 asum.yo 中代码段可以看到最后的位置是 0x090: 90, 所以数值的入栈和出栈没有影响到代码段

$ ../misc/yis  asum.yo
Stopped in 34 steps at PC = 0x13.  Status 'HLT', CC Z=1 S=0 O=0
Changes to registers:
%rax:   0x0000000000000000      0x0000abcdabcdabcd
%rsp:   0x0000000000000000      0x0000000000000200
%rdi:   0x0000000000000000      0x0000000000000038
%r8:    0x0000000000000000      0x0000000000000008
%r9:    0x0000000000000000      0x0000000000000001
%r10:   0x0000000000000000      0x0000a000a000a000

Changes to memory:
0x01f0: 0x0000000000000000      0x0000000000000055
0x01f8: 0x0000000000000000      0x0000000000000013

数字电路和逻辑门

接下来书中又介绍了关于数字逻辑电路的相关知识, 首先是最基础的三个布尔函数 AND OR NOT, 对应的表示HCL符号为 && || !

利用这三个基本的逻辑门就可以构建很多复杂的组合电路, 这些电路的网络有一些限制

1. 每个逻辑门的输入必须连接到 [一个系统输入] | [某个存储器单元的输出] | [某个逻辑门的输出]

2. 两个或多个逻辑门的输出不能连在一起(会导致信号矛盾, 不合法的电压/电路故障)

3. 无环(会导致计算歧义)

下面来看一个简单的例子, 下图的组合电路的效果是只有a,b同为1/0的时候结果才为1, 想要写出它的HCL语言可以从右向左看, 首先是一个OR, 所以是 bool x = ? || ?, 上下再分别观察拆分为 bool x = (a&&b) || (!a && !b)

再看一个小例子, 下图是一个很经典的组合电路, 也被称为多路复用器(MUX), 其特点为当 s=1 时结果为 a 的值, 当 s=0 时结果为 b 的值, 其 HCL 表示为 bool x = (s&&a) || (!s&&b)

同时需要注意的是 HCL 表达式和 C 表达式也有一些区别

1. 因为组合电路是由一系列的逻辑门组成,它的属性是输出会持续地响应输入的变化.如果电路的输人变化了,在一定的延迟之后,输出也会相应地变化.相比之下,C表达式只会在程序执行过程中被遇到时才进行求值.

2. C的逻辑表达式允许参数是任意整数,0表示FALSE,其他任何值都表示TRUE.而逻辑门只对位值0和1进行操作.

3. C的逻辑表达式有个属性就是它们可能只被部分求值.如果一个AND或OR操作的结果只用对第一个参数求值就能确定,那么就不会对第二个参数求值了.而组合逻辑没有部分求值这条规则,逻辑门只是简单地响应输入的变化.

通过将位级电路进行组合可以得到更大的网, 处理器设计经常会包含很多字, 我们可以做一个字级别的抽象, 如下图所示, 只要AB的每一位都相同我们就可以说 A == B. 这里的字级抽象即将线所代表的意义从比特上升为了(8*)含义上的字

于此同时处理器中也会经常使用多路复用器, 下图是前文提到过的MUX, 其效果是当 s=1 时输出A, 否则输出B. 对应的字级抽象如右侧所示.

但是这里的 HCL 表达式会有一点点奇怪, 这里简单解释一下. 多路复用函数采用情况表达式来描述, 表达式的通用格式就是 [select: expr; ...]. 这里不要求每一个表达式都互斥, 且表达式的选择是顺序求值的, 第一个求值为1 的情况会被选中, 有点类似 if elif elif ... else

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

所以分析一下上面的HCL表达式, 当 s=0 的时候第一项没有匹配到, 所以选择了第二项B. 当s=1的时候匹配到了所以选择A, 和预期相同.

需要注意的是表达式的选择是顺序求值的, 所以通常最后一个标记为1, 相当于最后一个 else

我们再看一个简单的四路复用器, 其中 s0 s1 一起控制了输出结果

一般来说可能会写出如下的 HCL

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

但考虑到顺序判断的行为, 也可以写作如下的方式. 当然从阅读的角度来说笔者更倾向于前者

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

ALU(算数逻辑单元)是一种重要的组合电路, 具体的实现比较复杂, 其大致功能效果如下所示, 即对于不同的输入 s ALU 可以执行不同的运算

这里的是 X-Y 对应 Y86-64 中 subq 的顺序

在处理器设计中,很多时候都需要将一个信号与许多可能匹配的信号做比较,以此来检测正在处理的某个指令代码是否属于某一类指令代码.比如下面这个例子中 code 是一个 2-bits 的信号, 为了使用MUX控制ABCD的选择需要将其拆分为 s0, s1 两个信号

因此可以分别判断 s1s0 两位的值, 即2和3的高位为1, 1和3低位为1, 可以写作如下的方式

bool s1 = code == 2 || code == 3;
bool s0 = code == 1 || code == 3;

当然可以更简化一些写成集合的形式, 这两种方式也是等价的

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

组合电路从本质上讲,不存储任何信息.相反,它们只是简单地响应输人信号,产生等于输入的某个函数的输出.为了产生时序电路( sequential circuit),也就是有状态并且在这个状态上进行计算的系统,我们必须引入按位存储信息的设备.存储设备都是由同一个时钟控制的,时钟是一个周期性信号,决定什么时候要把新值加载到设备中.

在说到硬件和机器级编程时,"寄存器"这个词是两个有细微差别的事情.

• 在硬件中,寄存器直接将它的输入和输出线连接到电路的其他部分.

• 在机器级编程中,寄存器代表的是CPU中为数不多的可寻址的字,这里的地址是寄存器ID.这些字通常都存在寄存器文件中,虽然我们会看到硬件有时可以直接将一个字从一个指令传送到另一个指令,以避免先写寄存器文件再读出来的延迟.

需要避免歧义时,我们会分别称呼这两类寄存器为"硬件寄存器"和"程序寄存器". 下图展示了一个硬件寄存器的工作模式, 大多数时候寄存器保持在稳定状态 x, 输出等于它的当前状态x. 这时候虽然产生了一个新的寄存器输入 y 但只要始终是地点为的寄存器的输出就仍然不变

当始终变为高电位的时候输入信号 y 就加载到寄存器中成为下一个状态 y, 直到下一个时钟上升沿这个状态 y 也一直是寄存器的新输出

下图展示了一个典型的寄存器文件

寄存器文件有两个读端口(A和B),还有一个写端口(W).这样一个多端口随机访问存储器允许同时进行多个读和写操作.

图中所示的寄存器文件中,电路可以读两个程序寄存器的值,同时更新第三个寄存器的状态.

每个端口都有一个地址输人,表明该选择哪个程序寄存器,另外还有一个数据输出或对应该程序寄存器的输人值.地址是用上文中编码表示的寄存器标识符.两个读端口有地址输入srcA和 srcB("source A"和"source B"的缩写)和数据输出valA和 valB("value A"和"value B"的缩写).写端口有地址输人dstw("destination W"的缩写),以及数据输人valw("value W"的缩写).

在我们的实现中,从寄存器文件读数据就好像它是一个以地址为输人、数据为输出的一个组合逻辑块.当srcA或srcB被设成某个寄存器ID时,在一段延迟之后,存储在相应程序寄存器的值就会出现在valA或valB上.

例如,将srcA设为3,就会读出程序寄存器%rbx的值,然后这个值就会出现在输出valA 上.

如果读写的寄存器相同, 解决办法是前半个周期写,后半个周期读

Y86-64 的顺序实现

通常,处理一条指令包括很多操作.将它们组织成某个特殊的阶段序列,即使指令的动作差异很大,但所有的指令都遵循统一的序列.每一步的具体处理取决于正在执行的指令.创建这样一个框架,我们就能够设计一个充分利用硬件的处理器.下面是关于各个阶段以及各阶段内执行操作的简略描述:

1. 取指(fetch):取指阶段从内存读取指令字节,地址为程序计数器(PC)的值.从指令中抽取出指令指示符字节的两个四位部分,称为icode(指令代码)和ifun(指令功能). 取出指令后分析指令属于哪一种类型, 并进行解析

2. 译码(decode):译码阶段从寄存器文件读入最多两个操作数,得到值valA和/或valB.通常,它读人指令rA和 rB字段指明的寄存器

3. 执行( execute);在执行阶段,算术/逻辑单元(ALU)要么执行指令指明的操作(根据ifun的值)完成对应的操作, 可能是修改栈指针, 设置条件码, 更新寄存器, 选择分支等等

4. 访存(memory):访存阶段可以将数据写入内存,或者从内存读出数据.读出的值为valM.

5. 写回( write back):写回阶段最多可以写两个结果到寄存器文件.

6. 更新PC(PC update):将PC设置成下一条指令的地址.

从前面的讲述可以看出,执行一条指令是需要进行很多处理的.我们不仅必须执行指令所表明的操作,还必须计算地址、更新栈指针,以及确定下一条指令的地址.幸好每条指令的整个流程都比较相似.因为我们想使硬件数量尽可能少,并且最终将把它映射到一个二维的集成电路芯片的表面,在设计硬件时,一个非常简单而一致的结构是非常重要的.降低复杂度的一种方法是让不同的指令共享尽量多的硬件.

我们面临的一个挑战是将每条不同指令所需要的计算放到上述那个通用框架中, 下表给出了 OPq rrmovq irmovq 指令在这六个阶段的具体操作方式

Y86-64指令OPq、rrmovq和irmovq在顺序实现中的计算.这些指令计算了一个值,并将结果存放在寄存器中.符号icode:ifun表明指令字节的两个组成部分,而rA:rB表明寄存器指示符字节的两个组成部分.符号M_1[x]表示访问(读或者写)内存位置x处的一个字节,而M_8[x]表示访问八个字节, R[x] 表示取寄存器 x 的值

回顾Y86-64 指令集部分, icode 和 ifun 共占 1 字节, rA rB 共占 1 字节

举一个例子, 下图为一段 Y86-64 的汇编代码及机器码, 以及前文提到过的 Y86-64 指令集设计和寄存器对应表

例如对于第三行起始地址为 0x14 的 subq %rdx, %rbx 指令, 其属于 OPq 指令的一种, 右侧显示了其按照左边的 OPq 指令通用规则的一个实例

最后的结果也如预期所料, 寄存器%rbx设成了12,三个条件码都设成了0,而PC加了2.

再比如对于第六行的 pushq %rdx

读者可对照前文提到的 Y86-64 指令集的相关规定

时钟周期与时序

关于周期有两个概念, 分别是时钟周期和机器周期.

• 时钟周期指的是硬件设备的时钟信号的周期时间, 是最小的单位.

• 机器周期指的是执行一条指令所需要的完整时间.

对于顺序实现结构, 也就是单周期, 此时时钟周期和机器周期相同, 也就是在一个时钟周期内机器执行完了完整的一条指令, 此时的时钟周期会比较慢, 因为需要在一个时钟周期内完成 IF ID EX MEM WB 所有过程

对于后文会提到的流水线结构, 此时一个机器周期包含多个时钟周期, 如下图所示. 在每一个时钟周期内部流水线的每一个阶段分别执行对应的 IF ID EX MEM WB, 同时执行 5 条指令的 5 个阶段. 因此完整执行完一条指令需要 5 个时钟周期, 所以 1 机器周期 = 5 时钟周期

了解周期的概念之后接下来介绍一下关于时序这个概念. 我们注意到上图中每一个时钟周期都是由一个个固定的波形组成的. 我们认为一个时钟周期由四部分组成

1. 上升沿跳变, 由低电平变为高电平

2. 高电平状态

3. 下降沿跳变, 由高电平变为低电平

4. 低电平状态

下图介绍了 SEQ 硬件如何处理汇编指令, 其中我们将一些具体的硬件电路抽象成一个大的组合逻辑电路, 以及时钟寄存器(程序计数器PC 和条件码寄存器 CC) 和随机访问寄存器(寄存器文件和内存). 最下面可以看到四个子图 1234, 分别对应第三条指令的开始,结束与第四条指令的开始和结束的状态, 分别对应最上方时钟周期的对应时刻点

图1对应了 cycle3 的上升沿, 处于该条 addq 指令执行的最开始阶段. 图2 经过完整的一个时钟周期到达结尾, 此时所有计算已经完成, 包括读随机访问存储器, 新的条件码 000, 程序寄存器 %rbx 的新值 0x300, 以及 PC 的新值 0x016. 此时需要注意的是虽然组合逻辑已经根据 addq 指令被更新了, 即蓝色部分. 但是状态仍然保持在第二条 irmovq 指令设置的值, 即浅灰色部分

当进入图3的时刻, 即 cycle4 的上升沿, 此时才会更新 PC, 寄存器和 CC 为蓝色的状态, 此时组合逻辑还没有对这些变化作出反应, 处于白色的状态. 在这个周期内执行 je dest 这条指令直到周期结束的图4. 此时组合逻辑已经根据 je 指令的被更新为深灰色, 但是直到下一个周期的上升沿为止程序的状态仍然保持 addq 指令蓝色设置的值

到此为止我们可以得出一些结论, 即在一个时钟周期开始的时钟上升沿, 此时从组合逻辑中完成对上个时钟周期的状态的更新, 然后在一个时钟周期内完成计算得到当前状态, 完成对于组合逻辑的更新. 只有在下一个时钟周期开始时组合逻辑中的状态才会被更新到 PC, 寄存器, 内存, CC 中.

图1 中的 PC CC 寄存器 内存都是浅灰色的, 即对应的是状态1 刚刚更新了 cycle2 中的组合逻辑的状态

硬件设计

实现所有Y86-64指令所需要的计算可以被组织成6个基本阶段:取指、译码、执行、访存、写回和更新PC.下图给出了一个能执行这些计算的硬件结构的抽象表示.

• 白色方框表示时钟寄存器.程序计数器PC是SEQ中唯一的时钟寄存器.

• 浅蓝色方框表示硬件单元.这包括内存、ALU等等.在我们所有的处理器实现中,都会使用这一组基本的单元.我们把这些单元当作"黑盒子",不关心它们的细节设计.

• 控制逻辑块用灰色圆角矩形表示.这些块用来从一组信号源中进行选择,或者用来计算一些布尔函数.我们会非常详细地分析这些块,包括给出HCL描述.

• 线路的名字在白色圆圈中说明.它们只是线路的标识,而不是什么硬件单元.

• 宽度为字长的数据连接用中等粗度的线表示.每条这样的线实际上都代表一簇64根线,并列地连在一起,将一个字从硬件的一个部分传送到另一部分.

• 宽度为字节或更窄的数据连接用细线表示.根据线上要携带的值的类型,每条这样的线实际上都代表一簇4根或8根线.

• 单个位的连接用虚线来表示.这代表芯片上单元与块之间传递的控制值.

要将这些计算映射到硬件上,我们要实现控制逻辑,它能在不同硬件单元之间传送数据,以及操作这些单元,使得对每个不同的指令执行指定的运算.这就是控制逻辑块的目标.我们的任务就是依次经过每个阶段,创建这些块的详细设计.

有关 SEQ 部分的具体 HCL 语言设计请参考 06-ArchY86Lab 中的 PartB 部分, 相关代码见 csapplab seq-full.hcl

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

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

流水线

在现代逻辑设计中,电路延迟以微秒或皮秒( picosecond,简写成"ps"),也就是10^-12秒为单位来计算.在这个例子中,我们假设组合逻辑需要300ps,而加载寄存器需要20ps.

上图为流水线图( pipeline diagram).在图中,时间从左向右流动.从上到下写着一组操作(在此称为I1、12和I3).实心的长方形表示这些指令执行的时间.这个实现中,在开始下一条指令之前必须完成前一个.因此,这些方框在垂直方向上并没有相互重叠.下面这个公式给出了运行这个系统的最大吞吐量:

但是如果我们能够将组合逻辑拆分成三部分,在各个阶段之间放上流水线寄存器( pipeline register),这样每条指令都会按照三步经过这个系统,从头到尾需要三个完整的时钟周期. 我们将时钟周期设为100+20=120ps,得到的吞吐量大约为8.33 GIPS.因为处理一条指令需要3个时钟周期,所以这条流水线的延迟就是3×120=360ps.我们将系统吞吐量提高到原来的8.33/3.12=2.67倍,代价是增加了一些硬件,以及延迟的少量增加(360/320=1.12).延迟变大是由于增加的流水线寄存器(20ps)的时间开销.

同前文介绍过的单周期时序, 组合逻辑在每一个时钟周期开始时从寄存器中读取值, 在结束前完成计算, 然后在下一个时钟周期开始的上升沿时将新值更新到下一阶段的寄存器当中

准确来说, "每一个时钟周期开始时从寄存器中读取值" 并不是读取值, 本身在时钟上升沿更新寄存器的时候就是获取新值的时刻

难点一:不一致的划分

但实际情况并不是那么完美和理想, 下图中我们划分为了三个阶段, 但是通过这些阶段的延迟从50ps到150ps不等. A B C 三个阶段的延迟分别为 50ps 150ps 100ps, 通过所有阶段的延迟和仍然为300ps. 但是运行时钟的速率是由最慢的阶段的延迟限制的.流水线图表明,每个时钟周期,阶段A都会空闲(用白色方框表示)100ps,而阶段C会空闲50ps.只有阶段B会一直处于活动状态.

尽管A C都存在空闲, 但为了满足B的延迟, 我们必须将时钟周期设为150+20=170ps,得到吞吐量为5.88 GIPS.

对硬件设计者来说,将系统计算设计划分成一组具有相同延迟的阶段是一个严峻的挑战.通常,处理器中的某些硬件单元,如ALU和内存,是不能被划分成多个延迟较小的单元的.这就使得创建一组平衡的阶段非常困难.

难点二:流水线深度

下图是书中的习题, 但是非常有趣和直观

• A.对一个两阶段流水线来说,最好的划分是块A、B和C在第一阶段,块D、E和F在第二阶段.第一阶段的延迟为170ps,所以整个周期的时长为170+20=190ps.因此吞吐量为5.26GIPS,而延迟为380ps.

• B.对一个三阶段流水线来说,应该使块A和B在第一阶段,块C和D在第二阶段,而块E和F在第三阶段.前两个阶段的延迟均为110ps,所以整个周期时长为130ps,而吞吐量为7.69GIPS.延迟为390ps.

• C.对一个四阶段流水线来说,块A为第一阶段,块B和C在第二阶段,块D是第三阶段,而块E和F在第四阶段.第二阶段需要90ps,所以整个周期时长为110ps,而吞吐量为9.09 GIPs.延迟为440ps.

• D.最优的设计应该是五阶段流水线,除了E和F处于第五阶段以外,其他每个块是一个阶段.周期时长为80+20= 100ps,吞吐量为大约10.00 GIPs,而延迟为500ps.变成更多的阶段也不会有帮助了,因为不可能使流水线运行得比以100ps为一周期还要快了.

我们可以观察到, 随着流水线的阶段数加倍,虽然我们缩短了每个计算时钟的时间,但是由于通过流水线寄存器的延迟,吞吐量并没有加倍.这个延迟成了流水线吞吐量的一个制约因素.

为了提高时钟频率,现代处理器采用了很深的(15或更多的阶段)流水线.处理器架构师将指令的执行划分成很多非常简单的步骤,这样一来每个阶段的延迟就很小.电路设计者小心地设计流水线寄存器,使其延迟尽可能得小.芯片设计者也必须小心地设计时钟传播网络,以保证时钟在整个芯片上同时改变.所有这些都是设计高速微处理器面临的挑战.

难点三: 流水线反馈

到目前为止,我们只考虑一种系统,其中传过流水线的指令相互都是完全独立的.但是对于像x86-64或Y86-64这样执行机器程序的系统来说,相邻指令之间很可能是相关的.例如,考虑下面这个Y86-64指令序列:

在这个包含三条指令的序列中,每对相邻的指令之间都有数据相关(data dependency),用带圈的寄存器名字和它们之间的箭头来表示.irmovq指令(第1行)将它的结果存放在%rax中,然后addq指令(第2行)要读这个值;而 addq指令将它的结果存放在%rbx中,mrmovq指令(第3行)要读这个值.

除此之外一些跳转指令例如 je jmp 也会造成流水线的中断