计算机组成

chapter2 instructions:language of the computer

2.1 introduction

2.2 operations of computer hardware

算术

ex

1
2
3
4
5

f=(h+g)-(i+j);
Risc-v code:
add t0,g,h
add t1,i,j
sub f,t0,t1

2.3 operands of computer hardware

• 64-bit data call doubleword

• 32-bit data call word

• Risc-v 有32个64位寄存器

• Risc-V 是小端模式（小端模式下，数据的低位存储在低地址，高位在高地址；而大端模式则相反，高位存储在低地址。在读取数据时，无论哪种模式，都是从低地址开始）即这个word的第0个byte放在最低的位置（least address of a word）

• Risc-V 不需要aligned

• 下面举一个memory的Risc-V编译例子

解释：ld和sd是对memory的指令，其中的数字代表对应的地址。

register和memory

• Registers are faster to access than memory
• 进行操作时将memory load到register或者被store
• Compiler must use registers for variables as
  much as possible

make common case fast

• 对于常见的命令，例如immeidate add，当我们把它们变作一个命令以后，就舍去了load操作，大大提升了编译时间。

2.4 有符号数和无符号数

2.5 representing instructions in the computer

• 指令在计算机中的表示方法（如下例）

这个表示方法就是RISC-V R-Format：
funct7(7 bits) rs2(5 bits) rs1(5 bits) funct3(3 bits) rd(5 bits) opcode(7 bits)

但是有些指令的相关寄存器只有两个（Risc-V I-Format Instructions）
immediate

encoding

format

• 解释：sb指令与UJ指令的immed的特殊位置排序的原因：功能不同并且尽可能多地位数相互对应。

2.6 logical operations

shift operations

• I-format 但是immediate只有六位（因为能够最多表示移63位已经满足所有情况

若是logical对应的immediate操作

• 因为我们的寄存器处理的数据为64位，但是immeidate为12位，所以对immediate作有符号数扩展

2.7 instructions for making decisions

branch

• branch instructions
  beq register1,register2,L1（若==则执行）
  bne register1,register2,L2(若!=则执行)

loop

• 解释：首先进行读取，因为是double word所以每次的地址都是i乘上8，所以在开头进行移位操作(解释一下A[i]的地址占据应该为[8i+7:8i])。再加上最初的A[0]地址算出A[i]地址，利用地址进行load操作（需要注意在这里因为已经是A[i]的地址所以我们load前面的immediate操作数为0），接着进入判断条件，若满足进入循环。

most popular compare operand

• slt
  If the first reg. is less than second reg. then sets third reg to 1
  slt x5,x19,x20(x5=1 if x19 < x20)

• more conditional operations
  blt rs1, rs2, L1
  if (rs1 < rs2) branch to instruction labeled L1
  bge rs1, rs2, L1
  if (rs1 >= rs2) branch to instruction labeled L1

• signed and unsigned
  Signed comparison: blt, bge
  Unsigned comparison: bltu, bgeu

jump register

• jalr
  jalr rd,imm(rs1)
  解释：rd是要保存返回地址的目标寄存器。
  rs1是包含要跳转到的地址的源寄存器。
  imm是一个偏移量，用于相对于rs1寄存器的计算（可选字段）。

2.8 supporting procedures in computer hardware

procedure call instruction

instructions of procedure

• jal x1,procedureaddress(UJ)
  跳转到绝对的地址，同时将返回地址（PC+4）保存到寄存器
  Address of following instruction put in x1
  Jumps to target address

procedure return

• jalr x0,0(x1)(I)
  跳转到一个寄存器中指定的地址，同时将返回地址保存到寄存器
  Like jal, but jumps to 0 + address in x1
  Use x0 as rd (x0 cannot be changed)
  Can also be used for computed jumps

Using more registers

• 在后面的RISC-V规定中会提及：

• 通常题目会说堆栈的指针要在16的倍数上对齐，意味着我们每次操作都至少要将sp移动16个字节。

• 采用堆栈操作
  push:sp=sp-8
  pop:sp=sp+8

• example

• sp在压栈前应该指向最后一个word（而不是下一个空的word(课堂上大家最终达成了共识)）

RISC-V规定

1. x0为常数0，这个一定要切记
2. x5 - x7 以及 x28 - x31 是 temp reg，如果需要的话 caller 保存；也就是说，不保证在经过过程调用之后这些寄存器的值不变。
3. x8 - x9 和 x18 - x27 是 saved reg，callee 需要保证调用前后这些寄存器的值不变；也就是说，如果 callee 要用到这些寄存器，必须保存一份，返回前恢复。
4. x10 - x17 是 8 个参数寄存器，函数调用的前 8 个参数会放在这些寄存器中；如果参数超过 8 个的话就需要放到栈上（放在 fp 上方， fp + 8 是第 9 个参数， fp + 16 的第 10 个，以此类推）。同时，过程的结果也会放到这些寄存器中（当然，对于 C 语言这种只能有一个返回值的语言，可能只会用到 x10 ）。
5. x1 用来保存返回地址，所以也叫 ra 。因此，伪指令 ret 其实就是 jalr x0, 0(x1) 。
6. 栈指针是 x2 ，也叫 sp ；始终指向 栈顶元素。栈从高地址向低地址增长。
   addi sp, sp, -24 , sd x5, 16(sp) , sd x6, 8(sp) , sd x20, 0(sp) 可以实现将 x5, x6, x20 压栈。
7. 一些 RISC-V 编译器保留寄存器 x3 用来指向静态变量区，称为 global pointer gp 。
8. 一些 RISC-V 编译器使用 x8 指向 activation record 的第一个 dword，方便访问局部变量；因此 x8 也称为 frame pointer fp 。在进入函数时，用 sp 将 fp 初始化。
   fp 的方便性在于在整个过程中对局部变量的所有引用相对于 fp 的偏移都是固定的，但是对 sp 不一定。当然，如果过程中没有什么栈的变化或者根本没有局部变量，那就没有必要用 fp 了。

Nested procedures

ex

1
2
3
4
5

int fact(int n)
{
  if(n<1) return 1;
  return n*fact(n-1);
}

现在我们研究上述c语言的risc-v指令

解释：我们首先要建立这样一个大概，在没有进行到底部时a0（参数）与ra（函数调用地址）不断被压栈保存。当递归到底部时，我们开始jarl zero，0（ra）开始回到上一个函数调用(因为注意当我们之前在L1中操作时命令jal ra,fact中的ra保留的是这一条指令的下面指令的位置，即开始进行L1的后半部分)，不断更新a0（即结果），然后将栈pop得到上一个函数地址再进行jarl zero,0(ra)

• 类似于这种将递归转化为risc-v其实有两种写法，一种是上面的写法在调用过程中跳转到另一个分支，另一种是在尾部才跳转到另一个分支。()

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

fact:
addi sp,sp,-16
sd a0,8(sp)
sd ra,0(sp)
bgt a0,1,L1
addi a0,a0,-1
jal ra,fact //调用fact(n-1)
ld  t1,8(sp)
mul a0,a0,t1
ld ra,0(sp)
addi sp,sp,16
jalr zero,0(ra)
L1:
addi a0,a0,1
jalr zero,0(ra)

• 斐波拉契数列同样地利用尾部跳转到另一个分支

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

fib:
  beq x10, x0, base_case_0  # 如果x10 == 0，跳转到base_case_0
  addi x5, x0, 1            # x5 = 1
  beq x10, x5, base_case_1  # 如果x10 == 1，跳转到base_case_1

  addi x2, x2, -16          # 分配16字节的栈空间
  sd x1, 0(x2)              # 保存返回地址x1
  sd x10, 8(x2)             # 保存参数x10

  addi x10, x10, -1         # x10 = x10 - 1
  jal x1, fib               # 递归调用fib(n-1)
  ld x5, 8(x2)              # 从栈中加载原来的x10值到x5
  sd x10, 8(x2)             # 保存fib(n-1)的结果

  addi x10, x5, -2          # x10 = x5 - 2
  jal x1, fib               # 递归调用fib(n-2)
  ld x5, 8(x2)              # 从栈中加载原来的x10值到x5
  add x10, x5, x10          # x10 = fib(n-1) + fib(n-2)

  ld x1, 0(x2)              # 从栈中加载返回地址x1
  addi x2, x2, 16           # 恢复栈指针
  jalr x0, 0(x1)            # 返回到调用者
done:
  jalr x0,x1

loacl data on the stack

• fp与sp两个指针
• fp在一次函数调用的储存中固定，而sp随着压栈的元素不断移动.即fp只指向这个进程的起始位置

2.9 communicating with people

string copy

• 因为这个例子是一个leaf procedure所以有优化的点
• For a leaf procedure
  The compiler exhausts all temporary registers
  Then use the registers it must save

2.10 对大立即数的RISC-V的编址和寻址

32-bit constants

• 当我们load时，要进行两次操作，先将前20位load进去，再加上后12位
• 但是后12位需要扩展到32位，当后12位的符号位为1，则前面都需要扩展为1，那么我们第一次20位就需要做出一点变化。
  

branch addressing

• 有些题目可能会遇到计算pc端的可能的地址，因为我们储存的特殊性，所以对于sb指令而言，正向只能至多移动（4094），但是负向可以至多移动（-4096）

• 对于bne指令，是SB类型，则imm[12]是符号位，而imm[0]默认为0，相当于跳跃时只能跳转偶数操作，这也与我们后面的指令地址以halfword对齐照应。

• PC-relative addressing
  Target address = PC + Branch offset
  = PC + immediate × 2 即通常存储的是相对位置，这也与下面的一个例子相互对应

jump addressing

• 解释：All RISC-V instructions are 4 bytes long
  PC-relative addressing refers to the number of halfwords
  The address field at 80012 above should be 6 instead of 12
• 但是其实你仔细研究上面的代码，会发现如果加上我们默认的imm[0]=0,其实蕴含的imm的距离就是12和-20，也就是imm其实就是代表两条指令的地址的字节差。

指令类型对应寻址方式

• immediate addressing addi x5,x6,4
• register addressing add x5,x6,x7
• base addressing ld x5,100(x6)
• PC-relative addressing beq x5,x6,L1

2.11 指令与并行性：同步

risc-v中的同步

• Load reserved: lr.d rd,(rs1)
  Load from address in rs1 to rd
  Place reservation on memory address

• Store conditional: sc.d rd,(rs1),rs2
  Store from rs2 to address in rs1
  Succeeds if location not changed since the lr.d Returns 0 in rd
  Fails if location is changed Returns non-zero value in rd

• 上述两条指令的例子
  

2.12 translating and starting a programme

2.13 A C sort example to put it all together

2.14 arrays vs pointers

解释：上述例子就是数组和指针两种方式进行清空一个数组操作，只是数组的操作通过i来控制每次i加1，再进行移位操作；而指针直接找地址，每次地址加8。

chapter3 arithmetic for computers

3.1 introduction

• there are 32bit/word(默认) or 64bit/word in RISC-V
• 数的表示二进制，有符号数与无符号数

3.2 arithmetic

addition and subtraction

• 加减法可以直接使用补码进行操作，但是乘法不能

overflow

• 次高位向最高位有进位，最高位上去没进位或次高位向最高位没进位，最高位上去有进位（即异或操作）
  则会发生溢出(前提都是考虑补码操作)
• 应对措施：忽略；在alu操作检测

construct an alu

• extended the adder

1. build a single
2. expand it to the desired width

• 添加comparison操作
  slt rd,rs,rt(32位寄存器)
  n If rs < rt, rd=1, else rd=0
  n All bits = 0 except the least significant

alu总体设计

需要注意：Less 和 Set 共同使用，是为了实现 slt rd, rs1, rs2 这个操作（即实现比较操作）（SLT 即 Set Less Than）的。这个操作的含义是，如果 rs1 < rs2 ，那么将 rd 置为 1 ，否则置为 0 。如何进行这一判断呢？很简单，rs1 < rs2 即 rs1 - rs2 < 0，也就是说如果 rs1 - rs2 结果的最高位是 1 ，那么就说明 rs1 < rs2 。所以对于 slt 这个操作，我们只需要计算 rs1 - rs2，而后将 ALU63 中加法器的结果（即最终结果的符号位）赋值给 Result[0] ，即运算结果的 Least Significant Bit，而将其他位的结果 Result[1:63] 都设成 0，就可以完成 slt 操作了。

• 常见的alu选择数对应的功能如下

verilog设计

• 检测overflow:增加一位观察其位数，并根据alu operation再根据原来的a和b的最高位三者
  进行综合来判断是否发生溢出。

更快的方法

• 超前进位加法器
  思路：对于普通加法器而言，运行缓慢的重要因素是因为在我们进行计算的时候，我们需要等待前面的部件
  计算完成产生进位后再来计算。而超前进位加法器则是通过假想所有进位可能产生的情况，提前对每一位进行
  与操作和或操作，大大减少了进行加法需要的时间

  详细的数学推导如下

  如果想要将运算的位数扩展为16位即原来的四倍，一种可能实现的方法如下：
  也就是对于每四位用之前所说的超前加法器，然后这四位产生的结果之间又存在一个
  迭代关系。

carry select adder

• carry select adder
  思路：这就是体现了在chapter中提到的设计中的冗余的思想，将carry为0或1的情况都列出来
  再从中选择符合实际的情况

乘法

V1

• 解释：最简单的乘法装置就是用一个64位寄存器用来存储乘数，然后每一次进行移位，并同时对被乘数进行移位，如果判断为1，则将现在移位的被乘数加到最终的结果上面（128位alu操作）.

V2

• 解释：进行第一次优化，将 Multiplicand 寄存器换为了 64 位，而将位移操作转移到了 Product 寄存器中进行。这里最重要的一点就是，64 位加法只影响 Product 寄存器左侧的 64 位，而之后的右移操作则是 128 位。这样，虽然最低位的结果一开始会被放在 Product 寄存器的第 65 位里，但是在经过 64 次右移之后，它就出现在第一位了。于是，所有的 128 位加法都被 64 位加法替代，实现了加速。

V3

• 解释：直接将 Multiplier 存在了 Product 的低 64 位中。当我们从中取出最低位并经过一次判断后，这一位就不重要了，而恰好 Product 需要右移，就将这一位消除，方便我们下一次从最低位拿出下一个比特。首先，少了一个寄存器，节省了空间；其次，原本需要 Multiplier 寄存器和 Product 寄存器都做右移，现在只需要 Product 寄存器右移即可，减少了一个 64 位右移操作。

faster multiplication

• 将乘数与被乘数展开转化为加法

signed multiplication

除法

V1-division

• 解释：最基本的竖式计算。最开始除数放在寄存器的左半部分，被除数放在寄存器的右半部分。然后对除数与被除数作减法，如果结果大于0，则此时的商取1，商移位，被除数也需要移位并且除数继续移位；否则商取0，商移位并且除数继续移位。

V2-division

• 解释：想要优化我们上述的除法结构，我们联想到上述加法的V3模式。我们采用类似的结构，64位除数不进行移位操作，而储存被除数的寄存器先放置在左侧，将被除数向左移，（空出来的位置用来放置商），与除数再进行减法。

floating point numbers

• 对于不同的取值范围对应的表达方式(尤其注意零和正负无穷的表达)

• 下面给出一个浮点数换算的具体例子

floating point addition

• 对齐：小对大进行对齐：为什么是小对大？首先，小对大的过程是在小指数的 fraction 前补 0，可能导致末尾数据丢失；大对小的过程是在大指数的 fraction 后补 0，可能导致前面的数据丢失。在计算过程中，我们保持的精确位数是有限的，而在迫不得已丢去精度的过程中，让小的那个数的末几位被丢掉的代价比大的前几位丢失要小太多了。
• 相加
• 将结果归一化
• 进行舍入操作（可能结果还需要进行归一化）

multiplication

• 将两个 Exponent 相加并 减去一个 bias，因为 bias 加了 2 次
• 将两个 (1 + Fraction) 相乘，并将其规格化；此时同样要考虑 overflow 和 underflow；然后舍入，如果还需要规格化则重复执行
• 根据两个操作数的符号决定结果的符号

准确计算

• 一般的浮点位数后面跟两个bit(guard、round)，其目的是让舍入更加精确，所以加减法一般只考虑guard即可。但是对于乘法，如果存在前导零的情况，需要把结果左移的时候，round就会起作用（成为有效位）。
• 一个位叫 sticky bit，其定义是：只要 round 右边出现过非零位，就将 sticky 置 1，这一点可以用在加法的右移中，可以记住是否有 1 被移出，从而能够实现 “round to nearest even”。

chapter4-the processor

4.1 introduction

• CPU performance factors
  Instruction count Determined by ISA and compiler
  CPI and Cycle time Determined by CPU hardware
• We will examine two RISC-V implementations
  A simplified version
  A more realistic pipelined version
• Simple subset, shows most aspects
  Memory reference: ld, sd
  Arithmetic/logical: add, sub, and, or
  Control transfer: beq

overview

解释：上图中蓝色的线是在原有的overview上面的控制信号

4.2 logic design convention

• 非阻塞赋值：等式右边的值全部被评估完全后，再会赋值给等式左侧。所有赋值操作在当前always块的末尾同时生效。这意味着即使多条赋值语句在代码中是顺序排列的，它们的执行效果是并行的。在时序逻辑中，非阻塞赋值确保了在同一个时钟周期内，所有变量的更新不会互相影响
• 阻塞赋值：右边的值在此刻马上赋给左侧的值。

4.3 building a datapath

instruction execution in Risc-V

• Fetch :
  Take instructions from the instruction memory
  Modify PC to point the next instruction
• Instruction decoding & Read Operand
  Will be translated into machine control command
  Reading Register Operands, whether or not to use (因为我们每一个指令的格式是固定的)
• Executive Control:
  Control the implementation of the corresponding ALU operation
• Memory access:
  Write or Read data from memory
  Only ld/sd
• Write results to register:
  If it is R-type instructions, ALU results are written to rd
  If it is I-type instructions, memory data are written to rd
• Modify PC for branch instructions

instruction fetch

R-format instructions

所需单元如下：

• Read two register operands
• Perform arithmetic/logical operation
• Write register result

load/store instrutions

branch instructions

• Read register operands
• Compare operands
  Use ALU, subtract and check Zero output (beq)
• Calculate target address
  Sign-extend displacement
  Shift left 1 place (halfword displacement)(默认最后一位为零，则需要左移进行补零)
  Add to PC value

full datapath

4.4 a simple implementation scheme

7 controller

• 具体七个控制逻辑的意义