计组后半部分预习

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

存储系统

常用半导体存储器

• 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 — 内存条

多体交叉存储器

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

高速缓冲存储器

主存与 Cache 的地址映射 ⭐️

以块为单位。

1. 全相联：主存的任意一块可以映像到 Cache 的任意一块。

   • Cache 地址：| Cache 块号 | 块内地址 |
   • 主存地址：| 主存块号 Tag | 块内地址 |
   • 变换：Cache 块号 $\xrightarrow{目录表}$ 主存块号

2. 直接映射：主存的每一块只能映像到 Cache 的一个特定块。

   • Cache 地址：| 块号 | 块内地址 |
   • 主存地址：| 区号 Tag | 区内块号 Index | 块内地址 |
   • 无需变换：<u>所访问的主存区号</u>与<u>目录表中记录的主存区号</u>相比较

3. 组相联：组间直接映射，组内全相联。

   • Cache 组数 = 区内块数
   • Cache 地址：| 组号 | 组内块号 | 块内地址 |

   • 主存地址（两种划分方法，看题目要求选择，一般用第二种）

     • | 区号 | 区内组号 | 组内块号 | 块内地址 |
     • | 区号 Tag | 区内块号 Index | 块内地址 |
     • 相联存储器容量 = 8 × (Tag 位数 + 1 位有效位)

替换算法

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

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

更新策略

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

Cache 性能测量

• 命中率 $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_C$：Cache 访问时间
  • $T_B$：数据块装入 Cache 的时间
  • $T_M$：主存访问时间，等于 $T_B+T_C$，而由于 $T_M\gg T_c$，$T_B\approx T_M$。
  • 推导：$\begin{align}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{align}$

• 加速比 $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_i$：价格，1 为主存，2 为 Cache
  • $S_i$：容量，1 为主存，2 为 Cache
  • $S_1\gg S_2$

Cache 性能提升

1. 多级 Cache 结构

2. 降低 Cache 的缺失率

   1. 缺失类型

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

虚拟存储器

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

• 地址映射：全相连
• 地址变换：MMU

• 页式虚拟存储器 ⭐️

  • 多级页表

    • 虚地址：| 虚页号 (V 位) | 页面偏移 (P 位) |
    • $\left(\frac{2^P}{m}\right)^i=2^V$

    • 页表级数 $i=\left\lceil\frac{V}{P-\log_2m}\right\rceil $

      • $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$

  • 设计

    • 霍夫曼编码
    • 特定规则
    • 地址码数量

寻址方式

1. 隐含寻址：操作数的位置默认，无需给出。
2. 立即寻址：操作数在指令中。
3. 寄存器寻址：操作数在指令指定的寄存器中。
4. 直接寻址：操作数在主存中，主存地址在指令中。
5. 寄存器间接寻址：操作数在主存中，主存地址在指令指定的寄存器中。
6. 相对寻址：跳转目标地址 $\text{EA}＝\text{(PC)}+\text{A}$
7. 基址寻址：操作数在主存中，$\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}$

微操作流程

1. 时序信号产生

   • 指令周期：完成一条指令
   • CPU 周期：完成一个子周期
   • 节拍周期：完成一个微操作

2. 取址周期

   • 一个简单的取址周期可由 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 速度的策略

• 多核技术
• 多线程技术

流水线技术与指令级并行

流水线处理的概念

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

流水线的类型

• 按流水线位于计算机系统的层次划分

  • 系统级流水线 / 宏流水线（多计算机系统串行）
  • 处理器级流水线
  • 部件级流水线

• 按流水线功能的强弱划分

  • 单功能流水线

  • 多功能流水线

    • 静态流水线
    • 动态流水线

• 按流水线是否有反馈回路划分

  • 线性流水线
  • 非线性流水线（需要流水线调度）

• 按流水线输出端任务流出顺序与输入端任务流入顺序是否相同划分

  • 顺序流动流水线（入出顺序相同）

  • 异步流动流水线（入出顺序不同）

    • 无序流水线
    • 错序流水线
    • 乱序流水线

• 按流水线一次处理对象的数量划分

  • 标量流水线
  • 超标量流水线
  • 向量流水线
  • 超长指令字流水线

浮点运算流水线

浮点加减 / 乘除流水线

1. 阶码比较
2. 尾数对齐
3. 尾数加 / 减
4. 规格化

指令流水线

指令流水线策略

1. 增加指令流水线深度

   • 局限性

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

RISC-V 基本指令流水线

1. 设计指令获取、执行的硬件逻辑电路

2. 对硬件逻辑分段

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

流水线性能度量 ⭐️

时空图

吞吐率

• 单位时间内，流水线所完成的任务数或输出结果的数量。

• 最大吞吐率 $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$ 段流水线，各段运行时间相等，为一个时钟周期 $T_\text{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$ 段流水线，$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. 总线释放

• 通信方式

  • 同步通信方式

    • 速度快，逻辑简单
    • 缺点：时钟速率受慢速设备限制

  • 异步通信方式

    • 无时钟信号线
    • 使用握手协议

总线仲裁

• 集中式仲裁

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

• 分布式仲裁

典型的总线

• 系统总线（内总线）

  • ISA 总线
  • PCI 总线
  • PCIe 总线

• 通信总线（外总线）

  • RS-232C
  • USB
  • SCSI
  • SAS
  • ATA
  • SATA

输入输出技术

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

并行体系结构

• SISD: 单指令流单数据流（串行计算机）

• SIMD: 单指令流多数据流

  • 阵列处理机
  • 向量处理机

• MIMD: 多指令流多数据流

  • 多处理器系统（共享内存）

    • UMA：每个处理器 / 内核访问内存的时间一样
    • NUMA：……不一样

  • 多计算机系统（不共享内存，通信采用消息机制）

    • MPP：大规模并行处理机（高性能）
    • Cluster：集群（性价比
    • 网格（客户端 — 服务器，计算任务只在客户端节点进行，服务器进行任务分发和结果汇总）