序

这是北航计算机组成理论概要。

計組，
終結。

概述

计算机基本组成与结构

计算机基本组成

硬件
- 运算器
- 存储器
- I/O
- 控制器
软件
- 系统软件（操作系统）
- 应用程序

计算机总线结构

总线Bus：符合一定标准的一组公用信息通道。

计算机层次结构

高级语言 -> 虚拟机 M3
  |           |
  |           |
汇编语言 -> 虚拟机 M2
  |           |
  |           |
机器语言 -> 实机 M1

指令集系统

计算机中数的表示

关于数制，参考这里。

无符号数
有符号数
浮点数
- IEEE 754：符号Sign，阶码Exponent，尾数Mantissa。
布尔值
- 真1，假0
西文字符
- ASCII
汉字字符
- GB2312
- CJK
- Unicode

计算机基本工作原理

机器指令
- 操作码
- 操作数地址
程序
- 程序计数器Programme Counter
冯·诺伊曼计算机的特点
- 由运算器，存储器，控制器和 I/O 组成
- 指令和数据的储存没有区别，放在存储器中按地址访问
- 指令由操作码和地址组成
摩尔定律

组合逻辑电路

逻辑代数

基本概念

逻辑代数 L = { K, ∨, ∧, ￢, 0, 1}，其中 K 为逻辑变量集。
- 与 ·
- 或 +
- 非
- 异或、同或等
- 运算优先级：() -> ￢ -> ∧ -> ⊕ -> ∨
逻辑门符号表示
公理系统
- A != 0 -> A = 1; A != 1 -> A = 0;
- 0 · 0 = 0; 1 + 1 = 1;
- 1 · 1 = 1; 0 + 0 = 0;
- 0 · 1 = 0; 1 + 0 = 1; 1 · 0 = 0; 0 + 1 = 1
- ￢0 = 1; ￢1 = 0;

定律、定理和规则

基本定律
- 交换律
- 结合律
- 分配律
- 0-1 律
- 互补律
基本定理
- 重叠律 A + A = A; A · A = A;
- 吸收律：两个乘积项中，若有一个乘积项的部分因子，恰好是另一个乘积项的全部，则这个乘积项是多余的：A + AB = A
- 另一个吸收律：A + ~AB = A + B
  - 证明如下
  1
  2
  3
  4
  A + ~AB = A(1 + B) + ~AB
  = A + AB + ~AB
  = A + B(A + ~A)
  = A + B
- 还原律：负负得正
- 德摩根律
- 更多……
规则
- 代入规则
- 反演规则：+ · 互换，0 1 互换，变量变为反变量，得到反函数
- 对偶规则：+ · 互换，0 1 互换，变量保持不变，得到对偶式

逻辑函数

与或式 AB + CD
或与式 (A + B)(C + D)
与或非式 ￢(AB + CD)
最小项表达式：最小项构成的与或式（积之和式）（标准与或式）
- 把输出为 1 的输入组合写成乘积项的形式，其中取值为 1 的输入用原变量表示，取值为 0 的输入用反变量表示，然后把这些乘积项加起来
- 最小项：n 个变量构成的与式中，每个变量或其反变量有且仅有一次出现
- n 个变量有 2ⁿ 个最小项
最大项表达式：最大项构成的或与式（和之积式）（标准或与式）
- 把使输出为 0 的输入组合写成和项的形式，其中取值为 0 的输入用原变量表示，取值为 1 的输入用反变量表示，然后把这些和项乘起来
- 最大项：n 个变量构成的或式中，每个变量或其反变量有且仅有一次出现
- n 个变量有 2ⁿ 个最大项
逻辑函数化简
- 最简与或表达式：乘积项最少，同时乘积项中的变量尽可能少
- 最简或与表达式：和项最少，同时和项中的变量尽可能少
  - 利用对偶规则化为与或表达式，得到最简与或表达式，利用对偶规则化为最简或与表达式
- 卡诺图

逻辑门电路

晶体管和 MOS 管

P 型半导体：带正电的空穴导电
N 型半导体：带负电的自由电子导电
PN 结：P 型和 N 型制作在一起
- 正向偏置：正极接 P 区，负极接 N 区，PN 结导通
- 反向偏置：正极接 N 区，负极接 P 区，PN 结截止
晶体二极管
- 正向导通：外加电压大于开启电压
- 反向截止：外加反向电压或电压小于开启电压
- 击穿：反向电压大于阈值（0.7V），二极管被击穿，失去单向导电性
晶体三极管
- 导通：U_BC > 0, U_BE > 0.7V
- 截止：U_BC < 0, U_BE < 0.7V
MOS 管
- 导通：V_GS > 开启电压
- 截止：V_GS = 0

门电路

与或非门的实现方式
CMOS 和 TTL 的对比
- CMOS 功耗相对低，抗干扰能力相对强，带载能力强
- TTL 功耗相对高，速度相对快，抗干扰能力相对弱

基本组合逻辑部件设计

半加器：两个 1 位二进制数相加求和，并向高位进位，不考虑低位进位
全加器：两个 1 位二进制数相加求和，并向高位进位，考虑低位进位
多位加法器
- 并行加法器——串行进位
- 并行加法器——并行进位
溢出判断
乘法器
数值比较器
ALU（运算逻辑单元电路）
编码器
- 2ⁿ 线 — n 线编码器（独热编码）
- 优先编码器（输出优先级最高的输入信号对应编号的反码）
译码器
- n 线 — 2ⁿ 线译码器
- 显示译码器（七段码等）
多路选择器多路复用器，MUX
- 8 选 1 MUX
竞争与冒险
- 竞争：某个输入变量通过两条或两条以上的路径传输到输出端，由于每条路径的延迟不同，导致不同路径的数据到达输出端的时间又先后
- 冒险：门电路由于输入端的竞争，在输出端出现尖峰干扰信号毛刺的现象
- 核心原因：门电路的延迟
- 代数法判断：逻辑函数 F 可以简化为 F = A + ~A 或 F = A · ~A
- 卡诺图法
- 消除竞争冒险

时序逻辑电路

锁存器和触发器

触发器Flip-Flop, FF是实现电路记忆功能的基本单元电路
- 两个互非的输出 Q 和 ~Q，Q 称为状态变量
- Q = 0 称为 0 态，Q = 1 称为 1 态
- Qⁿ 称为原态，Qⁿ⁺¹ 称为次态
RResetSSet 锁存器
- 与非门 RS 锁存器
- 或非门 RS 锁存器
- 输入：~R，~S
- 保持：~R = 1，~S = 1
- 置 0：~R = 0， ~S = 1 （低电平有效）
- 置 1：~R = 1，~S = 0 （低电平有效）
- 非法：~R = ~S = 0 （产生竞争）
- 约束条件：~R + ~S = 1
- 特性方程：反映次态、原态和输入之间关系的函数表达式：
$Q^{n+1}=S_D\bar{R}_D+\bar{S}_D\bar{R}_DQ^{n}\\ = S_D+\bar{R}_DQ^n$
- 状态转移图
- 时序图
钟控 RS 锁存器
- 加入时钟信号CP，高电位（或低电位）时改变锁存器状态，因此为电位触发方式的锁存器
- 亦称同步锁存器
- CP = 0 时，~S 和 ~R 恒为 1，保持；clk = 1 时，由 ~S 和 ~R 决定
- 仍有约束条件
钟控 D 锁存器
- 将 R，S 两个输入端换为一个输入端 D，S = D，R = ~D，保证二者恒为互非
- 特性方程：
$Q^{n+1} = D\quad(CP=1) \\ Q^{n+1} = Q^n\quad(CP=0)$
D 触发器
- 由两个反相的 D 锁存器构成
- 锁存器 L1 称为主Master锁存器，L2 称为从Slave锁存器
- 触发器是时钟有效沿触发，锁存器是电位触发
- 增加使能端
- 在时钟信号上一般不要设置逻辑，否则可能因延迟导致时序错误
- 增加复位端
  - 同步复位：复位信号有效和时钟沿有效才复位
  - 异步复位：复位信号有效则复位
JK 触发器
- 在钟控 RS 锁存器基础上，把 ~R = 1; ~S = 1 的情况变为翻转功能
- J = ~S, K = R
- 翻转：Qⁿ⁺¹ = ~Qⁿ
- 特性方程
$Q^{n+1}=J\bar{Q}^n+\bar{K}Q^n$
- 状态转换图

有限状态机

关于有限状态机，参考这里。

同步时序电路
- 每个电路元件都是组合逻辑或寄存器，且至少有一个寄存器
- 每一个环路至少有一个寄存器
- 所有寄存器接受同一个时钟信号
- 可以描绘成有限状态机
有限状态机
- 次态逻辑
- 状态存储
- 输出逻辑
- Moore 机
  - 输出信号与当前状态有关
- Mealy 机
  - 输出信号与当前状态及当前输入信号有关
- 必须有时钟信号和复位信号
- 状态编码方式
  - 二进制编码
  - 格雷编码
  - 独热编码

时序逻辑电路设计分析

寄存器
- 触发器和控制门电路组成
  - 一个触发器存储一位
  - 控制门电路保证各触发器同时接收数据
- 写/读/复位清零
- 边沿或电位触发
- 数据寄存器
  - 边沿触发器组成
- 数据锁存器
  - 电位触发器组成
- 移位寄存器
  - 具有移位功能的寄存器。每来一个时钟脉冲，寄存器中数据就依次向左或向右移一位
计数器
- 统计输入的脉冲个数
- 同步计数
  - 各触发器同时翻转，工作频率高
- 异步计数
  - 脉冲信号只作用于最低位触发器，高位触发器待低位触发器翻转后才能翻转，工作频率低
- 进制
- 加法/减法
时序电路的时序
- 建立Setup时间：触发时钟沿之前，输入必须稳定的时间
- 保持Hold时间：触发时钟沿之后，输入必须稳定的时间
- 孔径时间：T_Setup + T_Hold
- Clock-to-Q 时间：从触发时钟边沿开始到输入稳定的时间
- 时钟周期 >= T_CTQ + T_CDL最长路径延迟 + T_Setup + 时钟偏移（一般忽略）
- T_CTQ + T_CDS最短路径延迟 >= T_Hold，否则无法锁存输入，因为在上一个输入的保持时间内，输入发生了变化

主存储器

概述

性能指标

访问时间 T_A
- RAM：访问时间指读或写操作所用时间，即从给定地址到存储器完成读或写操作所需时间
- 其它：指将读写机构定位到目标位置所需的时间
存储周期 T_C
- 仅对 RAM 而言：指两次访问存储单元间的最小时间间隔
- T_C > T_A
带宽/数据传输率
存储器的性能特征：成本低的容量大，速度慢；成本高的容量小，速度快

存储单元电路

基本要求
- 具有两种稳定状态，表示 0 和 1
- 可以实现状态写入
- 可以实现状态感知
SRAM 存储单元电路
DRAM 存储单元电路
ROM 存储单元电路

非易失存储器

相变存储器PCM
- 非易失
- 空闲时功率低
- 延迟高
- 活跃时功率高
- 寿命短
自旋转矩磁随机存取存储器STT-MRAM
忆阻器Memristor

存储器芯片结构

基本描述
- 字单元数 * 每个字单元的位数例如 1K * 2：1024 个字单元，每个字单元 2 位。
- 存储位元数：字单元数 * 每个字单元的位数，如 1024 * 2 = 2048
- 地址线数：按字单元寻址，1024（2¹⁰）个字单元，需要 10 条地址线
- 数据线数：一次访问一个字单元，每个字单元 2 位，需要 2 条数据线
- 2ⁿ * m 个存储位元，需要 n 条地址线和 m 条数据线
二维地址结构
- （行/列）地址线通过 n - 2ⁿ 译码器变成（行/列）选择线，因此 n 根地址线表明有 2ⁿ 根选择线
- SRAM 的情况：例如 4096 * 4：2¹⁴ 个存储位元，划为 2⁷ * 2⁷ 的存储矩阵。一行 2⁷ = 128 个存储位元，每 4 个为 1 字单元，共 32（2⁵）个字单元。
  - 行地址线数：2⁷ 个存储位元，使用 7 条地址线（X 译码）
  - 列地址线数：2⁵ 个字单元，使用 5 条地址线（Y 译码）
  - 数据线数：4
- DRAM 的情况：例如 1M * 4 的 DRAM 芯片，有 1M (2²⁰) 个字单元（乘号前的数就是字单元个数），划分为 2¹⁰ * 2¹⁰ 的存储矩阵。
  - 行地址线数 = 列地址线数 = 10
  - 数据线数：4

存储器扩展

位扩展：多个同样的存储器芯片的数据位空间拼在一起
例如 2 个 1024 * 4 的 SRAM 芯片构造 1024 * 8 的存储器
字扩展：多个同样的存储器芯片的字空间拼在一起
例如 4 个 1024 * 8 的 SRAM 芯片构造 4096 * 8 的存储器。地址线需要增加 2 条以选择是哪一片 SRAM 芯片中的数据
混合扩展：综合运用位扩展和字扩展
例如 8 个 4096 * 4 的 SRAM 芯片构造 16384 * 8 的存储器（两个一组进行位扩展，四组进行字扩展）
异种扩展：多个不同的存储器芯片进行扩展
同一字空间的存储芯片选择信号连在一起
同一位空间的数据线连在一起

DRAM 的刷新

DRAM 存储单元电路的刷新
刷新的特点
- 刷新操作：读操作
- 按行刷新，所有芯片同时进行
- 刷新操作与 CPU 访问内存分开进行
- 刷新周期：2 ms，4 ms，8 ms
- 刷新地址及刷新地址计数器
刷新方式
- 刷新周期：DRAM 固有的刷新时间，超过该时间不刷新会导致数据丢失
- 刷新间隔：DRAM 整个被刷新一次的时间
- 刷新间隔 <= 刷新周期
- 集中式：在一个时间段内，刷新存储器所有行，此时 CPU 停止访问内存死区时间；另一个时间段内，CPU 可以访问内存，刷新电路不工作
- 分散式：CPU 与刷新电路交替访问内存，一个周期刷新一行，刷新最后一行后，又开始刷新第一行。分散刷新间隔 = 刷新行数 * 存储周期 <= 刷新周期
- 分布式：保证在一个刷新周期内将存储芯片所有行刷新一次，可能等时间间距，也可能不等。分布式刷新的刷新周期等于最大刷新间隔
刷新计数器的位数：2²ⁿ 个字单元，划为 2ⁿ * 2ⁿ 的存储矩阵，行地址位数为 n，则刷新计数器的位数为 n

指令系统与 MIPS 汇编

概述

机器指令的要素
- 操作码
- 源操作数地址
- 目的操作数地址
- 下条指令的地址（少数指令用）
指令类型
- 数据传输指令：寄存器与存储器之间、寄存器之间
- 算数/逻辑运算指令
- 程序控制指令：控制程序执行顺序，条件转移或跳转，返回等
- 浮点数运算指令
操作数
- 类型：数值，布尔值，地址
- 位置：存储器，寄存器，输入输出端口

存储方式

大端Big-Endian存储：最高有效字节存储在地址最小位置
小端Little-Endian存储：最低有效字节存储在地址最小位置

例如存储 0x12345678
// 大端存储 //
Addr    Value
0x00    0x12
0x01    0x34
0x02    0x56
0x03    0x78

// 小端存储 //
Addr    Value
0x00    0x78
0x01    0x56
0x02    0x34
0x03    0x12

指令集系统架构种类
- Register-Memory 式（如 X86）：多种指令可以访问内存；存在寄存器操作数和内存操作数直接运行的指令
- Load-Store 式（如 MIPS）：只有 Load 和 Store 类型可以访问内存；运算指令操作数全为寄存器操作数
操作数地址的数目
- 三地址：Opcode DesAddr Sur1Addr Sur2Addr
- 二地址：Opcode DesAddr SurAddr
- 单地址：Opcode Addr
- 无地址：Opcode
操作码结构
- 定长：如 MIPS
- 变长：如 X86
形式地址：指令中给出的地址编码
有效地址：根据形式地址和寻址方式计算出来的操作数在内存单元中的地址
寻址方式：根据形式地址计算到操作数的有效地址的方式
- 立即寻址：操作数直接在指令代码中给出
- 寄存器直接寻址
- 寄存器间接寻址
- 相对寻址
- 基址寻址
- 更多……
确定寻址方式

典型指令系统

8086/8088 指令系统
MIPS 指令系统
- 32 个 32 位通用寄存器GPRs
- 32 个 32 位浮点数寄存器FGPRs
- HI，LO，PC
- 指令类型
  - RRegister 型：两个寄存器操作数计算，结果送第三个寄存器
  - IImmediate 型：使用一个 16 位立即数做运算
  - JJump 型：跳转 26 位立即数表示的地址
- 最多三地址
- 对于 Load/Store 类型，寻址均为 Base + Offset
- 没有间接寻址
- 更多……
R 型
- Opcode (6)：操作码
- Rs (5)：第一寄存器源操作数
- Rt (5)：第二寄存器源操作数
- Rd (5)：目的寄存器操作数
- Shamt (5)：偏移量（SLL 等用）
- Func (6)：功能码
I 型
- Opcode (6)：操作码
- Rs (5)：第一寄存器源操作数
- Rt (5)：第二寄存器源操作数
- Imm16 (16)：16 位立即数
J 型
- Opcode (6)：操作码
- Imm26 (26)：26 位立即数
Complex Instruction Set Computer增强指令功能，CISC 和 Reduced Instruction Set Computer简化指令功能，RISC
- CISC：X86 等
- RISC：MIPS 等

MIPS 处理器设计

概述

CPU 功能：控制指令执行
四种基本操作
- 取数
- 存数
- 传送
- 运算
指令周期：CPU 从指令存储器中读出并执行指令全部功能的全部时间
- 取指周期：完成取指令和分析指令的时间
- 取数周期：从数据存储器中取出操作数所需时间，包括计算操作数有效地址
- 执行周期：完成指令规定动作的时间
功能部件
- 取指相关
- 执行相关
CPU 内部结构
- 数据通路Datapath
  - 运算，ALU 等
  - 寄存器，GRF 等
- 控制器CU
  - 指令译码器Instruction Decoder, ID
  - 指令寄存器Instruction Register, IR
  - 程序计数器
- 总线
寄存器传送语言Register Transfer Language, RTL
字对齐Alignment：对象的起始地址一定要是字长的整数倍

MIPS 模型机

指令集
数据通路
- 加法器Adder：处理 PC 值的增长
- 算数逻辑运算单元ALU
- 多路选择器
- 符号扩展器SignExt
- 寄存器堆GRF
- 数据存储器DM
- 指令存储器IM

MIPS 单周期处理器

哈佛体系：用 IM 和 DM 区分指令和数据的保存
设计数据通路
控制器设计
- PC 改变方式选择
- ALU 控制
- GRF 写入目标选择
- GRF 写使能
- ALU 输入选择
- 更多……
单周期
- 每条指令执行需要一个时钟周期（CPI = 1）
- 所有状态的更新在指令执行结束的时刻完成
- 最慢指令决定时钟周期的长度
- 数据信号操作的同时产生控制信号
- 指令处理周期的所有阶段都在一个机器时钟周期中完成
多周期
- 指令处理分布到多个周期中（CPI 浮动）
- 指令执行过程中可以更新状态
- 整体状态的更新在指令执行结束后更新
- 最慢“阶段”决定时钟周期长度
- 下一周期所需的控制信号可以在上一周期产生
- 指令处理周期的所有阶段可以在多个机器时钟周期中完成

MIPS 多周期处理器

普林斯顿体系：指令和数据共用一个存储器
设计数据通路
控制器设计

MIPS 流水线处理器

响应时间：从提交作业到完成作业花费的时间
吞吐量：一定时间间隔内完成的作业数
流水线不改善单个任务的处理时间，但改善了整体的吞吐率
CPU 执行时间
- CPU 执行时间 = 程序的 CPU 时钟周期数 * 时钟周期的长度 = 程序的 CPU 时钟周期数 / 时钟频率
- 程序的 CPU 时钟周期数 = 程序的指令数 * 每条指令的平均时钟周期数
五级流水线
- 取指令F 级
- 译码D 级
- 执行运算E 级
- 访存M 级
- 写回W 级
增加流水级寄存器
流水阶段
1. 前级流水级寄存器的输出
2. 组合逻辑计算
3. 写入后级流水级寄存器
所有指令都要经过五级流水线，故有些指令在某些阶段会处于空闲阶段
流水线性能
- $T_{C, pipelined} = \max(T_{stageF}, T_{stageD}, T_{stageE}, T_{stageM, T_{stageW}})$
- $T_{C, pipelined} \ge \frac{T_{C, single-cycle}}{number\;of\;stages}$ （若各阶段用时相等，则取等号）
流水线冒险
- 结构冒险：处于两个流水段的指令要用同一个资源例如同一个时钟周期，一条指令写 GRF，一条指令读 GRF
- 数据冒险
  - 写后读Read After Write, RAW
  - 读后写Write After Read, WAR
  - 写后写Write After Write, WAW：检测并旁路/转发数据给相关指令，若不行，则阻塞流水线
  - 阻塞等价于插入一条 nop：冻结 FD 寄存器，清空 DE 寄存器，保持 PC 值不变
  - 尽量避免阻塞：对代码重排序，避免下一条指令使用 load 类指令的结果
- 控制冒险
  - 分支指令（beq 等）的判断结果会影响接下来的执行的指令流：提前分支判断，延迟槽等
流水线设计的一般方法
- 以单周期数据通路和控制信号为基础
- 考虑转发
- 考虑冒险
- 考虑分支
流水线设计的工程化方法
- 集中式译码与分布式译码
  - 集中式：控制器Controller在 D 级，产生全部译码信号，并且全部控制信号都流水
  - 分布式：控制器分布在多个流水级，每级控制器只产生该级需要的控制信号，只流水指令（较优）
- 指令集规划和实现
- 功能部件的实现
  - PC
  - NPC
  - IM
  - GRF
  - EXT
  - CMP
  - ALU
  - MDU
  - DM
  - 更多……
- 流水级寄存器
- 数据通路
- 转发通路
  - T_use - T_new 模型
- 阻塞的条件判断
- 转发的条件判断
- 实现延迟槽
中断与异常的处理
- 轮询Polling：处理器周期性查询控制寄存器，确认是否允许 I/O
- 异常：CPU 内部产生（例如未定义的指令，算数溢出，系统调用等）
  - 自陷Trap，软件中断：编写程序时故意的陷入内核，如 syscall
  - 故障Fault，软件中断：执行程序时发生的意外，若异常处理代码可以处理，则返回现场；否则报错
  - 终止Abort，硬件中断：指令执行中发生致命错误，只能终止程序
- 中断：来自外部 I/O 控制器，硬件中断
  - 可屏蔽中断
  - 非屏蔽中断
- CP0 协处理器
  - SR 寄存器
  - 保存受害 PC（EPCException Program Counter）
  - 保存问题描述（Cause 寄存器）
  - PRId：CPU 唯一标识
- 跳转异常处理代码Exception Handler Code：如地址 0x00004180
- eret 无条件跳转指令
- 保持异常标志，一直流水到 M 级 CP0，早期流水级的异常覆盖晚期的，外部中断优先级最高
- 通知操作系统
- 中断I/O 中断：异步的，可以发生在任何时候，不会阻止任何指令的运行
- 恢复现场

处理器性能分析

性能分析
- 按比例计算平均 CPIClock Cycles Per Instruction，指令平均执行周期数（CPI 等于 指令所用时间 / 时钟周期）
- 程序执行时间：所有指令的（CPI * 机器时钟周期长度）和；等于 指令数 * 平均 CPI * 机器时钟周期长度
- MIPSMillion Instructions Per Second，百万指令每秒 = $\frac{number\;of\;instructions}{CPI\times10^6}$
- MFLOPSMillion Floating point Operations Per Second，百万浮点数操作每秒
- 加速比Speedup： $S=\frac{T_Y}{T_X}$ 其中 T_Y 是优化时间前的时间，T_X 是优化时间后的指令
- 标准基准程序Benchmark
流水线处理器执行一段指令序列的时长
- 对于 n 条指令构成的指令序列，一个五级流水线执行所需的时钟周期数是 n + 4
- 从 0 时刻开始，经过 4 个周期后（第一条指令经过 F、D、E、M 级），每经过一个周期，可以执行完毕一条指令，因此为 n + 4

高速缓冲存储器

Cache 的原理

局部性原理Principle of Locality
- 时间局部性Temporal Locality：刚被访问的存储单元可能马上要再次访问
- 空间局部性Spatial Locality：刚被访问的存储单元的临近单元可能马上要访问
高速缓冲存储器Cache：在 CPU 和主存中间设置，容量小，速度快，存储需要频繁访问的程序块和数据
存储系统的层次结构

1 ns    Reg                          1 KB
2 ns    Cache                        1 MB
10 ns   Main Mem                     1 GB
10 ns   Disk Cache                   1 GB
10 ms   Magnetic Disk                500 GB
10 s    Magnetic Tape/Optical Disk   100 TB

CPU 访问顺序
- 寄存器 -> Cache -> RAM -> 硬盘
相关术语
- 数据块Block：Cache 的存储单元，Cache 和主存的基本划分单位
  - 内存按照 Block 划分并映射到 Cache 的相应位置，Cache 与主存间按照 Block 为单位进行数据交换
- 标记Tag：保存该数据块对应的主存数据块的地址信息
- 有效位Valid bit, v：记录对应数据块的数据是否有效，一个 Block 一个有效位
- 行Line：Cache 中一个 {v}{Tag}{Data Block} 为一行
- 组Set：若干数据块为一组，地址比较一般能在组内各块间同时进行
- 路Way：Cache 相关联的等级，各路地址比较可以同时进行，路数等于一组内的数据块数
- 命中率Hit Rate：访问时，目标数据在 Cache 中的比例
- 缺失率Miss Rate：访问时，目标数据不在 Cache 中的比例
当数据被引用
- 命中Hit：数据在 Cache 中
- 缺失Miss：将相应的 Block 调入 Cache，可能踢出别的 Block
Cache 基本结构
- 存储：以 Block （若干字）为单位
- 地址：地址比较、地址转换、地址标记Tag，一个 Block 有一个 Tag
- 替换：记录 Block 使用情况、替换策略、有效位v记录对应数据块的数据是否有效
Cache 读操作过程

开始
接受来自 CPU 的地址
if (Cache 中包含此数据块) then
    从 Cache 中读取数据交给 CPU
else then
    从主存中读取数据
    在 Cache 中分配一个数据块
    当前数据交给 CPU
    从主存中读取当前数据块到 Cache
endif
结束

Cache 的映射机制

Cache 的映射：多个主存的数据块映射到一个 Cache 的数据块中
直接映射
- 主存的第 J 块映射到 Cache 中的固定块 K， $K = J \mod M$ ，其中 M 是 Cache 包含的块数
- 主存的地址格式：区地址Tag，区内块地址Index，块内偏移量Offset
组相联映射Set Asscociative
- Cache 分成 K 组，每组 L 块；主存的块 J 按照下列规则映射到 Cache 的组 I 中的任何一块：
$I = J\mod K$
- 主存的地址格式：组内块地址Tag，组地址#Set，块内地址Offset
全相联映射Full Associate
- 主存分为若干 Block，Cache 按照同样大小也分成若干 Block，Cache 中的 Block 比主存中的少得多。主存的某一个 Block 可以映射到 Cache 中的任意一个 Block
- 主存的地址格式：块地址Block Number(Tag)，块内地址Offset

Cache 基本参数

M = 2^m，表地址空间大小（byte），如 2³²
G = 2^g，表 Cache 访问的粒度大小（byte），如 4
C，表 Cache 的容量（byte），如 16 KByte
B = 2^b，Cache 块的大小（byte），如 16
a，Cache 的相联度

Cache 的替换策略

强制Compulsory缺失：第一次引用某个地址（块）时总是出现缺失（Cache 为空）
容量Capacity缺失：Cache 太小，不足以保持需要的每一个数据
冲突Conflict缺失，不属于上述二者的所有情况
缺失损失：CPU 等待数据装入 Cache 的时间
取出块的时间：第一个字的延迟时间 + 块剩余部分的传送时间
LRU 法
- 原则：将近期使用最少的块替换出去
FIFO 法
- 原则：总将最先调入 Cache 的块替换出去

Cache 性能分析

Cache 容量
- 不作特殊申明时，为 Block 数 * Block 大小 (bit)
- 求 Cache 的实际容量，则为 Block 数 * (Block 大小 (bit) + Tag (bit) + Valid Bit + ……)
- 主存容量为 2ⁿ bytes，则主存地址总位数为 n
直接映射的分析
- Cache 每数据块大小为 2^b bytes，则块内偏移量位数为 b；Cache 块数为 2ⁿ 个，则块地址位数为 n，则 主存Tag 位数 等于 Cache 的 Tag 位数 等于 主存地址总位数 - b - n
- Cache 实际容量等于 Cache 块数 * (Valid Bit(1 位) + Data Block(位) + Tag(位))，单位为 bits（若无其它要求）
组相联映射的分析
- Cache 每数据块大小为 2^b bytes，则块内偏移量位数为 b；Cache 组数为 2ⁿ 组，则组地址位数为 n，则 主存Tag 位数 等于 Cache 的 Tag 位数 等于 主存地址总位数 - b - n
- Cache 实际容量等于 Cache 块数 * (Valid Bit(1 位) + Data Block(位) + Tag(位))，单位为 bits（若无其它要求）
访存时间
- T_M 为主存的访问周期，T_C 为 Cache 的访问周期，H 为 Cache 的命中率，则存储系统的等效访问周期是：
$T=T_C \times H + T_M\times (1-H)$
- 加速比是：
$S_p = \frac{T_M}{T}$

外部存储，总线与 I/O

外部存储

磁盘存储器
- 磁头
- 软盘/硬盘
- 磁记录材料
- 片基（载体）
硬磁盘原理
- 一些术语
  - 磁头Head：一个磁盘有若干盘片，每个盘片有上下两个盘面，每个盘面由一个磁头负责读写
  - 磁道Track：磁盘表面的同心圆环
  - 扇区Sector：每个磁道包含若干扇区，扇区是读写最小单位，容量默认为 512 字节。每个磁道包含相同数量扇区
  - 柱面Cylinder：不同盘面的同一半径上的磁道构成一个柱面
- 扇区的地址表示：柱面号Cyliner #，磁头号Head #，扇区号Sector #
- 磁盘存储结构
  - 恒定角速度Constant Angular Velocity
  - 多重区域记录Multiple Zone Recording
磁盘的性能参数
- 道密度
- 位密度
- 存储容量：磁头数 * 磁道（柱面数）* 每道扇区数 * 每扇区字节数
- 旋转速率 r
- 寻道时间 T_S：磁头从当前位置定位到目标磁道的时间（平均值）
- 寻区时间旋转延迟 T_W：磁头定位到目标磁道后，等待目标扇区旋转到磁头下的时间（平均值 1/2r，旋转一周的时间乘以 1/2）
- 访问时间 T_A：T_A = T_S + T_W
- 数据传输率 D_r：每磁道字节数 * 每秒转速 = 每道扇区数 * 每扇区字节数 * 每秒转速
硬磁盘的种类
独立冗余磁盘阵列Reduntant Array of Independent Disks, RAID
固态硬盘Solid State Drive, SSD
光盘CD-ROM
DVDDigital Video Disk

总线

片内总线：芯片内部连接各元件的总线
系统总线：CPU、主存、I/O 接口等之间传递信息的公共通道，一般分为数据总线，地址总线和控制总线三部分
- 数据总线：传递数据
- 地址总线：传递存储器地址和 I/O 地址
- 控制总线
  - 数据传输控制
  - 总线请求和交换
  - 时钟、复位、电源等
I/O 总线：连接 I/O 设备
通信总线：用于计算机系统间或计算机系统与其它系统间的通信
单总线结构
多总线结构
总线标准
总线设计要素和性能指标
- 类型
- 集中式或分布式
- 异步或同步
- 信号线数：所有信号线的总数
- 总线宽度：数据总线位数，如 32，64
- 总线频率：总线时钟频率
- 总线传输周期：完成一次总线操作需要的时间
- 总线带宽：总线的最大传输速率（MB10⁶ Bytes/s 或 GB10⁹ Bytes/s）
总的来说，在表示传输速率的时候，比如 MB/sMBps，GB/sGBps 等，使用十进制进位法。
在表示存储空间的时候，比如 KB2¹⁰ bytes，MB2²⁰ bytes，GB2³⁰ bytes 等，使用二进制进位法。
- 负载能力：总线上能同时连接的设备数
总线传输过程
- 主设备请求使用总线，总线控制器决策，主设备获得总线使用权
- 主设备发出目标地址和控制指令，找到目标设备
- 进行数据传输
- 主设备释放总线使用权

I/O 接口

功能
- 设备寻址
- 数据交互
- 设备控制
- 状态检测
- 数据缓冲
- 格式转换
分类
- 按传送数据格式
  - 串行接口
  - 并行接口
- 按 I/O 方式
  - 程序查询接口
  - 中断接口
  - DMA 接口
- 按时序控制方式
  - 同步
  - 异步
I/O 过程
- 处理器查询外设状态
- I/O 接口回送外设状态
- 设备可用且准备好，则处理器向 I/O 接口发送命令请求传送
- I/O 设备获得外设的数据并传给处理器

I/O 数据传送方式

程序查询 I/O 方式编程式 I/O
- 检测设备状态
- 发送 I/O 命令
  - 包括控制命令，测试命令，读写命令
- 处理器等待 I/O 操作完成
- 传送数据
- 特点：I/O 操作由 CPU 完成，因为外设速度慢，CPU 不断轮询降低效率
中断 I/O 方式
- 关于异常和中断
- 中断源
  - 硬件故障
  - I/O
  - 外部事件
  - 更多……
- 中断编码：每个中断源独有的代号
- 中断请求及其硬件支持，优先级判断
  - 非屏蔽中断 > 内部异常中的终止 > 其它内部异常 > 可屏蔽中断
- 中断响应
- 中断处理
- 特点：I/O 操作由 CPU 完成，外设准备期间，CPU 可以执行其他程序，和外设的工作并行，是目前最主要的 I/O 方式
DMADirect Memory Access I/O 方式
- DMA：CPU 对总线的控制被临时禁止，DMA 控制器接管总线，控制数据在存储器和外设之间高速交换，适合高速批量数据传输
- DMA 过程（停止 CPU 访问内存）
  - 外设通过 DMA 控制器向 CPU 发出 DMA 请求
  - CPU 在当前总线周期结束后响应，总线控制权交给 DMA 控制器
  - DMA 控制器向总线发送信号和数据等
  - 所有数据传送完毕后，通过中断告知 CPU，交还总线控制权
- DMA 过程（周期挪用）
- DMA 控制器结构
- CPU 用于磁盘的 I/O 时间：CPU 主频为 x Hz，DMA 每次传送块大小为 n KB，每次用于预处理和后处理的总时间开销是 m 个时钟周期，那么只有这 m 个时钟周期时 CPU 用于磁盘 I/O，传送 n KB 的时候 CPU 没有用于磁盘 I/O，而是 DMA 在负责。
1 GHz = 10⁹ Hz
通道 I/O 方式
- I/O 通道：一种专用的 I/O 控制器，与 CPU 共享内存。I/O 通道负责实现和管理 I/O
- 选择通道
- 字节多路通道
- 数组多路通道

虚拟存储器

虚存概述

进程保存在辅助存储中，当进程执行时，只将其活跃部分调入主存，此时主存可以视为辅存的“高速缓存”，这种技术称为虚拟存储器技术
虚存空间和物理空间
- 用户编写程序时使用的地址称为虚地址逻辑地址，对应的存储空间称为虚存空间逻辑地址空间
- 计算机物理内存的访问地址称为实地址物理地址，对应的存储空间称为物理空间主存空间
虚拟存储器的调度方式
- 页式调度：虚存空间和物理空间都分成固定大小的页，二者按页进行交换
- 段式调度：按程序的逻辑和结构将空间划分成若干段，长度随意，按段进行交换
- 段页式调度：二者结合

页式虚拟存储器

虚存空间和物理空间都分成固定大小的页，虚存页称为虚页，主存页称为实页
虚地址格式：虚页号 + 页内地址页内偏移
实地址格式：实页号 + 页内地址页内偏移
页表：记录虚页和实页的映射关系，建立在内存中，用虚页号作为索引，页表项包括虚页对应的实页号和有效位
页表寄存器，保存页表在内存中的首地址
- 页大小 2ⁿ bytes，则页内偏移位数为 n
- 虚页号位数 VPN 等于虚拟地址位数逻辑地址 - 页内偏移 n，则有 2^VPN 个虚页
- 物理内存大小 2^m bytes，则实地址位数为 m
- 实页号位数 PPN 等于实地址位数 - 页内偏移 n（实页与虚页的页大小一致）
  - 实地址位数等于 log₂(主存容量)
- 每个页表项大小：1（有效位）+ PPN（实页号位数） + 1（修改位）+ ……
- 每个页表所占空间：虚页数量 2^VPN * 页表项大小
快表 TLBTranslation Lookaside Buffer：使用 Cache 存储部分活跃的页表项，称为 TLB
- TLB 包含虚页号（Tag），对应实页号（数据），有效位，修改位
n 路组相联 Cache 实现快表
- 分为 总表项数 / n 组，记为 2^s 组，则组地址位数为 s
- Tag = VPN（虚页号位数）- s（组地址位数）
- 快表项大小等于 Tag + 页表项大小
- 快表总大小等于 总快表项数 * 快表项大小
TLB，页表，主存，Cache，磁盘的关系
- TLB 可以视为页表的子集，TLB 命中则页表一定命中，TLB 未命中，页表也有可能命中
- 页表命中表示信息一定在主存中，页表未命中表示信息一定不在主存中。如果信息不在主存中，就要访问磁盘
- Cache 可以视为主存的子集，页表命中，则 Cache 有可能命中；页表未命中，则 Cache 不可能命中

序

目录

概述

计算机基本组成与结构

计算机基本组成

计算机总线结构

计算机层次结构

计算机中数的表示

计算机基本工作原理

组合逻辑电路

逻辑代数

基本概念

定律、定理和规则

逻辑函数

逻辑门电路

晶体管和 MOS 管

门电路

基本组合逻辑部件设计

时序逻辑电路

锁存器和触发器

有限状态机

时序逻辑电路设计分析

主存储器

概述

分类

性能指标

存储单元电路

非易失存储器

存储器芯片结构

存储器扩展

DRAM 的刷新

指令系统与 MIPS 汇编

概述

典型指令系统

MIPS 处理器设计

概述

MIPS 模型机

MIPS 单周期处理器

MIPS 多周期处理器

MIPS 流水线处理器

处理器性能分析

高速缓冲存储器

Cache 的原理

Cache 的映射机制

Cache 基本参数

Cache 的替换策略

Cache 性能分析

外部存储，总线与 I/O

外部存储

总线

I/O 接口

I/O 数据传送方式

虚拟存储器

虚存概述

页式虚拟存储器