计组后半部分预习

计组前半部分可看计组期中复习笔记。

存储系统

常用半导体存储器

RAM
- SRAM （速度最快）
- DRAM → SDRAM → DDR SDRAM（DDR2、DDR3、DDR4、DDR5）
ROM（虽然叫 Read-Only Memory，但是有的可以写）
- EPROM
- E²PROM → Flash（NOR、NAND）

相联存储器

其中任一存储项内容作为地址来存取的存储器。

用途：快速查找、地址变换

如：Cache 的地址映射表，页表中的快表（TB）、变换旁路缓冲器（TLB）

主存储器

存储芯片的连接方式 ⭐️

字扩展（字数的扩展，即地址的扩展）
- 扩展的芯片不能同时选中
位扩展（位数的扩展）
- 扩展的芯片可以同时选中
位数和字数同时扩展

用存储器芯片构成主存模块

SRAM（主存与 CPU 速度协调）
EPROM
E²PROM
SDRAM — 内存条

多体交叉存储器

多体并行访问
多体交叉访问（和流水线类似）

高速缓冲存储器

主存与 Cache 的地址映射 ⭐️

以块为单位。

全相联：主存的任意一块可以映像到 Cache 的任意一块。
- Cache 地址：| Cache 块号 | 块内地址 |
- 主存地址：| 主存块号 Tag | 块内地址 |
- 变换：Cache 块号 $\xrightarrow{\text{目录表}}$ 主存块号
直接映射：主存的每一块只能映像到 Cache 的一个特定块。
- Cache 地址：| 块号 | 块内地址 |
- 主存地址：| 区号 Tag | 区内块号 Index | 块内地址 |
- 无需变换：所访问的主存区号与目录表中记录的主存区号相比较
组相联：组间直接映射，组内全相联。
- Cache 组数 = 区内块数
- Cache 地址：| 组号 | 组内块号 | 块内地址 |
- 主存地址（两种划分方法，看题目要求选择，一般用第二种）
  - ~~| 区号 | 区内组号 | 组内块号 | 块内地址 |~~
  - | 区号 Tag | 区内块号 Index | 块内地址 |
  - 相联存储器容量 = 8 × (Tag 位数 + 1 位有效位)

替换算法

直接映射无需替换算法（因为一次就替换全部）

随机替换算法（RAND）
先进先出替换算法（FIFO）
最不经常使用（最少使用）替换算法（LFU）：计数器位数多，实现困难
近期最少使用（最久未用）替换算法（LRU）
最佳替换算法（OPT）

更新策略

写回法
写直达法（全写法）

Cache 性能测量

命中率 $h=\frac{N_C}{N}\times 100\%$ $h = \frac{N _{C}}{N} \times 100%$
- $N$ ：CPU 访问主存次数
- $N_C$ ：CPU 访问命中 Cache 的次数
- 缺失率 $m=1-h$
平均访问时间 $T_A=T_C+(1-h)\times T_M$ $T_{A} = T_{C} + (1 - h) \times T_{M}$
- $T_C$ ：Cache 访问时间
- $T_B$ ：数据块装入 Cache 的时间
- $T_M$ ：主存访问时间，等于 $T_B+T_C$ ，而由于 $T_M\gg T_c$ ， $T_B\approx T_M$ 。
- 推导： $\begin{aligned}T_A&=h\times T_C+(1-h)\times T_M \\ &=T_C+(1-h)\times T_B \\ &=T_C+(1-h)\times T_M\end{aligned}$
加速比 $S_P=\frac{T_M}{T_A}=\frac{T_M}{T_C+(1-h)\times T_M}=\frac{1}{1-h+\frac{1}{r}}$ $S_{P} = \frac{T _{M}}{T _{A}} = \frac{T _{M}}{T _{C} + ( 1 - h ) \times T _{M}} = \frac{1}{1 - h + \frac{1}{r}}$
- $r=\frac{T_M}{T_C}$
- 可见随着命中率 $h$ 的增大，加速比 $S$ 提高。
成本 $C=(C_1\times S_1+C_2\times S_2)/(S_1+S_2)$ $C = (C_{1} \times S_{1} + C_{2} \times S_{2}) / (S_{1} + S_{2})$
- $C_i$ ：价格，1 为主存，2 为 Cache
- $S_i$ ：容量，1 为主存，2 为 Cache
- $S_1\gg S_2$

Cache 性能提升

多级 Cache 结构
降低 Cache 的缺失率
1. 缺失类型
  - 强制缺失：第一次访问
  - 容量缺失：容量有限，不包含所需的所有主存块（增大 Cache 容量可减少）
  - 冲突缺失：主要发生在直接映射
2. 合理设计 Cache 块尺寸
3. 合理增加 Cache 容量
4. 合理设置相联度
5. 硬件预取（可解决强制缺失）
6. 编译优化
减少 Cache 开销

虚拟存储器

其实和 Cache 那块内容很相似。

地址映射：全相连
地址变换：MMU
页式虚拟存储器 ⭐️
- 多级页表
  - 虚地址：| 虚页号 (V 位) | 页面偏移 (P 位) |
  - $\left(\frac{2^P}{m}\right)^i=2^V$
  - 页表级数 $i=\left\lceil\frac{V}{P-\log_2m}\right\rceil$ $i = ⌈ \frac{V}{P - l o g _{2} m} ⌉$
    - $P$ ：页面偏移的位数
    - $V$ ：虚页号的位数
    - $m$ ：页表项编址单元位数
- 快慢表
  - 快表：CPU 内部的 TLB
  - 慢表：主存中的页表
- 实存空间、虚存空间、页面大小（决定页面偏移位数）

外部存储器（辅助存储器）

磁表面存储原理及记录方式

$\text{编码效率}η=\frac{\text{位密度}}{\text{最大磁化翻转次数}}$

磁盘存储器

磁盘结构
- 磁道（记录面的同心圆）
- 扇区（磁道的段）
- 柱面（相同序号的磁道构成的圆柱面）
数据应尽可能放在同一柱面或者相邻柱面，缩短寻道时间
技术指标 ⭐️
- 道密度：道 / mm
- 位密度：bit / mm（最靠近中心的磁道）
- 非格式化容量 = 位密度 × 内圈磁道周长 × 每个记录面磁道数 × 记录面数
- 格式化容量 = 每个扇区的字节数 × 每道道扇区数 × 每个记录面磁道数 × 记录面数
- 平均访问时间 = 平均寻道时间 + 平均等待时间 + 数据传输时间
  - 平均等待时间：磁盘旋转一周所用时间的一半
- 转速：RPM（转 / 分钟）
- 数据传输速率 = 每个扇区的字节数 × 每道扇区数 × 磁盘转速
与计算机主机的连接

磁盘阵列 RAID

由独立的磁盘组成的具有冗余特性的阵列。

指令系统

存储模式

数据存储顺序
- 大端存储：最低有效字节存储在最高地址位置
- 小端存储：最低有效字节存储在最低地址位置
边界对齐
- 16 位字长的数据：起始地址为 2 的整数倍。
- 32 位字长的数据：起始地址为 4 的整数倍。
- 64 位字长的数据：起始地址为 8 的整数倍。
堆栈
- PUSH 操作： $\text{(SP)}-i\to\text{SP},\text{(R1)}\to\text{M}_\text{SP}$
- POP 操作： $\text{M}_\text{SP}\to\text{(R1)},\text{(SP)}+i\to\text{SP}$
冯诺伊曼结构和哈佛结构
- 前者数据和指令存一起，后者数据指令分开存

指令类型

数据传送类（MOV）
运算类
- 算术运算类
- 逻辑运算类
输入/输出类
- 统一编址的情况
- 独立编址的情况
程序控制类
- 转移指令
- 循环控制指令
- 过程调用和返回指令
- 程序自中断指令
系统控制类（通常是特权指令，虚存管理、任务切换、改变处理器工作模式）

指令设计

指令格式

二地址指令：| 操作码 | 地址码 1 | 地址码 2 |

还有一地址指令、零地址指令……

定长操作码
变长操作码（扩展操作码）

操作码设计

定长操作码
- $N$ 条指令，所有指令均用 $n$ 位编码： $N\le 2^n$ 。
变长操作码 ⭐️
- 原则：短码不能是长码的前缀
- 扩展操作码设计
- 平均码长： $\sum_{i=1}^n p_i\times l_i$
- 设计
  - 霍夫曼编码
  - 特定规则
  - 地址码数量

寻址方式

隐含寻址：操作数的位置默认，无需给出。
立即寻址：操作数在指令中。
寄存器寻址：操作数在指令指定的寄存器中。
直接寻址：操作数在主存中，主存地址在指令中。
寄存器间接寻址：操作数在主存中，主存地址在指令指定的寄存器中。
相对寻址：跳转目标地址 $\text{EA}=\text{(PC)}+\text{A}$
基址寻址：操作数在主存中， $\text{EA}=\text{(基址寄存器)}+\text{A}$

指令系统结构的发展

复杂指令集计算机 CISC

用一条指令代替一串指令
增加新的指令
增强指令功能
设置功能复杂的指令
增加寻址方式增加数据表示方式

精简指令集计算机 RISC

指令系统简单
- 指令条数少、格式少、长度固定、功能简单
- 寻址方式少
- 采用硬布线控制逻辑（不用或少用微程序控制）
Load/Store结构
- 只有LOAD和STORE指令可以访问存储器
- 寄存器多
- 寄存器窗口技术
十分重视提高流水线的执行效率
- 大部分指令可以单周期执行完成
- 延迟转移技术
- 指令流调整技术
十分强调优化编译技术的作用

中央处理器（CPU）

CPU 的内部结构

微操作与微命令

微操作：CPU 的原子操作，以含有一个寄存器的传递操作为标志。如： $\text{AR}\gets\text{PC}$

微命令：控制微操作完成的控制信号，由控制器产生。如： $\text{PC}_\text{out},\text{AR}_\text{in}$

微操作流程

时序信号产生
- 指令周期：完成一条指令
- CPU 周期：完成一个子周期
- 节拍周期：完成一个微操作
取址周期
- 一个简单的取址周期可由 3 个步骤、4 个微操作组成
  - T1: $\text{AR}\gets\text{PC}$
  - T2: $\text{DR}\gets\text{Memory[AR]}$
  - T3: $\text{PC}\gets\text{PC}+\text{I},\text{IR}\gets\text{DR}$ （ $\text{I}$ 为指令长度 byte）

微程序控制器设计

微指令

微指令：一个节拍内出现的一组微操作进行描述的语句。

微程序 / 固件：一个微指令序列。

微指令设计

微指令地址的生成
- 两地址方式（断定方式）
- 单地址方式（计数方式，增量方式）
- 可变格式
编码
- 水平型：多个微操作同时发生
- 垂直型：类似于机器指令
相容性：可在同一时间有效的控制信号。
互斥性：不能在同一时间有效的控制信号。

微程序设计 ⭐️

看例题。

CPU 性能测量与提高

CPU 性能测量 ⭐️

CPU 时间 $T_\text{CPU}=N\times T_\text{CLK}=\frac{N}{f_\text{CLK}}$
- $N$ ：CPU 时钟周期数
- $T_\text{CLK}$ ：时钟周期时间
- $f_\text{CLK}$ ：时钟频率
CPI：每条指令执行所用时钟数。
- $I$ ：指令数
- $CPI=\frac{1}{I}\sum_{i=1}^n (CPI_i\times I_i)=\sum_{i=1}^n (\frac{I_i}{I}\times CPI_i)$
- $T_\text{CPU}=I\times CPI\times T_\text{CLK}=\frac{I\times CPI}{f_\text{CLK}}$
IPC：每时钟周期执行的指令数
MIPS：每秒钟执行的百万指令数
- $T$ ：执行时间
- $MIPS=\frac{I}{T\times 10^6}=\frac{f_\text{CLK}}{CPI\times 10^6}$
FLOPS：每秒钟完成的浮点运算次数
- $M$ ：浮点运算次数
- $FLOPS=\frac{M}{T}$
- 度量单位：MFLOPS、GFLOPS、TFLOPS…

提高 CPU 速度的策略

多核技术
多线程技术

流水线技术与指令级并行

流水线处理的概念

若将一重复的处理过程分解为若干子过程，每个子过程都可在专用设备构成的流水线功能段上实现，并可与其它子过程同时执行，这种技术称为流水技术。

流水线的类型

按流水线位于计算机系统的层次划分
- 系统级流水线 / 宏流水线（多计算机系统串行）
- 处理器级流水线
- 部件级流水线
按流水线功能的强弱划分
- 单功能流水线
- 多功能流水线
  - 静态流水线
  - 动态流水线
按流水线是否有反馈回路划分
- 线性流水线
- 非线性流水线（需要流水线调度）
按流水线输出端任务流出顺序与输入端任务流入顺序是否相同划分
- 顺序流动流水线（入出顺序相同）
- 异步流动流水线（入出顺序不同）
  - 无序流水线
  - 错序流水线
  - 乱序流水线
按流水线一次处理对象的数量划分
- 标量流水线
- 超标量流水线
- 向量流水线
- 超长指令字流水线

浮点运算流水线

浮点加减 / 乘除流水线

阶码比较
尾数对齐
尾数加 / 减
规格化

指令流水线

指令流水线策略

增加指令流水线深度
- 局限性
  - 指令执行过程的细化有限度
  - 随着深度增加，缓冲器增多，延迟加大，性能提高受阻碍
增加指令流水线条数

RISC-V 基本指令流水线

设计指令获取、执行的硬件逻辑电路
对硬件逻辑分段
- 尽量使每段处理功能相对独立，处理时间基本均衡。
- 保证当前指令在执行期间，指令流和数据流始终一个流向。
- 分段结果己是最细的划分：每段中仅有一个用于指令处理的功能部件。
段间加入流水线寄存器
设计流水线控制器

流水线性能度量 ⭐️

时空图

吞吐率

单位时间内，流水线所完成的任务数或输出结果的数量。
最大吞吐率 $TP_\text{max}$ ：流水线在达到稳定状态后所得到的吞吐率。
- 各段运行时间相等： $TP_\text{max}=\frac{1}{T_\text{CLK}}$
- 各段运行时间不等： $TP_\text{max}=\frac{1}{\max\{\tau_i\}}=\frac{1}{\tau}$
实际吞吐率 $TP$ ：流水线 $m$ 段组成，完成 $n$ 个的任务吞吐率为实际吞吐率。
- $m$ $m$ 段流水线，各段运行时间相等，为一个时钟周期 $T_\text{CLK}$ $T_{CLK}$
  - 完成 $n$ 个任务所用时间： $T_n(m)=(m+(n-1))\times\tau=(m+(n-1))\times T_\text{CLK}$
  - 实际吞吐率： $TP=\frac{n}{T_n(m)}=\frac{n}{(m+(n-1))\times T_\text{CLK}}=\frac{TP_\text{max}}{1+\frac{m-1}{n}}$
- 各段运行时间不等
  - 完成 $n$ 个任务所用时间： $T_n(m)=\sum_{i=1}^m\tau_i+(n-1)\times\max\{\tau_i\}$
  - 实际吞吐率： $TP=\frac{n}{T_n(m)}=\frac{n}{\sum_{i=1}^m\tau_i+(n-1)\times\max\{\tau_i\}}$
使用 $MIPS$ 表示： $TP=MIPS\times 10^6=\frac{f_\text{CLK}}{CPI}$
- 单流水线计算机系统：由于 $CPI_\text{最佳}=1$ ，故 $TP_\text{max}=f_\text{CLK}$

加速比

加速比 $S$ 定义为等功能非流水线执行时间 $T(1)$ 与流水线执行时间 $T(m)$ 之比。

$S=S_n(m)=\frac{T_n(1)}{T_n(m)}$

$m$ $m$ 段流水线， $n$ $n$ 个任务，若每段运行时间均为 $τ$ $τ$ 。
- $T_n(1)=n\cdot m\tau$
- $T_n(m)=mτ+(n-1)\cdot\tau$
- $S_n(m)=\frac{mn}{m+n-1}=\frac{m}{1+\frac{m-1}{n}}$
- 可见，增大指令流水线的级数和送入流水线的指令数均可提高运行速度。

效率

效率即流水线的设备利用率。流水线有通过（填充）时间和排空时间，效率 $E<1$ 。

各段运行时间相等

$m$ 个功能段， $n$ 个任务，各段运行时间为 $τ$ ，各段效率 $e_i$ 相等，即 $e_i=\frac{nτ}{T_n(m)}$

总效率 $E=\frac{1}{m}\sum_{i=1}^{m}e_i=\frac{nτ}{T_n(m)}=\frac{n}{m+n-1}=\frac{1}{1+\frac{m-1}{n}}$

可见当 $n \gg m$ 时， $E\approx 1$ 。

各段运行时间不等

E=\frac{n\text{ 个任务占用的时空区}}{m\text{ 个段总的时空区}}

指令流水线的性能提高

结构相关 / 冒险

部分功能单元没有充分流水
- 解决：将流水线设计得更合理
资源冲突：两个以上需要同时使用硬件资源
- 解决
  - 增加资源副本
  - 改变资源以能够并发使用
    - 主存访问冲突：哈佛结构（指令和数据分离）
    - 两个加法器：ALU、地址加法器
  - 延迟（或暂停）冲突段 / 在冲突段插入流水线气泡

数据相关 / 冒险

操作数未有效生成，就被作为后续指令的操作数
类型
- 先写后读（RAW，Read After Write）
- 先读后写（WAR）
- 写后写（WAW）
解决
- 采用转发/直通/相关直接通路技术
- 增加专用硬件（推后法）
- 利用编译器
- 对寄存器读写做特别设计（RISC-V）

控制相关 / 冒险

对条件分支指令的处理方法
1. 冻结流水线：检测到分支指令就清除紧随分支并插入气泡。
2. 静态分支预测
  - 不会发生
  - 总会发生
  - 编译器预测
  - 测试法
3. 动态分支预测
  - 分支历史表（分支预测缓存）
  - 分支历史移位寄存器
4. 延迟分支：在转移指令之后插入没有数据相关或控制相关的有效指令
带转移开销的流水线性能
- 控制相关对流水线性能造成的损失远比数据相关要大得多。
- $\text{有停顿流水线的实际 CPI}=\text{理想 CPI}+\frac{\text{各种相关造成的停顿周期数}}{\text{指令数}}$
- $\text{带转移开销流水线的加速比}=\frac{\text{流水线深度}}{\text{有停顿流水线的实际 CPI}}$

提高指令级并行的技术

乱序执行
推测执行

多发射处理器

超标量
超长指令字处理器（VLIW）

总线与输入 / 输出系统

总线类型

按连接层次
- 片内总线
- 系统总线
- 通信总线
按数据位数
- 并行总线
- 串行总线
按用法
- 专用总线
- 公用（共享）总线

总线的信息传输方式

过程
1. 传输请求
2. 总线仲裁
3. 部件 / 设备寻址
4. 数据传输
  - 并行传送方式
  - 串行传送方式
  - 分时传送方式
  - 消息传送方式
5. 总线释放
通信方式
- 同步通信方式
  - 速度快，逻辑简单
  - 缺点：时钟速率受慢速设备限制
- 异步通信方式
  - 无时钟信号线
  - 使用握手协议

总线仲裁

集中式仲裁
- 链式查询方式（菊花链）：离总线控制器越近优先级越高
- 计数器定时查询方式（轮询）
- 独立请求方式

	菊花链	轮询	独立请求
线数	$3$	$2+[\log_2n]$	$2n+1$
可扩充性	好	差	差
可靠性	低	高	高
优先级	固定	可变	可变
总线分配速度	慢	慢	快

分布式仲裁

典型的总线

系统总线（内总线）
- ISA 总线
- PCI 总线
- PCIe 总线
通信总线（外总线）
- RS-232C
- USB
- SCSI
- SAS
- ATA
- SATA

输入输出技术

程序查询方式
中断方式
直接存储器存取（DMA）
I/O 通道

并行体系结构

SISD: 单指令流单数据流（串行计算机）
SIMD: 单指令流多数据流
- 阵列处理机
- 向量处理机
MIMD: 多指令流多数据流
- 多处理器系统（共享内存）
  - UMA：每个处理器 / 内核访问内存的时间一样
  - NUMA：……不一样
- 多计算机系统（不共享内存，通信采用消息机制）
  - MPP：大规模并行处理机（高性能）
  - Cluster：集群（性价比
  - 网格（客户端 — 服务器，计算任务只在客户端节点进行，服务器进行任务分发和结果汇总）