计算机体系结构补充篇—-静态超标量流水线及循环展开（一）

本文仅供学习，不作任何商业用途，严禁转载。部分资料取自—-计算机系统结构教程(第二版)张晨曦等。部分资料来自—-国科大计算机体系结构课程PPT–张科、刘珂、高婉玲

计算机体系结构—-静态超标量流水线及循环展开（一）

• 摘要
• 静态编译器流水线调度
• 循环展开
• 静态超标量流水线

摘要

本文先简要介绍静态编译器流水线调度（消除数据冒险），再介绍循环展开（Loop Unrolling）技术（消除控制冒险），最后再结合静态超标量流水线技术（增加IPC）和循环展开技术对示例代码进行优化分析。

静态编译器流水线调度

假定有如下代码

for(i = 1000; i >0 ; i--)
	x[i] = x[i] + s;

上述代码转换成MIPS的汇编代码如下
（注意汇编代码段1先忽略各条指令之间的stall，即假定各条指令之间无stall）
汇编代码段1

 L.D F0, 0(R1) ; F0 = array element
 ADD.D F4, F0, F2 ; add scalar
 S.D F4, 0(R1) ; store result
 DADDUI R1, R1,# -8 ; decrement address pointer
 BNE R1, R2, Loop ; branch if R1 != R2
 NOP

现在我们做如下规定
LD -> any : 1 stall
FPMUL -> any: 5 stalls
FPMUL>ST : 4 stalls
IntALU ->BR : 1 stall
FPALU -> ST :2stalls
FPALU-> any: 3stalls
BR指的是分支指令。
每个BR指令后续都存在一个Stall。

那么汇编代码段1在上述假定下，实际执行情况如下
汇编代码段2

 L.D F0, 0(R1) ; F0 = array element
 stall
 ADD.D F4, F0, F2 ; add scalar
 stall
 stall
 S.D F4, 0(R1) ; store result
 DADDUI R1, R1,# -8 ; decrement address pointer
 stall
 BNE R1, R2, Loop ; branch if R1 != R2
 stall

汇编代码段2一共花费10 cycles。

在经过编译器的调度后，汇编代码段2变成如下代码段（注意，此时各条指令间不是不存在stall，而是被“合理”消除了））
汇编代码段3

 L.D F0, 0(R1) 
 DADDUI R1, R1,# -8
 ADD.D F4, F0, F2 
 stall
 BNE R1, R2, Loop
 S.D F4, 8(R1) 

汇编代码段3一共花费6 cycles。

实际上汇编代码段3真正在工作的时间只有ADD.D L.D S.D这三条指令，DADDUI BNE指令都是循环判断指令，知道了这个信息后，那我们还有再优化的空间吗？我们希望把几乎每个循环都控制在三个有效指令在工作，不想在每个循环中都加上循环判断指令。

循环展开

上面的汇编代码段3还可以依靠循环展开来二次优化。优化后的结果如下。
汇编代码段4（注意汇编代码段4先忽略各条指令之间的stall，即假定各条指令之间无stall）

 L.D F0, 0(R1) 
 ADD.D F4, F0, F2 
 S.D F4, 0(R1)
 L.D F6, -8(R1)
 ADD.D F8, F6, F2
 S.D F8, -8(R1)
 L.D F10,-16(R1)
 ADD.D F12, F10, F2
 S.D F12, -16(R1)
 L.D F14, -24(R1)
 ADD.D F16, F14, F2
 S.D F16, -24(R1)
 DADDUI R1, R1, #-32
 BNE R1,R2, Loop

如果我们考虑上汇编代码段4的各条指令间的stall，再合理的调度指令把stall给消除，可以得到如下代码段。（注意，此时各条指令间不是不存在stall，而是被“合理”消除了）
汇编代码段5

 L.D F0, 0(R1) 
 L.D F6, -8(R1)
 L.D F10,-16(R1)
 L.D F14, -24(R1)
 ADD.D F4, F0, F2 
 ADD.D F8, F6, F2 
 ADD.D F12, F10, F2
 ADD.D F16, F14, F2
 S.D F4, 0(R1)
 S.D F8, -8(R1)
 DADDUI R1, R1, # -32
 S.D F12, 16(R1)
 BNE R1,R2, Loop
 S.D F16, 0(R1)

汇编代码段5一共花费14 cycles，但是却做了汇编代码段2 40个cycles的事！
汇编代码段5每个原循环的cycle数为14/4 = 3.5 （14/4 中的14表示4个循环的总cycle数，4表示4个循环）
我们把这种一个循环展开四次在英文术语上称为Degree4，即循环展开N次，称为DegreeN。

当然，这还不是我们的极限，我们还可以使用静态超标量流水线继续加速！

静态超标量流水线

静态超标量可以简单理解成，处理器一次性发射两条指令，一条是整数指令，一条是浮点指令，以此来实现IPC > 1的效果。
将汇编代码段5改写成静态超标量流水线的形式，同时汇编代码段5的四次循环展开Degree4变成Degree5，代码段如下。
汇编代码段6，

Integer pipeline    FP pipeline
 L.D F0,0(R1)        NOP
 L.D F6,-8(R1)       NOP
 L.D F10,-16(R1)     ADD.D F4,F0,F2
 L.D F14,-24(R1)     ADD.D F8,F6,F2
 L.D F18,-32(R1)     ADD.D F12,F10,F2
 S.D F4,0(R1)        ADD.D F16,F14,F2
 S.D F8,-8(R1)       ADD.D F20,F18,F2
 S.D F12,-16(R1)     NOP
 DADDUI R1,R1,# -40  NOP
 S.D F16,16(R1)      NOP
 BNE R1,R2,Loop      NOP
 S.D F20,8(R1)       NOP

记住我们做的如下规定，注意汇编代码段6是建立在这个规定下的。
LD -> any : 1 stall
FPMUL -> any: 5 stalls
FPMUL>ST : 4 stalls
IntALU ->BR : 1 stall
FPALU->ST : 2stalls
FPALU-> any: 3stalls
BR指的是分支指令。
每个BR指令后续都存在一个Stall。
NOP = No option 即无操作。

代码007普通

打赏 收藏 海报 链接