说明

1. 博客作为笔记备份，不定时更新
2. 参考内容为《计算机组成原理（第3版）》唐朔飞 高等教育出版社；王道考研《计算机组成原理考研复习指导2023》
3. 文中的例题摘自王道考研《计算机组成原理考研复习指导2023》，大多是我个人认为较为典型的题目以及错题的部分整理

指令流水

《计算机系统结构（第2版）》张晨曦 王志英 高等教育出版社 $Chapter3P_{50}$

1. 流水线的基本概念

• 可从两方面提高处理机的并行性
  • 时间上的并行技术：将一个任务划分为几个不同的子阶段，每个阶段在不同的功能部件上并行执行，以便在同一时间能同时执行多个任务，从而提升系统性能。这种方法被称为流水线技术
  • 空间上的并行技术：在一个处理机内设置多个执行相同任务的功能部件，并让这些功能部件并行工作，这样的处理机称为超标量处理机

1.1 指令流水的定义

• 假设一条指令执行过程为如下5个阶段
  • 取指 IF：从IR或Cache中取指令
  • 译码/读寄存器 ID：操作控制器对指令进行译码，同时从寄存器堆中取操作数
  • 执行/计算地址 EXE：执行运算操作或计算地址
  • 访存 MEM：对存储器进行读/写操作
  • 写回 WB：将指令执行结果写回寄存器堆
• 流水线的设计原则
  • 指令流水段个数以最复杂指令所用的功能段个数为准
  • 流水段的长度以最复杂的操作所花的时间为准
  • 注：流水线方式并不能缩短单条指令的执行时间，但对于整个程序来说，执行效率得到了大幅提高
• 为了利于实现流水线，指令集应该：
  • 指令长度应尽量一致，有利于简化取指和译码操作
  • 指令格式应尽量规整，尽量保证源寄存器的位置相同，有利于在指令未知时就可取寄存器操作数，否则要等译码后才能确定指令中各寄存器编号的位置
  • 采用LOAD/STOER指令，其他指令不能访存，这样可以把LOAD/STORE指令的地址计算和运算指令的执行步骤规整在同一个周期中，有利于减少操作步骤
  • 数据和指令在存储器中对齐存放，有利于减少访存次数，使得所需的数据在一个流水段内就能从存储器中得到

1.2 流水线的表示方式

• 通常用时空图描述流水线的执行情况
  

1.3流水线特点总结

• 流水线实际上是把一个大的处理功能部件划分为多个独立的功能部件，并依靠它们的并行工作来缩短程序的执行时间
• 流水线各段的时间应尽量相等，否则将引起流水线堵塞、断流，因为时间长的段将成为流水线的瓶颈，此时流水线中其他功能部件就不能充分发挥作用
• 流水线每个功能部件后都要有一个缓冲寄存器（锁存器)，成为流水寄存器，其作用是在相邻两段之间传送数据，并把各段的处理工作相互隔离
• 流水线技术适用于大量重复的时序过程，只有在输入端不断地提供任务，才能充分发挥流水线的效率
• 流水线需要通过时间和排空时间，分别指第一个任务和最后一个任务从进入流水线到流出结果的那个时间段，在这两个时间段中，流水线都不是满段

流水线分类（补充，来自体系结构课本）

单功能流水线与多功能流水线

• 按流水线所完成的功能来分
• 单功能流水线：只能完成一种固定功能的流水线
• 多功能流水线：流水线的各段可进行不同的连接，以实现不同的功能

静态流水线和动态流水线

• 按同一时间内各段之间的连接方式对多功能流水线进一步划分
• 静态流水线：同一时间段内，多功能流水线各段只能按同一种功能的连接方式工作。比如：当要在n个浮点加法运算后进行定点乘法时，必须等最后一个浮点加法完成、流水线排空后，才能改变连接，开始新的运算
• 动态流水线：同一时间段内，多功能流水线中的各段可以按照不同的方式连接，同时执行多种功能。即允许某些段在实现某种运算时，另一些段在实现另一种运算

部件级、处理机级、处理机间流水线

• 按流水的级别分
• 部件级流水线（又称运算操作流水线）：把处理机的算术逻辑运算部件分段
• 处理机级流水线（又称指令流水线）：把指令的解释执行过程按流水方式处理
• 处理机间流水线（又称宏流水线）：由两个或两个以上的处理机串行连接起来，对同一数据流进行处理，每个处理机完成整个任务的一部分

线性流水线与非线性流水线

• 按流水线中是否有反馈回路来分
• 线性流水线：流水线各段串行连接，没有反馈回路，数据流过流水线的各段时，每个段最多只能流过一次
• 非线性流水线：含有反馈回路。在非线性流水线中，要确定何时向流水线引进新的任务，才能使该任务不会与先进入流水线的任务发生冲突——争用流水段，这就是非线性流水线的调度问题

顺序流水线和乱序流水线

• 按任务流入和流出的顺序是否相同来分
• 顺序流水线：流水线输出端任务流出的顺序与输入端任务流入顺序一致
• 乱序流水线：流出和流入顺序可以不同，允许后进来流水线的任务先完成

2. 流水线的性能指标

吞吐率 TP

• 单位时间内流水线所完成的任务数量，或输出结果的数量
• $TP=\frac{n}{T_k}$, n是任务数，$T_k$是处理完n个任务所用的总时间
• 设k为流水线段数，$\Delta t$是时钟周期，在输入流水线中的任务连续的理想情况下，一条k段流水线能在 $k+n-1$个时钟周期内完成n个任务，得到流水线吞吐率：
  $$TP=\frac{n}{(k+n-1)\Delta t}$$
• $T{P}_{max}=\frac{1}{\Delta t}$
• $TP=\frac{n}{k+n-1}T{P}_{max}$，只有当$n\gg k$时才有$TP\approx T{P}_{max}$

加速比 S

• 完成同一批任务，不使用流水线和使用流水线所用时间之比
• $S=\frac{T_0}{T_k}$，$T_0$表示不使用流水线的总时间，$T_k$表示使用k段流水线的总时间
  $$S=\frac{kn\Delta t}{(k+n-1)\Delta t}=\frac{kn}{k+n-1}$$
• $S_{max}=k$，当$n\gg k$时，流水线的加速比等于其段数

效率

• 流水线中的设备实际使用时间与整个运行时间的比值，即流水线设备的利用率
• 从时空图上看，效率就是n个任务占用的时空面积和k个段总的时空面积比

3. 流水线的冒险与处理

3.1 相关

• 相关指两条指令之间存在某种依赖关系。若两条指令相关，则它们就有可能不能在流水线中重叠执行或只能部分重叠

数据相关

• 对于指令i（在前）和指令j（在后），若满足一下条件之一，就称j和i数据相关：
  • 指令 j 使用指令 i 产生的结果
  • 指令 j 与指令 k 数据相关，而指令 k 与指令 i 数据相关（这表明数据相关具有传递性）
• 数据相关反映了数据的流动关系，即如何从其产生者流动到其消费者

名相关

• “名”指指令所访问的寄存器或存储器单元的名称。若两条指令使用相同的名，但它们之间没有数据流动，就成它们存在名相关
• 指令 j 和 i 之间的名相关有两种：
  • 反相关 anti-dependence：指令 j 写的名与指令 i 读的名相同。反相关指令之间的执行顺序必须严格遵守，以保证 i 读的值是正确的
  • 输出相关 output-dependence：指令 j 和指令 i 写相同的名。输出相关的执行顺序不能颠倒，以保证最后的结果是指令 j 写进去的
• 与真数据相关不同，名相关的两条指令之间并没有数据的传送，只是使用了相同的名
• 可通过改变指令中操作数的名来消除名相关，这就是换名技术，对寄存器操作数的换名又称为寄存器换名

控制相关

• 由分支引起的相关。它需要根据分支指令的执行结果来确定后续指令是否执行

if p1{
	S1;
};
S;
if p2{
	S2;
};
1
2
3
4
5
6
7

• 语句S1与p1控制相关，S2与p2控制相关，S与p1和p2均无关
• 控制相关带来的限制
  • 与一条分支指令控制的指令不能被移到该分支之前。对上例：then部分中的指令不能移到if语句之前
  • 若一条指令与某分支指令不存在控制相关，就不能把该指令移到该分支指令之后。对上例：不能把S移到if语句的then部分中

3.2 冒险（也称冲突）

结构冒险

• 由于多条指令在同一时刻争用同一资源而形成的冲突，也称为资源冲突，即由硬件资源竞争而造成的冲突
• 解决
  • 前一指令访存时，使后一条相关指令（以及其后续指令）暂停一个时钟周期
  • 单独设置数据存储器和指令存储器，使取数和取指令操作各自在不同的存储器中进行。（现代计算机引入Cache机制，L1 Cache通常采用指令和数据分离的方式，从而避免资源冲突）

数据冒险

• 在一个程序中，下一条指令会用到当前指令计算出的结果。当相关的指令靠的足够近时，它们在流水线中的重叠执行或者重新排序会改变指令读/写操作数的顺序，使之不同于它们非流水线实现时的顺序，则发生了数据冲突
• 数据冲突，习惯上这些冲突是按照流水线必须保持的访问顺序来命名的
  • 写后读冲突 RAW：指令 j 用到指令 i 的计算结果，而且在 i 将结果写入寄存器之前就去读该寄存器，因此得到的是旧值。对应于真数据相关
  • 写后写冲突 WAW：指令 j 和指令 i 的结果单元（寄存器或存储器单元）相同，而且 j 在 i 写入之前就先对该单元进行了写入操作，从而导致写入顺序错误。对应于输出相关
    • WAW冲突仅发生在：流水线中不止一个段可以进行写操作，或当先前某条指令停顿时，允许后续指令继续前进
  • 读后写冲突 WAR ：指令 j 的结果单元和指令 i 的源操作数单元相同，而且 j 在 i 读取该单元之前就对该单元进行了写操作，导致 i 读到的值是错误的
    • WAR冲突仅发生在：有些指令的写结果操作提前了，而有些指令的读操作滞后了，或者指令被重新排序了
• 解决
  • 采用数据旁路技术（定向技术）
    • 思想：在某条指令产生计算结果之前，其他指令并不真正立即需要该计算结果，若能够将该计算结果从其产生的地方直接送到其他指令需要它的地方，就可以避免停顿。推广：将结果数据从其产生的地方直接传送到所有需要它的功能部件
    • 可以这样实现定向：
      • EX段和MEM段之间的流水寄存器中保存的ALU运算的结果总是回送到ALU的输入端
      • 但当定向硬件检测到前一个ALU运算结果写入的寄存器就是当前ALU操作的源寄存器时，那么控制逻辑就选择定向的数据作为ALU的输入，而不采用从通用寄存器组中读出的值
  • 需要停顿的数据冲突
    • 把遇到数据相关的指令及其后续指令都暂停一至几个时钟周期，直到数据相关消失后再继续执行。可分为硬件阻塞（stall）和软件插入NOP指令两种方法
    • stall方式：设置一个“流水线互锁机制”的功能部件，一般来说它的作用是检测发现数据冲突，并使流水线停顿，直至冲突消失
  • 依靠编译器解决
    • 通过编译器对数据相关的指令编译优化，调整指令顺序来解决数据相关。这种技术称为指令调度或流水线调度

控制冒险

• 指令通常是顺序执行的，但在遇到执行转移、调用或返回执行时，会改变PC的值，会造成断流，从而引起控制冒险
• 解决
  • 分支预测：尽早生成转移目标地址
    • 分为简单（静态）预测和动态预测
    • 静态预测总是预测条件不满足，即继续执行后续指令
    • 动态预测根据程序执行的历史情况，进行动态预测调整，有较高的预测准确率
  • 预取转移成功和不成功两个控制流方向上的目标指令
  • 加快和提前形成条件码
  • 提高转移方向的猜准率

4. 流水线的基本实现

4.1 流水线的数据通路

• IF段包括PC、指令存储器、下条指令地址的计算逻辑
• ID段包括操作控制器、取操作数逻辑、立即数符号扩展模块
• EX段主要包括ALU、分支地址计算模块
• MEM段主要包括数据存储器读写模块
• WB段主要包括存储器写入控制模块
• 说明
  • 各种寄存器和数据存储器均采用统一时钟CLK进行同步，每来一个时钟，就会一条新的指令进入流水线IF段
  • 流水寄存器会锁存前段加工处理完的数据和控制信号
  • 不同流水寄存器锁存的数据不相同

4.2 流水线的控制信号

• 在某一时刻，每个流水段执行不同指令的某个阶段，每个流水段需要正在执行指令的对应功能段的控制信号
• 图5.19中的控制信号分类

• 每个流水寄存器中保存的信息包括：
  • 后面流水段需要用到的所有数据信息，包括PC+4、指令、立即数、目的寄存器、ALU运算结果、标志信息等
  • 前面传递过来的后面流水段要用到的所有控制信号

4.3 流水线的执行过程

1. 取指 IF
   • 将PC值作为地址从指令寄存器中取出第一条指令字，并计算PC+4将其送入PC输入端，以便于在下一个时钟周期取下条指令，这些功能由取指部件完成
   • 取出的指令字通过RD输出端送入IF/ID流水寄存器，PC+4也送入IF/ID流水寄存器（只要是后续功能段可能用到的数据和控制信号都要向后传递）
   • 时钟到来时将更新后的PC值和指令字锁存到IF/ID流水寄存器中；本条指令$I_1$进入ID段，IF段取出下一条指令$I_2$
2. 译码/读寄存器 ID
   • 由控制器根据IF/ID流水寄存器中的指令字生成后续各段所需的控制信号
     • 对于LW访存指令，根据指令字中的rs、rt取出寄存器堆中的值RS和RT
     • 符号扩展单元会将指令字中的16位立即数符号扩展为32位
     • 多路选择器根据指令字生成指令可能的写寄存器编号WriteReg#
   • 时钟到来时，这些数据、控制信号、PC+4都会锁存到ID/EX流水寄存器中；指令$I_1$ 进入EX段，$I_2$进入ID段，指令$I_3$进入IF段
3. 执行/计算地址 EX
   • EX段的功能由具体的指令确定，不同指令经ID段译码后得到不同的控制信号
     • 对于LW指令，EX主要用来计算访存地址，将ID/EX流水寄存器中的RS值与符号扩展后的立即数相加得到的访存地址送入EX/MEM寄存器
     • EX段可能还要计算分支地址，生成分支跳转信号BranchTaken
     • RT的值可能会在MEM段作为写入数据使用，所以RT会作为数据WriteData送入EX/MEM流水寄存器
   • 时钟到来后，这些数据和控制信号会锁存到EX/MEM流水寄存器中；$I_1$进入MEM段，$I_2、I_3、I_4$分别进入EX、ID、IF段
4. 访存 MEM
   • MEM段的功能也由具体指令确定
     • 对于LW指令，主要是根据EX/MEM流水寄存器中的访存地址，写入数据和内存读写控制信号MemWrite对存储器进行读/写操作
     • EX/MEM流水寄存器中的访存地址、WriteReg#、数据存储器读出的数据都会送入MEM/WB流水寄存器
   • 时钟到来后，这些数据和控制信号会锁存到MEM/WB流水寄存器中；$I_1$ 进入WB段，$I_2、I_3、I_4、I_5$分别进入MEM、EX、ID、IF段
5. 写回 WB
   • WB段的功能也由具体指令确定
     • 将MEM/WB流水寄存器中数据存储器读出的数据写回指令寄存器WriteReg#
   • 时钟到来时会完成数据写入寄存器；$I_1$ 离开流水线，$I_2、I_3、I_4、I_5、I_6$分别进入WB、MEM、EX、ID、IF段

5. 高级流水线技术

• 增加指令级并行的策略
  • 多发射技术：通过采用多个内部功能部件，使流水线功能段能同时处理多条指令，处理机一次可以发射多条指令进入流水线执行
  • 超流水线技术：通过增加流水线的级数，使更多的指令同时在流水线中重叠执行

5.1 超标量流水线技术

• 超标量流水线技术也称动态多发射技术，每个时钟周期内可并发多条独立指令，以并行操作方式将两条或多条指令编译并执行，为此需配置多个功能部件
• 超标量技术不能调整指令的执行顺序，因此通过编译优化技术，把可并行执行的指令搭配起来，挖掘更多的指令并行性

5.2 超长指令字技术

• 也称静态多发射技术，由编译程序挖掘出指令间潜在的并行性，将多条能并行操作的指令组合成一条具有多个操作码字段的超长指令字，为此需要多个处理部件

5.3 超流水线技术

• 流水线功能段划分的越多，时钟周期就越短，指令吞吐率就越高，因此超流水线技术就是通过提高流水线主频的方式来提升流水线性能的
• 流水线级数越多，用于流水寄存器的开销越大，因此流水线的级数是有限制的，并非越多越好
• 超流水线CPU在流水线充满后，每个时钟周期还是执行一条指令，CPI=1，但其主频更高；多发射流水线CPU每个时钟周期可以处理多条指令，$CPI<1$，相对而言， 多发射流水线成本更高，控制更复杂

6. 例题

超标量流水线

（$P_{254}2$）下列关于超标量流水线的叙述中，不正确的是（）
A. 在一个时钟周期内一条流水线可执行一条以上的指令
B. 一条指令分为多段指令由不同电路单元完成
C. 超标量通过内置多条流水线来同时执行多个处理器，其实质是以空间换取时间
D. 超标量流水线是指运算操作并行
解答：超标量流水线是指在一个时钟周期内一条流水线可执行一条以上的指令。一条指令分为多段指令，由不同电路单元完成。超标量通过内置多条流水线来同时执行多个处理器，实际是以空间换时间。选D
错误原因：错选A，对超标量流水线相关概念掌握不好

（$2017$）下列关于超标量流水线特性的叙述中，正确的是（）
I. 能缩短流水线功能段的处理时间
II. 能在一个时钟周期内同时发射多条指令
III. 能结合动态调度技术提高指令执行并行性
A. 仅II B. 仅I、III C. 仅II、III D. I、II、III
解答：选C
错误原因：错选A

数据通路

（$2017$）下列关于指令流水线数据通路的叙述中，错误的是（）
A. 包含生成控制信号的控制部件
B. 包含算术逻辑运算部件ALU
C. 包含通用寄存器组和取指部件
D. 由组合逻辑电路和时序逻辑电路组合而成
解答：数据在功能部件之间传送的路径被称为数据通路，包括数据通路上流经的部件，如程序计数器、ALU、通用寄存器、状态寄存器、异常和中断处理逻辑等。数据通路由控制部件控制，控制部件根据每条指令功能的不同生成对数据通路的控制信号，因此不包括控制部件
错误原因：错选D

流水线每段的时间与CPU时钟周期

（$2018$）若某计算机最复杂指令的执行需要完成5个子功能，分别由功能部件A~E实现，各功能部件所需时间分贝为80ps、50ps、50ps、70ps、50ps，采用流水线方式执行指令，流水段寄存器延时为20ps，则CPU时钟周期至少为（）
A. 60ps
B. 70ps
C. 80ps
D. 100ps
解答：80ps+20ps=100ps
错误原因：错选C，其实应该加上流水段的延迟时间

综合题

（$2014$）某程序中有循环代码段P: for (int i=0; i

请回答下列问题，并说明理由。

1. M的存储器编址单位是什么?
   解答：已知计算机M采用32位定长指令字，即一条指令占4B，根据表中各指令的地址可知，每条指令的地址差为4个地址单位，即4个地址单位代表4B，一个地址单位就代表了1B，因此该计算机是按字节编址的。
2. 巳知sll指令实现左移功能，数组A中每个元素占多少位?
   解答：在二进制中某数左移2位代表乘以4，由此可知，数组间的数据间隔为4个地址单位，计算机按字节编址，因此数组A中每个元素占4B
3. 表中bne指令的OFFSET字段的值是多少?已知bne指令采用相对寻址方式，当前PC内容为bne指令地址，通过分析表中指令地址和bne指令内容，推断bne指令的转移目标地址计算公式。
   解答：
   • 由表可知，bne指令的机器代码是1446FFFAH，根据题目给出的指令格式，后2B的内容是OFFSET字段，所以该指令的OFFSET字段为FFFAH，用补码表示，即值为-6
   • 系统执行到bne指令时，PC自动加4，PC的内容为08048118H，而跳转的目标是08048100H，二者相差18H，即24个单位的地址间隔，所以偏移地址的一位即是真实跳转地址的-24/-6=4位，可知bne指令的转移目标地址计算公式为$(PC)+4+OFFSET\times 4$
4. 若M采用如下“按序发射、按序完成”的5级指令流水线: IF (取值)、ID (译码及取数)、EXE (执行)、MEM (访存)、WB (写回寄存器)，且硬件不采取任何转发措施，分支指令的执行均引起3个时钟周期的阻塞，则P中哪些指令的执行会由于数据相关而发生流水线阻塞?哪条指令的执行会发生控制冒险?为什么指令1的执行不会因为与指令5的数据相关而发生阻塞?
   解答：由于数据相关而发生阻塞的指令为2,3,4,6条，因为它们都与各自前一条指令发生数据相关。第6条指令会发生控制冒险。当前循环的第5条指令与下次循环的第1条指令虽然有数据相关，但由于第6条指令后有3个时钟周期的阻塞，因而消除了数据相关

（$2014$）假设对于上题中的计算机M和程序P的机器代码，M采用页式虚拟存储管理; P开始执行时，(R1)= (R2)= 0，(R6)= 1000，其机器代码巳调入主存但不在Cache中;数组A未调入主存，且所有数组元素在同一页，并存储在磁盘的同一个扇区。请回答下列问题并说明理由。

1. P执行结束时，R2的内容是多少?
   解答：R2中装入的是i的值，循环条件是i<1000，即当i自增到不满足这个条件时跳出循环，程序结束，所以此时i的值为1000
2. M的指令Cache和数据Cache分离。若指令Cache共有16行，Cache和主存交换的块大小为32B， 则其数据区的容量是多少?若仅考虑程序段P的执行，则指令Cache的命中率为多少?
   解答：
   • Cache一共16行，每块32字节，所以Cache数据区的容量为$16\times 32B=512B$
   • P共有6条指令，占24B，小于主存块大小32B，其起始地址为0804 8100H，对应一块的开始位置，由此可知所有指令都在一个主存块内。读取第一条指令时会发生Cache缺失，因此将P所在的主存块调入Cache的某一行，以后每次读取指令时，都能在指令Cache中命中。因此1000次循环中，只会发生1次指令访问缺失，所以指令Cache的命中率为$\frac{1000\times 6-1}{1000\times 6}=99.98\%$
3. P在执行过程中，哪条指令的执行可能发生溢出异常?哪条指令的执行可能产生缺页异常?对于数组A的访问，需要读磁盘和TLB至少各多少次?
   解答：
   • 指令4位加法指令，即对应sum+=A[i]，当数组A中元素的值过大时，会导致这条加法指令发生溢出异常；而指令2,5虽都是加法指令，但它们分别是数组地址的计算指令和存储变量i的寄存器进行自增的指令，而i最大到1000，所以它们都不会产生溢出异常
   • 只有访存指令可能产生缺页异常，即指令3可能产生缺页异常。因为数组A在磁盘的一页上，而一开始数组并不在主存中，第一次访问数组时会导致访盘，把A调入内存，而以后数组A的元素都在内存中，不会导致访盘，所以该程序共访盘一次
   • 每访问一次内存数据就会查一次TLB，共访问数组1000次，因此此时又访问TLB1000次，还要考虑到第一次访问数组A，即访问A[0]时，会多访问一次TLB（第一次访问A[0]时会先查一次TLB，然后产生缺页，处理完缺页中断后，会重新访问A[0]，此时又查TLB），所以访问TLB的次数一共是1001次

更新文档