计组笔记

功夫再高,也怕挂科。

第一章 概述

CPU 主要由运算器控制器组成。
高速缓存 cache 采用 SRAM,内存采用 DRAM。
MIPS 和 ARM 都属于 RISC(Reduced Instruction Set Computer),x86 属于 CISC(Complex Instruction Set Computer)。
Amdahl 定律:$t_{new} = t_{related}/S + t_{unrelated}$,$S$ 为加速比

时钟周期数 = 指令数 x 平均每条指令所需周期数(即cycles = IC x CPI)
CPU 执行时间 = 指令数 x CPI x 时钟周期长(即 CPUtimes = IC x CPI x T)
CPUtimes = IC x CPI / f

能耗 = 负载电容 x 电压^2
功耗 = 1/2 x 负载电容 x 电压^2 x 开关频率

指令

MIPS 一共有 32 个 32 位的寄存器
程序中的变量放在保存寄存器(store reg)中:$s0~7 共 8 个
运算的临时变量放在临时寄存器(temp reg)中:$t0~9 共 10 个
零寄存器(zero reg):$zero,常用于赋值为 0

三类指令:
运算指令addsubmuldivandorxornorsltsllsrlsra
数据传送指令lwswlbsblui
决策指令beqbnejjaljr

三种指令格式:
R 型:op rd, rs, rt
I 型:op rt, rs, imm
J 型:op target

算术运算指令

如 a, b, c 三个变量分别存放在 $s0, $s1, $s2 中,要计算 c = a + b,则汇编代码为:

1
add $s2, $s0, $s1

计算 c = a - b,则汇编代码为:

1
sub $s2, $s0, $s1

加立即数,假设变量 i 位于 $s0,要计算 i = i + 1,则汇编代码为:

1
addi $s0, $s0, 1

要减就把立即数设为负数,故 MIPS 无 subi 指令。

逻辑运算指令

比较简单,nor 为或非,就是先或再非,与 0 或非可以实现取反。

1
sll $s2, $s0, 2 # $s2 = $s0 << 2

运算指令例子

result($s3) = a($s0) - 10 + (b($s1) + c($s2) * 5)

1
2
3
4
5
sll $t0, $s2, 2     # $t0 = c * 4
add $t1, $t0, $s2 # $t1 = c * 5
add $t2, $t1, $s1 # $t2 = b + c * 5
addi $t3, $s0, -10 # $t3 = a - 10
add $s3, $t3, $t2 # $s3 = a - 10 + (b + c * 5)

寄存器-存储器数据传送

lw 即 load word
假设数组 a 基址存放在 $s1 中,要把 a[5] 的值传送到 $s0 中:

1
lw $s0, 20($s1)

a[0]a[5] 的距离是 5 个字,而在 MIPS 中,一个字是 4 个字节,所以 a[5] 的地址是 a 的基址加上 20。
$t0 的值传送到 a[2]

1
sw $t0, 8($s1)

寄存器间数据传送

$t0 的值传送到 $s1

1
2
3
addi $s1, $t0, 0
add $s1, $t0, $zero
move $s1, $t0 # move 是伪指令,等价于 add $s1, $t0, $zero

把常数 10 传送到 $s2

1
2
addi $s2, $zero, 10
li $s2, 10 # li 是伪指令,即 load immediate

装载 32 位立即数

把 10A2 7FFF 放进 $s2

1
2
lui $s2, 0x10A2         # load upper immediate
ori $s2, $s2, 0x7FFF # or immediate

这里不能用 addi,因为如果低 16 位的最高位是 1,那么会被当作负数,造成结果错误。

例:数组元素运算与赋值
a[i] = a[0] + 100000,数组 a 的基址存放在 $s0 中,i 存放在 $s1 中:

1
2
3
4
5
6
7
lw $t0, 0($s0)          # $t0 = a[0]
lui $t1, 1 # notice: 100000 = 0x186A0 > 0xFFFF
ori $t1, $t1, 0x86A0
add $t2, $t0, $t1 # $t2 = a[0] + 100000
sll $t3, $s1, 2 # $t3 = i * 4
add $t4, $s0, $t3 # $t4 = &a[i]
sw $t2, 0($t4) # a[i] = a[0] + 100000

决策指令

beq 即 branch equal,bne 即 branch not equal
j 即 jump,无条件跳转
例子:将如下代码翻译成 MIPS 汇编代码

1
2
if (i == j) f = g + h;
else f = g - h;

假设 f, g, h 分别存放在 $s0, $s1, $s2 中,i, j 分别存放在 $s3, $s4 中:

1
2
3
4
5
6
beq $s3, $s4, Else
add $s0, $s1, $s2
j Exit
Else:
sub $s0, $s1, $s2
Exit:

slt 即 set on less than,即小于则置位,否则清零(复位)
比如 $s0 = 0, $s1 = 0, $s2 = 1,则:

1
slt $s0, $s1, $s2

$s0 的会被置为 1,因为 0 < 1。

例子:

1
while (a[i] == k) i++;

假设 i 存放在 $s3k 存放在 $s5a 的基址存放在 $s6

1
2
3
4
5
6
7
8
Loop:
sll $t0, $s3, 2 # $t0 = i * 4
add $t1, $s6, $t0 # $t1 = &a[i]
lw $t2, 0($t1) # $t2 = a[i]
beq $t2, $s5, Exit # if a[i] == k, exit
addi $s3, $s3, 1 # i++
j Loop
Exit:

指令格式

R 型指令

指令中含三个寄存器的运算指令都属于 R 型(register type)指令,格式为 op rd, rs, rt
32 位的 MIPS 指令一共分为 6 个字段:

  • 操作码(opcode):6 位
  • 源寄存器 1(register source 1,rs):5 位
  • 源寄存器 2(register source 2,rt,叫 rt 应该是因为 t 是 s 的下一个字母):5 位
  • 目的寄存器(register destination,rd):5 位
  • 移位量(shamt):5 位
  • 功能码(funct):6 位

MIPS 有 32 个寄存器,所以 5 位就可以表示全部的 32 个寄存器,所以 rs、rt、rd 都是 5 位
R 型指令的 opcode 都是 0,由 6 位功能码指定操作,$t0 ~ $t7 的编号是 815,$s0 ~ $s7 的编号是 1623,add 的 funct 是 32,sub 的 funct 是 34。
sll/srl 也是 R 型指令,没有第二个源寄存器,rt 被置为 0,用 shamt 表示移位量。

I 型指令

addiori 都属于 I 型(immediate type)指令,格式为 op rt, rs, imm
I 型指令用 opcode 表示操作,rs 表示源寄存器,rt 表示目的寄存器,并把 rd-shamt-funct 三个字段合并成了 16 位的 imm,即立即数。

lwsw 也是 I 型指令,但是 rt 表示目的寄存器,rs 表示基址寄存器,和上面相反,imm 表示偏移量,这两个指令的操作码分别是 35 和 43。

过程

支持过程的三大寄存器:4 个参数寄存器 $a0 ~ $a3,两个返回值寄存器 $v0 ~ $v1返回地址寄存器 $ra

jal 即 jump and link,跳转到标签并保存返回地址到寄存器 $ra,由调用者主程序使用。
jr 即 jump register,跳转到寄存器中的地址,由被调用者过程使用,一般是 jr $ra

两个栈指针寄存器 $sp(stack pointer) 和 $fp (frame pointer),分别表示栈指针和帧指针。在过程调用时,如果要用到保存寄存器,就要先压入栈中,调用结束后再弹出

还有一个全局指针寄存器 $gp,便于寻找位置固定的数据,如主程序使用的变量、声明为 static 的变量,统称静态变量。

一般程序在内存中有 5 个段,地址从低到高依次为

  1. 保留段
  2. 代码段
  3. 静态数据段
  4. 堆段(动态数据段)
  5. 栈段

堆由低向高增长,栈由高向低增长,双向奔赴,实现了内存空间的高效利用。

寻址

R 型指令都是寄存器寻址。
I 型指令第三个操作数(即第二个源操作数)是立即数的指令采用立即数寻址。lwsw 采用基址偏移寻址。beqbne 采用 PC(program counter) 相对寻址,分支 32 位地址 = PC + 4 + 字地址偏移量
J 型指令都是伪直接寻址,因为 J 型指令是由 6 位操作码和 26 位目标地址组成的,寻址时先左移 2 位形成 28 位字节地址,再和 PC 的高 4 位拼接成 32 位地址

假设第一行代码的地址是 10000,对如下代码:

1
2
3
4
5
6
7
8
Loop:
sll $t1, $s3, 2 # Temp reg $t1 = i * 4
add $t1, $t1, $s6 # $t1 = address of save[i]
lw $t0, 0($t1) # Temp reg $t0 = save[i]
bne $t0, $s5, Exit # go to Exit if save[i] != k
addi $s3, $s3, 1 # i = i + 1
j Loop # go to Loop
Exit:

bne $t0, $s5, Exit 中的立即数应该是 2,这里可以大概理解成隔了两条指令,而 j Loop 中的立即数稍微麻烦,首先因为 PC 的高 4 位是一样的,都是全 0,所以只需要考虑低 28 位,Loop 的地址是 10000,右移 2 位就是 100,所以 j Loop 的立即数是 100 (十进制的 4)的补码

PC 相对寻址的范围是 (PC + 4) - 2e17 ~ (PC + 4 + 2e17 - 4),大约是前后各 128 KB。
伪直接寻址的范围是和 PC 高 4 位相同的一切地址,即 256 MB。
要分支到更远的地址,就要把 beq 或者 bne 切换一下,然后下面跟一个 j 指令。
比如 beq $s0, $s1, L1 就换成如下代码:

1
2
3
bne $s0, $s1, L2
j L1
L2:

扩展跳转范围就直接换成 jr 指令,把目标地址放在寄存器中即可。
32 位系统最多只能支持 4 GB 的内存,所以 32 位的寄存器已经支持全部的内存寻址了。

C 语言的 4 个翻译层次

编译器将高级语言文件(.c)翻译成汇编文件(.asm),然后由汇编器将汇编文件翻译成机器码文件(.obj),再由链接器将机器码文件链接成可执行文件(.exe),最后由加载器将可执行文件加载到内存中执行。

算术运算

整数的表示

以下以 8 位二进制数为例:
无符号整数很好理解,就是 8 位全用来表示数值,如 0000 0000 表示 0,1111 1111 表示 255。
原码:用最高位表示正负号,其余 7 位表示绝对值
反码:将最高位为 0 的原码按位取反表示负数
补码:按位取反再加 1

符号扩展:
16 位扩展到 32 位时,将最高位(即符号位)复制到高 16 位。

大端编址和小端编址:
大端编址是将高位放在低地址,小端编址是将高位放在高地址。

比如 0xFFE0 在内存中时
大端编址:
低 8 位:0xFF
高 8 位:0xE0
小端编址:
低 8 位:0xE0
高 8 位:0xFF

ALU

符号位进位称为上溢,符号位借位称为下溢,统称溢出。

比较简单的 32 位 ALU 是行波进位加法器,即每一位都是一个全加器,每个全加器有三个输入:两个加数和上一位的进位,两个输出:和位和进位。
但是每次进位都要过一次或门和与门,就产生了 64 个门延迟。

为了加快进位,进而加速加法运算,现在广泛采用超前进位加法器,通过将进位分为 4 位一组,抽象成每组的进行,实现加法器的并行执行。

要执行 n 位加法,求出 n 是 4 的几次方,并向上取整,再乘 2 加 1,就是超前进位加法器的门延迟。
用数学表达式表示就是 $2 \times \lceil \log_4 n \rceil + 1$,n 为 16 时是 5,n 为 32 和 64 时都是 7

除法中,规定余数和被除数同号,比如 -7/2 = -3 余 -1,而不是商 -4 余 1。

MIPS 中的乘除指令有 4 条,multdiv 是有符号的乘法和除法,multudivu 是无符号的乘法和除法,均为双操作数 R 型指令。
mfhimflo 分别是将乘法和除法的高 32 位和低 32 位传送到寄存器中,均为单操作数 R 型指令。

浮点数

IEEE 754 标准规定了浮点数的表示方法,32 位单精度浮点数由 1 位符号位、8 位指数位和 23 位尾数位组成。注意指数要加 127 的偏差,同时这里的尾数是指小数点后的部分,因为二进制的科学计数法里,只要不是 0.0,那么小数点前的部分一定是 1。
举个例子 -0.00101 = -1.01 x 2^-3,很明显,因为是负数,所以符号位是 1,指数位是 -3 + 127 = 124,尾数位是 01(后面补 0)。
64 位双精度浮点数由 1 位符号位、11 位指数位和 52 位尾数位组成,指数偏差是 1023。

MIPS 中增加了单独的 32 个单精度浮点寄存器 $f0 ~ $f31,一对单精度浮点寄存器组合成一个双精度寄存器,以偶数编号。

add.ssub.s 是单精度浮点数的加减法,mul.sdiv.s 是单精度浮点数的乘除法,s 换成 d 就是双精度浮点数的运算。
比较两个浮点数大小,用 c.eq.sc.lt.s,分别表示等于和小于,为真时用 bc1t 跳转,为假时用 bc1f 跳转。

这里我查了一下应该是 bc1tbc1f,但是课本写的是 bcltbclf,我觉得应该是笔误。

IEEE 754 在运算时引入了两个尾数位,分别是保护位和舍入位,运算误差不超过 0.5 个 ulp(unit in the last place,即尾数最低位)。

处理器

最核心的部分。

存储层次

参考

https://www.bilibili.com/video/BV1je4y1Q7BK

作者

未央

发布于

2024-06-05

更新于

2024-06-18

许可协议

评论