Computer Organization&Design学习记录

发表于 更新于

Chapter2 指令：计算机的语言

本章将介绍MIPS汇编语言指令。

三条设计原则

  1. 简单源于规整 Simplicity favors regularity.
  2. 越小越快 Smaller is faster.
  3. 优秀的设计需要适宜的折中方案 Good design demands good compromises.

2.2 硬件的操作与操作数

规整

add a, b, c // a = b + c MIPS汇编语言使用这样的固定记法。
每条MIPS算术指令只执行1个操作，仅有3个变量。

操作数必须来自寄存器

变量f、g、h、i、j依次分配给$s0~$s4，编译下面的C语句

f = (g + h) - (i + j);
---
add $t0, $s1, $s2 // t0 = s1 + s2
add $t1, $s3, $s4
sub $s0, $t0, $t1 // s0 = t0 + t1

数据传输

只有少量数据存在寄存器中，因此需要在存储器和寄存器间传输数据

A的基址是存在$s3，编译下面的C语句

A[12] = h + A[8]
---
lw  $t0, 32($s3) // 先读数，再相加；32为偏移量，8*4byte
add $t0, $s2, $t0
sw  $t0, 48($s3) // 存数

立即数

addi $t0, $t1, 4 // t0 = t1 + 4；无需读取4，作为立即数相加
subi $t0, $t1, 4

2.5 指令的表示

MIPS字段

  • op: operation code
  • rs: source register
  • rt: target register
  • rd: destionation register
  • shamt: shift amount
  • funct: function code
指令 格式 op rs rt rd shamt funct
共32位 register 6位 5位 5位 5位 5位 6位
add R 0 reg reg reg 0 32
sub R 0 reg reg reg 0 34

5位字段太小，用处不大，取常数也取不了多大范围；所以设计了I型指令，支持16位字段

指令 格式 op rs rt |-----address----|
共32位 Immeidate 6位 5位 5位 16位
addi I 8 reg reg 常数
lw I 35 reg reg 地址
sw I 43 reg reg 地址

大部分CPU只有16或32个寄存器，再增加，rs和rt字段都必须额外增加位，很难满足指令32位字长的要求。

将下面C语句编译成MIPS，并写出机器代码

A[300] = h + A[300];
---
lw $t0, 1200($t1) // 注意t1存的是A的基址，不能当做temp随意修改！
add $t0, $s2, $t0 
sw $t0, 1200($t1)

两个准则

  1. 指令用数的形式表示
  2. 和数据一样，程序存储在存储器中，并且可以读写
    这两个原则引出"stored-program"概念，释放了计算机的潜力。程序可以编译好放到存储器中，需要时再读取。

2.6 逻辑操作

Logical Operation MIPS Instructions
Shift Left Logical sll
Shift Right Logical sdl
And & and, andi
Or | or, ori
Not ~ nor

均为R型指令，Not通过nor 0（或非0）来实现

2.7 决策指令

branch if

i, k分别存放在$s3, $s5， save基址存放在$s6，编译下面的C语句

while (save[i] == k)
    i += 1;
---
Loop: sll $t1, $s3, 2 // 左移2，相当于i*4
add  $t1, $t1, $s6 // 下标*4与基址相加，得到save[i]
lw   $t0, 0($s6) // 取save[i]
// beq 与 bne，两条判断相等、不等的指令
bne  $t0, $s5, Exit // branch if not equal, jump to Exit
addi $s3, $s3, 1 // i++
   j Loop // jump to Loop
Exit:

可以看出对i不仅要做程序的加法处理，作为下标还要做*4处理。save[i]是通过每次加i的地址到&save[0]，再取数取出来的。

小于

检查数组下标是否越界

// set on less than (unsigned)
sltu $t0, $s1, $t2 // t0 = 0 if s1 >= t2(length) or s1 < 0
// 小于则为1，大于则为0
beq $t0, $zero, IndexOutOfBounds

用无符号数，正树正常比较，负数会被解释为一个很大的数，所以$t0会被置0，完成越界判断

case/switch语句

实际上被汇编转换成了if-then-else

2.8 过程

根据提供的参数执行一定任务的存储子程序
六个步骤：

  1. 参数放到可访问位置
  2. 控制权交给过程
  3. 获取过程所需存储空间
  4. 执行任务
  5. 结果放到调用程序可访问位置
  6. 返回控制权

MIPS过程调用硬件

  • $a0 - $a3 四个参数寄存器
  • $v0 ~ $v1 两个返回值寄存器（为什么是两个？返回值不是只有1个吗？）
  • $ra return address register

过程调用指令jal

jal ProcedureAddr // jump and link，把下条指令地址PC+4放到$ra

栈

在MIPS中，栈从高地址开始
栈指针寄存器为$sp，stack pointer

将下面的C语句编译成MIPS汇编代码

int leaf_example(int g, int h, int i, int j)
{
    int f;
    
    f = (g + h) - (i + j);
    return f;
}
---
leaf_example:
addi $sp, $sp, -12 // 分配地址，需要保存3个寄存器（看下面操作），-4*3
sw $t1, 8($sp) // 8~11
sw $t0, 4($sp)
sw $s0, 0($sp) // 从高地址到低地址压栈push
// 操作用到3个寄存器
add $t0, $a0, $a1
add $t1, $a2, $a3
add $s0, $t0, $t1
// return f
add $v0, $s0, $zero
// 释放栈空间，pop
lw $s0, 0($sp)
lw $t0, 4($sp)
lw $t1, 8($sp)
// 跳出函数，返回控制权
jr $ra

寄存器保存约定

$t0 ~ $t9 是10个临时寄存器，不一定要保存（使用t寄存器就默认使用者不指望保存）
$s0 ~ $s7 是8个保留寄存器，必须保存
上面的示例中，可以不保存t1、t0，节省步骤

嵌套

int factorial(int n)
{
    if (n < 1) return 1;
    else return (n * factorial(n - 1));
}
---
factorial:
addi $sp, $sp, -8 // 分配栈，push
sw $ra, 4($sp) // 保存地址
sw $a0, 0($sp) // 嵌套函数，需要保存调用时的参数

slti $t0, $a0, 1
beq $t0, $zero, L1 // if(n >= 1) L1

addi $v0, $zero, 1 // n < 1时执行
addi $sp, $sp, 8 // 释放，原来sw的寄存器没有变，所有不lw
jr $ra
// 递
L1: addi $a0, $a0, -1 // n - 1
    jal factorial
// 归
lw $a0, 0($sp) // 释放栈，pop
lw $ra, 4($sp)
addi $sp, $sp, 8
mul $v0, $a0, $v0 // 返回v = n * factorial(n - 1)
jr $ra // 跳出，返回控制权

帧指针与堆

帧指针

当存储局部数组或结构体时，这些局部变量无法放入寄存器（过大），就需要一个帧指针统一偏移量，保存变量到栈中。（函数多于四个参数时，多余参数也会存到栈中。
帧指针不是必须的，它方便了统一偏移量；有的编译器将$fp用作$s8。

堆

动态数据类型，例如指针，存放在堆里。
在C中，malloc()即申请堆空间，free()即释放堆空间。忘记释放就会占满内存导致泄漏！提前释放就会导致指针指向错误的位置。在Java，有自动的内存分配和无用单元回收避免泄漏和错误指向。

在内存中，从低地址往高地址依次是保留空间、代码段、静态变量段，然后是从低到高的堆空间和从高到低的栈空间。堆与栈相互增长，最大化利用空间。

内存空间
栈↓
（空间）
堆↑
静态数据（常量）
代码段
保留

2.9 取字节（8bit）或更高位（32bit）数

C使用ASCII码表示字符，每个ASCII码是8bit；Java使用Unicode，每个Unicode是16bit。因此寄存器也有lb (load byte)、lh (load halfword)、lhu指令

字符串的表示

三种选择

  1. 保留第一个位置给出字符串长度（Java）
  2. 附加一个带有字符串长度的变量（结构体）
  3. 字符串结尾设置一个字符标识（C, ‘\0’)
    注意，读取字符串的每个字符时，str[i]不需要每次把i*4。

2.10 指令拓展

2.10.1 32bit立即数

把32bit常量加载到寄存器

32bit constant:
0000 0000 0011 1101 0000 1001 0000 0000
---
lui $t0, 61 // load upper immediate
---
001111 00000 01000  0000_0000_0011_1101 // MIPS指令
0000_0000_0011_1101 0000_0000_0000_0000 // $t0, 把61拷贝到高16bit
---
ori $t0, $t0, 2304 // or immediate
---
0000_0000_0011_1101 0000_1001_0000_0000 // 把2304拷贝到低16bit

2.10.2 寻址模式

J型指令除了6位操作码，其余位都是地址字段：

操作码 操作数
6位 26位

bne条件分支指令：

操作码 操作数1 操作数2 地址
6位 5位 5位 16位

如果地址只有16位就太小了，所以PC=寄存器+分支地址，地址成为了求和，变成了32位。

PC相对寻址

实际上，MIPS寻址是对于下一条指令（而不是当前指令），这个设计加速了大概率事件。

// 2.7.1的while循环，i存在$s3，k存在$s5，save[0]基址存在$s6
while (save[i] == k)
    i += 1;
---
Loop: sll  $t1, $s3, 2 // i * 4
add  $t1, $t1, $s6 // 加地址，save[i*4]
lw   $t0, 0($t1)
bne  $t0, $s5, Exit
addi $s3, $s3, 1
j    Loop
Exit:
---
// Q: 把Loop存在80_000，MIPS代码是什么？
// Loop:
80000: |0 |0 |19|9 |2 |0 | // sll
80004: |0 |9 |22|9 |0 |32| // add
80008: |35|9 |8 |   0    | // lw
// 注意：
80012: |5 |8 |21|2(8Byte)| // bne，MIPS用字寻址，1word = 4Byte
// 8 + 80016，实际上16位存的是偏移量，利用下一跳地址来寻址
80016: |8 |19|19|   1    | // addi
80020: |2 |     20000    | // j，完整的2000word*4 Byte
80024: ... // Exit

长跳转寻址

对于距离远的跳转，bne的16位地址不够用，可以间接利用j来跳更远距离。

bne $s0, $s1, L2
j   L1
L2:

寻址模式总结

  1. 立即数寻址
  2. 寄存器寻址
  3. 基址寻址
  4. PC相对寻址：bne指令用的方法
  5. 伪直接寻址：J型指令用的方法

Q：MIPS中，条件分支beq指令的地址范围多大？（K = 1024）
A：beq指令地址前后±128K，beq使用相对PC寻址，相对寻址有1个符号位，PC相对寻址模式把16位地址左移2位与PC相加，±215∗22\pm2^{15} * 2^2。

Q：MIPS中，跳转和跳转链接j、jal指令的地址范围多大？（M = 1024K）
A：256M任意地址，J型指令使用伪直接寻址，26位地址左移2位与PC高4位相连，226∗222^{26} * 2^2。

2.11 同步

计算机进行数据操作必须要知道能不能目标地址读写，也就是任务之间需要同步sync，否则就会竞争race。同步使用lock和unlock操作。

lock基本原理

实际上就是用0表示解锁，1表示加锁，把锁的值和对应的寄存器交换就可以了。lock操作是在硬件层面实现的，不在硬件层实现会很麻烦。
两条指令：load linked、store conditional

again:
addi $t0, $zero, 1 // 加上锁的值，1表示加锁
ll   $t1, 0($s1) // 取寄存器s1的值
sc   $t0, 0($s1) // 给s1加锁
beq  $t0, $zero, again // 如果是0（解锁状态），加锁失败，就重试
add  $s4, $zero, $t1 // 把取来的值加载到寄存器s4上操作
...

实际上，不仅仅是多处理需要这样的lock操作；单处理器也需要lock来保证程序运行独立不受干扰、保证写入无错、指令执行成功。

2.12 从语言到可执行程序

C语言

系统 源文件 汇编文件 目标文件 静态链接库 动态链接库 可执行文件
UNIX .c .s .o .a .so .out / no suffix
MS-DOS .C .ASM .OBJ .LIB .DLL .EXE

1. 编译

编译器把高级语言转换成汇编语言

2. 汇编

汇编器把汇编语言汇编成机器代码，生成obj file，包括了机器语言指令、数据和指令正确放入内存所需的信息。
汇编语言有硬件层没有实现的伪指令，如move dest, tar移动，实际上在硬件层是add dest, 0, tar
MIPS汇编器使用16进制Hex
为了把汇编语言转换成二进制，有一个符号表。表由标号、地址对构成

3. 链接

链接器把独立汇编的机器语言程序拼接到一起，生成可执行文件。链接器做到拼接操作，使程序每次只需要重新编译和汇编一部分代码。修补代码比重新编译和汇编快得多（ccache）。
工作步骤：

  1. 将代码、数据块象征性地放入内存
  2. 决定数据、指令标签的地址
  3. 修补内部、外部引用
    也就是它寻找旧地址并用新地址取代它们。

4. 加载

工作步骤：

  1. 读取exe文件头，确定代码段、数据段大小
  2. 为内容、数据创建足够的地址空间
  3. 将exe中的指令、数据复制到内存
  4. 主程序参数复制到栈顶
  5. 初始化寄存器，栈指针指向第一个空位置
  6. 跳转到启动例程，把参数复制到寄存器，调用main()；并在return 0后调用exit终止程序

动态链接库 DLL

传统的链接静态链接库的方法很快。但是静态链接库有更新问题，并且库可能很大，静态库需要全部装载到程序。
而动态链接库，只有程序运行的时候才链接和加载例程。（第一次调用库例程会把整个库走一遍，以后会按需调用）
DLL需要额外空间存储动态链接库信息，但是不需要复制或链接整个库。

JAVA

编译与解释

编译依赖特定指令集，而Java是为了兼容性而发明的。
Java程序被编译成Java字节码，经过JVM虚拟机解释字节码运行。
解释的优势是可移植性，也导致了它更慢、性能较差。
现代的方法是使用即时编译器（Just In Time complier），编译过的部分保存起来，下次运行直接调用，这样每次运行都会更快。在今天，实际上Java与C的性能差距越来越小了。

思考：“缓存”的概念真的很伟大，在计算机的世界中几乎无处不在。

2.13 一个完整程序示例

void swap(int v[], int k)
{
    int temp; // 交换相邻项
    temp = v[k];
    v[k] = v[k+1];
    v[k+1] = temp;
}

void sort(int v[], int n)
{
    int i, j;
    for(i = 0; i < n; i += 1) {
        for (j = i - 1; j >= 0 && v[j] > v[j+1]; j -= 1) {
            swap(v, j); // 数组后项比前项大，则交换相邻项
        }
    }
}
---
swap:
sll $t1, $a1, 2
add $t1, $a0, $t1 // 取址
// 取数
lw $t0, 0($t1) 
lw $t2, 4($t1)
// 交换
sw $t2, 0($t1) 
sw $t0, 4($t1)

sort:
addi $sp, $sp, -20 // 分配栈空间，并保存寄存器值
sw   $ra, 16($sp)
sw   $s3, 12($sp)
sw   $s2,  8($sp)
sw   $s1,  4($sp)
sw   $s0,  0($sp)

move $s2, $a0 // 复制参数到寄存器, int v[]
move $s3, $a1 // int n

move $s0, $zero // 循环初始化i = 0
for1tst:
slt  $t0, $s0, $s3 // i < n ?
beq  $t0, $zero, exit1 // i > n => exit1，跳出循环

addi $s1, $s0, -1 // j = i-1
for2tst:
slti $t0, $s1, 0 // j < 0 ?
bne  $t0, $zero, exit2 // j < 0 => exit2
sll  $t1, $s1, 2
add  $t2, $s2, $t1 // 得到v[j],v[j+1]
lw   $t3, 0($t2)
lw   $t4, 4($t2)
slt  $t0, $t4, $t3 // v[j+1] < v[j] ?
beq  $t0, $zero, exit2 // v[j+1] > v[j]，从小到大 => exit2

move $a0, $s2 // int v[]
move $a1, $s1 // int j
jal  swap

addi $s1, $s1, -1 // j--
j    for2tst // 下一轮循环

exit2:
addi $s0, $s0, -1
j    for1tst

exit1:
lw   $s0, 0($sp)
lw   $s1, 4($sp)
lw   $s2, 8($sp)
lw   $s3, 12($sp)
lw   $ra, 16($sp)
addi $sp, $sp, 20

j    $ra

上面的程序，不适用jal swap，直接把swap复制到程序里，叫做内联程序，可以省掉指令。
然而，如果内联程序在多个地方调用，代码复用率会降低，有可能导致cache不命中，从而性能下降。

执行时间是衡量程序性能的唯一指标，不是代码量，也不是CPI

MIPS的编译器总是会-16来保存四个参数寄存器，不管有没有这么多参数。

2.13 数组和指针

在硬件中，指针*p++会智能地增加地址长度(+4而不是1)
数组必须要做下标*4，再加上首地址，指针不需要。
然而，现代编译器会优化数组的代码；所以，为了写出可读的程序，放心用数组吧！

2.14 编译/解释高级语言

面向对象语言：针对对象而不是过程；针对数据而不是逻辑

2.15 其他指令集

ARMv7

  • 有更多（9种）寻址模式，没有专门寄存器保存0
  • 有4位条件码决定分支是否执行
  • 每一条代码有可选执行条件（占用代码空间少，节省运行时间）
  • 解释12位立即数字段的方式很新颖：低8位填0，变成32位，然后循环右移，由此可以用32位字的范围表示所有2的幂次

x86

  • ARM和MIPS是单独的小组在1985年推出的；x86是很多个互相独立小组开发的，并且持续改进了35+年。
  • 兼容性是一个“金手铐”
  • x86要求算术、逻辑运算中一个操作数必须又是源操作数，又是目的操作数（Dest = Dest + Source）
  • x86的操作数可以存在存储器里

ARMv8

  • ARMv8更像MIPS
  • 为了使寄存器加宽为64位，做了完全的改进（与x86只做了很小改进）
  • PC不再是寄存器
  • 有一个zero寄存器，32个通用寄存器

2.19 谬误与陷阱

  • x86很强大，可以循环执行某条指令。然而，这导致了额外的性能开销。代码复制比循环快1.5倍；用更大的浮点寄存器，比用x86整数寄存器，复制操作比复杂指令快2倍
  • C语言有register，把变量存在寄存器；但是编译器能比程序员更好地分配寄存器
  • 一旦代码写好，下一个危险是它变成一个流行的程序

Chapter3 计算机的算术运算

3.1 引言

  • 计算机小数和其他实数如何表示？
  • 操作生成了一个无法表示的大数该怎样处理？
  • 硬件的乘除法是怎样的？

3.2 加减法

用加法表示减法，取反相加
用补码表示整数，好处是符合硬件的特征（溢出容易判断）
加法，只有符号相同才会溢出，异号相加最多变成全2；减法是反过来。

在做减法时，
如果用一个正数减去一个负数得到一个负的结果，
或者用一个负数减去一个正数然后得到一个正的结果，
则发生了溢出 。

无符号数可以忽略溢出，因为无符号一般表示地址

溢出时产生异常，也称为中断，交给操作系统处理。
遇到异常，会跳到预设好的指令异常处理程序的地址。有EPC（Exception Program Counter，异常PC）来存储异常发生的地址，方便后序跳转。
EPC有一个问题：跳转到中断的位置，先恢复寄存器，EPC的值就没了；恢复寄存器同时保留EPC，那么有一个寄存器的值就没了。
针对这个问题，MIPS使用$k1、$k0两个异常时不会恢复的寄存器。异常处理程序会把返回地址放在其中一个寄存器里面。
小测验：MIPS对字节和半字用lb、lh，sw、sh指令，但是算术运算就是用普通的add。MIPS没有针对半字的运算。

饱和：溢出后，设置数值为最大数或最小数。例如，收音机，不断调大音量后，如果采用没有溢出的那几位，会发生：最大音量突然变小声的情况。
MIPS没有检测溢出的条件分支。只能用一系列指令实现。

更快的加法：使用超前进位加法器（carry lookahead）

3.3 乘法

乘法就是复制：

  1. 当乘数为1，把被乘数复制到合适位置
  2. 当乘数为0，填0
    乘法经常要处理溢出，因为总是有32位×32位的情况
    编译器使用移位来优化乘法

有符号的乘法：记住符号位，转为正数相乘；单独处理符号
更快的乘法：并行加法运算，无需等待

3.4 除法

除法和乘法差不多，但是计算机只能一位一位尝试做减法来运算。
除法：得到商和余数

有符号的除法：使用 被除数 = 商 x 除数 + 余数 这个公式来处理符号
更快的除法：使用SRT算法，通过查找表来猜测商。还有一种算法，商为负数时，不要马上加回去，而是依照另一个等式来继续运算。

MIPS的硬件既可以做乘法，又可以做除法，Hi存放余数、Lo存放商

3.5 浮点数

3.5.1 浮点数表示

单精度 1 8 23
func sign Exp Frac
双精度 1 11 52(20+32)
func sign Exp Frac

Bias 偏阶

为了让最小的负指数表示为全0，最大的正指数表示为全1。浮点数使用Biased Notion
(−1)sign×(1+Fraction)×2Exponent+Bias(-1)^{sign} \times (1 + Fraction) \times 2^{Exponent + Bias}
IEEE 754使用127作为单精度Bias，即指数为-1，表示为126 0111 1110B；指数为1，表示为1000 0000B，正指数看起来比负指数大。

十进制数转浮点

  • -0.75如何用浮点数表示？
    −0.75=−3/4=−3/22=−112/22=−1.1×2−1-0.75 = -3/4 = \mathbf{-3/2^2} = -11_2/2^2 = -1.1 \times 2^{-1}
    套公式，-1+127=126
sign Biased Exponent Fraction
1 0111 1110 1000 0000 0000 0000 0000 000

技巧：表示成“除以2的次方”的形式

sign Biased Exponent Fraction
1 1000 0001 0100 0000 0000 0000 0000 000
套公式，129-127=2
(−1)×(1+0.25)×22=−5(-1) \times (1 + 0.25) \times 2^2 = -5

3.5.2 浮点数加法

flowchart TD
    start(开始)
    step1[1. 比较两个数的指数；将指数小的数右移，直到指数匹配]
    step2[2. 尾数相加]
    step3[3. 结果规格化]
    jdg1{"上溢、下溢？"}
    err(异常)
    step4[4. 尾数舍入，保留适当位数]
    jdg2{"是否为规格化数？"}
    ed(结束)

    start --> step1 --> step2 --> step3 --> jdg1 
    
    jdg1 -- N --> step4 --> jdg2
    jdg2 -- Y --> ed
    jdg2 -- N --> step3
    
    jdg1 -- Y --> err

3.5.3 浮点数乘法

flowchart TD
    start(开始)
    stp1[1. 指数相加，加上偏阶值得到新的Bias Exponent]
    stp2[2. 尾数相乘]
    stp3[3. 规格化乘积；乘积右移，指数增大]
    jdg1{上溢或下溢？}
    err(异常)
    stp4[4. 尾数舍入]
    jdg2{是否仍为规格化数？}
    stp6[6. 符号相同正，符号相异负]
    ed(结束)

    start --> stp1 --> stp2 --> stp3 --> jdg1 -->|N| stp4
    jdg1 -->|Y| err
    
    stp4 --> jdg2 -->|Y| stp6 --> ed
    jdg2 -->|N| stp3

3.5.4 MIPS 浮点指令

lwc1 (Load Word into Coprocessor1)：取浮点
swc1：存浮点
Coprocessor：80年代的晶体管没办法把浮点运算和整数运算的单元放在同一个芯片上，所以有了协同处理器。

add.s/add.d：单、双精度浮点运算
双精度如何储存？用$f2 $f3一对浮点寄存器，用偶数作为名字
实际上，为了避免浮点运算，编译器会把程序中的浮点运算的结果直接存到内存里。

float f2c(float fahr) 
{
    return ((5.0 / 9.0) * (fahr - 32.0));
    // 5.0 / 9.0 直接存入内存
}

3.5.5 算术精确问题

在IEEE 753中，中间计算会保留多2位，称为保护位和舍入位，根据这两位来舍入，提升精确度。
衡量精确度：尾数最低位ulp (unit in the last place) 这个术语可以衡量精确度。IEEE 754保证浮点运算在半个ulp以内

3.9 谬误与陷阱

  1. 右移指令无法代替2次幂相除！
// -5
1111 1111 1111 1111 1111 1111 1111 1011B 
// -5 >> 2 = -2，而答案是-1
1111 1111 1111 1111 1111 1111 1111 1110B

  1. 浮点加法不能使用结合律！舍入会毁掉一切。
  2. 对于浮点运算，顺序执行正常的程序，不一定能正常并行执行。同样是精度问题，会导致每次输出不同结果。