代码执行流水之循环展开优化

引言

流水线定义

指令执行流水

指令流水图

循环展开优化

引言

详细的流水线分析大家可以参考：计算机体系结构——流水线技术（Pipelining）。本篇只是由探讨循环展开如何提高代码执行效率延申过来的，因此只说明基本的流水线定义以及关于循环展开的部分。

流水线定义

计算机中的流水线是把一个重复的过程分解为若干个子过程，每个子过程与其他子过程并行进行。由于这种工作方式与工厂中的生产流水线十分相似，因此称为流水线技术，从本质上讲，流水线技术是一种时间并行技术。

流水线工作设计

基本思想：延伸重叠方式，使指令解释过程进一步细化，提高各部件的利用率，以提高指令执行速度
理想目标：完成任务的时间与其中某个指令执行时间无关，只与指令执行的频率有关（假设一个任务有n个指令，将完成一个指令分为m个段，每段执行时间为△t ，则理想目标是完成任务的时间是T=m△t+(n-1)△t；当n >> m时，T=(n-1)△t。指令执行频率为 1 / △t：即与m无关，只和指令执行的速度△t有关）

指令执行流水

取指：

　　指令取指（InstrucTIon Fetch）是指将指令从存储器中读取出来的过程。

译码：

　　指令译码（InstrucTIon Decode）是指将存储器中取出的指令进行翻译的过程。经过译码之后得到指令需要的操作数寄存器索引，可以使用此索引从通用寄存器组（Register File，Regfile）中将操作数读出。

执行：

　　指令译码之后所需要进行的计算类型都已得知，并且已经从通用寄存器组中读取出了所需的操作数，那么接下来便进行指令执行（InstrucTIon Execute）。指令执行是指对指令进行真正运算的过程。譬如，如果指令是一条加法运算指令，则对操作数进行加法操作；如果是减法运算指令，则进行减法操作。

　　在“执行”阶段的最常见部件为算术逻辑部件运算器（ArithmeTIc Logical Unit，ALU），作为实施具体运算的硬件功能单元。

访存：

　　存储器访问指令往往是指令集中最重要的指令类型之一，访存（Memory Access）是指存储器访问指令将数据从存储器中读出，或者写入存储器的过程。

写回：

　　写回（Write-Back）是指将指令执行的结果写回通用寄存器组的过程。如果是普通运算指令，该结果值来自于“执行”阶段计算的结果；如果是存储器读指令，该结果来自于“访存”阶段从存储器中读取出来的数据。

指令流水图

横坐标：表示时间，即各个任务或指令在流水线中所在该时刻所对应的子过程

纵坐标：表示某个任务或某条指令，即流水线依次处理的任务或指令

循环展开优化

在流水线中，往往因为指令顺序安排不合理而导致CPU等待空转，产生延迟，影响流水线效率。

解决办法：循环展开和指令调度

前提假设：假设采用MIPS的5段整数流水线：

 分支的延迟：1个时钟周期。

 整数load指令的延迟：1个时钟周期。

 整数运算部件是全流水或者重复设置了足够的份数。

从例题入手理解：

例: 对于下面的源代码，转换成MIPS汇编语言，在不进行指令调度和进行指令调度两种情况下，分析其代码一次循环所需的执行时间。

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

　 Loop：L.D F0,0（R1）

ADD.D F4,F0,F2

S.D F4, 0（R1）

DADDIU R1,R1，#-8

BNE R1,R2,Loop、

其中：  整数寄存器R1：指向向量中的当前元素（初值为向量中最高端元素的地址）

 浮点寄存器F2：用于保存常数s

 第二部浮点加法需要4个周期

分析：

假设一个浮点计算部件需要4周期完成一个计算，若该部件不使用流水线，则延迟为：

循环展开：

在上例中，只有L.D、ADD.D和S.D这3条指令是有效操作 (取、加、存) ，占用3个时钟周期。而DADDIU、空转和BEN这3个时钟周期都是附加的循环控制开销。可以通过循环展开的方式消除冗余，减少循环控制开销。

循环展开技术

 把循环体的代码复制多次并按顺序排列，然后相应调整循环的结束条件

 这给编译器进行指令调度带来了更大的空间

将上述例子中的循环展开3次得到4个循环体，然后对展开后的指令序列在不调度和调度两种情况下，分析代码的性能。

分配寄存器（不重复使用寄存器）：

 F0、F4：用于展开后的第1个循环体

 F2：保存常数

 F6、F8：展开后的第2个循环体

 F10、F12：第3个循环体

 F14、F16：第4个循环体

下面分三种情况比较循环展开和指令调度节省的时间：

第一种情况：

第二种情况：

 对指令序列进行优化调度，以减少空转周期

 浮点加法部件采用流水指令流出时钟

第三种情况：

 对指令序列进行优化调度，以减少空转周期

 浮点运算部件不采用流水

循环展开和指令调度时要注意以下几个方面：

 保证正确性。在循环展开和调度过程中尤其要注意两个地方的正确性：循环控制，操作数偏移量的修改。

 注意有效性。只有能够找到不同循环体之间的无关性，才能有效地使用循环展开。

 使用不同的寄存器。（否则可能导致新的冲突）

 删除多余的测试指令和分支指令，并对循环结束代码和新的循环体代码进行相应的修正。

 注意对存储器数据的相关性分析

 注意新的相关性

　　3.指令级并行

　　指令调度可以通过两种形式实现：静态调度和动态调度

静态调度

　　 依靠编译器（编译器需要做的很复杂，很完善）对代码进行静态调度，以减少相关和冲突。

　　 它不是在程序执行的过程中、而是在编译期间进行代码调度和优化。

　　 通过把相关的指令拉开距离来减少可能产生的停顿。

动态调度

　　 在程序的执行过程中，依靠专门硬件对代码进行调度，减少数据相关导致的停顿。

　　 能够处理一些在编译时情况不明的相关（比如涉及到存储器访问的相关），并简化了编译器；

　　 能够使本来是面向某一流水线优化编译的代码在其他的流水线（动态调度）上也能高效地执行。

　　 以硬件复杂性的显著增加为代价