计算机组成原理

本文最后更新于 2025年1月18日凌晨

前言

教材情况：

课程名称	选用教材	版次	作者	出版社	ISBN 号
计算机组成原理	《计算机组成与系统结构》	3	袁春风	清华大学出版社	978-7-302-59988-3

最基本的计算机硬件普及：

为什么要学这门课？

上上学期学习了《数字逻辑电路》，云里雾里；上学期学习了《计算机系统基础》，继续云里雾里。本学期开始学习《计算机组成原理》？如果用一句话来概括我对数字逻辑电路的理解，大概可以这样说：原来计算机是一个由“门电路”、“导线”和“时钟脉冲”组成的机器。如果用一句话来概括我对计算机系统基础的理解，大概可以这样说：原来计算机所有的活动都是由翻译过来的 01 序列驱动的。

现在我们让 AI 模仿上面我对课程理解的概括逻辑，用一句话来概括计算机组成原理，ta 是这样回答的：原来计算机的高效运作是通过硬件架构的精妙设计，将复杂的指令和数据流转化为有序的电子信号运动来实现的。

会收获什么？

对计算机整体有一个宏观的把握，了解 CPU、存储和 I/O 设备的工作逻辑，尤其要熟悉单核 CPU 的工作逻辑。最后能够利用 verilog 硬件描述语言从逻辑上实现一个单周期单核 32 位 CPU。

注：

本书 ISA 采用 MIPS 指令系统。之前学习的《计算机系统基础》中 ISA 采用的是 IA-32 指令系统，也就是大名鼎鼎的 x86-64 指令系统的 32 位前身。

为了形式化地描述 CPU 的运行逻辑，需要使用寄存器传送级 (register transfer level, 简称 RTL) 语言。本书 RTL 语言有以下规定：R [r] 表示通用寄存器 r 的内容，M [addr] 表示存储单元 addr 的内容；M [R[r]] 表示寄存器 r 的内容所指存储单元的内容；PC 表示 PC 的内容，M [PC] 表示 PC 所指存储单元的内容；SEXT [imm] 表示对 imm 进行符号扩展，ZEXT [imm] 表示对 imm 进行零扩展；传送方向用 $\leftarrow$ 表示，即传送源在右，传送目的在左。

绪论

1 计算机组成原理概述

注：本章与《计算机系统基础》的第 1 章重复，详见 https://blog.dwj601.cn/GPA/4th-term/SysBasic/#第1章-计算机系统概述

主要掌握 冯诺依曼状态机 和 计算机性能度量 两个知识点。

2 数据的机器级表示

注：本章与《计算机系统基础》的第 2 章重复，详见 https://blog.dwj601.cn/GPA/4th-term/SysBasic/#第2章-数据的机器级表示与处理

主要掌握 数值/非数值数据的表示、数据宽度、存储对齐 和检错四个知识点。

数据的检错见 chapter7.5。

CPU

3 运算部件和运算方法

本章我们学习 CPU 中的运算部件，即 算数逻辑单元（Arithmetic and Logic Unit，ALU）。ALU 在计算机中的地位大致如下图所示：

graph RL
    实现功能
    执行程序
    机器指令
    subgraph ALU
    direction RL
    运算方法
    subgraph 运算部件
    direction LR
    加法器
    移位器
    end
    end
    
    运算部件 -->|硬件支持| 运算方法
    ALU --> 机器指令
    机器指令 --> 执行程序
    执行程序 --> 实现功能

在开始学习具体的运算部件和运算方法之前，有必要先学习 chapter4 中的 MIPS 指令集体系结构。这里，我们就是要弄懂 chapter4 中提到的那 11 条 MIPS 指令的具体运算逻辑。将会分为「运算部件」和「运算方法」两个部分展开。

3.1 运算部件

执行部件与控制信号

执行部件。ALU 有两个运算数输入 A 和 B 以及一个控制输入 ALUctr，输出为一个运算结果 Result、零信号 Zero 和溢出信号 Overflow。ALU 的内部结构如下图所示：

ALU 实现

控制信号。对于 MIPS 中的 11 条指令，可以归纳为 7 种操作：addu、add、or、subu、sub、sltu、slt。也就是说 ALUctr 只需要 $\lceil \log_2(7) \rceil =3$ 个选择控制位。如下表所示，列出了 ALUctr 的选择控制逻辑：

ALUctr 的选择控制逻辑

ALU 内部运算逻辑。在 ALU 内部，需要根据控制信号 ALUctr 产生对应的运算逻辑。具体的，ALUctr 内部有 4 个运算控制信号，分别为 SUBctr、OPctr、OVctr 和 SIGctr。下面借书中原文分别解释 4 个控制信号对应的逻辑：

SUBctr 用来控制 ALU 执行加法还是减法运算。当 SUBctr = 1 时，做减法；当 SUBctr = 0 时，做加法。

OPctr 用来控制选择哪种运算的结果作为 Result 输出。因为所实现的 11 条指令中只可能有加/减、按位或、小于置 1 这 3 大类运算，所以 OPctr 有两位。

OVctr 用来控制是否要进行溢出判断。当 OVctr = 1 时，进行溢出判断，此时，若结果发生溢出，则溢出标志 Overflow 为 1，当 OVctr = 0 时，无须溢出判断，此时，即使结果发生溢出，溢出标志 Overflow 也不为 1。

SIGctr 信号控制 ALU 是执行「带符号整数比较小于置 1」还是执行「无符号数比较小于置 1」的功能。当 SIGctr = 0，执行「无符号数比较小于置 1」的功能；当 SIGctr = 1 时，执行「带符号整数比较小于置 1」的功能。

这样就可以完整实现 ALU 运算了。下表详细解释了每一条指令的运算类型与 ALUctr 取值之间的关系：

运算类型与 ALUctr 取值之间的关系

控制逻辑详解

加减运算控制（SUBctr）：很显然，加法（SUBctr = 0），减法（SUBctr = 1）。

输出内容控制（OPctr）：很显然， 3 大类运算就对应 3 个取值。

溢出判断控制（OVctr）：很显然，有符号运算需要溢出判断，其他运算都不需要。

小于置一控制（SIGctr）：这个逻辑比较有意思。为什么无符号数比大小时 Less = Carry ^ SUBctr；有符号数比大小时 Less = Sign ^ Overflow 呢？首先我们知道，比大小的本质是使用加法器做减法运算，那么 $A-B=A+B_{\text{补}}=A+(\sim B +1)$ 。

对于无符号数的比大小逻辑。由于是减法，SUBctr 一定是 1，因此此时的输出其实可以进一步归纳为 Less = Carry ^ 1 = !Carry。也就是说我们只需要分析加法运算的进位结果即可，而这就是之前学过的无符号整数加减运算逻辑了。如果 A 严格小于 B，则 B 的补码与 A 相加后不会产生进位，此时 !Carry = !0 = 1 表示 $A<B$ ；如果 $A\ge B$ ，则 B 的补码与 A 相加后就会超过无符号整数表示的范围产生进位，此时 !Carry = !1 = 0 表示 $A \ge B$ 。很巧妙的逻辑；
对于有符号数的比大小逻辑
- 如果运算没有溢出，即 Overflow=0，此时 A 与 B 的正负一定相同。A 与 B 的比大小结果可以直接根据加法器运算结果的符号位来确定。如果运算结果是负的，即 Sign=1，那么显然 $A<B$ ；反之如果运算结果是正的，即 Sign=0，那么显然 $A\ge B$ ；
- 如果运算发生溢出，即 Overflow=1，此时 A 与 B 的正负一定不同。但我们不知道谁正谁负，根据有符号整数加减运算的溢出符号判定逻辑可知：
  - 若 A 为正数 B 为负数。溢出发生时运算结果一定是负数（正溢出），即 Sign=1，此时 Less = Sign ^ OverFlow = 0，即 $A \ge B$ ；
  - 若 A 为负数 B 为正数，溢出发生时运算结果一定是正数（负溢出），即 Sign=0，此时 Less = Sign ^ OverFlow = 1，即 $A< B$ 。

3.2 运算方法

指令的运算需求有了，能进行基本运算的硬件 ALU 也设计出来了。如何利用已有的运算部件来巧妙地设计算法以高效地实现常用的数学运算呢？让我们一探究竟！

整数加减运算

不重复造轮子，见上学期记的笔记：https://blog.dwj601.cn/GPA/4th-term/SysBasic/#2-7-4-整数加减运算

原码乘法运算

计算逻辑与手算完全一致，只不过在计算机内部进行了一定的改进，有三点：

并不是全部算完每一步的乘法结果后再一次性累加，而是使用一个 “局部变量” 保存前缀和（部分积）；
由于每一位的乘法结果都是在最高位进行的，因此我们不是对当前的乘法运算结果左移一位，而是将前面计算出的前缀和 逻辑右移 一位；
由于单步乘法运算时只有 0 和 1，显然若当前为 0 则对答案的贡献也为 0，因此当乘法位为 0 时只需要前缀和右移一位即可，而不需要执行相加操作。

▶

推导过程

其实算法过程很简单，就是模拟了乘法运算的过程，这里就不罗列了。只不过其中有一些关于运算部件的巧妙利用。比如将每次部分积右移后多出来的一位存放到 $Y$ 中，反正 $Y$ 右移后的最后一位已经没用并且舍弃掉了，前面空出来的一位正好就用来存储部分积的最后一位。

我们将二进制位从低到高的下标从 $1$ 开始计数，进位位记作 $C$ ，部分积记作 $P$ ，乘数位记作 $Y$ ，则有这样的递推式：

P_i = (P_{i-1}+Xy_i) \gg 1,\quad P_0 = 0

模拟过程如下：

原码乘法可以应用在在浮点数的尾数运算中。对数值位直接使用原码乘法即可，符号位就是两个乘数的符号位相异或的结果，例如：设 $[x]_\text{原}=0.1110$ ， $[y]_\text{原}=1.1101$ ，计算 $[x\times y]_\text{原}$ ，符号位为 $0\oplus 1=1$ ，数值位为 $[x]_\text{原} \times [y]_\text{原}$ ，即 $1110 \times 1101$ 的原码乘法运算结果 $10110110$ 。同时，可以采用分块思想对该算法进行优化。具体的，由于是逐位运算，因此我们需要进行 $n$ 次相乘再相加的操作，时间复杂度为 $O(n)$ 。现有的优化方案就是逐 $k$ 位运算，那么时间复杂度就可以优化为 $O(\frac{n}{k})$ 。

补码乘法运算

如何在已知 $[X]_{\text{补}}$ 和 $[Y]_{\text{补}}$ 的情况下，计算 $[X\times Y]_{\text{补}}$ 呢？由于 $[X\times Y]_{\text{补}} \ne [X]_{\text{补}} \times [Y]_{\text{补}}$ ，因此补码乘法不能直接使用原码乘法的算法，需要我们重新设计运算方法，这里引入 Booth 算法。

▶

推导过程

布斯算法的本质是将符号位与数值位一起运算，也就是对有符号数的一次性运算算法。如下推导：

进而可以得到关于「真值」的部分积递推公式：

P_{i} = [P_{i-1} + (y_{i-2}-y_{i-1})X] \gg 1

于是可以得到关于「补码」的部分积递推公式：

\begin{aligned}[P_{i}] _{\text{补}} &= [P_{i-1} + (y_{i-2}-y_{i-1})X]_{\text{补}} \gg 1 \\&= [P_{i-1}] _{\text{补}} \gg 1 + [(y_{i-2}-y_{i-1})X]_{\text{补}} \gg 1\end{aligned}

显然的 $y_{i-2}-y_{i-1}$ 只有 $-1,0,1$ 共 3 种情况，因此我们只需要知道 $[-X]_{\text{补}}$ 和 $[X]_{\text{补}}$ 即可利用 算数移位 和加法快速运算。例如下面的算例：

由于计算机中的数据都是以补码形式存储，因此补码乘法的使用场景更加广泛。至于优化，与原码乘法的优化方案类似。

4 指令集体系结构

▶

基本术语

在开始学习指令系统之前有必要知道一些基本术语：

在 逻辑层面 上。CPU 能理解的只有指令，不同功能的指令组成了一个集合叫做 指令集，指令集中不同的指令的组合方式就构成了 指令集体系结构 (Instruction Set Architecture, ISA)，基于特定的指令集体系结构开发的应用程序可以运行在任何一个支持相同指令集体系结构的硬件上（也就是所谓的兼容）；
在 物理层面 上。CPU 能理解的指令就是 01 序列，不同功能的 01 序列就是指令集（也被称为架构），指令集体系结构的具体实现就是 CPU 内核（也被称为微架构），多个 CPU 内核加上全局缓存（例如 L3 缓存）就是现代 CPU（也被称为芯片）。

下面针对上述的术语举一些当下的实际应用与产品：

在 逻辑层面 上。ISA 固然重要，但是显然不利于人类与机器的交互，在此基础之上出现了汇编语言，并继续诞生出了 高级语言与编译器。编译器就是一个遵循 ISA 的软件，因此每一个架构上都有特定的编译器。通用的编程语言在不同的架构上可以被编译成遵循对应架构的机器码从而正确运行；
在 物理层面 上。当前主流的指令集（架构）有 x86 架构、ARM 架构、RISC-V 架构、MIPS 架构。基于不同的架构针对不同的应用场景可以设计出不同的 CPU 内核（微架构）如 基于 ARM 架构的 A35、A76、Cyclone 内核 等。基于不同的 CPU 内核针对不同的应用场景可以设计出不同的 CPU 如 基于 ARM 架构的 A76 内核设计出的骁龙 865 处理器 等。

指令集体系结构简称指令系统，下面全部用 ISA 来表示。

本章我们会学习指令集体系结构中的一种：MIPS。将会围绕「如何设计一个 ISA」和「基于 ISA 封装的程序与 ISA 的关系」两个部分展开。

4.1 如何设计一个 ISA

在开始了解如何设计一个指令系统之前，不妨先从结果论的角度了解一下程序运行的一般流程：

首先需要填充 CPU 中寄存器的信息。操作系统需要根据可执行文件（也就是程序，包括代码、数据、堆栈等信息）的目录位置将其调入内存，对于采用虚拟化技术的操作系统而言，需要分页调入，并维护当前程序对应的进程中的页表信息，并通过缓存机制将内存中的信息调入 cache 中保存，cache 中的信息再调入到用户态的通用寄存器中保存。当然寄存器信息不仅可以源于存储器中的程序信息，通过 chapter8 的学习，我们知道 CPU 的寄存器信息也可以来自 I/O 接口中的端口信息；
然后 CPU 就可以利用寄存器中存储的信息开始进行计算工作。也就是所谓的取指令（Instruction Fetch）、解码（Instruction Decode）、执行（Execution）、内存访问（Memory Access）和结果写回（Write Back）五大步骤。这些都将在 chapter5 和 chapter6 中具体展开。

知道了最基本程序运行流程以及其中的的指令执行流程后，针对当前的指令系统，产生的问题也接踵而至：支持的操作数类型有哪些？支持的操作类型有哪些？如何对操作进行编码？以及如何进行寻址？前两个问题大同小异，并且操作类型与操作数类型是捆绑的，都可以通过操作类型编码来进行区分。因此我们需要重点关注的就是如何进行操作编码以及如何通过寻址来得到对应的操作数。也因此可以得知，一条指令需要有的信息就是「操作码」和「地址码」两类信息。具体的：

操作码。就是说明这条指令需要执行什么样的操作；
地址码。就是说明当前指令对应的操作需要的数据，例如源操作数的地址、目的操作数的保存地址等。

4.2 MIPS 指令与 MIPS 汇编

我们知道指令都是 01 序列，这并不利于快速编程实现与人类阅读理解，为此引入了汇编语言。一般来说每一种指令集都会对应一套汇编，MIPS 也不例外。因此我们就需要学习 MIPS 的指令类型及其在程序中的汇编表示（选择、循环和过程调用）。

当然，程序与汇编之间的转换已经在《计算机系统基础》这门课程中已经学习过了，具体的是 C 语言与 IA-32 指令集之间的转换，见 https://blog.dwj601.cn/GPA/4th-term/SysBasic/#第3章-程序的转换及机器级表示，就不再赘述。同时，很多基础性的概念诸如「程序转换步骤」也不再赘述。本节，我们重点学习 MIPS 的指令格式以及 11 条 MIPS 指令的汇编表示，具备「通过查表将 MIPS 系统的机器代码与 MIPS 系统的汇编代码进行转换」的能力即可。

在开始介绍具体的 11 条 MIPS 指令之前，我们先看一下 MIPS 的指令类型，共有三种，如下图所示：

MIPS 指令类型及其格式

R-型指令

这里的 R 即 Register。操作数和结果都存放在寄存器中。对应的操作码 OP 为 000000，具体的操作类型由 func 字段决定。具体的：

若是双目运算，则将寄存器 rs 和 rt 中的数据运算后送到寄存器 rd 中；
若是移位运算，则根据 shamt 字段给出的移位数，将 rt 中的数据进行移位后送到寄存器 rd 中。

下图仅列出了 5 条双目运算的汇编指令及其功能阐述：

R-型指令的：汇编、RTL描述、功能描述

I-型指令

这里的 I 即 Immediate。字段相对于 R 型指令就少了不少，具体的：

若是双目运算。就将 rs 和扩展后的立即数进行运算，并将结果保存到 rt 中；
若是访存指令。就将 rs 和符号扩展后的立即数相加得到一个地址，Load 就将内存中该地址中的值保存到 rt 中，Store 就将该地址保存到 rt 中；
若是条件转移（分支转移）。就将 rs 和 rt 进行运算后，根据运算结果决定是否要转移到相应的地址处执行，具体的寻址方式是相对寻址，即将 PC 加上立即数对应的偏移量得到有效地址。

下图列出了上述三种指令的具体逻辑：

I-型指令的：汇编、RTL描述、功能描述

J-型指令

这里的 J 即 Jump。J-型指令只有一个操作码和一个 26 位的直接地址。具体的：

主要是无条件转移指令。只需要在取指令部件中将 PC 的高四位拼接上 26 位直接地址，最后在末尾补两个 0 即可得到 32 位的跳转地址。

为什么在末尾补两个 0 即可？ 是因为在 MIPS 指令集体系结构中，是按照字（4 个字节）对齐的，也就是说其对内存的访存都是以 4 个字节为一个整体，每次寻址时只需要知道起始的字节位置并一次性读取 4 个字节即可得到 32 位地址。又由于从 0 开始编址，那么最终的地址就都是 4 的倍数了。更进一步的，如果按照 $k$ 个字节对齐，那么所有的地址就都是 $k$ 的倍数。

下图列出了具体实现：

J-型指令的：汇编、RTL描述、功能描述

5 单周期处理器

本章我们开始学习具体的 CPU 执行指令的过程。CPU 的设计方法分为「硬连线设计」和「微程序设计」两种。其中硬连线的设计方法就是根据指令直接设计硬件来支持执行，而微程序的设计方法就是将指令的执行构成抽象为程序设计来支持执行。前者的执行速度更快但是不易维护，适用于精简指令集架构 RISC 的设计，后者的执行速度较慢但是可维护性和可扩展性更好，适合复杂指令集架构 CISC 的设计。下面要介绍的「单周期处理器」和「流水线处理器」都是采用硬连线的设计思路。

同样的，由于一个 ISA 涉及几十上百条指令，因此我们仅仅学习最基本的 chapter4 中的 11 条 MIPS 指令在「单周期处理器」中的执行过程。而所谓的单周期处理器，就是一个周期仅仅执行一条指令（于是单周期处理器的周期就是执行时间开销最长的指令对应的时间）。

然而无论是即将要学习的单周期处理器，还是之后在 chapter6 要学习的流水线处理器，所有的处理器执行指令的过程都无外乎：取指、译码、执行、访存和写回。这主要由两大部件来完成，分别是「控制部件」和「执行部件」。其中控制部件通过对指令译码产生控制信号，执行部件在接收到控制信号后对数据进行各种运算得到相应的计算结果。因此我们需要重点关注的有两点：

控制信号。每一条指令分别对应了哪些控制信号？
数据通路。数据在执行部件中是如何流通的？

下面我们将会围绕 MIPS 中那 11 条指令，来回答上述问题。

5.1 数据通路

下图是单周期处理器完整的控制部件与执行部件：

单周期处理器的控制部件与执行部件

如上图所示，加下划线的都是控制信号，用虚线箭头指出。共有 9 个，从上到下分别为：

RegWr：寄存器写使能控制信号。1 表示允许写，0 表示禁止写；
RegDst：目的寄存器控制信号。1 表示选择 Rd 作为目的寄存器，0 表示选择 Rt 作为目的寄存器；
Branch：条件转移控制信号。1 表示需要通过条件进行 PC 的更新，0 表示 PC 默认通过 +4 更新；
Jump：无条件转移控制信号。1 表示需要通过指令进行 PC 的更新，0 表示 PC 默认通过 +4 更新；
MemWr：存储器写使能控制信号。1 表示允许写入存储器，0 表示禁止写入存储器；
MemtoReg：存储器是否写入寄存器的控制信号。1 选择存储器的数据写入寄存器，0 表示选择 ALU 的数据写入寄存器；
ExtOp：扩展类型的控制信号。1 表示符号扩展，0 表示零扩展；
ALUSrc：第二源操作数的选择控制信号。1 表示选择扩展后的立即数作为第二源操作数，0 表示选择 busB 端口的数据作为第二源操作数；
ALUctr：算数运算单元的选择控制信号。3 bits 对应 8 种信号。详情见 chapter3.1 的内容。

5.2 控制信号

指令类型	指令	RegWr	RegDst	Branch	Jump	MemWr	MemtoReg	ExtOp	ALUSrc	ALUctr
R-型	`add rd,rs,rt`	1	1	0	0	0	0	x	0	add
-	`sub rd,rs,rt`	1	1	0	0	0	0	x	0	sub
-	`subu rd,rs,rt`	1	1	0	0	0	0	x	0	subu
-	`slt rd,rs,rt`	1	1	0	0	0	0	x	0	slt
-	`sltu rd,rs,rt`	1	1	0	0	0	0	x	0	sltu
I-型	`ori rt,rs,imm16`	1	0	0	0	0	0	0	1	or
-	`addiu rt,rs,imm16`	1	0	0	0	0	0	1	1	addu
-	`lw rt,rs,imm16`	1	0	0	0	0	1	1	1	addu
-	`sw rt,rs,imm16`	0	x	0	0	1	x	1	1	addu
-	`beq rs,rt,imm16`	0	x	1	0	0	x	x	0	subu addu
J-型	`j target`	0	x	0	1	0	x	x	x	addu

6 流水线处理器

本章我们学习「流水线处理器」的设计。与上述「单周期处理器」类似，学习 11 条 MIPS 指令在流水线处理器中是如何执行的。而由于流水线的指令执行方式会带来一些冒险问题，因此再介绍一下冒险问题是如何产生的以及应该如何规避冒险问题。

所谓流水线，其实就是并行执行指令。首先我们需要将指令统一划分为相同的字段，例如（取指、译码、执行、访存、写回）五个字段。接下来就可以并行执行指令了，当然这里的并行并不是很多指令一起执行，这样显然就不能正确运行程序逻辑了，所谓并行指的是指令仍然顺序执行，只不过可以分字段并行，例如，下一条指令在上一条指令进入译码阶段时可以开始进入取指阶段，以此类推。

具体的，对于上述 11 条指令，都有取指和译码两个阶段，区别就在于根据译码得到控制信号后的运算逻辑以及是否需要从存储器取数或是否需要将数据写入存储器。其中 Load 指令具有所有的阶段，如下「时空图」所示：

lw 指令的功能段划分

但并不是所有的指令都像 Load 指令一样具有所有的段，为了能够让所有的指令能够在统一的段划分下并行执行，需要对其余的指令进行空段扩展，使其均成为 5 段指令。具体的：

5 条 R 型指令和 I 型运算指令 ori 和 addiu 都需要在 Write 之前加上一段空 Mem 段；
I 型指令中的 sw 和 beq 指令都需要在 Mem 之后加上一段空 Write 段；
J 型指令需要在 Exec 段之后加上一段空 Mem 段和一段空 Write 段。

6.1 数据通路

进而可以得到如下图所示的 5 段流水线处理器的控制部件和处理部件：

5 段流水线处理器的控制部件和处理部件

如上图所示，5 段流水就对应了指令执行过程中的 5 个逻辑。仍然用下划线表示控制信号并用虚线指出，从左到右共有 10 个控制信号，相比于单周期处理器多了一个 R-type 指令，其余不变。当 R-type 取 1 时表示当前指令是 R-型指令，取 0 表示非 R-型指令。

注意到上图的寄存器堆结构中，写口与读口是分离的，也就是说允许在一个周期内同时进行寄存器的读和写操作。

6.2 控制信号

在流水线处理器中，所有的控制信号都在 IF/ID 段寄存器中全部产生并不断向之后的段寄存器传递，直到某个信号不再被使用就终止传递。也就是说在流水线处理器中，段寄存器传递的不仅仅是数据，也有各种控制信号。下面详细介绍数据在各段寄存器中的传递情况。

IF 段

IUnit的内部实现

向下一个段寄存器 IF/ID 传递：指令 I、PC+4、PC[31:28] 共 3 个信息。

ID 段

向下一个段寄存器 ID/Ex 传递：PC+4、PC[31:28]||target[25:0]||00、func、imm16、R[Rs]、R[Rt]、Rt、Rd 共 8 个信息。

Ex 段

Ex 段开始产生控制信号。此处的 5 个控制信号除了 R-type 的取值取决于指令类型以外，其余的控制信号取值与单周期处理器完全一致。

向下一个段寄存器 Ex/Mem 传递的内容取决于指令需要计算的东西：

R 型指令：ALUout、Overflow、Zero、待保存数据的寄存器编号；
I 型运算指令（ori、addiu）：ALUout、Overflow、Zero、待保存数据的寄存器编号；
I 型访存指令（lw、sw）：ALUout（存储器地址）、待保存数据的寄存器编号；
I 型条件转移指令（beq）：Zero、Btarg（ PC+4 与 扩展后的imm16 × 4 之和）
J 型无条件转移指令（jump）：Jtarg（ PC[31:28]||target[25:0]||00 ）

Mem 段

Mem 段产生控制信号的逻辑与单周期处理器同样一致。

向下一个段寄存器 Mem/Wr 传递的内容取决于指令逻辑：

R 型指令和 I 型运算指令：ALUout、Overflow、待保存数据的寄存器编号；
lw 指令：待保存数据的寄存器编号、Do（从存储器读出来的数据）；
sw 指令：不用传递了（将待保存的地址通过 WA 端口送入后再将 R[Rt] 中的数据写入 Di 端口即可）；
beq 指令：不用传递了（若 Zero=1 则将 Btarg 送回 PC 寄存器来更新 PC 中的值）；
jump 指令：不用传递了（将 Jtarg 送回 PC 寄存器来更新 PC 中的值）。

Wr 段

Wr 段产生控制信号的逻辑与单周期处理器同样一致。

这是最后一段，需要决定是否需要向寄存器堆写入数据，具体的：

R 型指令和 I 型运算指令：MemtoReg 取 0 让 ALUout 中的数据写入 Rt 或 Rd 寄存器中，当然写使能信号需要在不溢出的情况下才能为 1；
lw 指令：MemtoReg 取 1 让 Do 写入 Rt 寄存器中；
sw、beq、jump 指令禁止改变寄存器的值即可，即 RegWr=0。

6.3 冒险解决

结构冒险

hardware resource confilicts

现象：同一个部件同时被不同的指令所使用。

解决：

每一个硬件部件在一个时刻只能被一条指令使用；
将指令存储器 (Instruction Memory, IM) 和数据存储器 (Data Memory, DM) 分离。由于流水线策略的并行机制，取指令和写存储器操作会因为并行而同时访问存储器，因此我们可以将 IM 和 DM 分离。这样就可以在同一个周期内同时取指令以及向存储器写数据了。Data Memory 见 chapter6.1 中的数据通路图，Instruction Memory 见 chapter6.2 中的 IUnit 内部实现；
将寄存器的读口和写口分离。同样由于流水线策略的并行机制，会导致指令写寄存器 (Write) 和指令读寄存器 (Reg/Dec) 的情况同时发生，为了解决这个问题，可以将寄存器的读口和写口分离，详情见 chapter6.1 中的数据通路图。

解决结构冒险的示意图如下所示：

结构冒险解决策略

数据冒险

data dependencies

现象：写后读，即从 Reg 读取的数据是没有更新过的旧值。

解决：

转发 (Forwading)。现在寄存器的值不仅仅取决于指令指向的寄存器的数据，也有可能是之前的指令运算后的结果。在物理实现上，前者就是从前面的段寄存器正常流水过来的数据，后者属于从后面的段寄存器额外传过来的数据；
寄存器写后立刻读。让寄存器能够在一个周期内将数据从写口传递到读口。

解决数据冒险的示意图如下所示：

数据冒险解决策略

特殊的。上述示意图中执行的都是算数运算。但如果出现了 Load 指令，那么运算结果是在 Mem 段之后才能从数据存储器 DM 中读出来，由于「后续指令只能依赖已经计算出的数据」，因此如果紧跟在 Load 指令之后的一条指令需要使用 DM 中读出的数据参与 ALU 的计算，就没办法使用上述的转发技术。如下图所示：

Load-use 数据冒险

解决方法就是在 Load 指令的后面增加一条无关指令或者空指令，然后再转发。至于怎么增加，可以从硬件、软件、编译三个角度进行：

硬件角度。阻塞一个周期；
软件角度。插入一条无关指令；
编译角度。将编译的指令中无关的指令提前到 Load-use 指令之间。

控制冒险

changes in program flow

现象：转移或异常改变执行流程，顺序执行指令在目标地址产生前已被取出。

解决：

首先可以使用上述 Load-use 中的软硬件方法；
也可以使用编译优化重排指令来实现；
也可以使用分支预测技术来解决。

存储

7 存储器

当机器有了记忆，就可以不用人为干预而自动运行，从而真正意义上实现了自动化的流程。本章主要学习计算机中的存储器件、存储策略以及数据交互逻辑。

现代计算机中有很多类型的存储器，核心功能都是存储数据，那为什么不统一成一种存储器呢？根本原因是 CPU 的计算速度远大于从存储器中访存数据的速度，因此我们不得不设计出可以匹配 CPU 计算速度的存储器结构。但这样的存储器造价极高并且存储量很小，因此我们只能退而求其次，从而诞生了现代计算机中的层次存储结构。从 CPU 开始依次为：寄存器 (Register)、缓存 (Cache)、内存 (Main Memory) 和 外存 (Secondary Memory)。这些存储器的访存速度逐渐降低。本章也将按照这样的顺序分别讲解相应的概念，然后从上帝视角并结合上面所有的存储层次，宏观地讲解 虚拟化 技术。最后补充介绍一下存储器中的 数据校验 策略。

7.1 缓存

缓存采用的随机存取存储器是 SRAM，即静态随机存取存储器。由于其速度快容量小且造价很高，因此适合做 cache 工作。SRAM 存储高低电平的方式是触发器。

为什么会有缓存

基于程序的局部性。从高级语言的逻辑进行理解不难发现，数据的重复访问往往集中在一个程序段中（例如循环），对应的指令和数据是连续存储的，因此程序在内存中运行时具有局部性。不断执行的某些指令和不断访问的某些数据就可以存入缓存中。这里根据局部性再衍生出「空间局部性」和「时间局部性」两个概念。

空间局部性简单来讲就是某些指令或数据「存储顺序和访问顺序的差异」。差异越小，空间局部性就越好；
时间局部性简单来讲就是某些指令或数据「短时间内重复访问的情况」。重复访问的越多，时间局部性就越好。

缓存的工作逻辑

前置知识。cache 一般被组装在 CPU 内部，便于和寄存器进行高效的数据交互。与此同时，设计者将 cache 和内存划分为由相同大小存储空间组成的存储器，这里 “相同大小的存储空间” 在 cache 中被称为行 (line) 或槽 (slot)，在内存中被称为块 (block)。为了知道 cache 中每一个行是否有效缓存了内存的信息，设计者对 cache 中的每一行设定了一个有效位来区分是否缓存了有效信息。

CPU 读取内存信息的流程

如上图展示的 CPU 读取内存信息的流程图。CPU 在得到内存中的某一个地址后需要访问该地址指向的信息。此时可以首先查询 cache，若果没有找到，再进行 cache 缺失处理并去内存中查询。

int a[M][N] {};

// 更快
for (int i = 0; i < M; i++)
    for (int j = 0; j < N; j++)
        A[i][j] = 1;

// 很慢
for (int j = 0; j < N; j++)
    for (int i = 0; i < M; i++)
        A[i][j] = 2;

知道了 cache 的工作原理后，上面两个代码段执行时间天壤之别的原因也就呼之欲出了。由于对数据进行访问时，不同的数据仅仅是地址的差异，而每一个数据的地址都是用加法器一步运算出来的，按道理并不会有任何时间开销的差异。那这几十倍的时间开销差异从何而来？其实就是缓存的功劳。通过将数据按块缓存，可以减少 CPU 访问内存的次数，而只需要从缓存中取数即可，从而大大降低了时间开销。

值得一提的是。如果数据/指令的大小比一个「缓存行」或「内存块」还要小，那缓存机制就没什么优势了。并且从上述讨论可以发现，缓存机制对于代码编写者和编译器而言都是透明的存在，是从物理层面上对程序进行的优化。

注意：在考虑 CPU 访存时间时，如果脱靶，不仅仅需要考虑访问内存的时间，还要考虑访问 cache 的时间。

缓存与内存的映射关系

1）直接映射（模映射）

直接映射

映射关系。首先我们需要对内存块和缓存行进行编号。假设缓存一共有 $k$ 行，那么第 $i$ 个内存块就会唯一对应到第 $i\ \%\ k$ 个缓存行。

访存机制。假设现在 CPU 需要访问一个地址 AR。如果没有缓存机制，那就直接到内存中访问这个地址对应的信息即可；在直接映射的缓存规则下应该如何访问呢？在块的大小是 2 的幂并且缓存行数 k 也是 2 的幂的情况下，可以将内存地址划分为：标记、cache 行号、块内地址三个部分。前两个部分其实直接对应了内存中的哪一块，只不过在模映射规则下，可以先通过「cache 行号」的比较结果来判断是否需要继续进行标记匹配。具体的，如果此时 cache 行号匹配成功 && 标记匹配成功 && cache 的这一行是有效行，那就算命中了，此时地址译码器就直接返回 cache 中当前地址 AR 存储的数据/指令；反之如果 cache 行号匹配失败 || 标记匹配失败 || cache 的这一行不是有效行，那就算脱靶，此时就需要到内存找这个地址对应的数据/地址并返回，同时需要把这个地址在所在的块复制一份到 cache 对应的行。

工作特点。这种缓存方式的优点在于可以在一定程度上减少地址的匹配位数。但是越简单的东西缺点也一定越明显，这种策略很可能造成极端情况发生，即某些被频繁访问的内存块对应的 cache 行号是一样的，这就无法利用上别的闲置的行，并且会导致 cache 对应的行被一直被替换，起不到缓存的作用。

2）全相联映射

分块示意图 | 全相联映射

映射关系。内存中的每一个块可以缓存到任意一个 cache 行中。

访存机制。内存地址从高位到低位被划分为：标记和块内地址。地址译码器根据 CPU 发出来的地址进行解析之后，遍历 cache 中所有的行进行标记匹配。

特点。显然的全相联映射的优点在于直接解决了模映射策略中不断遇到模数相等需要不断替换的极端情况。缺点在于丢失了模映射的匹配优势，每一次匹配都需要完全匹配所有的标记。

3）组相联映射

分块示意图 | 组相联映射

映射关系。对于 N 路组相联，cache 中每一个组含有 N 个 cache 行，组间进行直接映射，组内全相联映射。

访存机制。内存地址从高位到低位被划分为：标记、cache 组号和块内地址。首先用内存块号 $\%$ cache 的组数得到当前内存块在 cache 中的组号，然后遍历当前组中所有的 cache 行进行标记匹配和标志位判断。

特点。综合了直接映射和全相联映射的优点，既可以避免频繁替换的极端情况，也可以加快地址的匹配速度。

缓存的替换算法

不难发现，在上述三种映射策略中，除了模映射是一一对应可以直接替换以外，另外两种映射策略需要考虑替换哪一个缓存行。有如下几种缓存的替换算法。

1）最佳时间 (Optimism Time, OPT)

算法思想就是提前预知所有内存块的调度顺序，然后每次需要替换时替换后续最后才需要访问的缓存行。这种方法显然不切实际，但是可以作为基准来度量其他替换算法算法的性能。

2）先进先出 (First In First Out, FIFO)

算法比较简单，就是一个队列算法。当然实际技巧是，每次标记队头缓存行，一旦脱靶就替换队头对应的缓存行，然后将下一行标记为队头即可。这种算法会产生「Belade」异常，所谓的 Belade 异常就是缓存行数量与命中次数不成正比，其他的替换算法都不会出现这种情况。

3）最近最少使用 (Least Recently Used, LRU)

算法也比较简单。实现技巧在于给每一个 cache 行一个计数器，从而找到最近最久未被使用的 cache 行进行替换。

注意：这里的计数器就是给每一个 cache 行增加合适的标记位。至于位数的多少，取决于 LRU 的执行范围。例如采用 N 路组相联映射时的 LRU 算法，如果每一组有 16 个 cache 行，那么这里关于 LRU 替换算法就需要 4 个标记位。

4）最不经常使用 (Least Frequently Used, LFU)

5）时钟页面调度 (Clock)

采用循环指针，每一个调度内存的页面只有 0 和 1 两种状态。当首次被调入或者再次访问内存中某个实页（页框）时，将其标志位定义为 1，并让指针后移一位。当且仅当某个实页为 0 并且指针指向当前实页时，就将其调出。

▶

综合例题

问：假定计算机系统有一个容量为 $32K\times 16$ 位的主存，主存按字编址，每字 $16$ 位。且有一个数据区容量为 $4K$ 字的 $4$ 路组相联 cache，采用 LRU 替换算法。主存和 cache 之间数据交换块的大小为 $64$ 字。假定 cache 开始为空，处理器顺序地从存储单元 $0,1,\cdots,4351$ 中取数，一共重复 $10$ 次。设 cache 比主存快 $10$ 倍。试分析 cache 的结构和主存地址的划分，并说明采用 cache 后速度提高了多少？

答：

cache 的结构。由于 cache 的数据区容量为 4K 字，根据传输的数据块大小 64 字可以很容易算出 cache 一共有 4K/64 = 64 行。由于是 4 路组相联，因此 cache 一共有 16 组，每组 4 行。
主存地址的划分。根据主存总容量 32K 字，以及传输的数据块大小 64 字可以很容易算出主存一共有 32K/64 = 512 块。每一个块对应到 cache 16 个组中的一个，因此主存结构如下：
标记 cache 组号块内地址
5 位 4 位 6 位
速度提升。由于取数是对应 $[0,4151]$ 共 $4152/64=68$ 块，因此本质上只访问了内存中的 $68$ 块数据。初始的 $64$ 块数据需要全部访问内存获取，最后 $4$ 块由于需要替换也需要从内存获取。因此第一轮需要访问内存 $68$ 次。不难发现，在 LRU 算法下，后续的 $9$ 轮都是在对前四组中的 cache 行替换 $5$ 次，因此后续的 $9$ 轮每一轮都需要从内存访问 $20$ 次。那么命中率 $P$ 为：
$P =\frac{43520-68-20\times 9}{43520}\approx99.43\%$
速度提升的倍数为：
$\frac{T_m}{P\times T_c + (1-P)\times(T_m+T_c)} = \frac{10}{99.43\% \times 1 + (1-99.43\%)\times (10 + 1)}\approx 9.46$

标记	cache 组号	块内地址
5 位	4 位	6 位

缓存与内存的一致性

CPU 在执行写操作时，可能会写入 cache，为了保证 cache 和内存的一致性，提出了以下两种策略：

white through。如果写命中 cache，就同时写 cache 和内存；如果写不命中 cache，要么只写内存，要么写完内存后将更新过的内存块添加到 cache 中；
white back。如果写命中，就只写 cache；如果写不命中，就从内存中调入对应的内存块然后在 cache 中进行写入。

注意：这种方法需要给每一个 cache 行增加一个标记位来表示是否需要进行写回操作。

可以发现上述 white through 策略可以绝对确保 cache 和内存的一致性，但是由于写如内存操作的开销很大，因此这种方法带来的性能损失也很大。相反 white back 策略就只会写入 cache，对应的开销就小很多，但是显然会出现 cache 和内存的不一致问题，这种策略需要结合别的策略来确保 cache 和内存的一致性。

7.2 内存

内存采用的随机存取存储器是 DRAM，即动态随机存取存储器。相比于 SRAM，DRAM 速度较慢但容量更大，因此适合做内存工作。DRAM 存储高低电平的方式是电平，即通过电容的高低电平状态来存储 01 状态。由于 DRAM 的读操作会对高电平进行放电，因此需要定时对 DRAM 的电容进行充电，也就是所谓的按行刷新。

部分内容参考：深入内存/主存：解剖 DRAM 存储器

内存的工作逻辑

上图与 chapter7.1 中 “缓存的工作逻辑” 类似，隐藏了 cache，突出了地址译码的逻辑。

CPU 首先通过「控制线」将读/写信号送到内存，然后分读写两种情况：

CPU 需要读数据时。就将需要读取数据的地址通过「地址线」送到内存寻找相应的数据，内存通过「数据线」将数据返回给 CPU；
CPU 需要写数据时。就将需要写入数据的地址通过「地址线」送到内存寻找待写入的内存，同时将需要写入的数据通过「数据线」送到内存并写入指定的内存中。

CPU 与内存的数据通信分为异步和同步两种：

异步。CPU 从数据线取数时需要收到内存已经准备好数据的信号；
同步。CPU 从数据线取数无须内存的信号，而是在向内存发出取数信号后，经过确定的时间后就从数据线取数。

地址译码器

一维单译码器 VS 二维双译码器

如果有 $n$ 位地址位，就决定了寻址范围为 $[0,2^n-1]$ 。不难发现如果是一维单译码，就需要译码器有 $2^n$ 个译码寻址线。如果是二维双译码，就只需要译码器有大约 $2 \times 2^{n/2}$ 个译码寻址线。显然当地址位较多时，二维双译码器是更优的。

芯片扩展

芯片扩展分为「字扩展、位扩展和字位同时扩展」三种。已经在数电中学习过了，具体见 https://blog.dwj601.cn/GPA/3rd-term/DigitalLogicCircuit/#4-4-2-译码器-数据分配器，不再赘述。

7.3 外存

见 chapter8 中的外存设备。

7.4 数据校验

数据在信道传送的过程中，可能会因为各种噪声或者硬件原因出现错误，我们有必要进行数据的检错与纠错。通俗来说就是我们想知道数据在传输的过程中有没有发生变化以及如果发生了变化我们应该如何纠正这个错误变化。本目我们只学习数据传输过程中的错误检测，具体的叫做「奇偶校验法」策略。

在开始学习具体的错误检测方法之前，先看一下数据校验的流程图来对其有一个全局的把握：

数据校验流程图

如上图所示，对于原始数据 M，我们想知道其在经过各种期间和总线之后有没有发生异变，显然我们可以将 M 的副本一起传送，但这样的开销就直接变成了两倍，因此尝试用一个存储开销更小的东西来作为原始数据 M 的一个唯一表示，即校验码。数据传输的过程中，我们将原始数据和校验码一起传输，最后通过比对原始数据的校验码以及最后数据的校验码来判定是否发生了数据传输的错误。

具体的。对于偶校验法。我们将校验码取作原始数据 $M$ 所有二进制位的异或，此时校验码只有一位，因此也被称为校验位 $P$ 。现在 $(M,P)$ 开始传输，经过了各种存储器和总线后我们将其表示为 $(M',P'')$ 。我们想知道此时的 $M'$ 和之前的 $M$ 是不是同一个东西，怎么办呢？重新拿 $M'$ 计算一次校验位得到 $P'$ ，比较 $P''$ 和 $P'$ 是否相同即可，如果相同，我们就认为数据传输没有发生问题，如果不相同那么数据传输就发生了问题，需要对 $M'$ 纠错后再输出。奇校验就是在用原始数据的每一位计算异或值后，再异或一次 $1$ 。

这合理吗？显然不具备绝对正确性。但奇偶校验强就强在逻辑很简单，并且对于硬件的开销很小，毕竟只多传输了 1 位。反例如下：

首先我们不能保证校验码传输前后是否会发生错误；
其次针对校验逻辑，奇偶校验都不能检测出偶数位数据传输错误，并且，如果校验位前后不同则表明数据传输的过程中一定发生了错误，但是不能知道多少位 $(1,3,5,...2n-1)$ 发生了错误，并且也不知道哪几位发生了错误，也就没办法进行后续的数据纠错。

码距是什么？所谓码距就是两个二进制代码（码字）中不同位的个数。在奇偶校验的码制下，两个合法码字的最小码矩就是 $2$ 。

参考：什么是奇偶校验原理？奇校验、偶校验、校验位（单比特奇偶校验、两维奇偶校验（矩阵校验或交叉奇偶校验））

设备

8 系统互连与 I/O 设备

本章主要介绍外部设备和计算机系统的交互逻辑。这里的外部设备包括输入输出设备 (I/O 设备) 以及外部存储。

8.1 I/O 设备

主要有：输入输出设备、外部存储设备、网络设备三类设备。其中外部存储设备就是第七章存储器中的外存部分。

8.2 I/O 接口

一般而言，设备通过接口与南桥芯片相连来减少 CPU 的布线压力，主板中的数据通过名为总线的线路进行数据传输。这里的接口指的是设备与芯片的中间硬件，起到一个数据缓冲的作用。既然起到缓冲，就需要存储数据，也就对应了需要存储器，接口中的存储器一般都是寄存器，被称为端口。

8.3 I/O 传输

设备与内存的数据传输有三种方式：

程序查询方式（OS 主动轮询）。操作系统定时从设备读取数据；
程序中断方式（设备主动请求）。设备主动向 CPU 发送数据传送的中断请求，OS 通过执行中断程序来让设备与内存进行数据交互；
DMA 方式（即 Direct Memory Access 成批传输数据）。在传输的数据量较大时，接口的缓冲区需要多次接受数据进行传输，而缓冲区每一次数据传输都需要向 CPU 发送「请求总线」和「完成传输」两次中断请求，这就意味着在传输的数据量很大的情况下，CPU 需要花很多计算代价来处理 I/O 操作。为了降低 I/O 的开销，设计者设计了 DMA 接口来控制大批量数据的传输。具体来说，DMA 接口中有一个 DMA 控制器，其只需要在一开始向 CPU 发送「请求总线」的中断请求，以及在最后向 CPU 发送「完成传输」的中断请求，期间可以自主的让外设与内存进行数据交互，而无需再使用 CPU 的计算资源。这种方式有一种 ”多核“ 的思想在里面。

GPA > 5th-term

计算机组成原理

https://blog.dwj601.cn/GPA/5th-term/ComputerOrganization/

作者

Mr_Dwj

发布于

2024年8月27日

更新于

2025年1月18日

许可协议

数字图像处理上一篇

操作系统下一篇