12 KiB
指令级并行 - 章节习题与答案详解
说明
本章节内容涉及指令级并行的核心概念、动态调度算法、分支预测技术以及多指令流出技术。三位老师的PPT中均包含相关练习题目，以下整理所有习题并给出参考答案与详细解析。
曲冠南老师习题
习题一：Tomasulo算法指令执行状态表题目
原题（Slide 60）：
单流出处理器采用基于Tomasulo算法进行指令调度。有一个LSU部件（部件内有加法器），2个LS缓冲器（FIFO队列），一个加/减法运算部件，一个乘/除法运算部件，2个ALU保留站。指令序列执行前，指令均未流出，所有缓冲器/保留站均空闲。
（1）各个硬件操作流水段及指令通过的时钟周期如下表
（2）待执行指令序列如下：
问： （1）请给出指令执行状态时钟周期表 （2）请给出第14周期末尾各个状态表内容
习题二：前瞻执行Tomasulo算法题目
原题（Slide 97）：
单流出处理器采用基于Tomasulo的IS算法进行指令调度。有一个LSU部件（内部自带加法器），2个LS缓冲器（私有时间戳实现FIFO），1个加法ALU部件，1个乘法ALU部件，2个ALU保留站。总是预测分支失败。指令序列执行前，指令均未流出，所有缓冲器/保留站均空闲。分支指令由加法ALU部件执行。ROB空间足够。
（1）各个硬件操作及指令执行的时钟周期如下表
（2）待执行指令序列如下：
问： （1）请给出指令执行状态时钟周期表 （2）给出第16周期末尾各状态表内容
李宏图老师习题
习题三：记分牌算法题目
原题（Slide 75）：
例 单流出处理器采用基于scoreboard算法进行指令调度。有一个LSU部件，2个ALU部件。指令序列执行前，指令均未流出。
（1）各个硬件操作及指令执行的时钟周期如下表
（2）待执行指令序列如下：
问： （1）请给出指令执行状态时钟周期表 （2）请给出第18周期末尾各状态表内容
参考答案与解析：
考点：记分牌算法的四个阶段（发射、读操作数、执行完成、写结果）以及三张表（指令状态表、功能部件状态表、寄存器结果状态表）的管理。
原理：
记分牌算法允许指令乱序执行，通过三张表来跟踪和管理指令的执行状态：
- 指令状态表：记录每条指令当前处于哪个阶段（发射、读操作数、执行完成、写结果）
- 功能部件状态表：记录每个功能部件是否在使用、做何种操作、目标寄存器、源寄存器等
- 寄存器结果状态表：记录哪个功能部件将写入每个寄存器
解题思路：
- 首先分析指令序列中各指令间的数据相关（RAW、WAR、WAW）
- 根据功能部件的可用性和寄存器状态，决定每条指令何时可以进入下一阶段
- 跟踪每个时钟周期各表的变化
习题四：Tomasulo算法指令执行题目
原题（Slide 124）：
例 单流出处理器采用基于Tomasulo算法进行指令调度。有一个LSU部件，2个LS缓冲器（私有时间戳实现FIFO），2个ALU部件（一个加/减法运算，一个乘/除法运算），2个ALU保留站。指令序列执行前，指令均未流出，所有缓冲器/保留站均空闲。
（1）各个硬件操作流水段及指令通过的时钟周期如下表
（2）待执行指令序列如下：
问： （1）请给出指令执行状态时钟周期表 （2）请给出第14周期末尾各个状态表内容
参考答案与解析：
考点：Tomasulo算法的三个阶段（流出、执行、写结果）、保留站和寄存器状态表的管理。
原理：
Tomasulo算法通过保留站实现寄存器换名，消除WAR和WAW冲突。关键点包括：
- 指令按程序顺序流出到保留站
- 操作数就绪后从寄存器或CDB获取
- 结果通过CDB广播到所有等待的保留站
解题思路：
- 跟踪每条指令的流出时间（需要检查保留站空闲）
- 跟踪执行阶段的等待（需要检查源操作数是否就绪）
- 跟踪写结果阶段（需要检查CDB就绪）
- 更新保留站状态表和寄存器状态表Qi
习题五：分支目标缓冲器BTB计算题
原题（Slide 148-150）：
举例： 假设有一条长流水线，仅仅对条件转移指令使用分支目标缓冲。假设分支预测错误的开销为4个时钟周期，缓冲不命中的开销为3个时钟周期。假设：命中率为90%，预测精度为90%，分支频率为15%，没有分支的基本CPI为1。
（1）求程序执行的CPI。 （2）相对于采用固定的2个时钟周期延迟的分支处理，哪种方法程序执行速度更快？
参考答案：
（1）求程序执行的CPI
程序执行的CPI = 没有分支的基本CPI（1） + 分支带来的额外开销
分支带来的额外开销 = 分支指令中缓冲命中但预测错误带来的开销 + 缓冲没有命中带来的开销
= 15% × (90%命中 × 10%预测错误 × 4 + 10%没命中 × 3) = 15% × (0.9 × 0.1 × 4 + 0.1 × 3) = 15% × (0.36 + 0.3) = 15% × 0.66 = 0.099
所以，程序执行的CPI = 1 + 0.099 = 1.099
（2）比较两种方法
采用固定的2个时钟周期延迟的分支处理： CPI = 1 + 15% × 2 = 1 + 0.3 = 1.3
由（1）（2）可知：1.099 < 1.3，因此分支目标缓冲方法执行速度更快。
详细解析：
考点：BTB（分支目标缓冲器）的性能计算，理解命中率、预测精度与分支频率对CPI的影响。
原理：
- BTB通过缓存分支指令的地址和目标地址来加速分支处理
- 命中BTB且预测正确时，分支开销最小（接近0）
- 命中BTB但预测错误时，承受分支预测错误开销
- 未命中BTB时，承受缓冲不命中开销
解题思路：
- 识别题目给出的参数：命中率90%、预测精度90%、分支频率15%、预测错误开销4周期、不命中开销3周期
- 分支总开销 = 分支频率 × [命中率 × (1-预测精度) × 预测错误开销 + (1-命中率) × 不命中开销]
- 代入公式计算
习题六：前瞻执行例题
原题（Slide 169）：
例题： 假设浮点功能部件的延迟时间为：加法2个时钟周期，乘法10个时钟周期，除法40个时钟周期。对于下面的代码段，给出当指令MUL.D即将确认时的状态表内容。
L.D F6,34（R2）
L.D F2,45（R3）
MUL.D F0,F2,F4
SUB.D F8,F6,F2
DIV.D F10,F0,F6
ADD.D F6,F8,F2
参考答案与解析：
考点：基于Tomasulo的前瞻执行机制，理解流出、执行、写结果、确认四个阶段，以及ROB的工作原理。
原理：
前瞻执行在Tomasulo算法基础上增加了"确认"阶段：
- 指令前瞻执行的结果写入ROB而不是直接写寄存器
- 按顺序确认，只有到达ROB头部且就绪的指令才能确认
- 分支预测错误时，清空ROB并从另一分支重新开始
解题思路：
- 首先分析指令间数据相关
- 跟踪每条指令在四个阶段的状态
- 当MUL.D即将确认时，给出保留站和ROB的状态
习题七：多流出超标量MIPS流水线题目
原题（Slide 181-183）：
例1： 对于采用了Tomasulo算法和多流出技术的MIPS流水线，考虑以下简单循环的执行。该程序把F2中的标量加到一个向量的每个元素上。
Loop: L.D F0, 0（R1） // 取一个数组元素放入F0
ADD.D F4, F0, F2 // 加上在F2中的标量
S.D F4, 0（R1） // 存结果
DADDIU R1,R1，#-8
// 将指针减少8（每个数据占8个字节）
BNE R1,R2,Loop
// 若R1不等于R2，表示尚未结束，转移到Loop继续
现做以下假设： ①每个时钟周期能流出一条整数指令和一条浮点指令，即使它们相关也是如此。 ②有一个整数部件，用于整数ALU运算和地址计算； 并且对于每一种浮点操作类型都有一个独立的流水化了的浮点功能部件。 ③指令流出和写结果各占用一个时钟周期。 ④具有动态分支预测部件和一个独立的计算分支条件的功能部件。 ⑤分支指令单独流出，没有采用延迟分支，但分支预测是完美的。分支指令完成前，其后续指令只能被取出和流出，但不能执行。 ⑥因为写结果占用一个时钟周期，所以产生结果的延迟为：整数运算1个周期，load为2个周期，浮点加法运算3个周期。
列出该程序前面3遍循环中各条指令的流出、开始执行和将结果写到CDB上的时间。
参考答案与解析：
考点：超标量处理机的动态调度，理解多流出技术、Tomasulo算法在超标量中的应用，以及分支预测对流水线的影响。
原理：
超标量技术允许每个时钟周期流出多条指令，题目假设为1条整数指令+1条浮点指令的组合。关键点：
- 分支预测是完美的，所以不会有预测错误开销
- 分支指令完成前，后续指令只能取出和流出但不能执行
- load指令有2周期延迟，浮点加法有3周期延迟
解题思路：
- 列出循环中各指令及其延迟
- 分析指令间的数据相关
- 按时间周期跟踪各指令的流出、开始执行、写结果状态
- 注意相邻迭代之间的数据相关
习题八：VLIW例题
原题（Slide 192）：
3.例题 假设VLIW处理机每个时钟周期可同时流出5条指令：两条访存指令、两条浮点操作指令和一条整数指令或分支指令。对于例1中的循环展开后的代码，给出它在该VLIW中的代码序列。不考虑分支指令的延迟槽。
参考答案与解析：
考点：VLIW（超长指令字）技术，理解显式并行指令表示、指令打包以及循环展开。
原理：
VLIW技术将多条并行指令打包成一条长指令，由编译器静态调度决定哪些指令可以并行流出。题目要求将循环展开后的代码映射到VLIW的5个操作槽中。
谭婧炜佳老师习题
习题九：Tomasulo算法详细执行过程题
原题（Slide 134）：
前瞻执行示例 例 假设浮点功能部件的延迟时间为：加法2个时钟周期，乘法10个时钟周期，除法40个时钟周期。对于下面的代码段，给出基于Tomasulo算法的前瞻执行的执行过程。
L.D F6,34（R2）
L.D F2,45（R3）
MUL.D F0,F2,F4
SUB.D F8,F6,F2
DIV.D F10,F0,F6
ADD.D F6,F8,F2
参考答案与解析：
考点：基于Tomasulo的前瞻执行机制详细执行过程。
原理：
前瞻执行机制的关键是引入ROB来实现顺序确认：
- 流出：指令从浮点指令队列头部取出，分配保留站和ROB项
- 执行：操作数就绪后执行
- 写结果：结果写到ROB而非寄存器
- 确认：按顺序确认，只有到达ROB头部且就绪才能确认
解题思路：
- 逐周期跟踪各指令的状态变化
- 记录保留站中各字段的变化
- 记录ROB各目的状态
- 理解乱序执行但顺序确认的概念
章节重点知识总结
核心考点
-
CPI公式：CPI流水线 = CPI理想 + 停顿结构冲突 + 停顿数据冲突 + 停顿控制冲突
-
三种相关：数据相关（RAW）、名相关（WAR/WAW）、控制相关
-
循环展开与指令调度：通过重命名和调度开发循环级并行性
-
Tomasulo算法：保留站、CDB、寄存器换名、流出-执行-写结果三阶段
-
记分牌算法：发射-读操作数-执行完成-写结果四阶段，三张表管理
-
BHT/BRB：分支历史表和分支目标缓冲器的原理与性能计算
-
前瞻执行：ROB、顺序确认、精确异常
-
超标量vs VLIW：动态vs静态多流出
解题要点
- 熟练掌握Tomasulo算法的状态表更新规则
- 理解各算法如何解决RAW、WAR、WAW冲突
- 掌握分支预测技术的性能计算公式
- 理解前瞻执行的确认机制和精确异常处理