引言与基础 Introduction and Basics

当前的四大方向：

安全
节省能源
低延时和可预测
AI/ML，生物，医疗，健康等的专属硬件

课程高层次目标：

了解基础
原则
惯例

基于此：

了解计算机工作
权衡不同的设计和思想
实现基于原则的硬件
在越来越复杂的系统中 debug
开发新颖的、开箱即用的设计

这些 DDCA 的原则有利于：

设计更好的硬件、软件、系统
设计中更好地取舍
了解计算机工作原理
并行、批判性思考

最重要的是：

Learning is for life, while exam study is until you pass.

计算机体系结构

机会在底层

内存中的问题：

row hammer
meltdown and spectre
data movement

权衡，指标 Tradeoffs, Metrics

数据移动消耗了大量的能源，尤其是在机器学习中

新的计算范式（重新思考整个栈）：

在内存中处理，在数据边处理
量子计算
安全与可靠计算机

新的加速单元与系统（算法-硬件协同设计）：

AI & ML
图 & 数据分析，视觉，视频
生物分析

新的内存，存储系统，联系，设备：

非易失性内存，智能内存系统，量子
高速连接，分离式系统

两个课程的主要目标：

批判性思考
广阔思考

建筑

总是从基本的建筑块和设计原则开始
如何使用、应用、增强的知识
潜在的技术可能会改变
- 但是利用技术的方法有相似之处
- 用于该设计的方法依赖于原则

一般用途和特殊用途的处理器

组合逻辑电路 Combinational Logic

计算机用大量的晶体管 transistors 组成

MOS：用导体 Conductor(Metal)，绝缘体 Insulators(Oxide)，和半导体 Semiconductors 组成

MOS

有两种类型的 MOS 晶体管：n 类型和 p 类型

两种类型的晶体管

如果 n 类型的晶体管的 gate 被施加高电压，则从 source 到 drain 的连接像导线一样。基于技术，高电压可能从 0.3V 到 3V
如果 n 类型的晶体管的 gate 被施加零电压，则 source 到 drain 的连接破坏了

p 类型的晶体管工作和 n 类型的相反

p 类型：pull up
n 类型：pull down

现代的计算机同时使用两种晶体管，即 CMOS（Complementary MOS）技术

最简单的门：

更复杂一点的门：

NAND门

可以使用 NOT 和 NAND 门组成 AND 门

注意 AND 门至少要用 6 个晶体管，而 NAND 反而只要 4 个晶体管，因为 CMOS 是反相的

CMOS门结构

当晶体管并联 Parallel 时，一个晶体管 ON，整个电路 ON
当晶体管串联 series 时，所有晶体管 ON，整个电路 ON
如果两个网络都 ON，则短路
如果两个网络都 OFF，则输出浮动 floating，无法确定

MOS 晶体管是不完美的开关

pMOS 擅长传递 1 而不擅长 0
nMOS 擅长传递 0 而不擅长 1

动态功率： $C × V^2 × f$

C = 电路电容量
V = 提供的电压
f = 电容器改变的频率

静态功率： $V × I_{leakage}$

维持摩尔定律的方法：创新

制造更小的晶体管/结构
寻找更好性质的材料
更精密的制造
新设备技术

组合逻辑 Combinational Logic：

无记忆
输出严格依赖于当前输入的组合
输入的函数规范

德摩根律

布尔代数的用途：

表达组合逻辑块的函数
化简函数

用真值表简单、通用的表达布尔函数的方法：

Sum of Products 形式：所有导致输出为 1 的极小项的和
Product of Sums 形式：导致输出为 0 的极大项的积

解码器 Decoder

输入模式检查
n 输入 $2^n$ 输出
一个输出为 1，其余为 0
为 1 的输出对于输入匹配

decoder

decoder 对于确定如何解释一个 bit 模式很有用，如内存地址、程序指令等

选择器 Multiplexer：选择 N 个输入之一连接到输出，基于 $\log_2 N$ bit 的控制位

mux

选择器可以作为实现逻辑函数的查询表

decoder 可以使用或门建造逻辑函数（类似于 SOP 形式）

使用decoder实现逻辑函数

全加器：

全加器

顺序全加器

多位并行全加器

可编程逻辑阵列 Programmable Logic Array(PLA)

AND 和 OR 门的阵列
使用 SOP 实现任何逻辑函数

FPGA 就使用了其中的一部分技术

PLA

等值检查器

将一些算术和逻辑操作组合到一起形成 ALU

ALU

三态门 tri-state buffer

三态门

类似于一个开关

可用于控制总线上的设备：

可以使用三态门制造 Mux：

三态门实现Mux

三态门的晶体管实现

化简的关键工具：联合定理 Uniting theorem： $F = A\bar{B} + AB = A$ ，即如果 $B$ 和 $\bar{B}$ 同时出现，则可以消去

优先电路

输入：有优先级的请求
输出：授予每个请求信号

卡诺图 Karnaugh Map：是一个化简的可视化方法，然而在实际中意义不大，因为无法处理六维或更高维度的数据

时序逻辑设计 Sequential Logic Design

相互耦合的反相器：有两个稳定的状态：Q = 0 和 Q = 1，但是无法设置 Q

相互耦合的反相器

SRAM 是一种改进方式，但是两边的晶体管并不稳定

SRAM

存储元素：

锁存器和触发器
SRAM
DRAM
闪存，硬盘，磁带

速度减小，成本降低，所以有了内存层次结构

R-S 锁存器 Reset-Set Latch：

稳定状态下，S 和 R 都为 1
S：若 S 为 0，则设 Q 为 1
R：若 R 为 0，则该 Q 为 0
S 和 R 不能同时为 0，因为破坏了不变式 $Q = !Q^{\prime}$ ， $Q$ 和 $Q^{\prime}$ 振荡，进入亚稳态 metastability

RS锁存器

为了保证 R-S 锁存器的操作正确，使用门锁 D 锁存器 gated D latch

门锁D锁存器

当 WE 为 1 时，Q 取 D 的值。S 和 R 不会同时为 0

寄存器 register：用多个 D latch 表示多个位

寄存器

内存 Memory 是地址的组合

对内存输出使用一个 Mux 读内存：

Mux读内存

对输入内存使用一个 decoder 写内存：

写内存

组合起来添加更多寄存器得到内存：

更大的内存阵列

基于内存的查找表（可以用来实现逻辑函数）：

每个地址：真值表中的行
每个数据位：相关的输出数据

内存实现逻辑函数

查找表 Lookup Table(LUT) 广泛应用于 FPGA 中

我们已经设计了能够存储信息的电路，可以用其实现记忆过去的输入的电路

一个系统的状态 state 是那个时刻所有相关元素的快照

顺序锁是一个异步 asynchronous 的机器：当状态转移发生时就发生

现代计算机都是同步 synchronous 机器：在固定单位时间后状态转移才会发生

使用一个时钟 clock 决定何时改变状态，时钟信号交替 0 和 1

在一个时钟周期的开始，系统状态改变

同步控制更容易正确，而异步控制更高效

有限状态机 Finite State Machine(FSM)

一个状态系统的离散时间模型
每个状态表示系统在一个给定时间的快照

FSM 图形化：

一个系统所有可能的状态
系统如何从一个状态转移到另一个

一个有限状态机有三个部分组成：

下一个状态逻辑
状态寄存器
输出逻辑

有限状态机

状态寄存器的两个性质：

在每个时钟周期开始时存储数据
数据在整个时钟周期可用

D触发器

上升沿触发的触发器

触发器 flip-flop 叫做边缘触发的状态元素
锁存器是电平触发的状态元素

基于D触发器的寄存器

两种有限状态机：

Moore FSM：输出仅取决于当前状态
Mealy FSM：输出取决于当前状态和输入

两种有限状态机

状态编码：

二进制编码
- 使用 $\log_2$ 状态数量 位表示状态
- 最小化触发器，但并不是输出逻辑或下一个状态逻辑
one-hot 编码
- 使用 状态数量 个位表示状态
- 最小化下一个状态逻辑，但最大化触发器
- 最简单的设计过程
输出编码
- 输出直接在状态编码
- 最小化输出逻辑
- 只适用于 Moore 机器

识别1101序列的状态转移图

FSM 设计过程：

决定所有可能的状态
设计状态转移图
- 决定每个状态的输入和输出，还有转移
方法
- 从 reset 状态开始
- 添加转移和状态
- 选择合适的状态名
- 建造一个 FSM 就像编程，但不是编程
  - FSM 像有条件和 goto 的程序的顺序控制流

在硬件上，一般有很多并发的 FSM

硬件描述语言和 Verilog Hardware Desccription Languages and Verilog

硬件描述语言：

用于描述硬件
可以描述复杂的设计
可以模拟行为
可以合成部分硬件

两大最有名的 HDL：Verilog 和 VHDL

HDL 让描述硬件更轻松，无缝表达硬件的内在并行

设计模块的层次结构：

预先定义的原始门
由这些门构建简单模块
由简单模块构建复杂模块

层次结构控制了复杂性

自顶向下设计方法和自底向上的设计方法，通常两者都会使用

模块 module 是 Verilog 中的主要组成，需要定义

模块的名字
端口方向

然后描述模块的功能

有两种风格：

module test(a, b, y);
    input a;
    input b;
    output y;
endmodule
// 或
module test(input a, input b, output y);
endmodule

对于多 bit 的输入/输出，可以使用 [结束访问:开始范围]，如 input [31:0]a; 表示 a[31],a[30]..a[0]，顺序可以交换，但是必须一致

操作位：

// 切片
wire [15:0] longbus;
wire [7:0] shortbus;
assign shortbus = longbus[12:5];

// 连接
assign y = {a[2], a[1]};

// 可以定义重复
assign x = {4{a[0]}};

HDL 实现的两个主要风格：

结构化：
- 侧重于描述门级别的电路
- 用门描述模块层次结构
表现化：
- 侧重于电路的函数描述
- 包括逻辑和数学运算符
- 比门级别更高层次抽象
- 一个表现描述可能有多种门层次的实现方式

使用模块 small(A,B,Y) 的两种方法：

// 要求顺序匹配
small i_first(A, SEL, n1);
// 或
small i_second (.B(C), .Y(Y), .A(n1));

结构化例子：

module mux2(input d0, input d1, output y);
    and g1 (d0, d1, y);
endmodule

也就是和模块实例化一样，但是不需要定义

表现化：

module example(a, b, y);
    input a;
    input b;
    assign y = a & b;
endmodule

可以按位操作，如

module and4(input [3:0] a, input [3:0] b, output [3:0] y);
    assign y = a & b;
endmodule

约简操作：

module and8(input [7:0] a, output y);
    assign y = &a;
endmodule

条件赋值：assign y = s ? d1 : d0;

数的表示：N'Bxx

N：bit 的数量
B：基，可以是 b, h, d, o
xx：数字
- 用基表示的值
- 也可以是 X（无效）和 Z（浮动）
- _ 有利于提高可读性

有Z和X的AND门真值表

合成：

将合成的 HDL 代码映射到低层次 cell 库中
可以实现许多优化
但是并不能保证是最优的，因为需要计算量太大

模拟

模块可以有参数

module mux2 #(parameter width = 8) (input [width-1:0]d0, d1, output[width-1:0] y);
endmodule

// 使用
mux2 i_mux(d0, d1, out);
// 12 bit
mux $(12) i_mux_b(d0, d1, out);

时间

只可模拟
不可合成
用于电路的建模延迟

时间和验证 Timing and Verification

时序 = 组合 + 内存

always 块：

always @ (sensitivity list)
    statement;

当 sensitivity list 中的事件发生，语句执行

例如 flip-flop：

module flop(input clk, input [3:0] d, output reg [3:0] q);
always @ (posedge clk)
    q <= d;
endmodule

赋值的变量被声明为 reg，但并不意味着这个值是一个寄存器
always 块中不能有 assign

一个异步 reset 的 flip-flop：

always @ (posedge clk, negedge reset)
    begin
        if (reset == 0) q <= 0;
        else q <= d;
    end

对于更长的雨具，begin-end 对可以提高可读性

一个同步 reset 的 flip-flop：

always @ (posedge clk)
    begin
        if (reset == '0') q <= 0;
        else q <= d;
    end

可能有多个 always 块，但是不能在不同的 always 块中给相同的信号赋值

always 块可以用于定义组合逻辑，如果：

所有的输出都总是更新
右边的信号都在感知列表中，如 always @ *
左边的信号在每个可能的情况下都赋值

case 语句

always @ (*)
    case (data)
        4'd0: segments = 7'b111_1110;
        4'd1: segments = 7'b111_1010;
        4'd2: segments = 7'b111_1000;
        default: segments = 7'b000_0000; // 为了避免遗忘某些情况，一定要有 default
    endcase

注意 if...else 只能用于 always 块中

非阻塞式 <=：并行赋值
阻塞式 =：知道前面的赋值完成才开始进程

parameter 相当于常量，可以用于提高可读性，如 parameter s0 = 2'b00;

事实上输出相对于输入有延迟，因为晶体管开关需要时间

组合电路延迟

延迟的造成原因：

电路的容抗和阻抗
光速有限

污染延迟 contamination delay：Y 开始改变之前的延迟

传播延迟 propagation delay：Y 完成改变的延迟

污染延迟和传播延迟

关键路与最短路

最长（关键 critical）路： $t_{pd} = 2 t_{pd\_AND} + t_{pd\_OR}$

最短路： $t_{cd} = t_{cd\_AND}$

脉冲 glitch：一个输入转移造成多重输出转移

脉冲在卡诺图中可见，当主要隐含数之间移动时，脉冲出现：

只需要将其连起来即可

D flip flop 输入时间约束

当采样 sample 时，D 必须是稳定的

设置时间 setup time：在时钟边缘到来之前数据必须稳定的时间
保持时间 hold time：在时钟边沿之后数据必须保持稳定的时间
孔径时间 aperture time：时钟边沿周围数据必须保持的时间， $t_a = t_{setup} + t_{hold}$

D flip flop 输入时间约束

D flip flop 输出时间约束

到 q 的污染延迟 contamination delay clock-to-q( $t_{ccq}$ )：在时钟边沿后 Q 开始改变的最短时间
到 q 的传播延迟( $t_{pcq}$ )：在时钟边沿后 Q 停止改变的最短时间

filp-flop输出时间

对于时序电路，D2 必须稳定，即

至少在时钟边沿到来前 $t_{setup}$
至少在时钟边沿到来后 $t_{hold}$

故两个触发器之间有最大和最小延迟

$T_c > t_{pcq} + t_{pd} + t_{setup}$ ，其中 $t_{pd}$ 是有效工作，由关键路延迟决定，其余部分为时序开销 sequencing overhead
$t_{cd} > t_{hold} - t_{ccq}$ ，注意与 $T_c$ 即时钟周期无关

时钟也有延迟，不同时钟边沿的时间差为时钟歪斜 clock skew，若考虑这一延迟，则原等式的两边都要加上 $t_{skew}$

Testbench：一个用于测试的模块，被测试的模块叫待测设备 device under test(DUT)

其提供输入，有人工的，也有自动生成（顺序或随机数）
将 DUT 的结果和人工值或黄金设计相比较

module testbench2();
    reg a;
    sillyfunction dut(.a(a), .b(b), .c(c), .y(y));

    initial // 类似 always 块，但是只在一开始运行一次
        begin
            a = 0; b = 0; c = 0;
            #10;	// 等待 10 ns
            if (y != 1) $display("000 failed.");	// 打印信息
        end
endmodule

好的设计原则：

关键路径设计：最小化最大逻辑延迟
平衡设计：平衡系统中不同部分的最大逻辑延迟，即不出现瓶颈
面包黄油设计：优化一般情况，但也要考虑到非一般情况

冯诺依曼结构 Von Neumann Model

为了用计算机完成一个任务，需要

计算机程序
计算机

程序：指令集

指令：程序中最小工作单元

指令集：计算机被用于设计执行的指令的集合

冯诺依曼结构

两种内存：

字长地址的内存：每个字长数据有一个独特的地址
字节地址的内存：每个字节数据有一个独特的地址

读内存：

将希望读的地址装载到 MAR（内存地址寄存器）中
将相关位置的数据放到 MDR（内存数据寄存器）中

写内存：

将希望读的地址装载到 MAR 中，将需要写入的数据装载到 MDR 中
激活写使能信号

处理单元：由很多功能单元组成，如 ALU

为了更快的存储，临时数据存在寄存器中

控制单元：一步一步执行程序

指令寄存器
PC

冯诺依曼结构两个关键的性质：

存储程序
- 指令在线性内存阵列中存储
- 内存对指令和数据一视同仁，所以对储存值的解释依赖于控制信号
顺序指令处理
- 一个处理一个指令
- PC 识别当前指令
- PC 顺序向前，除了控制转移指令

LC-3机器

指令集架构 Instruction Set Architectures

计算机语言可以写作：

机器语言：0 和 1
汇编语言：人类可读

指令由两部分组成：指令编码 opcode 和操作数 oprand

指令循环：

取指令
解码指令
计算地址
获取操作数
执行
存储结果

然后返回循环，注意不是所有的指令都有这六个阶段

ISA 是软件命令和硬件执行的接口，其规定了

内存组织
寄存器集
指令集

指令集的复杂和简单中是权衡：

硬件复杂度 vs 软件复杂度
简单 vs 复杂指令的延迟

语法沟

有四种寻址方式：

PC-相关：Memory[PC + sign-extend(PC offset 9)]
间接访问：Memory[Memory[PC + sign-extend(PC offset 9)]]
集 + 偏移：Memory[$s0 + 8]
立即数寻址：LEA(Load Effective Address)：PC + sign-extend(PC offset 9)

计算机基本方法：如果有什么是解决不了的，那就在中间加一层：

数据流模型 Dataflow Model：指令以数据流顺序执行，即不是 PC，而是生产者-消费者模型

通常使用图表示

顺序和数据流

数据流结点

这种架构提取出了并行

微架构 Microarchitecture

ISA：规定程序员看到这些指令怎样被执行

微架构：执行指令的潜在实现

计算机体系结构定义：ISA + 实现

处理指令：根据 ISA 规范把状态从 AS 转化为 AS'

类似于一个抽象有限状态机
从 ISA 视角，每条指令一个状态转移
从微架构视角，每条指令可以有多重状态转移

单周期机器

单周期机器：

每条指令一个时钟周期
所有状态在指令执行结束时更新
缺点：可以发现时钟周期时间由关键路决定

多周期机器：

每条指令被分成多个周期/阶段
在指令执行期间更新状态
在指令执行结束时更新架构状态
相对优点：最慢的阶段决定周期时间

指令处理机制由两部分组成：

数据路径：有处理和转移数据信号的硬件组成
- 函数单元
- 硬件结构
- 存储单元
控制逻辑：决定控制信号，即指定进入数据的数据路径中的元素

效率分析：

每条指令的执行时间：CPI * 时钟周期时间
整个程序的执行时间：（CPI _ 时钟周期时间）的总和 = 指令数 _ 评价 CPI * 时钟周期时间

MIPS的状态元素

假设：

组合读
同步写
单周期，同步内存

R类型数据路径

I 类型的寄存器编码位置不同，还有要选择是使用寄存器还是立即数，故添加两个 Mux

I类型数据路径

LD数据路径

SW数据路径

和之前的组合起来，得到完整的数据路径

读写数据路径

注意 PC 相关跳转中的 PC 是这条指令的下一个，所以要先 PC + 4

无条件跳转数据路径

条件跳转数据路径

把所有的放在一起，并加入控制信号：

单周期机器2

控制信号	为 0 的情况	为 1 的情况	等式
RegDest	选择 inst[20:16]	选择 inst[15:11]	opcode == 0
ALUSrc	第二个寄存器	立即数	opcode != 0 && opcode != BEQ && opcode != BNE
MemtoReg	存储 ALU 结果	储存内存输出	opcode == LW
RegWrite	禁止写寄存器	允许写寄存器	opcode != SW && opcode != Bxx && opcode != J && opcode != JR
MemRead	禁止读内存	允许读内存	opcode == LW
Memwrite	禁止写内存	允许写内存	opcode == SW
PCSrc_1	根据 PCSrc_2	26 位立即数跳转	opcode == J \|\| opcode == JAL
PCSrc_2	PC = PC + 4	16 位立即数跳转	opcode == Bxx && 条件满足

控制盒子：

组合逻辑：根据指令解码
时序逻辑：将控制信号与指令关联起来的内存结构

多周期微架构设计 Multi-Cycle Microarchitecture Design

多周期设计的缺点：需要在每个时钟周期结束都储存当前结果

硬件寄存器开销大
寄存器设置和保持的开销

实现的思想：有限状态机

状态由控制信号确定
下一个状态的控制信号在当前状态确定

除了运行效率外，多周期微架构还有节省硬件资源的优势

注意到单周期微架构使用了两个内存和三个加法器
多周期微架构可以在不同周期复用这些资源

直接根据指令执行过程划分阶段：对于 lw 指令，有

指令获取

读寄存器

lw地址

读内存

写寄存器

增加PC

其余指令同理

多周期处理器

接下来是控制单元：

控制单元

控制单元的状态机

但这种设计的缺陷假定了内存访问 < 一个周期，所以需要设计内存准备位

LC-3b状态机

微编程控制术语：

微指令：和当前状态相关的控制信号
微顺序：从一个状态转移到另一个的动作
控制存储：存储每个可能的控制信号
微顺序器：决定哪个控制信号会被用于下一个时钟周期

微编程控制结构

流水线 Pipelining

观察之前的多周期设计，可以发现在指令执行的不同阶段有一些硬件资源闲着，所以可以增加并发性

流水线核心思想：

把指令执行周期分成不同的处理阶段
每个阶段处理不同的指令

理想流水线：

相同的操作重复
独立的操作重复
均匀划分的子操作

可惜我们的设计决不是理想的流水线

吞吐量增大，但增加了寄存器，成本增加

流水线寄存器

每经过一个阶段一些不用的信号可以丢弃了，即后面的寄存器会越来越小，可以节省成本

流水线控制信号

资源竞争：两个流水线阶段需要相同的资源

解决方案：

减少竞争造成原因
检查资源竞争并暂缓其中一个竞争的阶段

数据依赖：

类型：

流依赖（真实的数据依赖——写后读）
反依赖（读后写）
输出依赖（写后写）

三者都会导致流水线的暂缓，但是后两者是因为寄存器的数量有限导致的，也就是依赖于一个名字，而不是值

流依赖的六种处理方法：

检测并等待直到寄存器文件中的值可用
检测并旁路数据至独立的指令
检测并在软件层次减少依赖
检测并把它移出，给独立指令让路
预测需要的值，并确认
做其他事（细粒度的多线程）

互锁 interlock：流水线处理器的指令之间检查依赖以保证正确执行

方法：

计分板：每个寄存器文件中都有一个有效位
组合依赖检查：检查指令在后面是否需要写

流水线处理器设计 Pipelined Processor Design

造成流水线暂停的原因：

资源竞争
依赖
长延迟（多周期）的操作

暂停实现方法：

关闭 PC 和 IF/ID 锁
在暂停的指令后插入无效指令（bubbles）

数据转发 data forwarding：也叫 data bypassing，即在数据可用时就将结果值转发给依赖的指令，在写回之前

从内存阶段而后写回阶段转发到执行阶段，如果两者都匹配目标寄存器，则优先转发内存阶段数据，因为其更新

数据转发

但是，例如 lw 指令，其最后一个阶段才会获取数据，数据转发无效

暂停所需的硬件：

获取和解码的使能
执行寄存器的 CLR 或每个寄存器的有效位

当 lw 暂停发生

保持解码和获取阶段的寄存器的值
清楚执行阶段寄存器的内容，插入 bubble

分支预测：特殊的数据依赖——依赖 PC

在分支被解决之前，分支后的指令已经被获取了

简单的策略：总是循序执行（总是不选择），如果分支要执行，则清空未选择路径的指令

分支误测的惩罚：清空的指令数

减少的方法：早期分支解决：在更靠前的阶段测试分支

基于软件的指令调度——静态调度，硬件以编译器指定的顺序执行指令，问题在于编译器不知道运行时确定的值

细粒度多线程 Fine-grained multithreading：每个周期从一个不同的线程中获取指令，使得同时在流水线中没有两个从同以一线程中的指令

硬件有多线程上下文（PC+寄存器）
线程完全独立
直到之前的指令结束，没有指令从同一线程中获取

优点：

多线程吞吐量增加
一个线程中不需要处理控制和数据依赖的逻辑

缺点：

单线程效率低
保存线程上下文的额外逻辑
如果线程数量不够，则吞吐量降低

细粒度多线程

现代 GPU 常用这个方法，即超多线程和超多寄存器

精确异常 Precise Exceptions

即保持顺序的语义

因为在执行阶段，不同的指令所需时间不同，所以可以在之前的长延迟的指令执行结束前，让独立的指令在不同的函数单元执行

多周期执行异常

若第一个指令出现异常，但后面的指令已经执行完了，故无法确定这个异常是谁引起的

程序执行过程中为计划的改变或中断

内部问题：异常 exception
外部事件：中断 interrupt

处理时间：

异常：当检测到
中断：当方便时，除了一些高优先级的，如没电了、机器故障等

当异常/中断准备好处理时，架构状态应该一致（精确）

所有之前的指令都必须完全退休 retired
之后的指令都没有退休

当最老的即将退休的指令被检测到造成异常时，控制逻辑

确保架构状态精确（寄存器文件，PC，内存）
清楚流水线中所有年轻的指令
保存 PC 和寄存器
重定向到合适的异常处理过程

精确异常的优点：

便于调试程序
容易从异常恢复
容易重启过程
进入软件

单周期不需要，多周期需要

在控制 FSM 添加特殊的指向异常处理器的状态
只在精确状态时切换到处理器

精确异常数据路径

EPC 寄存器：保留造成异常的 PC
Cause 寄存器：保持造成异常的原因
异常处理器：在地址 0x80000180 开始

支持精确异常的方法：

重排序缓冲区
历史缓冲区
未来寄存器文件
检查点

重排序缓冲区 Reorder Buffer(ROB)：乱序完成指令，但是在使结果对架构状态可见之前重排序

当指令解码时，把下一个顺序项保留在一个特殊的叫重排序缓冲区（ROB）的缓冲区中
当指令完成时，把结果写回道 ROB 项中
当 ROB 中最老的指令无异常完成时，结果写回到寄存器文件或内存中

ROB 以硬件的队列实现：

ROB：保持所有被解码但没有退休的指令的硬件结构

ROB项

有效位用于跟踪结果的可读性，找出指令是否完成执行

我们可以使用内容可寻址的方法访问 ROB，即查找最新的寄存器：

ROB访问1

还可以使用间接访问，即将寄存器映射到一个 ROB 项

ROB访问2

可以发现，两种假的依赖已经被消除了，增加了寄存器名字空间到 ROB 大小

ROB 的缺点：需要访问 ROB 以得到还没有写入寄存器文件的值，延迟和复杂度都上升了

乱序执行 Out-of-Order Execution

也称动态指令调度

分发 dispatch：把指令发送到函数单元的动作

注意到顺序流水线的问题是一个未准备好的指令阻塞了更年轻的指令分发到函数单元

上图的第二条指令在等待第一条指令完成，但是第三条指令明明与前两条指令独立，可以先执行，却被第二条指令暂停了

乱序执行类似于数据流结构，但是并不暴露给 ISA

思想：将未准备好的指令移除出独立的指令的路

优点：延迟容忍：运行独立的指令在有一个长延迟的操作的情况下执行并完成

顺序执行vs乱序执行

OoO 执行：

将值的消费者而后生产者连接起来：寄存器重命名：每个数据值关联一个标签
在指令准备好执行前缓存：在重命名后插入到保留区 Reservation stations(RS) 中
指令需要跟踪源值的可读性：
- 在值生产后广播 broadcast 标签
- 指令将它们的源标签与广播标签比较，若相同，则源值准备好了
当一个指令的所有源值都准备好了，则发送指令到 FU 中
- 如果所有的源值都准备好了，则指令唤醒 wake up
- 如果多重指令醒着，则需要选择为每个 FU 选择一个

两个驼峰

乱序执行

关键路径：标签广播->值捕捉->指令唤醒

保存区：中心化 vs 分布式

精确异常：和之前一样

一条指令在执行完成后更新 RAT（前端寄存器文件 frontend register file），在退休后如果是最老的指令，则更新架构寄存器文件

乱序执行寄存器文件

可以发现寄存器中存了很多重复的值，可以将其存一个较小的指针，指向一个大寄存器表（物理 RF）

重复寄存器解决方案

乱序执行总结：

链接
缓存
跟踪可读性
发送

乱序执行实际上动态地找到了程序中的平行操作

超标量执行 Superscalar Execution

思想：一个周期获取，解码，执行，退休多条指令

硬件实现了同时获取的指令的依赖性

超标量执行和乱序执行是正交的概念

超标量执行

分支预测 Branch Prediction

处理控制依赖：

暂停流水线直到知道下一个获取的地址
猜测下一个获取地址（分支预测）
实施延迟分支（分支延迟槽）
做其他事（细粒度多线程）
减少控制流指令（预测执行）
两个可能的路径都获取（多路径执行）

最简单的方法：NextPC = PC + 4

优化方法：编译器提前预测两个分支执行的可能性，将概率高的放在顺序位置

摆脱控制流指令：

摆脱不必要的控制流指令——组合预测并检测一次
把控制依赖转化为数据依赖——预测执行（也叫做 if 转换）

分布预测 Branch Prediction

思想：预测下一条获取的地址

观察到对于一个直接条件分支，目标地址是相同的

思想：从之前的实例中存储目标地址，并用 PC 访问

叫做分支目标缓存 Branch Target Buffer(BTB)

分支目标缓存

静态分支预测：

总是不选择：编译器排列好了代码
总是选择：对于循环来说非常有优势
这两者的优点可以兼顾，即后向选择，前向不选择（BTFN），即循环总是选择，条件分支总是不选择

基于剖析 profile-based：编译器使用剖析运行决定每个分支的可能的方向

缺点：

需要在分支指令格式上有提示位
准确性依赖于动态分支表现
准确性依赖于剖析输入数据的代表性

进阶分支预测 Advanced Branch Prediction

基于程序 program-based：使用基于程序分析的启发式决定静态预测方向，例如预测循环总是选择，异常处理总是不选择

缺点：

启发式可能不具有代表性
需要编译器分析和 ISA 支持

基于程序员 programmer-based：程序员提供静态预测方向，通过在编程语言中使用 pragmas 实现

缺点：需要程序员、编程语言、编译器、ISA 支持

pragmas：使程序员能够向低层次表达提示的关键词，如 if(likely(x)),#pragma omp parallel

这三种静态技术的缺点都是无法适应动态改变

上次预测 last time predictor：猜测分支和其上次一样，需要在 BTB 中存储一个位

优点在于对于较大的 K 的循环，准确率非常高

上次预测状态机

可以观察到这种方法改变地太快了，只看到一次改变就改变了自己的看法

基于两位计时器的预测 tow-bit counter based prediction：每个分支和两位计时器关联，即提供了滞后

两位计时器滞后

两级预测 two-level Prediction：前两者都探索了上次预测，还可以从其他维度观察：

一个分支的结果可能而后其他分支的结果有关——全局分支关联
一个分支的结果可能和相同分支的过去结果有关（注意不是上次）——局部分支关联

全局分支关联 global branch correlation将分支结果和所有分支的全局历史关联，基于上次相同全局分支历史出现的分支结果预测分支

实现：

所有分支的全局历史——全局历史寄存器（GHR）
使用 GHR 索引记录结果的表

两级历史——GHR + GHR 处的历史

两级全局分支预测

改进：向全局预测器添加正在选择的分支的上下文

Gshare 预测器：用分支 PC 哈希 GHR

Gshare预测器

局部分支关联 local Branch correlation：有每个分支历史寄存器，基于上次相同局部分支历史出现的分支结果预测分支

两级历史——每个分支历史寄存器 + 历史寄存器值处的历史

两级局部分支预测

两级预测器分类：

BHR 可以是全局的，每个分支集的，每个分支的
PHT 可以是全局的，每个分支集的，每个分支的

这些方法各有适用的分支类型，无法对所有分支都适用

混合分支预测器 hybrid branch predictors：使用不止一个预测器，选择最佳的预测

有偏向分支：许多分支都偏向于一个方向
这些分支污染了分支预测结构
检测这些有偏向的分支，使用更简单的预测器预测他们

其他分支预测器类型：

循环分支检测器和预测器：计数循环迭代次数
感知机分支预测器：使用简单的机器学习算法赋权值
基于混合历史长度的预测器：使用不同历史长度的不同表

感知机 perceptron 是一个简化的神经元模型，也叫做二项分类器

输入向量 X，X 为历史寄存器的每个位
感知机学习向量的每个元素如何影响输出，并存储在内部的加权向量中
输出 Weight @ X + Bias > 0，即当前分支的预测结果

使用多重历史长度的预测器：有多个用不同的历史长度的 GHR 索引的 PHT

使用多重历史长度的预测器

分支自信度估计 branch confidence estimation：估计预测正确的可能性

实现：

记录过去 N 个分支的实例的正确/错误结果
基于这些匹配，猜测当前预测是否正确

延迟分支 delayed branch：延迟分支执行，在分支后的 N 条指令不管分支方向，总是执行

份额只必须和延迟槽指令独立

延迟分支

带压扁的延迟分支 delayed branch with squashing：在 ISA 中的语法：如果分支未选择，则延迟槽中的指令不执行

带压扁的延迟分支

缺点：延迟槽难以填满

VLIW 结构，脉动阵列结构，解耦合访问-执行 VLIW, Systolic Array Architectures, Decoupled Access-Execute

VLIW（Very Long Instruction Word）：编译器把独立的指令打包到一起，硬件同时获取和执行这些指令

不需要硬件上的依赖性检查

Lock-step 执行：如果有一个 VLIW 指令中的任何操作暂停，则所有同时的操作暂停

所以 VLIW 的问题在于操作延迟可能是可变的

可以发现 VLIW 在嵌入式，DSP，一些 GPU 中比较成功，其原因是容易找到平行操作

超级块 superblock：将频繁执行的基础块组合，形成一个单入口多出口的大块，就像直线的代码一样

缺点：

增加代码大小
需要重新编译
依赖剖析

其可用于编译器优化：

超级块代码优化

Systolic Array Architectures 脉动阵列结构：特定目的的加速器，现在常用于机器学习加速器

思想：用 PE 的阵列替代一个执行单元（PE）并小心地协调 PE 间的数据流

这种做法的好处：最大化在一个从内存中出来的数据上的计算

脉冲计算卷积

2D脉冲阵列计算

优点：I/O 带宽大

也可以使用流水线，把计算划分成多个阶段：

解耦合访问执行 decoupled access-execute(DAE)：通过两个分离的指令流，其通过 ISA 可见的队列通信，以解耦合访问和执行的操作

DAE

指令示例：

访问	执行
AEQ+z+10, A2	x4+x2*f AEQ
x, A2 +EAQ	EAQ+AEQ*f X6

这种方法的优点在于两个操作可以不用等待另一个操作

缺点：

编译器需要划分程序和管理队列
分支指令需要同步

SIMD 处理器 SIMD Processors

四种划分：

SISD：单指令操作单数据元素
SIMD：单指令操作多数据元素
- 阵列处理器，向量处理器
MISD：多指令操作单数据元素
- 脉动阵列结构
MIMD：多指令操作多数据元素
- 多处理器
- 多线程处理器

SIMD 的并发出现在对不同部分数据执行相同的操作，即采用了对不同数据的操作级别的平行

多处理元素（PE）

时间-空间对偶

阵列处理器 Array processor：同时使用不同空间操作多重数据
向量处理器 Vector processor：在相同空间以连续时间步数操作多重数据

存储多重数据元素：向量寄存器

每个向量数据寄存器 vector data register 保持 N 个 M bit 的值

向量寄存器

阵列处理器vs向量处理器

向量处理器：

向量寄存器
向量长度寄存器 VLEN
向量步长寄存器 VSTR

向量指令允许更深的流水线：

没有内部向量依赖
向量内部没有控制流
已知步长允许对所有向量元素的简单的地址计算
- 允许简单或更早的加载

Amdahl's Law：

\text{加速} = \frac{1}{1-f +\frac{f}{N}}

向量寄存器：

向量数据寄存器保存值
向量控制寄存器：VLEN，VSTR，VMASK
- VMASK 指示要操作哪个元素，如 VMASK[i] = (V[i] == 0)

向量函数单元：使用深的流水线执行元素操作

如果我们能每个周期开始加载一个元素，则元素可以连续周期被加载，方法就是堆积 bank 内存，通过 bank 交错元素

内存被划分到可以独立访问共享地址和数据总线的 bank 中

内存bank

如果步长 == 1 && 连续的元素交错在 bank && bank 的数量 >= bank 的延迟，则可以维持 1 元素/周期的吞吐量

向量链：数据从一个向量函数单元转发到另一个

向量链

还可以增加多个 bank 的端口

如果向量数据不在内存中以固定步长模式存储，则可以使用间接索引将其组合到向量寄存器中，这也对稀疏向量有益

gather/scatter 操作：向量使用索引向量加上基寄存器来产生加载和存储的地址

scatter操作

循环中的条件操作使用 Masked 操作

如果是双分支，则可以 Masked 计算 A 后取 Masked 的互补计算 B

Masked 有两种实现，简单实现和稠密时间实现

简单实现vs稠密时间实现

步长和 bank 要互质

减小 bank 冲突：

更多 bank
每个 bank 更多端口
更好的数据布局
更好的地址向 bank 的映射

图形处理单元 Graphic Processing Units

GPU 指令流水线像 SIMD 流水线一样运行，但是编程使用线程完成，即 GPU 是一个 SIMT 机器

执行相同指令的线程集合被硬件动态地分组到一个 warp 中

这个编程模型叫 SPMD

SIMT 的优点：

分别处理每个线程
灵活地分组线程到 warp 中

warp 可以在相同流水线上交错，即 warp 的细粒度多线程，通过这个容忍了延迟

warp执行

SIMD执行单元结构

warp指令级别并行

分支发散 branch divergence：warp 内部的线程分支到不同执行路径

可以找到相同 PC 的线程，动态地将它们分组到一个 warp 中

动态warp合并

以两级调度来处理长延迟的操作

内存概览，组织与技术 Memory Overview, Organization & Technology

内存的阵列组织：M bit 的值可以在每个独特的 N bit 的地址读写

内存的阵列组织

访问晶体管连接 bit 存储到 bitline，由 wordline 控制访问

访问控制

随着内存越来越大，速度也越来越慢，所以需要将内存划分成更小的阵列

DRAM 的层次结构：Channel -> rank -> bank -> subarrays -> Mats

Channel

module

rank

bank

chip

动态随机访问内存 dynamic random access memory(DRAM)：

电容充电状态储存值
电容通过 RC 电路泄漏，故需要 refresh

SRAM读

相变内存 phase change memory：非易失内存

内存层次结构与缓存 Memory Hierachy and Caches

由于速度、成本、容量等的权衡，就有了内存的层次结构

手动管理缓存（GPU，ML 加速器） vs 自动管理缓存

递归延迟等式：

T_i = t_i + m_i \cdot T_{i+1}

其中 $m_i$ 表示 miss 的概率， $t_i$ 表示访问的时间， $T_i$ 表示实际访问时间

三种映射方法：

更高的关联度：

更高的命中率
更慢的缓存访问时间
更贵的硬件

进阶缓存 Advanced Caches

驱逐方法：

最小最近访问的块 LRU：问题在于跟踪块的访问顺序

所以通常使用近似的 LRU，如

Not MRU（非最近使用）
层次结构 LRU：划分到 M 个组，跟踪 MRU 组和每个组中的 MRU
受害者-下一个受害者替换

集合痛打 set thrashing：一个程序工作集合大于集合关联性

当 thrashing 出现时，随机取代更好

在实践中，表现依赖于负载，LRU 和随机的平均命中率差不多，一般两者混合使用，通过集合采样选择

Balady's OPT：取代未来被引用最远的块

最优化 miss 比率，但是没有最优化执行时间，因为没有考虑 miss 的延迟

处理写：

是否写到下一级？

write-back：
- 在驱逐之前将多重写组合到一个块中
- 但需要 tag 中 dirty bit
write-through：
- 设计简单
- 缓存一致
- 但是带宽受限

写 miss 的时候是否分配缓存块？

分配：
- 组合写
- 写和读一样，处理更简单
- 但是需要整个缓存块的转移
不分配：
- 如果写的局部性差，则节约缓存空间

如果每次只写块的一部分，则可以使用子块 subblock 缓存

每个子块都有独立的有效和脏位
一次请求只分配一个子块

优点：

无需转移整个缓存块
转移更自由

缺点：

设计复杂
没有完全利用空间局部性

子块缓存

指令和数据缓存：

统一：

动态共享缓存空间
但是指令和数据会互相驱逐，即不保证都有空间
指令和数据在流水线的不同阶段访问，统一缓存的位置不易确定

故通常：

一级缓存分离——流水线约束
更高级缓存统一

流水线设计中的多级缓存：

一级缓存
- 受时钟周期影响
- 小，更低的关联；延迟很重要
- tag 和 data 储存并行访问
二级缓存
- 平衡 hit 比率和访问延迟
- 大而高的关联度；延迟没那么重要
- tag 和 data 储存顺序访问

顺序 serial：

只有一级缓存 miss 了，二级缓存才会访问

缓存性能：

缓存大小

过大：速度慢
过小：时间局部性利用率差，经常要替换数据

缓存大小

块大小

过大：
- 时间局部性利用差
- tag 开销大
过小：
- 空间局部性利用差
- 浪费带宽

块大小

更大的块：

填入时间长：关键字

先用关键字填充缓存块
立刻向处理器提供关键数据

浪费带宽：划分为子块

每个块有有效位和脏位

关联性：

大：miss 率低，延迟和花费大
小：花费小，延迟低

缓存 miss 的分类：

义务 miss：第一次引用地址会 miss
- 预获取
容量 miss：缓存太小，不能保存所有东西
- 更好地利用缓存空间
冲突 miss：不是前两者的 miss
- 更多关联

重建数据访问模式：

循环交换
分块
分离数据结构常用的域并把它们包装到一个分开的数据结构中

内存级别并行 Memory Level Parallelism(MLP)

内存级别并行

所以从这个角度看，miss 的花费是不一样的，孤立 miss 比并行 miss 更重要

多核系统中的缓存：

共享缓存：多个上下文使用一个硬件资源

优点：

提高容量利用率
动态划分可用缓存空间
维持一致性更简单

缺点：

资源争夺
访问慢

缓存一致性的解决方法：所有缓存窥探 snoop 互相的读写操作，如果一个处理器写到了一个块中，所有其他的缓存使块无效

预读 Prefetching

预读 prefetching：在数据被程序需要前读取它

可以减少延迟
减少义务 miss
不会有较大的错误预期的惩罚

带宽消耗

增加 window 的大小以忍受内存延迟

超前执行 runahead execution：从大的指令窗口中受益，可以维护内存级别的并行

目的是生成预读取

优点：

精确预读取
实现简单——绝大多数硬件已经有了
没有上下文的浪费
无需创建预执行线程

缺点：

额外执行指令
效率受可用的内存级别并行的限制
预读取距离受内存延迟限制

虚拟内存 Virtual Memory

页表过大——多级页表

指令获取或读写都需要至少两次内存访问——翻译查找缓冲 TLB

虚拟内存需要哦软件和硬件的支持，硬件组件叫 MMU

时钟页替代算法：

在内存中保持物理栈帧的循环列表
保持指针为最后检查的栈帧
当页被访问时，设置 PTE 中的 R 位
当一个栈帧需要被替代时，替代第一个 R 位没有设置的栈帧，顺时针清除遍历的 R bit

Row Hammer：

把物理内存填充满 PTE，其指向相同的物理文件
如果 PTE 中的一个 bit 翻转，则对应的虚拟内存地址指向错误的物理页，且有 RW 权限
攻击者可以读写页表，映射到任意拥有读写权限的内存

如果 TLB miss，则需要 walk 页表

缓存是虚拟地址还是物理地址？

虚拟
- 相同的 VA 映射到不同的 PA
- 不同的 VA 映射到相同的 PA
物理：延迟大

所以对于一级缓存，通常两者都使用；对于更高级的缓存，则延迟不是那么重要

L2 TLB 中的 4KB/2MB 结构有 2 步：

假设页表大小为 4 KB，访问，如果失败，进行下一步
假设页表大小为 2 MB，访问，如果失败，miss
即时间上的关联性

虚拟环境的虚拟内存原理相似，只是由软件实现