软流水的方法--国科大体系结构 期末必考题
软流水的概念
软流水是通过重组循环体使得不同循环体指令并行执行，新循环体的每个操作来自不同的循环体，以分开数据相关的指令。
软流水后，循环体会变成装入、主体循环、排空三个部分。
在软流水后循环执行时，主要是主体循环部分在执行，装入和排空仅执行一次。因而可以通俗理解为：装入是为了让主体循环可以正确执行的预处理阶段，排空是保证主体循环执行后结果正确的收尾阶段。
之后会对这些概念有更深入的介绍。不想理解就直接看解题方法。
软流水的方法
写在前面，我会在指令前加序号，同时在分析时直接用序号来描述指令。
先看一个简单例子。
假设我们需要执行如下循环：
for(i = 1; i <= 100; i++) x[i] = x[i] + s;
假设 s 是一个常量,存在寄存器 F0 中，数组首地址在 R1 中，数组每个元素占 8 字节。且 R2 = R1 + 800。同时我们假设 R1 地址初始是0，在之后会用到这一点。
于是有如下指令段：
// 注： L.D S.D 有时候写成 LDC1 SDC1
L1:
1 L.D F2, 0(R1) // 取X[i]
2 ADD.D F4, F2, F0 // 计算X[i] + s
3 S.D F4, 0(R1) // 存X[i]
4 DADDIU R1, R1, 8 // X的下标+1
5 BNE R1, R2, L1 // R1不等于R2，程序跳转到L1处继续执行
流水线延迟为：
那么分析可知，
1 和 2 延迟为2，之间需要加上 1 条不相关指令
2 和 3 延迟为3，之间需要加上 2 条不相关指令
接下来我们要通过软流水来消除延迟。
主体循环
对于刚刚的指令段，我们可以看到前三条指令存在两组数据相关：第 2 条和第 1 条，第 3 条和第 2 条。可以看到它们之间是顺序相关的，那么，如果改变指令的顺序怎么样？
于是我们可以将这三条指令想象成三个独立的模块（不要着急为什么，先往下看）。然后将它们的顺序倒过来，如下
1 S.D F4, 0(R1) // 存X[i]
2 ADD.D F4, F2, F0 // 计算X[i] + s
3 L.D F2, 0(R1) // 取X[i]
这样先存后取显然不合理。但如果改变一下下标呢？如下：
1 S.D F4, 0(R1) // 存X[i]
2 ADD.D F4, F2, F0 // 计算X[i+1] + s
3 L.D F2, 16(R1) // 取X[i+2]
这样显然是合理的，即第 1 条指令存的是上一轮循环算出的值，只是放在这一轮循环存了而已。
而且可以看到，这样是没有流水线等待的。为什么？
1 存的是 X[i] 的值，是上一轮计算出的，而两轮循环中间的间隔是大于流水线延迟的（之后会计算）。
2 计算的是下一轮要存的值，也就是 X[i+1]，而取数是上一轮取得，而两轮循环中间的间隔是大于流水线延迟的（之后会计算）。
3 取的是下一轮要计算的值，也就是 X[(i+1)+1]。 取数指令明显没有数据相关，同样寄存器 F2 的值也已经使用过了，可以更新。
那么，每次循环像刚刚这样写就可以避免相关消除延迟了。
怎么写？且往下看。
首先，写下这三个模块的三轮循环。
一、
1 L.D F2, 0(R1) // 取X[i]
2 ADD.D F4, F2, F0 // 计算X[i] + s
3 S.D F4, 0(R1) // 存X[i]
二、
1 L.D F2, 8(R1) // 取X[i+1]
2 ADD.D F4, F2, F0 // 计算X[i+1] + s
3 S.D F4, 8(R1) // 存X[i+1]
三、
1 L.D F2, 16(R1) // 取X[i+2]
2 ADD.D F4, F2, F0 // 计算X[i+2] + s
3 S.D F4, 16(R1) // 存X[i+2]
可以看到，在第二次和第三次循环中 Load/Store 的偏移量跟着做了改变，这是因为在这三次循环里 R1 的值并没有改变，为了正确存取需要改变偏移量。
然后，依次倒着从每轮循环取每个模块。
第一轮取第三个模块，第二轮取第二个模块，第三轮取第一个模块，就变成下面这样：
1 S.D F4, 0(R1) // 存X[i]
2 ADD.D F4, F2, F0 // 计算X[i+1] + s
3 L.D F2, 16(R1) // 取X[i+2]
这不就是刚刚分析出的循环体嘛。
然后我们补全循环体，一个循环之所以叫循环，总得有循环结束条件吧。
如下：
1 S.D F4, 0(R1) // 存X[i]
2 ADD.D F4, F2, F0 // 计算X[i+1] + s
3 L.D F2, 16(R1) // 取X[i+2]
4 BNE R1, R2, L1 // R1不等于R2，程序跳转到L1处继续执行
5 DADDIU R1, R1, 8 // X的下标+1
这里将 X的下标+1 放在延迟槽中。
现在开始分析这样重排指令是否还存在延迟问题。
（延迟为n，两条相关指令中需要间隔 n-1 条不相关的指令）
1 是存储上一轮循环计算出的值，也就是从上一轮的 2 到这一轮的 1，延迟为 3，中间有 3 条指令，满足。
2 是计算下一轮要存储的值，刚刚分析过了。
3 是取下一轮要计算的值，也就是从这一轮的 3 到下一轮的 2 ，延迟为 2，中间有 3 条指令， 满足。
同时，可以注意到，因为循环结束条件没变，所以当我们执行到第 100 轮循环时，第 2 条指令是计算的第 101 轮要存的数，第 3 条指令取的是第 101 轮要计算的数（且这个数要在第 102 轮存），显然没有 101 轮的数组元素，通俗地说就是数组越界。况且，由于 X的下标+1 放在延迟槽中，程序是先判断循环是否结束，再进行 下标+1 的操作，之前题目已经声明 R2 = R1 + 800，且 R1 初始为 0，即 R2 = 800，那么第 100 轮的主体循环在指令 4 判断循环是否结束时，R1=792 ≠ R2=800。所以还会有第 101 轮循环，造成越界。
注：如果将下标+1指令放在循环判断前，就没有这个额外的判断了，这样的话循环会在第100轮结束
为了防止这种情况，有两种解决方法，一种简单，就是修改一下主体循环的偏移量（按照刚刚 X的下标+1 放在延迟槽中最后一轮的例子，之前分析可知正确情况下最后一轮 R1 = R2 = 800，但最后一位数组元素地址是 792，所以取数指令的偏移量需要为 -8）；另一种是修改循环结束条件，让它在第 98 轮就结束。
这里就使用第一种方法。先将第3条指令的偏移量修改成 -8，这样最后一轮循环就是取的最后一位数组元素（循环结束时 R1 = R2 = 800，最后一位数组元素地址是 792），不会访问越界，其他的同幅度调整即可，如第 1 条之前是 0，第 3 条之前是 16，都减 24 （16 - 24 = -8）即可。
为了方便理解，修改了注释的下标，修改如下：
1 S.D F4, -24(R1) // 存X[i-3]
2 ADD.D F4, F2, F0 // 计算X[i-2] + s
3 L.D F2, -8(R1) // 取X[i-1]
4 BNE R1, R2, L1 // R1不等于R2，程序跳转到L1处继续执行
5 DADDIU R1, R1, #8 // X的下标+1
这样就不会有数组越界的情况发生。（这道题因为指令少，不用修改寄存器就是正确的）
到这里我们就完成了主体循环的指令段，还差装入和排空两个阶段。这两个阶段可以不考虑指令相关。
装入
之前提到过，装入就是预处理。那么看刚刚完成的主体循环，可以看到当第一次执行时，就要存数组首位元素的计算结果，以及要对数组第二位元素进行计算。
所以，我们在装入阶段就要把数组首位元素取出并且结算，把第二位取出。同时，注意Store偏移量是 -24，那么在装入还要对下标进行 +24 处理。如下：
1 L.D F2, 0(R1) // 取X[0]
2 ADD.D F4, F2, F0 // 计算X[0] + s
3 L.D F2, 8(R1) // 取X[1]
4 ADDIU R1, R1, #24 // X的下标+3
这样就完成了装入的指令段。
排空
同样，之前也提过，排空就是收尾。那么看之前的主题循环部分，可以知道最后一轮循环执行时，存的是倒数第三个数组元素，计算的是倒数第二个数组元素，取出的是末尾数组元素。
所以，在排空阶段我们要存储倒数第二个数组元素，计算并存储末尾数组元素。同时注意判断循环结束时R2 =800，那么在这之后又执行了延迟槽指令，即主体循环结束时又对下标进行了+1，这时候R1 = 808。倒数第二个数组元素地址为784 = 808 - 24 ，倒数一个数组元素地址为792 = 808 -16。修改如下：
1 S.D F4, -24(R1) // 存倒数第二个
2 ADD.D F4, F2, F0 // 计算末尾元素
3 S.D F2, -16(R1) // 存末尾元素
如果让算平均多少拍一次，那就是
{（循环次数-模块数+1）× 主体循环指令条数 + 装入的拍数 + 排空的拍数 } ÷ 循环次数
装入排空的拍数因为存在延迟所以不等于指令数。
到此即结束，如果还不懂请看解题方法。
解题方法
高斯消元法的核心操作是一个循环，可以概括为 Y = a*X +
Y，我们假设循环共100次，循环变量每次增加8位，假设从0位开始，到800结束（792是末尾数组元素地址）。且假设R1、R2存放数组X、Y的首地址，F0存储浮点常量a的值。
指令如下，进行软流水处理。
bar：
1 L.D F2, 0(R1) // 取X[i]
2 MUL.D F4, F2, F0 // 计算a*X[i]
3 L.D F6, 0(R2) // 取Y[i]
4 ADD.D F6, F4, F6 // a*X[i] + Y[i]
5 S.D 0(R2), F6 // 存Y[i]
6 DADDIU R1, R1, #8 // X的下标+1
7 DADDIU R2, R2, #8 // Y的下标+1
8 DSGEIU R3, R1, #800 // 测试循环是否结束
9 BEQZ R3, bar // 如果循环没有结束，程序跳转到bar位置
10 NOP
首先看循环主体（取数、计算、存数），去掉下标变换和循环结束的判断。为：
1 L.D F2, 0(R1) // 取X[i]
2 MUL.D F4, F2, F0 // 计算a*X[i]
3 L.D F6, 0(R2) // 取Y[i]
4 ADD.D F6, F4, F6 // a*X[i] + Y[i]
5 S.D 0(R2), F6 // 存Y[i]
按照顺序看相关性
1 和 2 有相关
2 和 3 没有相关
3 和 4 有相关
4 和 5 有相关
其中2 和 3没有相关，那么根据是否有相关性将这五条指令分成四个模块，分别是
1、 2和3、 4、 5
有四个模块，于是将这四个模块写四轮，偏移量从0开始每轮 +8 递增，如下
一、
1 L.D F2, 0(R1) // 取X[i]
2 MUL.D F4, F2, F0 // 计算a*X[i]
3 L.D F6, 0(R2) // 取Y[i]
4 ADD.D F6, F4, F6 // a*X[i] + Y[i]
5 S.D 0(R2), F6 // 存Y[i]
二、
1 L.D F2, 8(R1) // 取X[i+1]
2 MUL.D F4, F2, F0 // 计算a*X[i+1]
3 L.D F6, 8(R2) // 取Y[i+1]
4 ADD.D F6, F4, F6 // a*X[i+1] + Y[i+1]
5 S.D 8(R2), F6 // 存Y[i+1]
三、
1 L.D F2, 16(R1) // 取X[i+2]
2 MUL.D F4, F2, F0 // 计算a*X[i+2]
3 L.D F6, 16(R2) // 取Y[i+2]
4 ADD.D F6, F4, F6 // a*X[i+2] + Y[i+2]
5 S.D 16(R2), F6 // 存Y[i+2]
四、
1 L.D F2, 24(R1) // 取X[i+3]
2 MUL.D F4, F2, F0 // 计算a*X[i+3]
3 L.D F6, 24(R2) // 取Y[i+3]
4 ADD.D F6, F4, F6 // a*X[i+3] + Y[i+3]
5 S.D 24(R2), F6 // 存Y[i+3]
然后，依次倒着从每轮循环取每个模块。
第一轮取第四个模块，第二轮取第三个模块，第三轮取第二个模块，第四轮取第一个，并将最后一个取数指令的偏移量减去一个值变为0，同时将其它所有偏移量也减去这个值。就变成下面这样：
1 S.D -24(R2), F6 // 存Y[i-3]
2 ADD.D F6, F4, F6 // a*X[i-2] + Y[i-2]
3 MUL.D F4, F2, F0 // 计算a*X[i-1]
4 L.D F6, -8(R2) // 取Y[i-1]
5 L.D F2, 0(R1) // 取X[i]
可以看到，第二条指令的运算结果存在 F6 中，第 4 条Load指令取的数也在 F6，显然不合理，将 4 的寄存器修改为 F8，同时将相关的寄存器也修改(也就是第二条指令的后一个 F6 改为 F8 )。
然后补上下标+1的指令，以及循环结束条件。（这里因为 下标+1 的指令放在循环结束条件判断语句之前，所以最后一条取数指令的偏移量为0，其它同幅度减少，结合上个例子体会）
1 S.D -24(R2), F6 // 存Y[i-3]
2 ADD.D F6, F4, F8 // a*X[i-2] + Y[i-2]
3 MUL.D F4, F2, F0 // 计算a*X[i-1]
4 L.D F8, -8(R2) // 取Y[i-1]
5 L.D F2, 0(R1) // 取X[i]
6 DADDIU R1, R1, #8 // X下标+1
7 DADDIU R2, R2, #8 // Y下标+1
8 DSGEIU R3, R1, #800 // 测试循环是否结束
9 BEQZ R3, bar // 如果循环没有结束，程序跳转到bar位置
10 NOP
以上就是主体循环部分，接下来写装入部分。
装入部分是预处理，可知主体循环部分的第一轮就要：存储数组首位计算结果 Y[0]、计算数组第二位的 Y[1]、计算数组第三位 aX[2]。（取第四位和之前没有关系）
因此，我们需要在装入部分完成：取出并计算数组首位 Y[0]、取出并计算数组第二位的 **aX[1]**以及取出 初始Y[1]，取出数组第三位的 X[2]。同时要根据主体循环部分处理下标，以及要将寄存器的值正确对应（ 取Y 和 加法 的后一个Y 改为F8）。如下：
1 L.D F2, 0(R1) // 取X[0]
2 MUL.D F4,F2, F0 // 计算a*X[0]
3 L.D F8, 0(R2) // 取Y[0]
4 ADD.D F6, F4, F8 // a*X[0] + Y[0]
5 L.D F2, 8(R1) // 取X[1]
6 MUL.D F4, F2, F0 // 计算a*X[1]
7 L.D F8, 8(R2) // 取Y[1]
8 L.D F2, 16(R1) // 取X[2]
9 DADDIU R1, R1, #24 // 下标 +3
10 DADDIU R2, R2, #24 // 下标 +3
这样就完成了装入。
排空部分就是收尾，可知主体循环部分的最后一轮完成的操作：存了倒数第四位 Y[97]（那这一位已经不用管了）、计算了倒数第三位 Y[98]、计算了倒数第二位 aX[99]并且取了 初始Y[99]、取出了最后一位 X[100]。
那么，我们将要做的就是：存倒数第三位 Y[98]、计算并存储倒数第二位 Y[99]、计算最后一位的 **aX[100]**并且取出并计算 Y[100]。同时注意，循环结束时R1和R2的地址是800，最后一位是792，以此类推写偏移量。如下：
1 S.D -24(R2), F6 // 存Y[98]
2 ADD.D F6, F4, F8 // a*X[99] + Y[99]
3 S.D -16(R2), F6 // 存Y[99]
4 MUL.D F4, F2, F0 // 计算a*X[100]
5 L.D F8, -8(R2) // 取Y[100]
6 ADD.D F6, F4, F8 // 计算Y[100]
7 S.D -8(R2), F6 // 存Y[100]
至此全部完成。
如果让算平均多少拍一次，那就是
{（循环次数-模块数+1）× 主体循环指令条数 + 装入的拍数 + 排空的拍数 } ÷ 循环次数
装入排空的拍数因为存在延迟所以不等于指令数。
解题步骤秘诀
- 先确定循环主体（取数、计算、存数）
- 根据顺序看相关，根据相关分模块
- 几个模块写几轮，偏移量要跟着变
- 每个循环倒着取，一个循环取一块
- 末尾偏移要变零，其它偏移减同数
- 寄存相同变其一，补上下标和判断
- 装入就是预处理，排空就是收个尾
- 写完再查越界否
最后，写完了一定要检查最后一轮是否越界、偏移量是否合理
我也有写循环展开
考试题的话软流水基本上不会因为修改延迟有变化，只会因为指令本身变化而变化。