循环展开的方法--国科大体系结构 期末必考题

如何进行循环展开，是胡老师体系结构课的一个重点，也是必考点。根据20年的经验，在助教汪老师的精心准备下，成功让很多小伙伴没有拿到分数，希望接下来的同学们加油。
听说 LoongArch 出了，我是不是白写了。。。

循环展开的意义

写在前面，我会在指令前加序号，同时在分析时直接用序号来描述指令。

进行循环展开，是为了尽量避免指令相关造成的流水线等待。
直奔题目而言，是通过将多次（大于等于两次）的循环指令展开为一次的循环指令，从而将数据相关消除。不考虑结构相关。
如

// 注： L.D S.D有时候写成 LDC1 SDC1
1  L.D    F2, 0(R1) 
2  MUL.D  F4, F2, F0  // 第二条指令使用了第一条LD指令取数寄存器F2
3  L.D    F6, 0(R2)		
4  ADD.D  F6, F4, F6  // 第四条指令使用了第三条LD指令取数寄存器F6，以及第二条指令的运算结果寄存器F4
5  S.D    0(R2), F6	  // 第五条指令使用了第四条LD指令的运算结果寄存器F6
1
2
3
4
5
6

可以看到存在四组数据相关
1 和 2
2 和 4
3 和 4
4 和 5
按照课本中的延迟

延迟为n，两条相关指令中需要间隔n-1条不相关的指令才算达到循环展开的目的：消除数据相关。
即：
1 和 2 延迟为2，之间需要加上 1 条不相关指令
2 和 4 延迟为4，之间需要加上 2 条不相关指令
3 和 4 延迟为2，之间需要加上 1 条不相关指令
4 和 5 延迟为3，之间需要加上 2 条不相关指令

接下来我会讲解两种循环展开的方法来避免流水线等待。

循环展开的暴力方法

按照刚刚的分析，对于刚刚的指令段(如下)，需要通过循环展开来避免流水线等待（资源浪费）。

1  L.D    F2, 0(R1) 
2  MUL.D  F4, F2, F0  // 第二条指令使用了第一条LD指令取数寄存器F2
3  L.D    F6, 0(R2)		
4  ADD.D  F6, F4, F6  // 第四条指令使用了第三条LD指令取数寄存器F6，以及第二条指令的运算结果寄存器F4
5  S.D    0(R2), F6	  // 第五条指令使用了第四条LD指令的运算结果寄存器F6
1
2
3
4
5

从最简单的方法开始（这个方法20年不给分，我想以后大概率也是，不过可以用来帮助理解）。
为了方便理解指令段作用，这里加入题目要求，同时我修改了加下来的注释。
题目可以理解为：高斯消元法的核心操作是一个循环，可以概括为 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
2
3
4
5
6
7
8
9
10
11

为了方便理解指令段作用，我修改了注释。
然后我们使用一个暴力方法来解决所有的流水线等待问题。
根据之前的分析，我们需要在

1 和 2 延迟为2，之间需要加上 1 条不相关指令
2 和 4 延迟为4，之间需要加上 2 条不相关指令
3 和 4 延迟为2，之间需要加上 1 条不相关指令
4 和 5 延迟为3，之间需要加上 2 条不相关指令

那么一次循环同时进行多次运算就可以达到插入不相关指令的目的了，解释一下，就是之前我们每轮循环只对当前的下标进行了一次高斯消元操作，如只进行了 Y[i] = aX[i] + Y[i]；现在我们打算每轮循环对两个下标进行高斯消元操作，也就是循环展开两次，如 Y[i] = aX[i] + Y[i]，Y[i+1] = aX[i+1] + Y[i+1]。就是说之前循环需要执行100轮，现在只需执行50轮。
于是，先对之前的指令循环展开两次，如下

bar：
	1  L.D    F2, 0(R1) 	 // 取X[i]
	2  L.D    F3, 8(R1) 	 // 取X[i+1] 	
	3  MUL.D  F4, F2, F0 	 // 计算a*X[i]
	4  MUL.D  F5, F3, F0	 // 计算a*X[i+1]
	5  L.D    F6, 0(R2)		 // 取Y[i]
	6  L.D    F7, 8(R2)		 // 取Y[i+1]
	7  ADD.D  F6, F4, F6 	 // a*X[i] + Y[i]
	8  ADD.D  F7, F5, F7 	 // a*X[i+1] + Y[i+1]
	9  S.D    0(R2), F6	 	 // 存Y[i]
	10 S.D    8(R2), F7	 	 // 存Y[i+1]
	11 DADDIU R1, R1, #16	 // X的下标+2
	12 DADDIU R2, R2, #16	 // Y的下标+2
	13 DSGEIU R3, R1, #800	 // 测试循环是否结束
	14 BEQZ   R3, bar		 // 如果循环没有结束，程序跳转到bar位置
	15 NOP 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

可以看到，这样进行循环展开只需要对主要的指令重复写一次就可以了，只用注意寄存器的正确使用和下标的变换即可，简单暴力。
如何使用寄存器？对于做题而言，我觉得 F1 至 F9 够用了，你只用像我刚才那样，把寄存器想象成一个变量，需要存储值时使用，当该值不再使用后可以用它存储新值。如加法指令 7 和 8，F6/F7 在运算前存的是之前的 Y 值，运算后存了新的 Y 值，这样可以少用几个寄存器，方便整理思路。
但每轮循环对两个下标进行高斯消元操作仍然有流水线等待问题，分析如下

1 和 3 延迟为2，不需要等待
2 和 4 延迟为2，不需要等待
3 和 7 延迟为4，不需要等待
4 和 8 延迟为4，不需要等待
5 和 7 延迟为2，不需要等待
6 和 8 延迟为2，不需要等待
7 和 9 延迟为3，之间需要加上 1 条不相关指令
8 和 10 延迟为3，之间需要加上 1 条不相关指令

所以展开两次是不够的，需要更多次的展开。
那么显然，循环展开三次一定是够的，但是循环展开三次，第三十三轮循环结束时，按照之前的规定

循环共 100 次，循环变量每次增加8位，假设从 0 位开始，到 800 结束（792 是末尾元素地址）

此时下标在 784 位，循环仍未结束，所以还要再执行第三十四轮循环，明显会多执行两次，执行完后下标在 808，这样就发生了不合理的访问越界行为。
为了避免这种情况发生，切记循环展开次数一定要可以整除循环次数，如 2 可以整除 100，可以展开两次；3 不可以整除 100，不可以展开三次。
显然，展开四次一定是够的，太费篇幅我就不写了。
算了写一下吧。送佛送到西，这个方法写作业应该不扣分吧。

bar：
	1  L.D    F1, 0(R1) 	 // 取X[i]
	2  L.D    F2, 8(R1) 	 // 取X[i+1] 	
	3  L.D    F3, 16(R1)	 // 取X[i+2]
	4  L.D    F4, 24(R1) 	 // 取X[i+3] 
	5  MUL.D  F1, F1, F0 	 // 计算a*X[i]
	6  MUL.D  F2, F2, F0	 // 计算a*X[i+1]
	7  MUL.D  F3, F3, F0 	 // 计算a*X[i+2]
	8  MUL.D  F4, F4, F0	 // 计算a*X[i+3]
	9  L.D    F5, 0(R2)		 // 取Y[i]
	10 L.D    F6, 8(R2)		 // 取Y[i+1]
	11 L.D    F7, 16(R2)	 // 取Y[i+2]
	12 L.D    F8, 24(R2)	 // 取Y[i+3]
	13 ADD.D  F5, F1, F5 	 // a*X[i] + Y[i]
	14 ADD.D  F6, F2, F6 	 // a*X[i+1] + Y[i+1]
	15 ADD.D  F7, F3, F7 	 // a*X[i+2] + Y[i+2]
	16 ADD.D  F8, F4, F8 	 // a*X[i+3] + Y[i+3]
	17 S.D    0(R2), F5	 	 // 存Y[i]
	18 S.D    8(R2), F6	 	 // 存Y[i+1]
	19 S.D   16(R2), F7 	 // 存Y[i+2]
	20 S.D   24(R2), F8 	 // 存Y[i+3]
	21 DADDIU R1, R1, #32	 // X的下标+4
	22 DADDIU R2, R2, #32	 // Y的下标+4
	23 DSGEIU R3, R1, #800	 // 测试循环是否结束
	24 BEQZ   R3, bar		 // 如果循环没有结束，程序跳转到bar位置
	25 NOP 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26

循环展开的合理方法

接下来才是应该掌握和使用的循环展开方法，所以我愿意称之为合理方法。
其实，只用对之前循环两次的指令进行小小的修改即可。按照之前的规定

高斯消元法的核心操作是一个循环，可以概括为 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
2
3
4
5
6
7
8
9
10
11

之前的循环展开两次（不合格）：

bar：
	1  L.D    F2, 0(R1) 	 // 取X[i]
	2  L.D    F3, 8(R1) 	 // 取X[i+1] 	
	3  MUL.D  F4, F2, F0 	 // 计算a*X[i]
	4  MUL.D  F5, F3, F0	 // 计算a*X[i+1]
	5  L.D    F6, 0(R2)		 // 取Y[i]
	6  L.D    F7, 8(R2)		 // 取Y[i+1]
	7  ADD.D  F6, F4, F6 	 // a*X[i] + Y[i]
	8  ADD.D  F7, F5, F7 	 // a*X[i+1] + Y[i+1]
	9  S.D    0(R2), F6	 	 // 存Y[i]
	10 S.D    8(R2), F7	 	 // 存Y[i+1]
	11 DADDIU R1, R1, #16	 // X的下标+2
	12 DADDIU R2, R2, #16	 // Y的下标+2
	13 DSGEIU R3, R1, #800	 // 测试循环是否结束
	14 BEQZ   R3, bar		 // 如果循环没有结束，程序跳转到bar位置
	15 NOP 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16

修改部分指令次序后循环展开两次：

bar：
	1  L.D    F2, 0(R1) 	 // 取X[i]
	2  L.D    F3, 8(R1) 	 // 取X[i+1] 	
	3  MUL.D  F4, F2, F0 	 // 计算a*X[i]
	4  MUL.D  F5, F3, F0	 // 计算a*X[i+1]
	5  L.D    F6, 0(R2)		 // 取Y[i]
	6  L.D    F7, 8(R2)		 // 取Y[i+1]
	7  ADD.D  F6, F4, F6 	 // a*X[i] + Y[i]
	8  ADD.D  F7, F5, F7 	 // a*X[i+1] + Y[i+1]
	9  DADDIU R1, R1, #16	 // X的下标+2
	10 S.D    0(R2), F6	 	 // 存Y[i]
	11 S.D    8(R2), F7	 	 // 存Y[i+1]
	12 DSGEIU R3, R1, #800	 // 测试循环是否结束
	13 BEQZ   R3, bar		 // 如果循环没有结束，程序跳转到bar位置
	14 DADDIU R2, R2, #16	 // Y的下标+2
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

前六条指令之前已经分析过，是没有流水线等待的，现在分析修改后的7至11条指令。
显然，
7 和 10 延迟为3，不需要等待
8 和 11 延迟为3，不需要等待

这样就是一个正确的答案了。
可以看到，我只修改了两条指令的位置，其一是 X的下标+2 的第 9 条指令（原第 11 条），将其插在加法指令和 Store 指令（S.D）之间，避免了 ADD 之后 Store 的流水线等待；其二是 Y的下标+2 的第 14 条指令（原第12条），我将其作为延迟槽指令，既避免了修改 Store 指令的偏移量下标，也合理使用了延迟槽。
同样，我的方法只是答案的一种，当然也可以将 Store 指令放入延迟槽，不过都要保证偏移量下标的合理。

如 20 年大题，之前的条件都一样，但是修改了流水线延迟，如下

也是循环展开两次就可以解决的。

bar：
	1  L.D    F1, 0(R1) 	 // 取X[i]
	2  L.D    F2, 8(R1) 	 // 取X[i+1] 
	3  L.D    F3, 0(R2)		 // 取Y[i]
	4  L.D    F4, 8(R2)		 // 取Y[i+1]	
	5  MUL.D  F1, F1, F0 	 // 计算a*X[i]
	6  MUL.D  F2, F2, F0	 // 计算a*X[i+1]
	7  DADDIU R1, R1, #16	 // X的下标+2
	8  ADD.D  F5, F1, F3 	 // a*X[i] + Y[i]
	9  ADD.D  F6, F2, F4 	 // a*X[i+1] + Y[i+1]
	10 DADDIU R2, R2, #16	 // Y的下标+2
	11 DSGEIU R3, R1, #800	 // 测试循环是否结束
	12 S.D    -16(R2), F5	 // 存Y[i]
	13 BEQZ   R3, bar		 // 如果循环没有结束，程序跳转到bar位置
	14 S.D    -8(R2), F6	 // 存Y[i+1]
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15

注意，这里因为先对 Y的下标加2 ，所以 Store 指令的偏移量也跟着修改。
如有错误欢迎指正~
我应该还会写一篇软流水吧~
喜欢了赏个赞吧！