课程
计算机体系结构雨课堂第五章作业
计算机体系结构雨课堂第五章作业
1. 说出两种比较典型的动态调度算法:
- A. 记分牌算法 (Scoreboarding)
- B. Tomasulo算法
正确答案：记分牌算法、Tomasulo算法
解析： 动态调度旨在在硬件运行时解决数据相关导致的停顿。两种里程碑式的算法是：
- 记分牌算法 (Scoreboarding)：CDC 6600最早采用，集中式控制。
- Tomasulo算法：IBM 360/91最早采用，基于保留站和公共数据总线（CDB）的分布式控制，支持寄存器重命名。
2. 要扩充Tomasulo算法支持前瞻执行，需将Tomasulo算法中的“写结果”段分为____和____两个段。
正确答案：写结果、指令确认 (Instruction Commit)
解析： 基于硬件的前瞻执行（Hardware-Based Speculation）在Tomasulo算法基础上增加了重排序缓冲（ROB）。为了保证精确异常和错误分支恢复，指令不能立即写回寄存器堆或存储器。原来的“写结果”阶段被分解为：
- 写结果（Write Result）：将结果广播到ROB和保留站。
- 指令确认（Commit/Retire）：只有当指令到达ROB头部且无异常/分支预测正确时，才永久更新状态（写寄存器/内存）。
3. 开发指令级并行的方法主要有两类:基于硬件的____开发方法以及基于软件的____
正确答案：动态、静态
解析：
- 基于硬件的动态开发方法：如动态调度（Tomasulo）、动态分支预测、硬件前瞻执行等，在运行时由硬件发现并行性。
- 基于软件的静态开发方法：如基本块调度、循环展开、静态分支预测、VLIW/EPIC等，在编译时由编译器重排指令。
4. Tomasulo算法中换名功能是在____中完成；而在前瞻执行机制中，换名功能是由____(请按照英文专业术语缩写填写)来完成的。
正确答案：保留站 (Reservation Stations)、ROB (Reorder Buffer)
解析：
- Tomasulo：寄存器重命名通过保留站（RS）的ID来实现。当指令发射到RS时，如果源操作数未就绪，就将其映射到生产该值的RS编号，从而消除了WAR和WAW冲突。
- 前瞻执行：重命名通过重排序缓冲（ROB）的表项ID来实现。目标结果先写入ROB，ROB编号代替了物理寄存器号，直到Commit阶段才写入ARF（体系结构寄存器文件）。
5. 主观题（5分）
假定有多个加法器，不存在加法器的资源冲突.有3条连续指令组成的程序代码如下：
ADD R1, R2, R4ADD R2, R1, R8SUB R1, R4, R5
（1)分析程序代码段中的数据相关。 （2)采用何种硬件技术可解决这些数据相关？请加以说明.
答案/解析：
(1) 数据相关分析：
- RAW (写后读)：
ADD R2, R1, R8依赖于ADD R1, R2, R4的R1。 (指令2 读 指令1 写)- WAR (读后写)：
ADD R2, R1, R8写R2，而ADD R1, R2, R4读R2。 (指令2 写 指令1 读) —— 注意：这是反相关，在乱序执行中可能导致冲突，但顺序发射通常先读后写。如果指令2先完成写回，指令1还在读，就会出错。SUB R1, R4, R5写R1，而ADD R2, R1, R8读R1。 (指令3 写 指令2 读)- WAW (写后写)：
SUB R1, R4, R5写R1，ADD R1, R2, R4也写R1。 (指令3 写 指令1 写)(2) 解决技术：
- 寄存器重命名（Tomasulo算法）：
- 通过保留站（RS）将架构寄存器（Logical Register）映射到物理资源（Tag）。
- 对于 WAR 和 WAW：重命名可以分配不同的存储位置。
- 指令1写到
R1_tag1。- 指令3写到
R1_tag3。- 指令2读取
R1_tag1的值。并不是物理上的同一个R1，从而消除了名相关。- 对于 RAW：通过公共数据总线 (CDB) 广播和监听。
- 指令2在保留站中监听
R1_tag1的结果，一旦指令1计算完成并在CDB广播，指令2自动捕获数据，从而正确处理真相关。
6. 在数据相关中，下面哪一种属于数据真相关（）
- A. RAW (Read After Write)
- B. WAR (Write After Read)
- C. WAW (Write After Write)
- D. RAR (Read After Read)
正确答案：A
解析：
- RAW（写后读）：后面指令用到前面指令计算的结果，是真正的数据传递依赖，称为真相关。
- WAR（读后写）和 WAW（写后写）：是由于复用寄存器名字导致的名相关（Name Dependence），可以通过寄存器重命名消除。
- RAR（读后读）：不产生冲突，不是相关。
7. 下面说法正确的是（）
- A. 指令调度可以避免冲突，也可以改变相关。
- B. 记分牌算法对Tomasulo算法改进了许多。
- C. 基于硬件的前瞻执行根本无法解决控制相关的问题。
- D. 基于动态和基于静态的多指令流出技术以及超长指令字技术都属于多指令流出技术。
正确答案：D
解析：
- A 错：指令调度（静态或动态）只能避免由于相关引发的流水线冲突（Stall），但不能改变指令间本质的数据相关（Dependency）。相关是程序的属性。
- B 错：历史发展是 Scoreboard -> Tomasulo。Tomasulo改进了Scoreboard（引入重命名消除WAW/WAR，引入CDB消除RAW等待）。
- C 错：硬件前瞻执行（Speculation）正是为了解决控制相关（Control Dependence）。它允许在分支结果出来前执行后续指令（预测），如果预测错误则回滚。
- D 对：多指令流出（Multiple Issue）包括超标量（Superscalar，动态/静态）和超长指令字（VLIW，静态），它们都属于这一类技术。
8. 在动态分支预测技术中，不论是BHT还是BHB，对分支预测结果只有（）种
- A. 1
- B. 2
- C. 3
- D. 4
正确答案：B
解析： 分支预测的最终结果只有两种基本状态：跳转 (Taken) 或 不跳转 (Not Taken)。
- 虽然2位预测器有4个状态（00, 01, 10, 11），但它们映射到的预测动作只有两种（例如 >=10 预测跳转，<10 预测不跳转）。题目问的是“预测结果”，通常指Taken/Not Taken。
9. 在硬件调度算法中，ROB算法的特征表现在（）
- A. 按序流出，乱序执行，顺序提交
- B. 按序流出，顺序执行，乱序提交
- C. 按序流出，乱序执行，乱序提交
- D. 以上都不对
正确答案：A
解析： ROB（重排序缓冲）的主要作用就是支持推测执行并保证精确异常。
- Issue (流出/发射)：按程序顺序（In-Order）。
- Execute (执行)：乱序（Out-of-Order），只要操作数就绪即可执行。
- Commit (提交/写回)：按程序顺序（In-Order），必须等ROB头部的指令完成且无异常才提交，确保程序状态的更新是顺序的。
10. 下列属于多指令流出技术的是 （）
- A. 超标量指令流水线 (Superscalar)
- B. 超流水流水线 (Superpipelining)
- C. 超长指令字流水线 (VLIW)
- D. B选项不对
正确答案：ABC
解析：
- 严格定义的“多指令流出”（Multiple Issue）通常指在一个时钟周期内发射多条指令。
- A Superscalar：硬件动态/静态决定并发发射多条。是典型的多流出。
- C VLIW：编译器打包多条操作到一条长指令，并行发射。是典型的多流出。
- B Superpipelining：通过增加流水线级数提高主频。虽然它提升了吞吐率，但并没有增加“单周期发射指令数”（IPC仍<=1）。
- 注意：但在很多中文教材或广义分类中，常将超标量、超流水、VLIW并列讨论为提高指令级并行（ILP）的三大技术。如果题目答案选ABC，说明通过“提高单位时间吞吐量”的角度，或者教材将超流水也归类于此（例如MIPS R4000）。这里遵从题目标准答案ABC。
11. 为解决数据冲突，Tomasulo算法中换名技术是在保留站中完成的。（）
正确答案：正确 (√)
解析： 如Q4所述，Tomasulo利用保留站（Reservation Station）的Tag（编号）代替寄存器名，实现了寄存器重命名，从而消除了WAR和WAW冲突。
12. Tomasulo算法支持乱序流出、乱序执行、顺序提交。（）
正确答案：错误 (×)
解析：
- 原始Tomasulo算法（如IBM 360/91浮点单元）：
- Issue：顺序流出（In-Order Issue）。
- Execute：乱序执行（Out-of-Order Execution）。
- Write Result：乱序写回（Out-of-Order Write）——只要计算完就写CDB。
- 它不保证顺序提交。如果发生异常，可能导致不精确异常。
- 支持“顺序提交”的是加了ROB的Tomasulo（即前瞻执行/硬件推测）。
13. 静态调度和动态调度的时间不同。（）
正确答案：正确 (√)
解析：
- 静态调度：在编译时（Compile Time）由编译器完成。
- 动态调度：在运行时（Run Time）由硬件完成。
14. Tomasulo算法步骤中：流出阶段的工作首先判断是否有结构冲突，若无结构冲突判断是否有数据冲突，若无数据冲突则读取操作数；最后对目标操作数进行预约写回。（）
正确答案：正确 (√)
解析： 这一描述虽然略显简化，但基本符合流程：
检查结构冲突：是否有空闲的保留站（RS）。
处理数据冲突：
- 如果寄存器中有数据（无RAW），将数据读入RS。
- 如果寄存器中无数据（有RAW，被其他指令占用），将产生数据的RS编号（Tag）记录到当前RS中（而不是等待）。
预约写回/重命名：将目的寄存器的Tag更新为当前RS的编号，以便后续指令引用。
- 题目描述的“判断是否有数据冲突，若无…则读取”可以理解为读取就绪数值的过程。