计算机结构体系：循环展开题型 （非凭感觉的方法详解）_daddiu

体系结构这门课程中，指令调度和循环展开可以说是课程最困难的地方，很多初学者（包括我）都只能凭感觉进行指令调度和循环展开。
在复习这门课程的过程中，我找出了一种比较通用的求解循环展开题型的思路。这种思路不仅能获得循环展开完全填充的最优解，同时还可以在使用的过程中自动确定循环展开的次数，因此在此和大家分享一下。直接用例题进行分析：

题目初始分析

这是一道很典型的循环展开例题。循环展开来减少每个循环平均的时钟周期并不难，但是难就难在确定最优展开方式。

1.确定所使用的各个寄存器的作用

遇到循环展开题型，首先应该分析代码，将循环体的执行内容大致理解一下，并记录各个寄存器的作用，如下所示：

整数寄存器：

• R1：存放X向量当前元素的地址。
• R2：存放Y向量当前元素的地址。
• R3：存放R1是否等于R4的比较结果。
• R4：存放X向量末尾哨兵的地址。

浮点寄存器：

• F0：存放常数a。
• F2：存放向量X的当前元素。
• F4：存放向量X当前元素和常数a的乘法结果。
• F6：存放向量Y的当前元素。

由此可知，每个循环体都要使用到的寄存器包括四个整数寄存器以及一个浮点寄存器F0，另外，每个循环体都需要单独配备三个浮点寄存器（第一个循环体中为F2 F4和F6）。

2.将循环体内容语句和控制语句分开

循环体内容语句是指循环体本身在每个循环中需要进行的操作；循环体控制语句则是控制循环的行进和终止的语句。
本题中，循环体内容语句如下：

循环体控制语句如下：

可以得出：内容语句共有五句，控制语句为四句。
通过多次的循环展开，可以使得多个循环体共用这四句控制语句，从而减少多次循环的时钟周期数，这也是循环展开的本质。

3.找出每一条循环体内容指令的代价并排序

本题中，由于数据相关的存在，使得循环体内容语句执行后可能会需要停顿，这样就导致了系统性能的下降，因此应该避免。
不同的语句与其后跟随的语句确定了每一次的停顿周期数。本题中每个循环体重各条指令的停顿周期数如下：

• 第一条LD指令：指令结果被MULD指令使用，因此由题目条件可知需要停顿两个周期。
• MULD指令：指令结果被ADDD指令使用，因此由题目条件可知需要停顿六个周期。
• 第二条LD指令：指令结果被ADDD指令使用，因此由题目条件可知需要停顿两个周期。
• ADDD指令：指令结果被SD指令使用，因此由题目条件可知需要停顿4个周期。
• SD指令：最后一条指令，指令结果不被其他指令使用，因此无停顿。

对循环体内容中各条指令的代价从大到小排序：

MULD指令（6个周期）>ADDD指令（4个周期）>两条LD指令（2个周期）。

4.找出每一条循环体控制指令的代价并排序

过程与上面类似，可以得到下面的递减排列顺序：

DADDIU（2个周期）>其他三条指令

5.基于贪婪算法的最优循环展开

接下来到了循环展开的重点部分了！就是如何实施循环展开。本方法的循环展开基本思路是基于贪婪原则的，因此得到的三条展开原则如下：

• 每一次执行的指令是当前能够执行的指令中代价最大的一条，且当指令的代价相同时，优先执行循环体内容指令，而滞后执行循环体控制指令；
• 如果当前不存在任何一条指令能够执行，则引入一个新的循环体。
• 一般只有各个循环的内容都接近结束时，才执行循环体控制指令。

最后的循环展开结果如下所示，下面对结果进行分析：

1.LD F2,0(R1)
2.LD F8,8(R1)
3.LD F14,16(R1)
4.MULD F4,F2,F0
5.MULD F10,F8,F0
6.MULD F16,F14,F0
7.LD F6,0(R2)
8.LD F12,8(R2)
9.LD F18,16(R2)
10.DADDIU R1,R1,#24
11.ADDD F6,F4,F6
12.ADDD F12,F10,F12
13.ADDD F18,F16,F18
14.DADDIU R2,R2,#24
15.DSLTU R3,R1,R4
16.SD F6,-24(R2)
17.SD F12,-16(R2)
18.BNEZ R3,foo
19.SD F18,-8(R2)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

1. 第一个周期：必定执行第一个循环体的第一条内容指令LD，不用过多叙述。
2. 第二个周期：此时，由于第一个循环体第一条LD指令还没有得出结果且当前只有一个循环体，不存在其他可执行的循环体内容语句；而目前执行循环体控制语句的时间又过早。因此，引入第二个循环体执行，执行其第一条LD指令。
3. 第三个周期：同前两个周期，由于当前前两个循环体都处于执行未产生结果的状态，因此执行第三个循环体。执行第三个循环体的第一条LD指令。
4. 第四个周期：此时第一个循环体的LD语句已经获得执行结果，而其他两个循环体的LD指令还未获得结果，因此只能继续第一个循环体。第一个循环体此时可以执行MULD指令或第二条LD指令，但是由于MULD指令的代价更大，因此首先执行第一个循环体的MULD指令。
5. 第五个周期：此时第一个循环体正在执行MULD指令，第三个循环体的LD指令还未出结果，按照最大代价原则，因此第二个循环体也执行MULD指令而不是LD指令。
6. 第六个周期：类似第五个周期，第三个循环体执行MULD指令。
7. 第七个周期：由于LD指令和MULD指令不相关，因此让第一个循环体执行LD指令。
8. 第八个周期：类似第七个周期，让第二个循环体执行LD指令。
9. 第九个周期：类似第八个周期，让第三个循环体执行LD指令。
10. 第十个周期：此时三个循环体的MULD指令都未执行完成无法执行后续指令，但是第一个循环体的MULD指令只需要再等待一个周期即可，因此可以考虑执行循环体控制指令。本题中，代价最大的循环体控制指令为第一条DADDIU指令，因此执行DADDIU指令。
11. 第十一个周期：此时第一个循环体的MULD指令已经执行完成，而其他两个循环体和循环控制语句都未执行完成，因此只能向下继续执行第一个循环体的ADDD指令。
12. 第十二个周期：第二个循环体的MULD指令执行完成，同时第一条DADDIU指令也已经执行完成，但是考虑到代价最大化，因此执行第二个循环体的ADDD指令。
13. 第十三个周期：类似于第十二个周期，执行第三个循环体的ADDD指令。
14. 第十四个周期：三个循环体内容均在执行ADDD指令，因此考虑执行循环体控制语句内容。由于第二条DADDIU和DSLTU指令的代价均为0周期，因此可以任选一条执行，此处先执行第二条DADDIU指令。
15. 第十五个周期：循环体内容均还在执行ADDD指令，因此继续执行循环体控制内容。执行DSTLU指令。
16. 第十六个周期：第一个循环体的ADDD执行完成。此时，除了跳转指令BNEZ外不存在其他可执行指令，但是BNEZ使用后会跳转到其他地方且只有一个周期延迟，因此放到程序末尾才能执行。所以此处执行第一个循环体的SD指令。
17. 第十七个周期：类似第十六个周期，执行第二个循环体的SD指令。
18. 第十八个周期：由于循环体内容中只剩下一条SD未执行且无周期延迟，因此先执行BNEZ指令。
19. 第十九个周期：执行第三个循环体的SD指令。所有指令执行完成。