Inspire Hub

CSAPP 读书笔记：处理器架构

我们将处理器支持的指令及其对应的字节编码方式称为指令集架构（Instruction Set Architecture，ISA）。不同的处理器系列，例如 Intel IA32/x86-64，IBM/Freescale Power 和 ARM 等，均使用不同的 ISA。为一种机器编译得到的程序，无法在 ISA 不同的机器上运行。

ISA 在编译器的编写者和处理器的设计者之间提供了一个抽象层。编译器的编写者只需要知道允许使用哪些指令以及它们是如何编码的，而处理器的设计者则需要创建能够执行这些指令的机器。

在传统的 ISA 模型中，每条指令顺序执行。而现代处理器则会同时执行多条指令的不同部分，从而获得比每次只执行一条指令更高的性能。不过我们还需要引入一个特殊机制，确保处理器的计算结果与顺序执行相同。

在本章中，我们仿照 x86-64 创建了一个简单的指令集，称其为“Y86-64”。同时使用 HCL（Hardware Control Language）来描述硬件系统的控制部分和处理器设计，它的作用类似于 Verilog HDL（Hardware Description Language）。

Y86-64 指令集架构

程序员可见状态

Y86-64 程序中的每条指令都可以读取和修改处理器状态的某些部分，即程序员可见状态。此处的“程序员”既指用汇编代码编写程序的人，又指生成机器代码的编译器。如下图所示：

20211212174453

Y86-64 中的程序员可见状态包括 15 个能够存储 64 位数据的寄存器、3 个单位（Singel Bit）条件码、程序计数器、虚拟内存和表示程序执行整体状态的状态码（图中的“Stat”）。

Y86-64 指令

Y86-64 指令是 x86-64 指令的子集，仅包含了 8 字节的整数运算，以及更少的寻址和运算模式。由于我们的数据均为 8 字节，因此可以无歧义地将它们称为字（Word）。

20211212175615

x86-64 中的movq指令被分成了四个不同的 Y86-64 指令：irmovq、rrmovq、mrmovq和rmmovq。其中，i代表立即数，r代表寄存器，m代表内存。

上图还缺少了部分信息，比如整型操作指令OPq实际上包含了四个指令：addq、subq、andq和xorq，它们会根据计算结果改变三个条件码的值。另外，该类指令和条件分支指令jXX以及条件移动指令cmovXX编码中的 $f_n$ 将随指令的具体名称变化：

20211212181034

call、ret、nop、pushq和popq指令的作用和 x86-64 中的类似，而halt指令则对应了 x86-64 中的hlt。x86-64 不允许程序使用htl指令，因为它会使整个系统暂停操作。不过在 Y86-64 中，halt指令会使处理器停止并将状态码置为 HLT。

指令编码

上一节的图中还展示了不同指令的字节编码，其长度范围在一到十字节之间，其中的首个字节标识了其类型。寄存器存储在 CPU 中的寄存器文件（一个小型的 RAM）中，下图中的寄存器 ID 就是它们的地址：

20211212205036

寄存器 ID 将替换指令编码中的 $r_A$ 和 $r_B$。x86-64 中条件分支和跳转指令的目的地址是相对于程序计数器（PC-Relative）的，这样可以使程序编码更加紧凑，同时代码在内存中移动时也无需更改所有分支目标的地址。由于我们更加关心设计的简洁性，因此 Y86-64 采用绝对地址。

举例来说，在一台小端法机器上，指令rmmovq %rsp, 0x123456789abcd(%rdx)的字节编码为4042cdab896745230100。其中，指令类型rmmovq对应的字节为40，寄存器 %rsp 和 %rdx 分别对应4和2。剩下的立即数将首先填充为八字节的000123456789abcd，然后反向追加到指令尾部。

任何指令集中的字节编码都必须与指令序列唯一对应。也就是说，只要我们知道了指令字节编码中的首个字节，就能确定完整的指令序列。反之如果我们无法得知字节序列的起始位置，那么也就无法将其拆分为多个单独的指令。

Y86-64 异常

Y86-64 中的状态码 Stat 如下：

20211212214542

我们没有引入异常处理程序（Exception Handler），只是简单地让处理器在遇到任何异常时停止执行指令。

Y86-64 程序

示例 C 程序如下：

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18

long sum(long *start, long count)
{
    long sum = 0;
    while (count)
    {
        sum += *start;
        start++;
        count--;
    }
    return sum;
}

int main()
{
    long array[4] = {0x000d000d000d, 0x00c000c000c0, 0x0b000b000b00, 0xa000a000a000};
    sum(array, 4);
    return 0;
}

与之对应的 Y86-64 汇编代码为：

20211213201935

从中我们可以看出它与 x86-64 汇编代码的区别：

  • 由于我们的算术运算无法直接使用立即数，因此需要先将其拷贝到寄存器中（第 24～25 行）；
  • 我们需要先从内存中读取值（第 30 行），然后再将其与寄存器中的值相加（第 31 行）。而 x86-64 中只需要使用一个addq指令；
  • 我们的subq指令（第 33 行）在执行减法运算的同时还会修改条件码，因此我们可以在不引入testq的情况下直接使用条件跳转指令jne（第 35 行）。不过为了实现这一点，我们必须在进入循环之前使用andq指令初始化条件码的值（第 27 行）。

汇编器会根据上图中以.开头的指令调整其生成的代码地址，如指令.pos 0（第 2 行）表示代码的起始地址为 0。指令irmovq stack, %rsp会初始化栈指针，其地址是由最后两行指令声明的。运行时栈将从0x200开始向较低的地址处增长，因此我们需要保证它不会覆盖到其他的程序数据。程序的第 8 到 13 行声明了一个四字数组，.align 8指令将使它在 8 字节边界上对齐。

一些 Y86-64 指令细节

指令pushq %rsp压入栈的值可能是寄存器 %rsp 的原始值，也有可能是栈指针减少后的值。而指令popq %rsp从栈中弹出的值可能是直接从内存中读取的，也有可能是栈指针增加后再读取的。为了避免混淆，我们需要规定上述两个指令均采用前者的方式。

逻辑设计和 HCL

在硬件设计中，电子电路用于计算位函数（Function on Bits）并将位存储在不同的存储器元素（Memory Element）中。我们可以使用高电压（约 1.0 V）来表示逻辑值 1，使用低电压（约 0.0 V）来表示逻辑值 0。

数字系统主要由以下三个部分构成：

  • 计算位函数的组合逻辑（Combinational Logic）
  • 存储位的存储器元素
  • 控制存储元素更新的时钟信号（Clock Signal）

逻辑门

20211213214742

逻辑门是数字电路的基本计算元素，其输出等于输入的位进行布尔运算后的结果。上图展示了用于布尔函数AND、OR和NOT的标准符号，逻辑门的下方则是对应的 HCL 表达式&&、||和!。逻辑门只对单个位进行操作而非整个字，因此我们不使用 C 中的位级运算符&、|和~。

组合电路和 HCL 布尔表达式

多个逻辑门组成的网络被称为组合电路，其构建方式有以下要求：

  • 每个逻辑门的输入必须是：
    • 整个系统的输入之一（即主输入）
    • 某个存储器元素的输出
    • 某个逻辑门的输出
  • 两个或多个逻辑门的输出不能连接到一起
  • 网络不能是一个回路（Acyclic）

下图展示了一个多路复用器（Multiplexor，MUX）的组合电路：

20211214105159

输入的数据信号是位 a 和 b，控制信号是位 s。当 s 为 1 时，输出将等于 a。而当 s 为 0 时，输出则为 b。输出信号的 HCL 表达式为：bool out = (s && a) || (!s && b);

HCL 表达式和 C 中的逻辑表达式之间存在一些差异：

  • 逻辑门和 HCL 的输出会动态地随输入的变化而变化，而 C 中的表达式只会在程序执行过程中运算；
  • C 中的逻辑表达式允许使用任意整型参数，而 HCL 表达式只能对位值 0 和 1 进行运算；
  • C 中的逻辑表达式可能只会执行部分运算。例如表达式(a && !a) && func(b,c)，由于(a && !a)一定为 0，整个表达式的值也为 0，因此不会计算func(b,c)的值。相比之下，HCL 没有任何的部分评估规则。

To be continued …

Edit this page on GitHub