计组学习笔记1

高级语言和机器指令中的运算

高级语言中的运算最后都要通过机器指令和硬件部件实现

从 C 语言角度看，常见运算包括：

算术运算：加、减、乘、除、取模
关系运算：等于、不等于、大于、小于等
逻辑运算：逻辑与、逻辑或、逻辑非
位运算：按位与、或、异或、取反、移位

算术运算

整数运算原则上只针对同种整数类型。不同类型混合运算时会发生类型转换

常见规则：

char 和 short 会变为 int
有符号和无符号数混合时，统一转成无符号类型
整数除法会截断小数部分
取模运算只能用于整数

浮点类型包括 float、double 和 long double

浮点和整数混合运算时，整数通常先转成浮点数

两个不同精度的浮点数运算时，低精度会向高精度转换

关系和逻辑运算

关系运算的结果是真或假，在机器里通常用 1 和 0 表示

比较整数时注意 signed 和 unsigned 的混合问题

浮点数一般不直接用 == 比较是否相等，而是判断： \[ |a-b| < \epsilon \]

原因是浮点数表示有限，并且浮点加法不满足严格结合律

逻辑运算 && 和 || 有短路计算：

a && b 中，如果 a 为假，则不计算 b
a || b 中，如果 a 为真，则不计算 b

位运算

位运算直接操作二进制位。

常见运算：

&：按位与
|：按位或
^：按位异或
~：按位取反
<<：左移
>>：右移

移位分为逻辑移位和算术移位

逻辑移位只把位整体移动，空位补 0

算术右移要保持符号位，因此高位补符号位。补码表示的带符号数右移时通常使用算术右移

举例：对于 8 位补码数 1111 1000（-8），算术右移 2 位得到 1111 1110（-2），逻辑右移 2 位得到 0011 1110（62）

短数据向长数据转换时，会发生扩展：

无符号数使用 0 扩展
补码带符号数使用符号扩展

长数据向短数据转换时，会发生截断，通常直接丢弃高位

这种错误很隐蔽，因为程序还能运行，但数值已经错了

MIPS 中的运算

MIPS 支持的运算大致包括：

逻辑运算：and、andi、or、ori、xor、nor
移位运算：sll、srl、sra
定点运算：add、addu、sub、subu
乘除运算：mult、multu、div、divu
数据传送：lw、sw、lbu、lhu、sb、lui
浮点运算：add.s、sub.s、mul.s、div.s

MIPS 乘除法比较特殊，结果不直接写入通用寄存器

乘法结果是 64 位，放在 HI 和 LO 中：

HI：高 32 位
LO：低 32 位

除法中：

LO 存商
HI 存余数

再用 mfhi 和 mflo 把结果取到通用寄存器中

举例：mult $s1, $s2 后，商在 LO，余数在 HI

基本运算部件

运算部件的核心是加法器

减法、比较、乘法、除法，最后都需要转化为加法、移位和控制逻辑的组合

此处可以参考数字逻辑课程中加法器的设计

全加器

全加器处理三个输入：

本位 $X_i$
本位 $Y_i$
低位进位 $C_{i-1}$

输出为：

本位和 $F_i$
高位进位 $C_i$

逻辑表达式为： \[ F_i=X_i \oplus Y_i \oplus C_{i-1} \]

\[ C_i=X_iC_{i-1}+Y_iC_{i-1}+X_iY_i \]

把 $n$ 个全加器串起来，就得到串行进位加法器

串行进位加法器结构简单，但必须等低位进位逐级传到高位，所以速度慢

并行进位加法器

并行进位加法器使用先行进位思想，提前计算各位进位

定义： \[ G_i=A_iB_i \]

\[ P_i=A_i+B_i \]

其中：

$G_i$ 表示本位一定产生进位
$P_i$ 表示本位会传递低位进位

进位公式为： \[ C_{i+1}=G_i+P_iC_i \]

4 位加法器中： \[ C_1=G_0+P_0C_0 \]

\[ C_2=G_1+P_1G_0+P_1P_0C_0 \]

\[ C_3=G_2+P_2G_1+P_2P_1G_0+P_2P_1P_0C_0 \]

\[ C_4=G_3+P_3G_2+P_3P_2G_1+P_3P_2P_1G_0+P_3P_2P_1P_0C_0 \]

这样各个进位可以并行产生，速度明显快于串行进位

缺点是门电路输入更多，硬件复杂度更高

带标志加法器

处理器中的加法器通常还要输出标志位

常见标志：

OF：溢出标志
SF：符号标志
ZF：零标志
CF：进位/借位标志

对无符号数来说，进位标志 CF 很重要

对补码带符号数来说，溢出标志 OF 更重要

算术逻辑部件

ALU 是在加法器基础上增加运算控制得到的

它可以支持：

加法
减法
与、或、异或、取反
比较
移位

控制信号通常称为 ALUop 或 ALUctr

控制信号位数越多，能区分的操作种类越多

在数据通路中，ALU 不只是做普通算术运算，也会用来：

计算访存地址
计算分支目标
做相等比较
做小于比较

定点数运算

补码加减法

假设两个 $n$ 位补码定点数为： \[ [X]_{\text{补}}=X_{n-1}X_{n-2}\cdots X_0 \]

\[ [Y]_{\text{补}}=Y_{n-1}Y_{n-2}\cdots Y_0 \]

则补码加减法统一为： \[ [X\pm Y]_{\text{补}}=[X]_{\text{补}}+[\pm Y]_{\text{补}}\pmod {2^n} \]

补码运算中，符号位也参加运算，最高位产生的进位直接丢弃

溢出判断常用两种方法：

最高位和次高位的进位不同，则溢出
两个同号数相加，结果符号与加数不同，则溢出

用进位表示： \[ OF=C_{n-1}\oplus C_n \]

一般来说，溢出有如下规律：

正数 + 正数得到负数，溢出
负数 + 负数得到正数，溢出
异号相加不会溢出

原码加减法

原码加减法把符号位和数值位分开处理

加法规则：

同号求和，符号取被加数符号
异号求差，符号取绝对值较大数的符号

减法可以转化为加法： \[ X-Y=X+(-Y) \]

原码加减法在通用整数 ALU 中不常用，但在浮点数尾数运算中很重要，因为浮点尾数通常按符号和绝对值分开处理

原码乘法

两个原码数相乘时，符号位单独处理： \[ SF=X_0\oplus Y_0 \]

数值位按无符号数乘法处理

手算乘法的本质是： \[ X \times Y=\sum_i X\times y_i \times 2^{-i} \]

计算机中不会把所有部分积都先保存下来再求和，而是边判断乘数位、边加、边移位

过程如下：

初始部分积 $P_0=0$
从乘数最低位开始判断
若该位为 1，则部分积加被乘数
若该位为 0，则不加
部分积和乘数整体右移
重复 $n$ 次

递推式可以写成： \[ P_{i+1}=2^{-1}(P_i+X\times y_{n-i}) \]

硬件中通常包括：

被乘数寄存器 $X$
乘积寄存器 $P$
乘数寄存器 $Y$
进位触发器 $C$
循环计数器
ALU

乘法本质上就是加法和移位的循环

补码乘法

补码乘法常用 Booth 算法（详细参考数字逻辑）

设乘数为补码： \[ Y=y_{n-1}y_{n-2}\cdots y_0 \]

并令： \[ y_{-1}=0 \]

Booth 算法每次观察相邻两位 $y_i$ 和 $y_{i-1}$：

00：不操作，只右移
11：不操作，只右移
01：加 $X$
10：减 $X$

递推式为： \[ P_i=2^{-1}(P_{i-1}+(y_{i-1}-y_i)X) \]

Booth 算法的好处是符号位和数值位可以统一处理，也能减少连续 1 情况下的加法次数

补码两位乘法进一步每次处理两位乘数，循环次数减半，缺点是控制逻辑更复杂

整数乘法溢出

两个 $n$ 位数相乘，完整结果需要 $2n$ 位保存

如果机器指令只保留低 $n$ 位，就可能溢出

判断规则：

无符号乘法：高 $n$ 位全 0 才不溢出
带符号乘法：高 $n$ 位必须全为低 $n$ 位最高位的符号扩展

MIPS 中 mult 和 multu 会产生 64 位结果，放入 HI 和 LO

一般来说硬件本身不处理乘法溢出，软件读取 HI 和 LO 自行判断

除法运算

除法也可以用加减和移位完成

无符号除法的思路和手算类似：

用中间余数减除数
够减，则商 1
不够减，则商 0
移位，继续试商

恢复余数法中，如果试减后结果为负，就把除数加回来恢复余数

不恢复余数法也叫加减交替法：它不立即恢复，而是在下一步用相反操作补回来。

定点除法前需要先处理特殊情况：

被除数为 0，商为 0
除数为 0，发生异常
整数除法中商超过可表示范围，发生溢出

浮点数运算

IEEE 754 格式

这部分参考 CSAPP

IEEE 754 浮点数分为三部分：

符号位
阶码
尾数

对于规格化数，尾数最高位隐含为 1，因此实际保存的是小数部分。

常见格式：

binary32：单精度，对应 C 中的 float
binary64：双精度，对应 C 中的 double
binary16：半精度

IEEE 754 还定义了特殊值：

$+0$ 和 $-0$
非规格化数
$+\infty$ 和 $-\infty$
NaN

浮点加减法

手工计算浮点加法时，先要对阶： \[ 1.123\times 10^5 + 2.560\times 10^2 \]

需要改写成： \[ 1.123\times 10^5 + 0.002560\times 10^5 \]

然后尾数相加。

二进制浮点加减法步骤：

求阶差
对阶，小阶向大阶看齐
尾数加减
规格化
舍入
判断溢出和特殊情况

对阶时，阶小的数尾数右移，右移位数等于阶差。

IEEE 754 中尾数右移时，要把隐含的 1 还原，并保留被移出的低位作为附加位，用于后续舍入。

规格化

尾数加减后可能不再是规格化形式。

如果尾数形如： \[ \pm 1x.xxxx \]

说明最高位产生进位，需要右规：

尾数右移 1 位
阶码加 1

如果尾数形如： \[ \pm 0.00\cdots 1xxx \]

说明最高有效位太靠后，需要左规：

尾数左移
阶码减少

右规通常最多一次，而左规可能需要多次。

舍入

浮点运算中间结果通常比最终格式更长，所以需要舍入

IEEE 754 常见舍入方式：

就近舍入：选择最近的可表示数，如果正好在中间，则选偶数
朝 $+\infty$ 舍入
朝 $-\infty$ 舍入
朝 0 舍入

为了支持舍入，硬件会保留附加位，如保护位、舍入位和粘滞位。

浮点数不是实数，只是实数集合的有限近似。

所以计算机中的浮点数运算经常会出现：

加法不满足结合律
大数吃小数
十进制小数无法精确表示
类型转换导致精度丢失

运算部件的组成

综合各种定点运算算法可以发现，核心操作基本都是：

加
减
移位
选择
暂存

因此运算数据通路通常由以下部件组成：

ALU
移位器
寄存器组
多路选择器
总线
控制逻辑

现代 CPU 中，运算部件也常称为功能部件或执行部件

整数 ALU 通常用于定点加减、逻辑运算、比较、地址计算等

浮点运算部件更复杂，通常会使用流水线方式实现

从硬件角度看，所谓运算器、运算部件、功能部件、执行部件和数据通路，含义接近，只是强调角度不同

指令系统

指令集体系结构 ISA 是软硬件之间的接口

程序员和编译器看到的是 ISA，处理器硬件实现的是 ISA

同一个 ISA 可以有不同的微体系结构实现，比如单周期、多周期、流水线、超标量等

指令集结构分类

区分指令集结构的一个重要因素是：CPU 中用来存放操作数的存储单元是什么

常见结构：

堆栈结构
累加器结构
通用寄存器结构

现代处理器基本都采用通用寄存器结构

按照 ALU 指令中操作数是否来自存储器，又可以把通用寄存器结构分为：

存储器-存储器结构：ALU 指令的操作数都可以来自内存
寄存器-存储器结构：部分操作数可以来自内存
寄存器-寄存器结构：ALU 指令只操作寄存器

寄存器-寄存器结构也叫 load-store 结构

它规定只有 load/store 指令能访问内存，普通运算指令只能访问寄存器

MIPS 就是典型的 load-store 结构

不同结构的例子

假设要计算： \[ C=A+B \]

且 A、B、C 都在内存中

堆栈结构可能写成：

push A
push B
add
pop C

累加器结构可能写成：

1
2
3

load A
add B
store C

寄存器-存储器结构可能写成：

1
2
3

load R1, A
add R1, B
store R1, C

寄存器-寄存器结构可能写成：

load R1, A
load R2, B
add R3, R1, R2
store R3, C

RR 结构的指令条数可能更多，但指令格式规整，执行周期更接近，也更适合流水线

寄存器-寄存器型指令集

优点：指令字长固定，指令结构简洁，是一种简单的代码生成模型，各种指令的执行时钟周期数相近
缺点：与指令中含存储器操作数的指令集结构相比，指令条数多，目标代码不够紧凑，因而程序占用的空间比较大

存储器-存储器型指令集

优点：目标代码最紧凑，不需要设置寄存器来保存变量
缺点：指令字长变化很大，特别是3操作数指令。而且每条指令完成的工作也差别很大。对存储器的频繁访问会使存储器成为瓶颈。这种类型的指令集结构现在已不用了

寄存器-存储器型指令集

优点：可以在ALU指令中直接对存储器操作数进行引用，而不必先用load指令进行加载。容易对指令进行编码，目标代码比较紧凑
缺点：指令中的两个操作数不对称。在一条指令中同时对寄存器操作数和存储器操作数进行编码，有可能限制指令所能够表示的寄存器个数。指令的执行时钟周期数因操作数的来源（寄存器或存储器）不同而差别比较大

指令格式

一条指令通常包含：

操作码：说明做什么操作
源操作数地址：说明操作数从哪里来
目的操作数地址：说明结果写到哪里
下一条指令地址：通常隐含在 PC 中

指令格式设计要考虑：

指令尽量短
操作码位数足够
编码解释必须唯一
指令字长最好是字节整数倍
地址字段个数合理
格式尽量规整

RISC 指令集倾向于定长、规整；CISC 指令集通常更复杂、更紧凑

寻址方式

寻址方式是指令说明操作数位置的方法。

常见寻址方式：

立即寻址：操作数就在指令中
- 优点：指令执行速度快
- 缺点：操作数幅值有限
直接寻址：地址字段就是有效地址
- 优点：有效地址计算简单
- 缺点：地址范围有限
间接寻址：地址字段指向一个保存有效地址的单元，其中保存了内存地址，取出再寻址
- 优点：有效地址范围大
- 缺点：多次存储器访问
寄存器寻址：操作数在寄存器中
- 优点：指令执行快，指令短
- 缺点：地址范围有限
寄存器间接寻址：寄存器内容是有效地址，取出寻址
- 优点：地址范围大
- 缺点：额外存储器访问
偏移寻址：有效地址为寄存器值加偏移量
- 优点：灵活
- 缺点：复杂
堆栈寻址：操作数在栈顶
- 优点：指令短
- 缺点：应用有限

偏移寻址很常用，可以细分为：

相对寻址：$EA=(PC)+A$
基址寻址：$EA=(B)+A$
变址寻址：$EA=(I)+A$

其中 $EA$ 表示有效地址

MIPS 的 lw 和 sw 使用的是基址寻址：

1	lw $t0, 32($s1)

它的有效地址为： \[ EA=R[\$s1]+SignExt(32) \]

MIPS 的 beq 使用 PC 相对寻址： \[ Target=PC+4+SignExt(imm16)\times 4 \]

这里立即数表示的是相对指令条数，不是字节数，所以要左移 2 位

举例：此时 $R1 = 300$
地址存放值
200 300
300 99
332 88
立即寻址：
1
MOV R2, #42
结果为 $R2=42$
直接寻址：
1
MOV R2, 300
结果为 $R2=99$
间接寻址：
1
MOV R2, (200)
步骤为：先取地址 200 中的值 300，再取地址 300 中的值 99，结果为 $R2=99$
寄存器寻址：
1
MOV R2, R1
结果为 $R2=300$
寄存器间接寻址：
1
MOV R2, (R1)
结果为 $R2=99$
偏移寻址：
1
MOV R2, 32(R1)
$EA = R1 + 32 = 300 + 32 = 332$，结果为 $R2=88$
堆栈寻址：操作数在栈顶
1
POP R2
结果：$R2$ 为栈顶值，栈指针增加 4

地址	存放值
200	300
300	99
332	88

MIPS 指令格式

MIPS 指令固定为 32 位，有三类基本格式。

R 型指令：

字段	位数	含义
op	6	操作码
rs	5	第一个源寄存器
rt	5	第二个源寄存器
rd	5	目的寄存器
shamt	5	移位量
func	6	功能码

R 型指令中，op=000000，具体操作由 func 决定

I 型指令：

字段	位数	含义
op	6	操作码
rs	5	源寄存器或基址寄存器
rt	5	目的寄存器或源寄存器
imm16	16	立即数或偏移量

J 型指令：

字段	位数	含义
op	6	操作码
target	26	跳转目标字段

MIPS 所有指令都是 32 位宽，按字节编址，但指令地址必须是 4 的倍数

因此指令地址最低两位总是 0，可以用 26 位 target 字段左移 2 位得到完整地址

MIPS 寄存器

MIPS 有 32 个 32 位通用寄存器

寄存器编号占 5 位，因为： \[ 2^5=32 \]

常用寄存器约定：

名称	编号	用途
`$zero`	0	恒为 0
`$v0-$v1`	2-3	返回值
`$a0-$a3`	4-7	参数
`$t0-$t7`	8-15	临时寄存器
`$s0-$s7`	16-23	保存寄存器
`$t8-$t9`	24-25	更多临时寄存器
`$gp`	28	全局指针
`$sp`	29	栈指针
`$fp`	30	帧指针
`$ra`	31	返回地址

$zero 是一个很有用的设计

比如清零可以写成：

1	add $t0, $zero, $zero

很多伪指令也依赖 $zero 实现

MIPS 常见指令

算术逻辑指令：

add  $1, $2, $3
sub  $1, $2, $3
and  $1, $2, $3
or   $1, $2, $3
slt  $1, $2, $3
addi $1, $2, 100

访存指令：

1 2	lw $1, -30($2) sw $3, 500($4)

分支和跳转：

beq $1, $2, label
bne $1, $2, label
j   target
jal target
jr  $ra

jal 用于过程调用，它会把返回地址写入 $ra： \[ \$ra \leftarrow PC+4 \]

然后跳转到目标地址。

jr $ra 用于返回调用点

汇编和反汇编

把汇编指令翻译成机器码称为汇编

比如：

1	add $t0, $s1, $s2

它是 R 型指令

字段为：

op=000000
rs=$s1=17
rt=$s2=18
rd=$t0=8
shamt=0
func=100000

最终机器码为： \[ 0x02324020 \]

反过来，根据 32 位机器码拆字段，再查寄存器表和操作码表，就能得到汇编形式，这称为反汇编

过程调用和栈

过程调用要解决几个问题：

参数如何传给被调用过程
如何跳转到被调用过程
如何返回调用过程
返回值放在哪里
如何避免寄存器内容被破坏

MIPS 中前 4 个参数通常放在 $a0-$a3 中，返回值放在 $v0-$v1 中

如果参数更多，或者有局部数组、结构体等复杂变量，就需要使用栈

MIPS 的栈从高地址向低地址增长。

每压入一个字，栈指针减少 4：

1 2	addi $sp, $sp, -4 sw $ra, 0($sp)

每弹出一个字，栈指针增加 4：

1 2	lw $ra, 0($sp) addi $sp, $sp, 4

寄存器保存约定：

$t0-$t9 是调用者保存，调用后可能被破坏
$s0-$s7 是被调用者保存，如果被调用过程使用它们，需要先保存再恢复
$ra 在非叶子过程里通常需要保存，因为再次调用函数会覆盖 $ra

叶子过程不会再调用其他过程，因此不一定需要保存 $ra

栈帧用于保存一个过程调用期间的局部变量、返回地址、保存寄存器和额外参数

#计组学习笔记1