计算机组成

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)

• 斐波拉契数列同样地利用尾部跳转到另一个分支(但是可以注意到的是，如果我们把fib中的最后一行去掉其实没有问题，因为程序会顺序执行(PC+4)也就是done。)

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

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

4.5 an overview of the pipeline

risc-v pipeline

Five stages, one step per stage

1. IF: Instruction fetch from memory
2. ID: Instruction decode & register read
3. EX: Execute operation or calculate address
4. MEM: Access memory operand
5. WB: Write result back to register

Note:CPI is decreased to 1, since one instruction will be issued (or
finished) each cycle.Speedup due to increased throughput but Latency (time for each instruction) does not decrease

risc-v pipeline 优势

1. All instructions are 32-bits
   Easier to fetch and decode in one cycle
   c.f. x86: 1- to 17-byte instructions
2. Few and regular instruction formats
   Can decode and read registers in one step
3. Load/store addressing
   Can calculate address in 3rd stage, access memory in 4th stage

hazard（竞争）

strutrue hazard

data hazard

control hazard

解决hazard

解决structure hazard

• 产生：前一个指令在ID阶段时会使用其在IF阶段读出的指令内容，但是此时后一个指令已经运行到IF阶段并读出内容，为了解决控制信号的冲突，我们实际上会在每两个stage之间使用寄存器保存这些内容。
• 解决
  
  解释：我们现在在两个stage中的竖条条就是pipline registers。但是还需要关注datapath中两个从右往左的path，一个是wb阶段写回数据（在这个情况下，write register要随着其他控制信号向下传递），一个是MEM阶段判断是否发生跳转。

解决data hazard

• forwarding

• load-use data hazard

如果是load我们所需要的数据就没有在EX后面产生，而是在MEM阶段产生，则我们可能再经过一个bubble，再将MEM的输出数据通过旁路转发给EX的输入

• 给定一段c语言与相对应的指令，计算出需要的时钟周期

ld x1, 0(x0)
ld x2, 8(x0)
stall
add x3, x1, x2
sd x3, 24(x0)
ld x4, 16(x0)
stall
add x5, x1, x4
sd x5, 32(x0)
13 cycles
相同的c语言代码但是改进的risc-v代码
ld x1, 0(x0)
ld x2, 8(x0)
ld x4, 16(x0)
add x3, x1, x2
sd x3, 24(x0)
add x5, x1, x4
sd x5, 32(x0)
11 cycles

解决control hazard

• Branch prediction

• 更长的流水线无法在早期确定分支结果
  停顿惩罚变得不可接受

• 预测分支结果
  仅在预测错误时停顿

• 在 RISC-V 流水线中
  可以预测分支未被采取
  在分支后立即获取指令，无需延迟

4.6 RISC-V pipeline datapath

pipline registers

• note：注意register number在流水线中需要随着进程往下传导，否则操作的register不再是原来的register

4.7 data hazard

判断何时出现 data hazard

• Data hazards when
  1a. EX/MEM.RegisterRd = ID/EX.RegisterRs1
  1b. EX/MEM.RegisterRd = ID/EX.RegisterRs2
  2a. MEM/WB.RegisterRd = ID/EX.RegisterRs1
  2b. MEM/WB.RegisterRd = ID/EX.RegisterRs2

• But only if forwarding instruction will write to a register!
  EX/MEM.RegWrite, MEM/WB.RegWrite

• And only if Rd for that instruction is not x0
  EX/MEM.RegisterRd ≠ 0,
  MEM/WB.RegisterRd ≠ 0

解决double data hazard

• Consider the sequence:
  add x1,x1,x2
  add x1,x1,x3
  add x1,x1,x4
• Both hazards occur（满足前面我们所说的a和b两种情况）
  Want to use the most recent
• Revise MEM hazard condition
  Only fwd if EX hazard condition isn’t true
• 具体条件代码
  if (MEM/WB.RegWrite
  and (MEM/WB.RegisterRd ≠ 0)
  and not(EX/MEM.RegWrite and (EX/MEM.RegisterRd ≠ 0)
  and (EX/MEM.RegisterRd = ID/EX.RegisterRs1))
  and (MEM/WB.RegisterRd = ID/EX.RegisterRs1)) ForwardA = 01
  解释：加粗部分是为了避免上一个EX/MEM也满足条件，从而选择上上级的MEM/WB进行旁路传输，而如果上一级的EX/MEM满足条件，则选择上一级的EX/MEM进行旁路传输。

hazard detection

解释：我们主要解释图片的hazard detection unit,这个单元就是为了解决load-use hazard，这个单元的输入分别为相应位置的rs1,rs2,rd,ID/EX.MemRead,而向右的输出如果存在hazard则进行赋零，向左的两个输出就是如果存在hazard则pc端先暂停一下等待一个时钟周期再往下进行（为了空泡的产生）。

4.8 Branch Hazards

dynamic branch prediction

calculating the branch target

• Even with predictor, still need to calculate
  the target address
  1-cycle penalty for a taken branch
• Branch target buffer
  Cache of target addresses
  Indexed by PC when instruction fetched
  If hit and instruction is branch predicted taken, can fetch target immediately

4.10 instruction-level parallelism

multiple issue(多发)

risc-v with static dual issue

• 对于双发问题，在packets中我们常常把alu/branch 与load/store指令放在一个包中
• 因为这两个类型的指令所使用的结构大多不相同，能够有效平衡资源利用。

loop unrolling

• 循环展开：比如将一次循环做一次的程序改为一次循环我们可以做多次，这样在双发系统中能让空泡减少，提高效率。
• ex

1
2
3
4
5
6
7
8
9
10

Loop: addi x20,x20,-32 ld x28, 0(x20)    1
nop                      ld x29, 24(x20) 2
add x28,x28,x21 ld x30, 16(x20)          3
add x29,x29,x21 ld x31, 8(x20)           4
add x30,x30,x21 sd x28, 32(x20)          5
add x31,x31,x21 sd x29, 24(x20)          6
nop sd x30, 16(x20)                      7
blt x22,x20,Loop sd x31, 8(x20)          8

dynamic scheduling

• ex
  ld x31,20(x21)
  add x1,x31,x2
  sub x23,x23,x3
  andi x5,x23,20
  则可以将sub先开始再执行add

4.11 exception

handling exceptions

1. save PC of offending instruction
2. save indication of the problem
3. jump to handler
   Assume at 0000 0000 1C09 0000hex,再跳到cause 寄存器，再跳转到程序发生异常的地方

an alternate mechanism

Chapter5-Large and Fast:Exploiting Memory Hierarchy

5.1 Memory technologies

5.2 Memory hierarchy

• 时间局部性：最近经常用的就放在离cpu近的地方
• 空间局部性：离最近常访问的元素较近的也可能被经常访问，也放在离cpu近的地方

taking advantage of locality

• 所有东西都存在disk中
• 将最近常访问的和离它们最近的从disk复制到较小的DRAM中
• 将最近常访问的和离它们最近的从DRAM复制到较小的SRAM中
  

some important items

• Block(复制单元)
• 如果被访问的数据出现在上层
  1. hit：上层满足权限
  2. hit ratio命中率：命中/访问
• 如果没有被访问的数据
  1. miss：the cpu accesses the upper level and fails.再把block从lower level复制而来，再将此时的上层数据提供给cpu
  2. miss ratio=1-hit ratio
  3. time taken:miss penalty

exploiting memory hierarchy

5.3 the basics of cache

direct mapped cache

• 一种cache结构，其中每个存储地址都映射到cache中的确定位置
• 使用以下方法得到index
  1. (块地址)mod(cache中的数据块数量)
  2. 若cache中有2^n个数据块，那么索引为主存块地址的最低n位

tags and valid bits

• 那么我们怎样确定在cache中编号到底是哪个block呢？—tag
• 确定这个block有效–valid bit

example

• 32位主存地址，4-block cache，1-word Block
• 4-block 则索引位index为两位（字节偏移量前两位）
• 且是1-word Block 则里面有4个byte，则字节偏移量(m+2)为两位(最后两位)
• 则另外的28位为tag
• 则我们成功把主存地址剥离三个部分！
• 此后我们就能进入cache找到对应的index再进行tag的比对，valid bit是否为1，如果都满足就可以读数据了
• total number of bits:2^n*(block size+tag size+valid field size)

example2

• How many total bits are required for a direct-mapped cache 16KB（总的数据大小） of data and 4-word blocks, assuming a 32-bit address?

handleing cahce hits and misses

read