计组复习

我在大二下选修了计算机组成原理，这篇blog用来梳理相关知识点

前言

一些学习计算机组成原理之前应该知道的知识…

1. 计算机结构：系统程序员所能见到的硬件特性，指的是计算机的逻辑结构
2. 计算机组成：计算机硬件的具体实现，指的是计算的物理结构
3. 两类汇编语言，RISC & CISC，对应精简与复杂的指令系统，MIPS属于RISC的一种
4. 计算机组成原理涉及：汇编，处理器、内存、IO三者对应的逻辑系统与硬件实现（数据通路），课程定位在整个计算机系统中处于硬件方面的数字电路之上，软件层面的操作系统之内（因为上到汇编），但在编译器之下（编译器同样属于OS的范畴）
5. 核心内容：CPU Organization(data path & controller), Caches
6. 重点内容：MIPS汇编，Virtual Memory
7. 了解内容：I/O, Bus

最后请谨记，该门课特点是概念抽象、繁琐…但是“清澈见底”，只要想弄清楚，一定可以！

指令系统

指令系统设计

这一部分主要是一些有关指令系统设计的知识点

于是，首先看看这三个知识点：

1. 指令：二进制的机器语言
2. 汇编指令：助记符，每种条符号语句都映射到一条二进制的机器代码
3. ISA：指令系统（指令集体系结构），软硬件交汇的地方

接下来，一条指令应该包含以下信息：

1. 操作码（定长 or 变长）
2. 源操作数参照（from where）
3. 目的位置参照（to where）
4. 下一条指令地址（what to do next?）

按地址数的指令分类：

零、一、二、三、多地址指令，其中二三是典型的RISC风格。三的特点是显示指定了dst，一或二的dst是隐含的（built-in or src）

指令执行的阶段：

取指令->译码->取操作数->运算（执行）->存放结果->取下一条指令
不一定所有指令都涉及所有步骤，但是考虑的时候应该按最复杂的来，何尝不是一种设计原则？

指令设计基本原则：
完备性，兼容性，均匀性，可扩展性
应当明白词语背后的含义

最简单的完备指令系统：
load, store, inc, brn

操作数类型

…

寻址方式

…

扩展操作码编码

这是涉及关于如何给操作码编码，以及对应数量关系的问题。
核心思想是一种数字状态，一个编码

涉及到的相关信息有：

1. 指令字长，例如16位、32位…
2. 地址长度，如6位…
3. 操作码长度，通常不同地址数量的编码不同
4. 不同地址数的指令的条数

通常会已知1、2，4中某些地址数的指令条数，求剩余一种地址数的指令最多的条数。

关键点是：

1. 明确已知的某些地址数的指令条数——剩下的一种地址数的指令条数一定存在函数关系
2. 从多地址数的指令开始考虑，考虑它的操作码有多少位，可求得这种指令至多有多少条
3. 利用“已知”的实际条数与至多有多少条，可以求得这种指令的剩余状态数量
4. 考虑减少一条地址的指令，对应操作码有多少位，记得计算操作码长度的时候，不仅是指令字长减去地址长度，还要减去上种指令操作码所用长度
5. 求得这种指令至多有多少条，利用剩余状态×操作码长度
6. 显然这个过程可以反复进行，由地址数量最多的情况，如3个地址码，到最少的情况，如零地址码
   最后，不一定所有的状态都有使用…

指令设计的风格

尤其关注RISC的风格。

RISC是load/store型指令系统，特点是只有load、store命令才能访问存储器，其它运算类的指令通通不能访问存储器
（值得注意的是这种指令系统，属于通用寄存器型指令系统的子集，特点是使用通用寄存器存放临时数据，而不使用累加器）

RISC的特点是：

1. 指令数目少
2. 指令格式规整
3. Load/store风格
4. 采用流水线的指令执行方式
5. 采用大量通用寄存器
6. 采用硬连线控制器
7. 采用优化的编译器

异常与中断

…

程序的机器级表示（MIPS指令系统）

这一部分是重点知识，所以会有多级的副标题。请着重掌握！

MIPS有关的基础知识

一些零碎的知识点，不好纳入后面的各级标题之中，于是集中在此...
或者说并非无法纳入，而是比较重要...单拎出来也方便记忆

1. MIPS指令长度都是32位
2. MIPS中设计了32个通用寄存器
3. MIPS使用大端的存储方式
4. MIPS设计的存储器按照字节编址，1Byte对应一个存储单元，有自己的专属地址
5. MIPS中人为修改pc的指令，如j、beq等，在机器级存储的转移值是相对转移的指令的条数（即应该修改pc的相对量除以4后的值）

MIPS指令的机器级表示

MIPS中指令格式包括R型、I型、J型。

1.R型指令

机器级表示:
op6+rs5+rt5+rd5+shamt5+func5

1. op是操作码，对于R型来说全是0
2. shamt是用于处理移位操作的
3. func是用于区分操作码的
4. rs, rt为源寄存器1、2
5. rd为目的寄存器

注意，R型指令助记符表示的时候，实际上是 op rd rs rt的顺序，要和机器级位置区分开
不妨考虑一下，op全为0的好处是什么

2.I型指令

机器级表示：
op6+rs5+rt5+imm16

1. 常用I型指令：双目运算，rs与imm运算，送至rt，例如addi $2,$1,imm
2. 常用I型指令，load、store，采用的MIPS采用基址+相对位移量的访存方式，例如lw $2,100($1)
3. 常用I型指令，beq、bne，条件分支，例如beq $1,$2,L
4. imm是16位，但是与其运算的寄存器rs是32位的，需要进行扩展，扩展的规则如下：
   ①用于进行双目运算的时候，i是符号扩展imm，iu是零扩展imm
   ②用于load、store的时候，imm总是符号扩展，虽然有u的存在，例如lhu, lbu等，但是这里的u对应的用于0扩展不足32位的存储内容，从而加载到寄存器
   ③用于条件分支的时候，beq、bne应该与slt搭配使用，所以imm通常只与1、0进行相等与否的比较，于是也不存在什么扩展与否的问题
   注意，实际上slt也可以是I型的，并且很常用，但是也有R型的

3.J型指令

机器级表示：
op6+target address26

1. 实际的目的地址计算方式，pc高4位:target address:00
   最后总是00的原因，在于MIPS中指令总是32位的，从0地址开始访存：0,100,1000,1100…（0、4、8、12…），末尾总是00，这个特点在后面设计用于MIPS的CPU的时候也非常有用
2. 显然，这是一种局部寻址的方式

MIPS设计的通用寄存器

MIPS使用32个通用寄存器，我们应该掌握以下有关的知识。

1.两种助记符号的使用

1. 编号：”$”+“数字：0~31”
2. 名称

程序中一般都使用名称，举例子的时候使用编号多一些。或许，前者体现“助记”，后者体现“通用”

2.经常使用的寄存器

1. zero
   编号为0，其功能是提供0值，寄存器中始终是全0
2. v0-v1
   编号2-3，功能是存放过程调用的返回值
3. a0-a3
   编号4-7，功能是存放过程调用的参数
4. t0-t7
   编号8-15，功能是存放临时使用的变量
5. s0-s7
   编号16-23 被调用者保存的寄存器
6. t8-t9
   编号24-25，功能是存放临时使用的变量
7. sp, fp, ra
   编号29-31，功能是，栈指针（栈顶），帧指针（栈底），存放调用过程返回地址

记忆的方法，“一个过程调用，使用了4个参数a，返回了两个值v，调用者保存了8个寄存器s，被调用者保存了10个寄存器t，关键在于sp、fp与ra”+zero

3.了解的寄存器

1. at
   编号为1，保留给编译器使用
2. k0-k1
   编号为26-27，保留给系统使用
3. gp
   编号为28，全局指针

MIPS汇编指令

在开始做这一部分的笔记之前，我思考了一个问题——如何才能更好的记忆MIPS汇编指令。我得出的答案是，一般性规律的记忆+特殊性个例的记忆。对于一般性规律的记忆，其规律包括：指令的助记符+什么类型的指令+指令的特性，前两者可以帮助我们正确地写出指令，后者可以帮助我们正确地理解指令。对于特殊性个例，我们不妨记住全部。在记忆的过程中带着这个思想，或许会容易记忆一些。

我们接下来按照指令的类别进行。

1.算术类指令

1. 算术运算包括，加、减、乘、除
   对应的基本助记符是add、sub、mult、div
2. 加、减有I型和R型，使用I型的时候，如addi、subi
3. 加、减默认会判断溢出，也有不判断溢出，对应u扩展（undo），如addu、subu
   当然也有addiu、subiu
4. 乘、除比较特殊，仅有R型，但是是双目操作符，因为结果存放在默认寄存器hi，lo（乘法hi，lo分别为高低32位，除法hi为32位余数，lo为32位商）
5. 乘、除分有符号数和无符号数，对应为u扩展（unsigned），如multu、divu
   注意区分unsigned和undo

一般性的规律是，助记符：加、减有I、R型，乘、除只有R型

2.存储访问

存储访问，按照访存字节，分为按字（word，MIPS中是32位），按半字（half word，16位），按字节（byte，8位）访问

以及MIPS最有特色的指令lui

1. lw、sw，按字访问lw/sw $1 100($2)，sw是MIPS中唯一一个dst在src之后的指令
2. lhu、lbu，按半字、字节加载，16位内存到32位存储器涉及扩展，格式与lw、sw相同，内存中数据是按无符号扩展
   注意，必须加u，这就意味着使用半字或字节的时候，内存中内容只能按字节扩展到寄存器
   但是imm的扩展只能是符号扩展，没有undo的选择
3. sh、sb，按半字、字节存储，格式与lw、sw相同，由于是寄存器到存储器，不用考虑扩展。
   sh、sb同样的只要是访存，imm都是按符号扩展
4. lui，I型，使用方法，lui rs,imm，将16位imm放置在rs的高16位
   这是一个很能体现MIPS特色的指令，如果程序员，按照自己的想象（这个数字并不存在于任何其它的位置），想要将一个32位的数字放置在寄存器中，就可以按照16位、16位的存放。可以先lui，再addi
   按照自己的想象是很重要的一点！这将lui和lw、lhu、lbu区分开来，因为lui根本没有访存！

一般性的规律是，助记符；访存都是I型

3.逻辑运算

MIPS中常用的逻辑运算是与、或、异或

1. 与，and，有R型、I型，I型对应i扩展，如addi rd,rs,rt
2. 或，or，同与
3. 异或，xor，同与

一般性的规律是，助记符，逻辑运算有R型、I型

4.移位操作

MIPS中的涉及的移位操作有，逻辑左、右移动，算术右移

1. 逻辑左移，sll，I型，如sll rt,rs,imm
2. 逻辑右移，srl，同上
3. 算术右移，sra，同上
   注意，表示是逻辑还是算术的l和a，放在最后

一般性的规律是，助记符，移位只有I型

5.条件分支

MIPS中涉及的条件分支，常用的是，slt、beq、bne

1. slt，有R型、I型，如slt rt,rs,imm
   注意slt的I型，不使用i扩展！
2. beq，I型，如beq rs,rt,L
   实际编程中L的位置，通常写label，进一步的处理或许是交给汇编器进行的…
3. bne，同beq

一般性的规律是，助记符，slt有R型，其它都是I型

6.无条件跳转指令

MIPS中的跳转指令常用的是j、jr、jal

1. j，J型指令，如j L（实际使用L是label）
2. jr，J型指令，地址存放在Register中，如j rd
3. jal，J型指令，注意这个指令有两个操作，一个如普通的j一般跳转到L，另一个是$ra = PC + 4（存放返回地址，所以这个指令常用于过程调用）

一般性的规律是，助记符，都是J型

MIPS汇编代码

这一小节主要是掌握MIPS汇编代码的编写的常见结构，包括分支结构、循环结构、还有过程调用

1.分支结构

分支结构主要有如下两种：

1. if(i == j) or if(i != j)这种等或不等，主要使用bne,beq进行
2. if(i < j)这种大于小于的关系，主要使用slt与bne,beq进行

下面是两个例子
eg1

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

$s1<-i $s2<-j $s3<-f $s4<-g $s5<-h

start: bne $s1,$s2,else
       add $s3,$s4,$s5
       j exit
else:  sub $s3,$s4,$s5
exit:  ...

2.循环结构

这里以while循环为例
eg

while(i != k){
    x = x + a[i];
    i = i + 1;
}

$s1<-x $s2<-i $s3<-k $s5<-a

loop: beq $2,$3,exit
      sll $s7,$s2,2 #注意这行，不能直接将i <<= 2 （Bits -> Byte）
      add $s7,$s5,$s7
      lw $s6,0($7)
      add $s1,$s1,$s6
      addi $s2,$2,1 #注意这行，i = i+1（Bits）
      j loop
exit: ...

注意，将偏移i换算为地址的时候要乘4，换算成对应按字节编址的情况

3.过程调用

首先我们应该清楚整个过程调用的执行过程：

1. P保存相应的寄存器（$t）
2. P将参数放置于Q可以访问的位置（$a）
3. P将返回位置保存，从而让Q可以执行返回（$ra）
4. P修改栈帧（$sp $fp）切换到Q的栈帧
5. Q将P的相关寄存器进行保存（$s、$ra、$fp）
6. Q为自己的局部变量分配栈帧空间
7. 执行Q的过程
8. 返回P（使用P最开始保存的$ra，或者是Q自己保存的$ra）

注意，以上是以最严格、完整的过程来叙述的，实际上都是根据需要来进行。于是可以做以下几点说明：

1. P是根据需要保存$t的，如果可以确保之后不再使用，不保存也行，对应了Q可以随意使用$t
2. 如果参数多于4个，$a不够用了，需要将参数放到相应的栈帧中（如果必要的话$a也可以与$t类似，由P保存）
3. $ra的保存实际上是用jal来隐式执行的
4. 在MIPS中$fp,$sp不一定都要修改，通常是只修改$sp，然后以其作为参考即可，当$fp需要修改的时候，$fp = $sp + 栈帧空间大小
5. Q也是根据需要保存，如果要使用$s的话必须保存，如果自己还要进行过程调用（会修改$ra、$fp，那么也应该自行保存）
6. 由于MIPS通用寄存器非常多，$t就多达10个，通常不需要将局部变量分配到栈帧中，直接使用寄存器即可
7. …
8. 返回时总是使用$ra，如果Q中间执行了过程调用修改了$ra，当Q的调用返回时，应该根据Q保存的P的$ra值，将$ra进行还原；并且需要先释放Q的栈帧空间，通常可以使用$sp = $fp（如果开始时修改了$fp，同样嵌套调用时若Q修改了$fp，在Q的调用结束时要先将$fp还原，就像$ra一样），或$sp = $sp - 栈帧空间，来释放Q的栈帧；最后使用jr $ra返回P的执行。

以上几点说明都是针对最开始描述的每一点过程进行的

下面还有一些需要补充的点

Ⅰ MIPS中栈帧是由高地址到低地址，这意味着分配栈帧空间对$sp执行的是减法操作

eg:在栈帧中分配空间，保存$ra,$a0

subi $sp,$sp,8
sw $a0,4($sp)
sw $ra,0($sp)

Ⅱ 一般只有在由数组或结构体等占用空间较大的复杂数据结构的时候才需要使用栈帧分配局部变量（$t不够用）

Ⅲ Q没有进一步嵌套调用其它函数的情况，Q被称为叶子过程。一般的叶子过程通常在MIPS中甚至不需要开辟栈帧，因为有足够多的通用寄存器

Ⅳ 如果$fp不使用（建立当前函数的栈帧时并没有维护$fp），可以将$fp作为$s8来使用