指令级并行

• 相关与指令级并行
  • 动态调度算法
    • Tomasulo 算法
• 习题

相关与指令级并行

指令调度

• 静态调度
  • 依靠编译器对代码进行静态调度，以减少相关和冲突。
  • 它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。
  • 通过把相关的指令拉开距离来减少可能产生的停顿。
• 动态调度
  • 在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。
    • 能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器；
    • 能够使本来是面向某一流水线优化编译的代码在其它的流水线（动态调度）上也能高效地执行。
  • 以硬件复杂性的显著增加为代价

动态调度算法

Tomasulo 算法

https://www.xinhecuican.tech/post/baebc2bf.html

核心思想

• 记录和检测指令相关，操作数一旦就绪就立即执行，把发生 RAW 冲突的可能性减少到最小。
• 通过寄存器换名来消除 WAR 冲突和 WAW 冲突。

部件

• 指令队列
• store 缓冲器
• load 缓冲器
• 加法保留站
• 乘法保留站
• 浮点寄存器
• 公共数据总线 CDB

保留站

• Busy: 为 yes 表示本保留站或缓冲单元忙
• Op: 要对源操作数进行的操作
• Vj/Vk: 源操作数的值
• Qj/Qk: 将产生源操作数的保留站号（对于一个操作数，V, Q 只会有一个）
• A: 仅 load 和 store 有，存放指令中的立即数。

Qi 寄存器状态表

• 用于存放将把结果写入该寄存器的保留站的站号
• 为 0 表示当前没有正在执行的指令要写入该寄存器，即其内容就绪

习题

对于下述指令

L.D F6, 34(R2)
L.D F2, 45(R3)
MUL.D F0, F2, F4
SUB.D F8, F2, F6
DIV.D F10, F0, F6
ADD.D F6, F8, F2

给出第一条指令执行完成时各个表中的状态

指令	流出	执行	写结果
L.D F6, 34(R2)	✓	✓	✓
L.D F2, 45(R3)	✓	✓
MUL.D F0, F2, F4	✓
SUB.D F8, F2, F6	✓
DIV.D F10, F0, F6
ADD.D F6, F8, F2

保留站

名称	Busy	Op	Vj	Vk	Qj	Qk	A
Load1	no
Load2	yes	LD					45+Regs[R3]
Add1	yes	SUB		Mem[34+Regs[R2]]	Load2
Add2	no
Add3	no
Mult1	yes	MUL		Reg[F4]	Load2
Mult2	no

寄存器状态表

	F0	F2	F4	F6	F8	F10	…	F30
Qi	Multi1	Load2			Add1		…