【分析解答】
第 3 版 · OCR 辅助 · 原书检索 · 文字用于定位，公式与图表请回原页核验 · 本次导入快照
## 【分析解答】
假设 M1、M2 和 M3 分别表示时钟频率为 480MHz、560MHz 和 640MHz 的多周期处理器，对如图 5.7 所示的有限状态转换图进行分析得知，Load、Store、Branch、Jump 和 ALU 类指令在 M1 中的 CPI 分别为 5、4、3、3、4，在 M2 中的 CPI 分别为 6、5、3、3、4，在 M3 中的 CPI 分别为 7、6、4、4、5。因此，用基准程序 CPUint 2000 来计算，得到它们的综合 CPI 分别为
$$
\mathrm{CPI}(M1) = 25\% \times 5 + 10\% \times 4 + 11\% \times 3 + 2\% \times 3 + 52\% \times 4 = 4.12
$$
<!-- page: 153 -->
$$
\mathrm{CPI}(M2) = 25\% \times 6 + 10\% \times 5 + 11\% \times 3 + 2\% \times 3 + 52\% \times 4 = 4.47
$$
$$
\mathrm{CPI}(M3) = 25\% \times 7 + 10\% \times 6 + 11\% \times 4 + 2\% \times 4 + 52\% \times 5 = 5.47
$$
因此，M1、M2 和 M3 的 MIPS 数分别为
$$
\mathrm{MIPS}(M1) = 480 / 4.12 = 116.5
$$
$$
\mathrm{MIPS}(M2) = 560 / 4.47 = 125.3
$$
$$
\mathrm{MIPS}(M3) = 640 / 5.47 = 117
$$
由此可见，数据访问改为双周期的做法效果较好。但进一步把取指令改为双周期的做法反而使 MIPS 数变小了，因此，这种做法不可取。因为数据访问只涉及 Load/Store 指令，而取指令则涉及所有指令，使得 CPI 显著增大，从而降低了性能。
19. 假定有一条 MIPS 伪指令 “bcmp $t1, $t2, $t3”，其功能是实现对两个主存块数据的比较，$t1 和 $t2 中分别存放两个主存块的首地址，$t3 中存放数据块的长度，每个数据占 1 字 (4B)，若所有数据都相等，则将 0 置入 $t1；否则，将第一次出现不相等时的地址分别置入 $t1 和 $t2 并结束比较。
（1）若 $t4 和 $t5 是两个空闲寄存器，请给出实现该伪指令的指令序列。
（2）假定比较的数据块大小为 50 字，说明在类似于图 5.6 所示的多周期数据通路中执行该伪指令时最多需要多少个时钟周期。
【分析解答】
（1）实现伪指令 “bcmp $t1, $t2, $t3”的指令序列如下。
[tbl-34.md](tbl-34.md)
（2）在类似图 5.6 所示的多周期数据通路中执行时，上述程序段中用到的指令 beq、lw、bne 和 addi 的时钟周期数分别为 3、5、3 和 4。若比较的数据块大小为 50 字，则上述指令序列中的循环最多被执行 50 次，因而所需的指令数最多为 $1 + 50 \times 7 + 1 = 352$。其中，Load 类指令为 $50 \times 2 = 100$ 条，时钟周期数为 $5 \times 100 = 500$；Branch 类指令数为 $1 + 2 \times 50 = 101$，时钟周期数为 $3 \times 101 = 303$；addi 指令数为 $1 + 3 \times 50 = 151$，时钟周期数为 $4 \times 151 = 604$。所以，总时钟周期数最多为 $500 + 303 + 604 = 1407$。
20. 在一个指令集中增添功能强大的复杂指令时，通常使用微程序方式对这些复杂指令进行控制。如果要求在图 5.6 所示的多周期数据通路中采用微程序控制方式实现第 19 题中的 bcmp 指令，并且规定使用通用寄存器作为两个额外临时寄存器 rt1 和 rt2，即指令的汇编形式为 “bcmp rs, rt, rd, rt1, rt2”。
（1）请给出全套的设计方案，包括该指令的机器码格式（与原有指令格式兼容）、指令执行流程（用 RTL 表示）、数据通路修改方案、控制信号增加或修改方案、指令执行对应的有
<!-- page: 154 -->
限状态机等。
(2) 与第 19 题的软件实现方式相比，该指令用硬件实现时的速度快了多少？硬件实现速度快的原因是什么？
(3) 能否用单周期数据通路实现？若能，则用软件实现合算还是用硬件实现合算？
(4) 如果 rt1 和 rt2 不用通用寄存器，而是用内部寄存器，则会有哪些好处？
【分析解答】
(1) 该指令的汇编形式为“bcmp rs,rt,rd,rt1,rt2”。
指令的机器码格式如下。其中，6 位 OP 字段可以选择一个未被其他指令使用的编码。
[tbl-35.md](tbl-35.md)
该指令的功能：比较个数由 rd 指出，如果 rd 的内容为 0，则什么都不做，继续执行下条指令；否则，对 rs 和 rt 所指内存单元的数据依次比较，直到发生以下情况为止。①若存在一对数据不相等，则将不相等的数据所在的内存单元地址分别保存在 rs 和 rt 中，结束执行；②若所有数据都相等，则将 0 存放在 rs 中，结束执行。rt1 和 rt2 是临时寄存器，在指令执行过程中，rs、rt、rd、rt1 和 rt2 都会被破坏。
该指令执行流程如图 5.14 所示。
对图 5.6 所示的数据通路和控制信号做以下修改。
① 在存储器的 Address 处对原 MUX 进行修改，增加 Rrs 和 Rrt 两个输入，原控制信号 IorD 改为两位，当 IorD 为 0、1、2 和 3 时，分别将 PC、ALUout、A 和 B 送 Address 处。
② 在寄存器堆的 Ra 处增加一个 MUX，除原来的 rs 外，增加 rt、rd 和 rt1 三个输入端，增加相应的两位控制信号 RdAdd1，当 RdAdd1 为 0、1、2 和 3 时，寄存器读地址分别为 rs、rt、rd 和 rt1。
图 5.14 指令执行流程图
③ 在寄存器堆的 Rb 处增加一个 MUX，除原来的 rt 外，另一个输入来自 rt2，增加相应的一位控制信号 RdAdd2，当 RdAdd2 为 0 和 1 时，寄存器读地址分别为 rt 和 rt2。
④ 在寄存器堆的 Rw 处对原 MUX 进行修改，除了原来的 rt 和 td 外，增加 rs、rt1 和 rt2 三个输入，原控制信号 RegDst 改为 3 位，当 RegDst 为 0、1、2、3、4 时，寄存器写地址分别为 rs、rt、rd、rt1 和 rt2。
⑤ 在寄存器堆的 Dw 处对原 MUX 进行修改，除了原来的输入以外，增加一个输入端 0，原控制信号 MemtoReg 改为 2 位，当 MemtoReg 为 0、1 和 2 时，存入寄存器的内容分别为存储器读出数据、ALU 输出结果和 0。
<!-- page: 155 -->
⑥ 在 ALU 的 B 输入端处对原 MUX 进行修改，再增加两个输入 0 和 1，以使 ALU 能执行“R[rd]−0”和“R[rd]−1”的操作，这样，原控制信号 ALUSelB 改为 3 位，ALUSelB 为 0、1、2、3 时，原先的定义不变，ALUSelB 为 4 和 5 时，ALU 的 B 输入端分别为 0 和 1。
根据该指令执行流程，以及相应数据通路和控制信号的定义，得到该指令执行过程对应的状态转换图，如图 5.15 所示。图中在每个状态内仅给出了关键控制信号的取值，并省略了最初的两个公共状态（取指令周期和译码/取数周期）以及其他指令执行的状态（见图 5.7）。该指令的执行从第 12 状态开始，每个状态按顺序编号，分别为 12、13、……、25。
图 5.15 指令执行的有限状态转换图
图 5.7 对应的原 11 条指令的有限状态机已有 12 个状态和 2 个分支点。加上该指令的 3 个分支点，新的有限状态机中有 5 个分支点和 26 个状态，需用 5 位表示状态号，如果用微
<!-- page: 156 -->
程序设计方式实现该指令的控制逻辑，每个状态对应一条微指令，那么，微指令地址应该有5位，转移控制字段BrCtr的位数为3，其编码及含义如下（Next $\mu$addr为下条微指令地址）。
000: Next $\mu$addr = 00000。
001: Next $\mu$addr = ROM1 中对指令译码得到的相应入口地址。
010: Next $\mu$addr = ROM2 中 lw/sw 对应的入口地址。
011: Next $\mu$addr = $\mu$addr + 1。
100: Next $\mu$addr = 该指令分支1处输出的地址。
101: Next $\mu$addr = 该指令分支2处输出的地址。
110: Next $\mu$addr = 该指令分支3处输出的地址。
执行到该指令时，则调出该指令对应的微程序执行。该指令对应的微程序是从第12状态开始的微指令序列。其中的三个分支点分别在第12、17和第24状态，都是根据标志ZF控制分支的。对于第12状态的分支1，若 $\mathrm{ZF} = 1$，则Next $\mu$addr = 00000，否则Next $\mu$addr = $\mu$addr + 1；对于第17状态的分支2，若 $\mathrm{ZF} = 0$，则Next $\mu$addr = 00000，否则Next $\mu$addr = $\mu$addr + 1；对于第24状态的分支3，若 $\mathrm{ZF} = 0$，则Next $\mu$addr = 01101，否则Next $\mu$addr = $\mu$addr + 1。因此，分支1和分支2处可以各用一个MUX实现，根据ZF的值选择将00000还是 $\mu$addr + 1输出作为Next $\mu$addr。分支3处用一个地址修改逻辑，当ZF = 0时，将输入11001改为01101，当ZF = 1时不修改。
对应的下条微地址生成逻辑如图5.16所示，在此假定采用计数器法。
图5.16 题20中的下条微地址生成逻辑
(2) 假定 bcmp 指令的比较次数为 $n (n \neq 0)$，根据上述有限状态机可知，最坏情况下，用硬件实现该指令所需的时钟周期数为 $2 + 1 + 12n + 1 = 4 + 12n$；而根据第 19 题给定的指令序列可知。最坏情况下，用软件实现所需的时钟周期数为 $10n + 3 + 6n + 4 + 12n = 7 + 28n$。
<!-- page: 157 -->
因此，硬件实现比软件实现至少快一倍。硬件实现比软件快的原因主要有两个：①软件方式下，指令序列中的每条指令都要取指令、译码/取数；而硬件实现时不需要。②软件方式下，每条指令都要保存结果，下条指令用时再取；而硬件方式下，中间数据可以直接使用，无需先存后取。
（3）因为本指令在执行过程中可能需要多次写寄存器，因此，不能用单周期数据通路实现。假设能用，因为单周期数据通路的时钟周期以最复杂指令为准，因此，这个复杂指令会大大延长时钟周期，此时用软件实现更合算。
（4）如果 rt1 和 rt2 不用在指令中明显给出，即不用通用寄存器而改用内部寄存器，则可大大简化数据通路、减少控制信号和时钟周期数，并且可减少被该指令破坏的通用寄存器的个数。但是，因为要额外增加专用的内部临时寄存器，其硬件成本会更高。
21. 假设微程序控制器容量为 $1024 \times 48$ 位，微程序可在整个控存内实现转移，反映所有指令执行状态转换的有限状态机中有 4 个分支点，采用水平型微指令格式，并采用断定法确定下条微地址，即由专门的下地址字段确定微地址。请设计微指令的格式，说明各字段的含义和位数，并对转移控制字段进行编码。
## 【分析解答】
微程序控制器容量为 $1024 \times 48$ 位，说明微地址占 10 位，微指令字为 48 位。微指令字分三个字段：微命令字段、转移控制字段和下地址字段。因为微地址占 10 位，所以下地址字段有 10 位，用来给出下条微指令的地址；因为需要对 5 种情况进行控制，所以转移控制字段有 3 位；剩下的 $48 - 10 - 3 = 35$ 位是微操作码（微命令）字段，用于对微命令进行编码。
采用断定法时，转移控制字段可按以下方案进行编码。
000：下地址字段指出的地址作为下条微地址。
100：根据分支1处的条件来选择下条微地址。
101：根据分支2处的条件来选择下条微地址。
110：根据分支3处的条件来选择下条微地址。
111：根据分支4处的条件来选择下条微地址。
如果采用计数器法，则转移控制字段需要对 6 种情况进行控制，在上述 5 种情况的基础上再加上“顺序执行下条微指令”的情况，其中第一种情况改为“取指微程序首地址作为下条微地址”。此时，转移控制字段也只要 3 位编码。
综上所述，微指令的格式如下。
[tbl-36.md](tbl-36.md)
22. 对于多周期 CPU 的异常和中断处理，回答以下问题：
（1）对于除数为 0、溢出、无效指令操作码、无效指令地址、无效数据地址、缺页、访问越权和外部中断，CPU 在哪些指令的哪个时钟周期能分别检测到这些异常或中断？
（2）在检测到某个异常或中断后，CPU 通常要完成哪些工作？简要说明 CPU 如何完成这些工作。
## 【分析解答】
（1）多周期 CPU 中不同指令执行时可能会发生不同的异常事件，这些异常事件发生在
<!-- page: 158 -->
不同的时钟周期内，CPU在不同的时钟周期中检测不同的异常事件。
① “除数为 0”异常在取数/译码周期进行检测。
② “溢出”异常在 R-型指令和 I-型运算类指令的执行周期进行检测。
③ “无效指令”异常在取数/译码周期进行检测。
④ “无效指令地址”“缺页”“访问越权”异常在取指令周期检测。
⑤ “无效数据地址”“缺页”“访问越权”异常在存储器访问周期检测。
⑥ “外部中断”可在每条指令的最后一个周期进行检测。
(2) CPU检测到某个异常或中断后，要完成的工作是关中断、保护断点和程序状态、识别异常事件(或中断源)并转异常(或中断)处理。CPU计算断点值并将断点和程序状态字寄存器信息送到栈或特定的寄存器中；异常的识别大多采用软件识别方式，而外部中断则可以采用软件识别或硬件识别方式，然后转到相应的处理程序。
<!-- page: 159 -->
# 第6章 指令流水线
## 6.1 教学目标和内容安排
主要教学目标：使学生深刻理解现代计算机的 CPU 是如何执行指令的，包括指令流水线基本原理、流水段寄存器的概念、流水线数据通路的设计、流水线的控制信号、结构冒险及其处理、数据冒险及其处理、转发技术、控制冒险及其处理、分支预测原理、超标量和动态流水线的概念；并让学生初步了解在指令流水线中如何处理异常和中断，以及各种存储器访问缺失对指令流水线的影响。
### 基本学习要求：
(1) 理解指令流水线的一般概念。
(2) 了解适合流水线执行的指令集特征。
(3) 掌握流水线数据通路的设计方法。
(4) 了解流水线控制器的设计原理。
(5) 理解流水线冒险的基本概念。
(6) 了解结构冒险的概念和处理策略。
(7) 了解数据冒险（数据相关）的概念。
(8) 了解运用转发技术解决数据冒险的基本原理。
(9) 了解“load-use”数据冒险的概念和处理策略。
(10) 了解控制冒险的概念和引起控制冒险的几种原因。
(11) 了解静态分支预测和动态分支预测的的基本原理。
(12) 了解异常和中断对流水线的影响。
(13) 了解访存缺失对流水线的影响。
(14) 了解超流水线、超标量和动态流水线等高级流水线的基本概念及其基本实现技术。
现代计算机都采用流水线方式执行指令，因此，有关指令的流水线执行方式和流水线处理器的实现等内容是非常重要的。主教材依照“总线式 CPU→单周期 CPU→多周期 CPU→基本流水线 CPU→动态超标量超流水线 CPU”的次序，循序渐进地介绍了 CPU 设计技术及其发展过程。实际上，前面介绍的单周期 CPU 和多周期 CPU 等非流水线 CPU 设计的内容，都是为后面介绍流水线 CPU 设计做铺垫的，因为真正需要学生掌握的应该是反映
<!-- page: 160 -->
现实的流水线处理器的实现技术。
主教材主要从流水线概述、流水线处理器的实现、流水线冒险及其处理和高级流水线技术4方面对流水线技术进行了介绍。
对于流水线概述部分，因为其内容比较简单，所以，只要通过对一个简单例子的讲解，让学生明白采用流水线方式执行指令的基本思想，以及采用流水线后指令的吞吐率与指令执行时间的变化。
对于流水线处理器的实现，以具有代表性的11条MIPS指令为实现目标，分析每条指令的功能和执行过程，找出最复杂指令所需要的执行阶段。在介绍流水线数据通路设计时，可以对照前面的单周期数据通路设计思路，对两者进行比较，以使学生有一个从简单到复杂的认识过程，有利于学生对流水线设计和实现的基本方法的掌握。课时有限的情况下，可以只选择对部分指令在流水线中的执行过程进行讲述。对于流水线CPU中控制器的设计，只要把控制信号在流水段寄存器中的传送过程讲清楚，再讲清楚流水线CPU中控制器设计方式与单周期CPU中控制器设计方式是一样的就可以了。
对于流水线冒险及其处理，结构冒险、数据冒险和控制冒险三种基本流水线冒险的含义和相应的冒险处理原理（如加 nop 指令、转发、阻塞、分支预测），可以通过具体的指令序列在流水线数据通路中的执行过程来讲解，使学生具有对具体问题进行相应分析的能力。课时有限的情况下，对于一些具体的实现细节可以跳过，例如具体的转发线路、带转发控制的流水线数据通路、load-use 数据冒险的检测和处理、分支预测的具体实现、异常或中断引起的控制冒险的具体处理、访问缺失引起的流水线阻塞处理等。虽然，上述内容的具体实现在课时不够时可以不讲，但是，对于这些内容所涉及的基本概念和基本原理，学生还是应该有一定程度的了解，因为这些内容对学生全面了解指令执行过程中数据的流动过程，以及全面掌握现代计算机处理器设计技术是必需的。
对于高级流水线技术，基本要求是能够了解超流水线、超标量和动态流水线等高级流水线的基本概念及其基本实现技术。在课时有限的情况下，课堂中只要简单说明一下每种实现技术的基本思想即可，具体的实现实例和详细的描述部分可以跳过。
## 6.2 主要内容提要
### 1. 指令流水线的设计和实现
指令流水线设计的基本思想是，将每条指令的执行规整化为若干同样的流水阶段，每个流水阶段的执行时间一样，都等于一个时钟周期。采用流水线方式执行指令，其吞吐率比非流水线方式下提高了若干倍，但是，对于每一条指令来说，反而比非流水线方式时延长了执行时间。
每个流水段中的部件都是一组组合逻辑加上一组寄存器，组合逻辑中产生的结果在时钟到来时被存到寄存器（如程序计数器、条件码寄存器、流水段寄存器）中。每两个相邻流水段之间的流水段寄存器，用以记录所有在后面阶段要用到的各种信息，例如指令代码、参加运算的操作数、指令运算结果、指令异常信息、寄存器读口地址、寄存器写口地址、存储单元地址、新的PC值。指令译码得到的控制信号也通过流水段寄存器传送到后面各个流水段中。
<!-- page: 161 -->
## 2. 指令流水线的局限性
理想情况下，每个时钟到来，都有一条指令进入流水线，也有一条指令执行结束。但是，很多因素会导致指令流水线的情况不很理想。首先，并不是每条指令都有相同多个流水段，也不是每个流水段的执行都需要一样长的时间，因此，为了能够方便地控制指令流水线的执行，通常以最复杂指令所需阶段数来确定流水段个数，并以最复杂阶段所需时间为基准来设计时钟周期；其次，随着流水线深度的增加，流水段寄存器的读写所带来的额外开销比例也增大；最后，指令执行时，还会发生资源冲突、数据相关、控制相关、cache缺失等问题，导致流水线被阻塞而延长程序执行时间。
## 3. 流水线数据通路设计举例
以下以 MIPS 处理器为例，概要说明流水线数据通路的实现原理。与第 5 章中单周期数据通路和多周期数据通路的实现目标一样，流水线数据通路的实现目标也是表 5.1 所示的 11 条 MIPS 指令。根据对这 11 条指令的分析，可以得到执行这 11 条指令的 5 段流水线数据通路基本框架，如图 6.1 所示。
图 6.1 5 段流水线数据通路基本框架
在图 6.1 所示的流水线数据通路中，每条指令的执行都经历 5 个流水段：IF、ID、Ex、Mem 和 Wr，每个流水段都在不同的功能部件中执行。流水段之间有一个流水段寄存器，例如，IF/ID 寄存器是介于 IF 段和 ID 段之间的寄存器。每个流水段寄存器用来存放从当前流水段传到后面所有流水段的信息。因为每个段间传递的信息不一样，所以各流水段寄存器的长度也不一样。
图 6.1 中的取指令部件 IUnit 和执行部件 ExecUnit 分别如图 6.2 和图 6.3 所示。
如图 6.2 所示的取指令部件中，IM 为指令存储器，取出的指令被送到 IF/ID 流水段寄
<!-- page: 162 -->
图6.2 取指令部件 IUnit 的实现
图6.3 执行部件 ExecUnit 的实现
存器的输入端，在下个时钟到来后开始写入。在取指令的同时，计算 $\mathrm{PC} + 4$，得到的值被送到 PC 的输入端，在下个时钟到来后开始写入 PC。
不同的指令在不同的控制信号控制下在执行部件中执行不同的操作。