计算机组成原理 · 核心算法与公式速查

各章关键算法、公式和判定条件的集中整理。

第1章 计算机系统概述

性能公式

CPU 时间 = 指令数 × CPI × 时钟周期时间
         = 指令数 × CPI / 主频

MIPS = 指令数 / (执行时间 × 10⁶)
     = 主频 / (CPI × 10⁶)

MFLOPS = 浮点运算次数 / (执行时间 × 10⁶)

时钟周期 = 1 / 主频
CPI = 总时钟周期数 / 指令总数
IPC = 1 / CPI

Flynn 分类法

SISD: 单指令流单数据流（传统单机）
SIMD: 单指令流多数据流（向量机）
MISD: 多指令流单数据流（少见）
MIMD: 多指令流多数据流（多处理器）

第2章 计算机的逻辑部件

三态电路

三态：0态、1态、高阻态Z
G=0 → Y=A（正常态），G=1 → Y=Z（高阻态）

加法器

半加器：H_i = X_i ⊕ Y_i
全加器：F_i = X_i ⊕ Y_i ⊕ C_{i-1}
       C_i = X_iY_i + (X_i + Y_i)C_{i-1}

超前进位

进位传递函数 P_i = X_i + Y_i
进位产生函数 G_i = X_i · Y_i
C_i = G_i + P_i · C_{i-1}

4位超前进位：
C_1 = G_0 + P_0·C_0
C_2 = G_1 + P_1·G_0 + P_1·P_0·C_0
C_3 = G_2 + P_2·G_1 + P_2·P_1·G_0 + P_2·P_1·P_0·C_0
C_4 = G_3 + P_3·G_2 + P_3·P_2·G_1 + P_3·P_2·P_1·G_0 + P_3·P_2·P_1·P_0·C_0

组进位产生函数 G* = G_3 + P_3G_2 + P_2P_3G_1 + P_0P_1P_2P_3G_0
组进位传递函数 P* = P_0P_1P_2P_3

第3章 运算方法和运算部件

补码表示

正数补码 = 原码
负数补码 = 反码 + 1
补码 = 模 - |负数|（模的概念）
移码 = 补码符号位取反

定点小数（n+1位）

补码范围: -1 ~ +(1 - 2^(-n))
原码范围: -(1 - 2^(-n)) ~ +(1 - 2^(-n))
最小正数: 2^(-n)
模 = 2

定点整数（n+1位）

补码范围: -2^n ~ +(2^n - 1)
原码范围: -(2^n - 1) ~ +(2^n - 1)
模 = 2^(n+1)

IEEE 754 单精度

数 = (-1)^S × (1 + M) × 2^(E - 127)
S: 符号位（1位）
E: 阶码（8位，偏置127）
M: 尾数（23位）

特殊值:
  全0阶+全0尾 → ±0
  全1阶+全0尾 → ±∞
  全1阶+非0尾 → NaN

浮点数表示范围（补码，n+1位尾数，k+1位阶码）

最大正数 = (1 - 2^(-n)) × 2^(2^k - 1)
最小正数 = 2^(-n) × 2^(-2^k)
绝对值最大负数 = (-1) × 2^(2^k - 1)

溢出判断

双符号位法:
  S1S2 = 00 → 正数，无溢出
  S1S2 = 11 → 负数，无溢出
  S1S2 = 01 → 正溢出
  S1S2 = 10 → 负溢出
  溢出 = S1 ⊕ S2

移位规则

负数补码左移: 补0
负数补码右移: 补1
负数反码移位: 补1
原码移位: 补0

符号扩展

正数: 附加高位全填0
负数原码: 附加高位填0，符号位保持1
负数补码: 附加高位全填1

补码一位乘法（Booth 算法）

yn  yn+1  操作
00       右移一位
01       加 [X]补，右移一位
10       加 [-X]补，右移一位
11       右移一位
重复 n+1 次，最后一步不移位

原码两位乘法

Yi-1 Yi  操作
00       +0，右移两位
01       +|X|，右移两位
10       +2|X|，右移两位
11       +3|X| → 执行 -|X|，欠帐 +4X 用 C 记录

不恢复余数法

第一步: 余 = 被除数 - 除数（余为正→溢出终止）
之后每步:
  余 ≥ 0: 商1, 余左移后减除数
  余 < 0: 商0, 余左移后加除数
重复 n 次，最后余数 × 2^(-n) 为真正余数

全加器与先行进位

Si = Ai ⊕ Bi ⊕ Ci-1
Ci = AiBi + Ci-1(Ai ⊕ Bi)

Gi = AiBi          （进位生成）
Pi = Ai ⊕ Bi       （进位传递）
Ci = Gi + PiCi-1

海明校验

2^r ≥ k + r + 1
k = 数据位数，r = 校验位数
校验位 Pi 在位号 2^(i-1) 的位置

S1~S5 检错:
  全0 → 无错
  一位不为0 → 校验位错
  两位不为0 → 两位错
  三位不为0 → 数据位错，S4~S1 指明出错位

CRC 校验

CRC 编码 = 数据字 + 余数
余数 = (M(x) × X^r) mod G(x)

循环纠错:
  余数=0 → 无错
  余数=101 → 左起第1位错
  余数非0非101 → 继续除，除n-1次得101 → 左起第n位错

第4章 主存储器

SRAM 与 DRAM

SRAM：6 管触发器 / 位，不需刷新，~1ns，地址一次送入，用于 Cache
DRAM：1T1C / 位，需 64ms 内刷新，~50ns，地址分两次接收（行列复用），用于主存

DRAM 刷新

刷新周期 = 64ms
集中刷新: 连续完成所有行，有死区
分散刷新: 穿插在读/写周期中，无死区延存取周期
异步刷新: 定时刷新一行，折中

ROM 分类

非易失性存储器（断电保留）

掩模 ROM: 出厂固化，成本最低
PROM:    用户一次性烧写（熔丝）
EPROM:   紫外线擦除，可重写
EEPROM:  电擦除，字节级修改
Flash:   电擦除，块级操作，密度高

Cache 平均访问时间

Ta = h × Tc + (1-h) × Tm
h = 命中率, Tc = Cache 访问时间, Tm = 主存访问时间
访问效率 e = 1 / (h + (1-h) × r), r = Tm/Tc

第5章 指令系统

指令格式

三地址: OP A1 A2 A3
二地址: OP A1 A2
一地址: OP A1
零地址: OP

操作数位置类型

SS 型: 两个操作数都在主存
RR 型: 两个操作数都在寄存器
RS 型: 一个在寄存器，一个在主存

寻址方式有效地址

立即寻址:   操作数 = A
直接寻址:  EA = A
间接寻址:  EA = (A)
寄存器寻址: EA = Ri
寄存器间接: EA = (Ri)
基址寻址:  EA = (BR) + A
变址寻址:  EA = (IX) + A
相对寻址:  EA = (PC) + A
堆栈寻址:  EA = SP

第6章 中央处理器

时序关系

1 指令周期 = 若干机器周期
1 机器周期 = 若干时钟周期
1 时钟周期 = 1 / 主频

微指令编码方式

直接控制:    1 位/微操作 → 并行度高，字长长
字段直接编码: 分字段编码 → 字长短，需译码
字段间接编码: 字段间有依赖 → 字长更短，控制复杂

后继微地址

计数器方式: μPC+1（顺序），BAF→μPC（转移）
断定方式: 微指令中下址字段直接指定

BCF 编码:
  000 顺序 (μPC+1)
  001 操作码产生
  010 无条件转移
  011 条件转移
  100 测试循环
  101 转子程序
  110 返回

流水线

5级流水线: IF → ID → EX → MEM → WB
冒险类型: 结构冒险、数据冒险、控制冒险
解决方法: 转发、插入气泡、分支预测

第7章 存储系统

Cache 地址映射

直接映射: i = j mod m（i行号，j主存块号，m总行数）
主存地址: [标记(s-r)] [行号(r)] [块内(w)]

全相联映射: 任意块→任意行
主存地址: [标记(s)] [块内(w)]

组相联映射: 组内全相联，组间直接映射
主存地址: [标记(s-d)] [组号(d)] [块内(w)]

Cache 替换算法

随机法: 随机选择一行替换
FIFO: 最先进入的行被替换
LRU:  最久未使用的行被替换（命中率最高）
LFU:  使用次数最少的行被替换

虚拟存储器

虚存地址: [逻辑页号] [页内行地址]
实存地址: [物理页号] [页内行地址]
地址转换: 通过页表完成逻辑页号 → 物理页号映射

第8章 辅助存储器

磁记录方式

RZ（归零制）:   正脉冲=1，负脉冲=0，位间电流为0
NRZ（不归零制）: 始终有电流，连续1/0时不改变方向
NRZ1（见1就翻）: 遇1翻转方向，遇0不变
PM（调相制）:   利用相位差180°代表0和1
FM（调频制）:   1在中心翻转且位间翻转，0仅位间翻转
MFM（改进调频）: 1在中心翻转，连续0时起始翻转

磁盘技术指标

存储容量 = 记录面数 × 每面磁道数 × 每道扇区数 × 每扇区字节数
平均寻址时间 = 平均找道时间 + 平均等待时间
数据传输率 = 记录密度 × 介质运动速度

RAID 级别

RAID 0: 无冗余分块，性能最高
RAID 1: 镜像，安全高，空间利用率50%
RAID 5: 分布校验，无专用校验盘
RAID 6: 两种奇偶校验，可坏两块盘
RAID 10: RAID 0+1，性能和安全性兼备

第9章 输入输出设备

ASCII 码

7位表示128个字符
数字0-9: 30H~39H（高3位011，低4位0000~1001）
大写A-Z: 41H~5AH
小写a-z: 61H~7AH
大小写仅b5一位不同

显示器参数

分辨率: 像素个数（如1920×1080）
灰度级: 亮暗差别（8位=256级）
帧存储器容量 = 分辨率 × 灰度级位数
刷新频率: >30次/秒不闪

第10章 输入输出系统

中断处理流程

中断请求 → 中断响应 → 中断隐指令（关中断、保存断点、转向入口）
→ 中断服务程序（保存现场→处理→恢复现场）
→ 开中断 → IRET 返回

中断响应条件

1. 至少有一个中断请求
2. CPU 允许中断（IF=1）
3. 当前指令执行完毕

DMA 传送方式

CPU 暂停方式:    DMA 占用总线直到完成
周期挪用方式:    窃取空闲总线周期
直接访问方式:    DMA 优先级高于 CPU 时才占用总线

DMA 控制器寄存器

DMAR: DMA 地址寄存器（主存地址）
ADR:  外设地址寄存器
WCR:  字计数器（传送字数）
CSR:  控制/状态寄存器
DBR:  数据缓冲寄存器