这章主要讲如何设计一个处理器,可以更好的理解计算机的运作过程。

设计处理器的指令集为Y86,比较简单,适合学习,与x86类似。然后用HCL(Hardware Control Language)设计其电路结构。利用连续的指令(每条指令细分为5步)实现流水线pipelined,就可同时执行多条指令。

The Y86 Instruction Set Architecture

这部分定义了Y86的一些数据结构、指令集、编码、协议、异常处理。

Programmer-Visible State

337页图4.1给出了Y86的数据结构。

  • 其中有8个32位寄存器,名称和IA32一致。
  • 同样也有ZF, SF, OF这3个condition单位寄存器。
  • PC计数器寄存器,还有DMEM内存,可以看作一个数组。
  • Stat状态码标志事件类型。

同样的,%esp作为栈指针,用于push, pop, call, ret等指令。

Y86 Instructions

这一部分介绍了Y86的指令集和编码,见338页图4.2。

可以看出Y86指令集类似于IA32指令集,但是比较简单,它的数据类型都是4字节的。

Y86指令集有这么几类:

  • halt
  • nop
  • movl
  • OPl(addl, subl, andl, xorl)
  • jXX(jmp, jle, jl, je, jne, jge, jg)
  • cmovXX(rrmovl, cmovle, cmovl, cmove, cmovne, cmovge, cmovg)
  • call
  • ret
  • push/pop

但是还是有些地方和IA32不同的,这里说明下。

IA32movl指令拆开了,拆成这四个:irmovl, rrmovl, mrmovl, rmmovl,其中第一个字母表示源操作数(i立即数、r寄存器、m内存),第二个字母表示目标操作数(r寄存器、m内存),拆成这样有助于实现。比如movl $233, %eax写成irmovl $233, %eax,明显后者更好实现(更具体),而前者movl有多种操作,需要分析具体是哪一种。

Y86内存引用只有i(r)这种形式,亦即基于一个寄存器r的值,加上一个偏移量立即数i得到最终地址。

同样2个操作数最多只能有1个内存引用,另外不支持直接将立即数存到内存中(可以配合irmovl,rmmovl实现)。

Y86对于OPl类指令,操作数只能在寄存器中。虽然IA32支持内存、立即数。

cmovXX类指令,源操作数和目标操作数都是在寄存器中,和rrmovle指令同类,和IA32一样只有满足条件才更新数据。

halt指令停止处理器执行,然后设置状态码为HLTIA32也有类似的指令叫hlt,它会导致整个系统停机,所以程序都不允许执行这条指令。

其他类指令和IA32差不多,不再概述。

Instruction Encoding

Y86指令集编码长度在1-6字节,依赖于具体字段。其中第一个字节表明了具体指令,而第一个字节又分为两部分:高4位(code部分)和低4位(function部分)。高4位指明了指令的种类,(0-0xB),低4位指明了某一类的具体指令。例如OPl类指令,高4位为0x6,低4位指明了具体的指令,例如addl0,拼起来第一字节就是0x60。有些指令类只有一条,例如ret类只有ret指令,高4位为0x9,低4位为0,拼起来就是0x90

339页图4.3给出了OPl,jmpXX,cmovXX类的具体指令编码。

340页图4.4给出了寄存器的编码(4位),0-7与对于的8个寄存器,F表示没有指定寄存器,相当于占位符。有些指令如irmovl只需要一个寄存器,而rmmovl需要2个寄存器,可能为了对齐吧,irmovl需要用一个F来指明另一个寄存器不存在,这样也好实现。具体可看图4.2,图中的F有点像占位符。

立即数都是4字节编码,注意字节序。call指令使用绝对地址,可能因为绝对地址编码长度都是4字节。

举个编码的例子,rmmovl %esp,0x12345(%edx),首先rmmovl第一字节为0x40%esp的编码为0x4%edx的编码为0x2,拼起来为0x420x12345little-endian0x45230100,所以最后编码为404245230100

需要注意,设计指令编码的时候,需要保证其唯一性,不能有任何歧义,亦即指令只能有唯一编码,编码对应唯一一条指令。无法解码的序列为非法序列。

因为Y86第一字节就指明了为哪条指令,这条性质可以保证处理器执行二进制代码的时候不会发生歧义。即使指令嵌入其他序列中,我们也能通过从序列第一字节开始,如果不从第一个字节开始执行,那么就无法判断具体是哪条指令了,反汇编也会有问题。

Y86 Exceptions

345页图4.5给出了异常代码,总共4类。

Y86 Programs

这节给出了Y86指令集的代码实例。对比346页代码,我们几乎可以看到和IA32程序差不多,除了IA32的一条指令在Y86中要多条来代替。

347页给出了一个完整Y86程序的代码。348页给出了程序运行过程中的寄存器、内存空间变化值。349页给出了汇编器汇编的二进制代码。

首先.pos 0指明了汇编器应该调整地址从0开始。在初始化栈帧寄存器(.pos 0x100)的时候,由于栈空间往低地址分配,需要注意以免栈空间把代码、数据覆盖。同样也使用了.align 4来对数组进行地址对齐。

Some Y86 Instruction Details

这里给了关于Y86IA32汇编的细节问题。

例如,pushl %esp后,%esp的值为多少?这里有2个答案:

  • pushl%esp的值
  • pushl%esp的值,亦即-4后的值

似乎2个都对,IA32对这种问题有约定答案,Y86也遵循这些约定。

.text
.globl pushtest
pushtest:
    pushl %ebp
    movl %esp, %ebp
    movl %esp, %eax
    pushl %esp
    popl %edx
    subl %edx,%eax
    leave
    ret

运行以上代码,结果总是0,那么答案就是第一种可能。INTEL文档约定了这个问题的答案:

  • I286开始,pushl %esp的值为%esp的旧值。
  • I8086的结果为新值,即更新后SP(-2)的值。

对于pop %esp,也有2个答案:

  • pop%esp的值,即+4后的值。
  • %esp栈指针指向的内存的值赋值为%esp,即movl (%esp), %esp

有趣的是结果没有二义性,为第二个答案。

为什么要纠结这种问题?答案很简单,为了一致性,为了更好的可移植性,为了文档更简洁,从长远看来,能减少很多问题。

Logic Design and the Hardware Control Language HCL

这节介绍了点关于数电的内容,和HCL语言。毕竟是从程序员角度来学习操作系统,所以硬件方面介绍的不是很深。

Logic Gates

353页图4.9给出了3个门:与或非门。

HCL表达式的逻辑运算和C语言差不多,用&&代表与,||代表或,!代表非。但是有点不同,C语言的单位操作是用&, |, ~等,而HCL都是用前面说的那3个符号。

比如一个与门有3个输入端A, B, C,那么输出端可以写成out = a && b && c

Combinational Circuits and HCL Boolean Expressions

组合逻辑电路就是将一些逻辑门连接在一起,以实现某些功能。有2个约束:

  • 多个输入端不能连在一起,否则会出现冲突。。
  • 组合电路中不能出现圈,也会导致歧义。

354页图4.10给出了同或的组合电路,写成HCL表达式如下:

bool eq = (a && b) || (!a && !b);

看起来和C语言差不多,需要注意的是eq为表达式的名字,不是一个变量,可以理解成函数。

355页图4.11给出了二路选择器(MUX)的例子,通过s控制端来选择输出是a还是b,写成HCL表达式如下:

bool out = (s && a) || (!s && b);

这里还有要注意的是,

  • HCL的表达式(对应组合电路)结果可能需要一定延迟才会更新,而不是像C表达式那样立即计算出结果。
  • HCL表达式的逻辑门只有0或者1。
  • 在C语言的逻辑表达式中,如果&&或者||一开始就能计算出结果,那么后面的部分就不会计算了,而HCL没有这个说法。

Word-Level Combinational Circuits and HCL Integer Expressions

HCL不仅支持以位为单位,还支持以字为单位。一个字就是一系列的位组合,可以表示一个整数、地址、操作码等等。

356页图4.12给出了判断2个字A, B是否相等的逻辑电路,它是通过每位同或的结果,然后与运算来判断。在HCL直接写成bool eq = (A=B)就行了,HCL把每个字当做int来看待,不需要指定字长。

357页图4.13给出了二路选择器的逻辑电路,输入信号是2个字A, B,控制端是s。在HCL可以用case expressions。如下:

[
    select_1: expr 1
    select_2: expr 2

    select_k: expr k
]

其中select_i为逻辑表达式,expr_i为对应的返回值。HCL会依次运算各个表达式,直到select_i表达式为1,将expr_i作为结果。那么前面的二路选择器可以写成:

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

当s为1的时候,输出A;当s为0的时候跳过,最后输出B。最后一条表达式1可看作默认表达式,当前面的表达式都没1时,那么就选择这条表达式了。

举个例子,4路选择器,2个控制端s1, s2,4个输入端A, B, C, D,那么:

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

359页图4.15给出了算数逻辑单元ALU的例子。它有2个输入端A, B,一个控制端,根据控制端的值来选择哪种运算。这4种运算的编码和前面的OPl指令的function部分对应的一致,同样源操作数和目标操作数的位置与ALU的位置也对应起来。

Set Membership

在设计处理器的时候,需要匹配一些指令的类型。HCL有个更简单集合写法,如下:

iexpr in {iexpr_1 , iexpr_2 , . . . , iexpr_k}

当被测试的iexpr在集合中,返回值就为1。那么前面的2路选择器的高位s1,之前这么写:

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

现在可以写成:

bool s1 = code in {2, 3};

Memory and Clocking

这节介绍了点关于时序电路的内容。组合电路不存储信息(状态);而时序电路能够保持状态,根据状态来计算。这里介绍了2种存储设备:

  • Clocked registers: 可以存储单个字,值由时钟信号来控制更新。
  • Random-access memories: 可以存储多个字,使用地址来选择读写哪个字。举个例子:
    • 虚拟内存,由软硬件来确定地址访问某个字
    • register file,寄存器的id作为地址,来选中某个寄存器(字)。在IA32Y86处理器中,有8个寄存器。

362页图4.16给出了(Clocked registers)寄存器的更新。大多数时间寄存器的值(x)保持,尽管输入端有新值(y),只要时钟信号是低电平,那么寄存器的值不变。直到时钟信号上升沿,才更新寄存器的值(y)。

我们的Y86处理器会使用这些时序寄存器来保存程序计数器(PC),condition单位寄存器(CC),程序状态(Stat)。

362页给出了典型的register file结构。其中有2个读端(A, B),1个写端(W),可以同时读写。读端的srcA, srcB相当于寄存器地址(ID),指定了哪个寄存器要读,valA, valB分别是指定寄存器的值;写端的dstW也是寄存器地址,通过valW来写。需要注意register file不是组合电路,而是个时序电路。假如设置srcA为3,那么过段时间,会读取寄存器%ebx的值,输出到valA。写一个字也受到时钟信号的影响,和前面说的Clocked registers一样,当时钟信号上升沿时,将valW写到dstW指定的寄存器ID上。如果dstW == 0xF,说明啥都不写。

363页给出了Random-access memory的结构,用来存储程序的数据。其中有一个地址线,一个输入线(写),一个输出(读)线。当write控制端信号为0,并且地址有效,那么就会输出指定的字(读);写受到时钟信号的影响,当write控制端信号为1,并且地址有效,那么过段延迟对应的地址内容将会更新。若地址无效,error端输出1。

综上所述,读可以随时读,但是写需要一定的延迟(时钟上升沿触发)。

设计的处理器有个只读存储器,用来读取指令。

Sequential Y86 Implementations

这一部分讲了下关于串行Y86指令的HCL实现和硬件实现,也就是说每一个时钟周期执行一条指令,后面会接着实现pipelined

Organizing Processing into Stages

处理一条指令分为好几个阶段,设计的时候应该保证每条指令的每个阶段相似,如下:

  • Fetch: 这个阶段从内存中读取一条PC指向的地址上的指令,然后根据指令第一个字节,分为高4位(code部分)和低4位(function部分),来判断是否接着读取寄存器id: rA, rB,和4字节的立即数。然后计算新的PC值:valP = PC+指令长度
  • Decode: 这个阶段通常从寄存器中读取值,分别为寄存器rA, rB指向的valA, valB。而有些指令只读取%esp寄存器的值(例如push/pop
  • Execute: 这个阶段通过算数逻辑单元(ALU)来进行运算,得到结果valE
    • 根据相应指令(OPl, rrmovl, irmovl, cmovXX)的function部分来执行相应的运算:add, sub, and, xor
    • 根据相应指令(rmmovl, mrmovl)来计算有效地址
    • 根据相应指令(pushl, popl, call, ret)来计算栈指针+4/+(-4)
    • 根据相应指令(jXX)通过condition code判断是否跳转。
  • Memory: 这个阶段通常从内存中读(valM)或者写内存。
  • Write back: 这个阶段更新寄存器的值。
  • PC update: 这个阶段更新PC的值。

处理器不断根据执行以上步骤,直到遇到异常/halt指令。当然有可能有些指令某一阶段什么都不做的,只要保证每个指令对应阶段都相似就能减少硬件设计复杂度了。

365页图4.17给了个Y86指令的代码,然后书上接着介绍每一条指令的每个阶段执行细节:图4.18到图4.21,这些步骤和硬件图相对应的。

SEQ Hardware Structure

这一部分讲硬件实现。376页图4.22,378页图4.23给出了硬件细节。

前面说过,Y86实现用了一个只读内存,专门用于Fetch阶段来读取指令,而Memory阶段专门读写数据内存。电路图的灰色方块可以看作一个选择器(MUX),从多个输入选择一个作为输出,而白色椭圆上的标签(eg. valA,valB)对应于上面“读取”的值。

SEQ Timing

这部分讲了关于串行执行的时序问题,一个时钟周期是如何工作的。

关于设计处理器,书上有这么一句话:

The processor never needs to read back the state updated by an instruction in order to complete the processing of this instruction.

大概意思应该是(有点绕口了。。):

处理器不能读取被当前指令更新的值而为了完成当前指令。

简而言之,因为电路采用的是时序电路,那么内存、寄存器更新需要等到下一个时钟周期才能更新。也就是说在上面各个阶段读取(读取的时候随时可读,写的时候要下一个时钟周期的上升沿)的是“旧值”(eg. valA, valB, valM),然后产生一系列“新值”(eg. valP, valE),等到下一个上升沿,将会同时更新产生的新值,周而复始。382图4.25给出了详细的过程。

SEQ Stage Implementations

这一部分就是HCL代码了,配合电路图、指令执行细节表来看,更容易理解。HCL代码主要就是描述各个端口的选择器–根据不同指令选择不同的数据。

接下来一部分就是讲关于pipelined的实现了,因为串行执行实在是太慢了。举个例子,一个简单的ret指令,在时钟周期的开始,首先从指令内存中读取一条指令,然后从寄存器中读取栈指针,ALU对栈指针+(-4),将新的PC(valP)值写入数据内存中,所有步骤都在一个时钟周期完成的。然而这么做不能充分利用好各个部件,因为一个时钟周期中只有一部分部件工作而已。

待续