F4 计算机系统的状态机模型

处理器的组成和工作原理

指令及其编码

指令的概念

指令：控制处理器的媒介

1. 指令的操作数(operand)：指定需要处理哪些数据。分为源操作数和目的操作数
2. 指令的操作码(opcode)：指定用何种方式处理数据（加，乘……）

寄存器

存放数据的部件

一些复杂的处理过程需要分步进行，依次用不同的指令处理数据

需要用寄存器临时存放指令处理的中间结果

通用寄存器(General Purpose Register,GPR)组

指令需要在操作数字段中指定：

• 从哪个GPR中读出数据（源操作数）
• 将计算结果存入哪个GPR（目的操作数）

指令的编码

指令=用二进制编码的菜单

例如, 某简单处理器有4个GPR, 支持3种指令, 其中2种如下:

 7 6 5 4 3 2 1 0
+----+----+-----+-----+
| 00 | rd | rs1 | rs2 | R[rd]=R[rs1]+R[rs2] add指令, 寄存器相加
+----+----+-----+-----+
| 10 | rd | imm | R[rd]=imm li指令, 装入立即数, 高位补0
+----+----+-----+-----+

由于指令只有3种, 因此最少可以用2位操作码就能区分所有指令.

在上述例子中, 操作码是00, 表示add指令; 操作码是10, 表示li指令. 为了方便叙述, 指令通常有相应的名称, 如add指令和li指令.

关于操作数, 因为GPR只有4个, 因此可以用2位来指定一个GPR的地址(00, 01, 10, 11). 操作数据的来源称为”源寄存器”, 上述的add指令需要从两个源寄存器中获取加数, 两个源寄存器的地址分别记为rs1和rs2, 分别用R[rs1]和R[rs2]来表示GPR中存放的内容; 操作需要写入的目的称为”目的寄存器”, 一般记为rd. 其中, 第2条li指令的操作数稍有不同, 其源操作数不再是GPR, 而是直接将指令中的imm字段解析成一个二进制数来使用, 这种操作数称为”立即数”.

综上, 上述指令的长度都是8位. 我们可以根据上述的指令编码规则来理解一条指令的含义, 一些具体的指令例子如下:

00100001 add指令, 将R[0]和R[1]相加, 结果写入R[2]
10110000 li指令, 将立即数0000写入R[3]
10000101 li指令, 将立即数0101写入R[0]

存储程序

让程序（=指令序列）自动控制计算机的执行

先把一段指令序列放在存储器(如现代计算机的内存)中, 让计算机从内存中取出指令来执行;

当计算机执行完一条指令之后, 就继续执行下一条指令.

为了能让计算机知道下一条指令在哪里, 还需要有一个用于指示当前执行到哪条指令的部件, 这个部件称为程序计数器”(Program Counter, PC)

重复以下步骤:
 从PC指示的存储器位置取出指令
 执行指令
 更新PC

分支指令

可以修改PC的指令

PC也是一个寄存器

 7 6 5 2 1 0
+----+---- -----+-----+
| 11 | addr | rs2 | if (R[0]!=R[rs2]) PC=addr bner0指令, 若不等于R[0]则跳转
+----+----------+-----+

bner0指令是Branch if Not Equal r0的缩写, 如果执行这条指令的时候R[rs2]与R[0]不相等, 则将PC寄存器更新为addr, 即让PC指向addr处的指令.

数列求和的程序

用指令来计算1+2+...+10这一数列的和

假设以下指令序列存放在存储器中, 用于计算上述数列之和, 其中:前的数字表示PC, #及其后的文字表示注释:

0: li r0, 10 # 这里是十进制的10
1: li r1, 0
2: li r2, 0
3: li r3, 1
4: add r1, r1, r3
5: add r2, r2, r1
6: bner0 r1, 4
7: bner0 r3, 7

用(PC, r0, r1, r2, r3)的格式来记录寄存器的值, 这一格式也反映了处理器所处的状态.

例如(7, 2, 3, 1, 8)表示接下来将要执行编号为7的指令, 当前4个GPR的值分别为2, 3, 1, 8. 我们约定在开始的时刻, 处理器的状态是(0, 0, 0, 0, 0)

以下是处理器执行前若干条指令的过程:

PC r0 r1 r2 r3
(0, 0, 0, 0, 0) # 初始状态
(1, 10, 0, 0, 0) # 执行PC为0的指令后, r0更新为10, PC更新为下一条指令的位置
(2, 10, 0, 0, 0) # 执行PC为1的指令后, r1更新为0, PC更新为下一条指令的位置
(3, 10, 0, 0, 0) # 执行PC为2的指令后, r2更新为0, PC更新为下一条指令的位置
(4, 10, 0, 0, 1) # 执行PC为3的指令后, r3更新为1, PC更新为下一条指令的位置
(5, 10, 1, 0, 1) # 执行PC为4的指令后, r1更新为r1+r3, PC更新为下一条指令的位置
(6, 10, 1, 1, 1) # 执行PC为5的指令后, r2更新为r2+r1, PC更新为下一条指令的位置
(4, 10, 1, 1, 1) # 执行PC为6的指令后, 因r1不等于r0, 故PC更新为4
(5, 10, 2, 1, 1) # 执行PC为4的指令后, r1更新为r1+r3, PC更新为下一条指令的位置
......

CPU=不断执行指令的部件

重新审视编程

上述的add和li等指令, 在计算机领域里面属于汇编语言。汇编语言是指令的符号化表示

更底层的机器语言：指令的二进制表示

10001010 # 0: li r0, 10
10010000 # 1: li r1, 0
10100000 # 2: li r2, 0
10110001 # 3: li r3, 1
00010111 # 4: add r1, r1, r3
00101001 # 5: add r2, r2, r1
11010001 # 6: bner0 r1, 4
11011111 # 7: bner0 r3, 7

指令集架构的状态机模型

指令集架构

GPR，PC，存储器，指令及其执行过程属于指令集架构（Instruction Set Architecture, ISA，简称指令集）

x86,ARM,RISC-V都是ISA

ISA的本质是一系列规范，定义了一台模型机的功能和行为

• 模型机=只存在于思维的机器
• 用数字电路实现模型机的功能 -> 一台真正的计算机

状态机的（不严谨）定义

状态机的定义包含如下部分:

• 状态集合$S=\{S_1,S_2,...\}$
• 激励事件集合$E$
• 状态转移规则$next:S\times E\rarr S$
• 描述每个状态在不同激励事件下的次态(next state), 即二元函数$next(S,E)$给出了在状态下接收到激励事件$E$后的次态
• 初始状态$S_0 \in S$

ISA的状态机模型

• 状态集合：ISA中的一个状态是一组具体的PC, GPR和内存, 而全体状态的集合则是PC, GPR和内存所有取值的组合

• 激励事件集合：在ISA中, 执行指令会改变状态。激励事件$E=\{指令\}$

• 状态转移规则$next:S\times E\rarr S$

• 在ISA中, 状态转移规则用于描述”在某个状态下执行某指令后的次态”, 也即指令的语义, 它约定了执行某指令后, 状态应该发生怎么样的变化

• 语义（Semantics） = 状态转移方程

• 语法 (Syntax) 是它的样子：比如二进制是 000000...，汇编是 ADD ...。

语义 (Semantics) 是它干了什么，也就是它如何改变了状态 $S$。

• 当我们说”这条指令的语义”时，我们就是在说：“执行这条指令后，寄存器和内存里的数据会发生什么变化”。

• 初始状态：$S_0=(PC_0,R_0,M_0)$

在sISA中, 状态转移规则就是以下3条指令的语义:

 7 6 5 4 3 2 1 0
+----+----+-----+-----+
| 00 | rd | rs1 | rs2 | R[rd]=R[rs1]+R[rs2] add指令, 寄存器相加
+----+----+-----+-----+
| 10 | rd | imm | R[rd]=imm li指令, 装入立即数, 高位补0
+----+----+-----+-----+
| 11 | addr | rs2 | if (R[0]!=R[rs2]) PC=addr bner0指令, 若不等于R[0]则跳转
+----+----------+-----+

除了指令的语义之外，ISA还包括：

输入输出，系统状态，中断异常，虚存管理，内存模型

C程序的状态机模型

想象你在玩一个像《大富翁》那样的棋盘游戏。

• 状态 ($S$)：你现在站在”第 5 格”，手里有 1000 块钱。
• 激励事件 ($E$)：“轮到你了，你扔了骰子走了几步，停在了第 8 格”。
• 这就是触发动作。如果你不扔骰子（不执行），游戏就停了。
• 状态转移规则 ($R$)：第 8 格的格子上写着规则——“在此处停留者，需支付过路费 200 元”。
• 这就是语义。它规定了在这个格子上发生动作后，你的钱（状态）该怎么变。

结果： 根据规则 ($R$)，因为你停在了第 8 格 ($E$)，你的钱从 1000 变成了 800，位置变成了第 8 格 ($S_{new}$)。

总结

• 激励事件是动态的：程序运行过程中，PC 一行一行地往下走，每一次”走”都是一次激励。
• 状态转移规则是静态的：代码写好后，每一行代码的含义（它会怎么改变量）就已经固定死了，不管你运不运行它，规则都在那里。

数字电路的状态机模型

数字逻辑电路=组合逻辑电路+时序逻辑电路

• 状态集合$S=\{(时序逻辑元件的值)\}$
• 具体包括寄存器，存储器，触发器等。因为只有时序逻辑电路才能存储信息
• 激励事件$E=\{组合逻辑\}$
• 组合逻辑电路输出的信号驱动时序逻辑元件改变状态
• 状态转移规则$next:S\times E\rarr S$ （由设计中的组合逻辑电路决定）
• 初始状态：$S_0=(复位时时序逻辑元件的值)$

 +------------------+
+-->| Sequential Logic |----+
| +------------------+ |
| next state | current state
| |
| +---------------------+ |
+--| Combinational Logic |<-+
 +---------------------+

Johnson计数器

D的Q端有一个反相器

 A B C D
(0, 0, 0, 0) # 初始状态
(1, 0, 0, 0)
(1, 1, 0, 0)
(1, 1, 1, 0)
(1, 1, 1, 1)
(0, 1, 1, 1)
(0, 0, 1, 1)
(0, 0, 0, 1)
(0, 0, 0, 0) # 与初始状态一致

在计算机上执行C程序

怎么让计算机执行C程序？

1. 将C程序的代码翻译成行为等价的指令序列
2. 让计算机的电路执行这个指令序列

指令序列=桥梁

编译(compile)

将C程序翻译成指令序列

编译器(compiler)

	C程序	ISA
状态	$\{PC,V\}$	$\{PC,R,M\}$
激励事件	执行语句	执行指令
状态转移规则	语句的语义	指令的语义

C程序执行一条语句后的状态, 与ISA执行编译得到的指令序列后的状态, 语义上是等价的

• 将C程序的状态翻译成ISA的状态, 也即
• 将C程序的PC对应到ISA的PC
• 将C程序的变量对应到ISA的GPR或内存
• 将C程序的状态转移规则翻译成ISA的状态转移规则, 也即, 将语句翻译成指令序列

CPU设计

根据ISA设计数字电路

	ISA	数字电路
状态	$\{PC,R,M\}$	时序逻辑电路
激励事件	执行指令	处理组合逻辑
状态转移规则	指令的语义	组合逻辑电路的逻辑

ISA执行一条指令后的状态, 与设计出的CPU在组合逻辑电路控制下的次态, 语义上是等价的

• 用数字电路的状态实现ISA的状态（用时序逻辑电路实现PC, GPR和内存）
• 用数字电路的状态转移规则实现ISA的状态转移规则（用组合逻辑电路实现指令的功能）

程序, ISA和CPU之间的联系

1. 根据ISA手册的功能描述, 画一张CPU的结构图 -> 处理器微结构设计
2. 根据结构图设计具体的电路 -> 逻辑设计
3. 开发程序 -> 软件编程
4. 将程序翻译成ISA手册中描述的指令序列 -> 编译
5. 在CPU上执行程序 = 用程序编译出的指令序列控制CPU电路进行状态转移

• 此时, 三个状态机产生联系: $S_C-S_{ISA}-S_{CPU}$