
merge 循环合并

dataflow


不能用dataflow


改进后可以用

不能用dataflow
改善后可以

循环嵌套



不同地方做流水的影响

最外层流水,延迟最低,消耗最多因为展开这个循环以内所有的循环体

建议最内层做流水,要不然消耗资源太多
其他优化方法

并行执行加流水



如果循环边界不确定出现?

循环优化Performace Optimization – Loopspipline 流水线unrolling 循环展开merge 循环合并![]()
merge 循环合并
dataflow
不能用dataflow
改进后可以用
不能用dataflow
改善后可以
循环嵌套
不同地方做流水的影响
最外层流水,延迟最低,消耗最多因为展开这个循环以内所有的循环体
建议最内层做流水,要不然消耗资源太多
其他优化方法
并行执行加流水
如果循环边界不确定出现?
前言
循环是程序中最常见结构,针对循环已有众多的优化技术。循环的优化分为源码上的修改和编译器的优化,编译器能自动执行许多循环优化技术,但对源代码的修改可辅助编译器就行优化处理。
1. 源码上的优化
1. 多重循环的“外小内大”
在多重循环中,采用迭代次数较小的循环驱动内层迭代次数较大的循环能减少内存的消耗,如下示例:
for (int i = 0; i < 10000; i++) { for (int j = 0; j < 200; j++) { } } 改为: for (int i = 0; i <200 ; i++) { for (int j = 0; j < 10000; j++) { } }
2. 循环变量实例化放在循环外
如下示例:
int i,j; for (i = 0; i <200 ; i++) { for (j = 0; j < 10000; j++) { } }
3. 循环无关的表达式放到循环外
如下示例:
int i,j; for (i = 0; i <200 ; i++) { for (j = 0; j < 10000; j++) { j = i*j*x/(y-1); } } 改为: int i,j,tmp; tmp = x/(y-1); for (i = 0; i <200 ; i++) { for (j = 0; j < 10000; j++) { j = i*j*tmp; } }
4. 消除循环终止时的方法调用
如下示例:
for (int i = 0; i < vec.size(); i++) { } 改为: int size = vec.size(); for (int i = 0; i < size; i++) { }
5. 循环外部捕获异常
在循环外部捕获异常能有效减少内层消耗。一般而言,foreach 循环优先于传统的 for 循环。
6. 循环的 i++ 改为 ++i
效率上来说++i 比 i++来的更有效率(后置操作符必须先保存操作数原来的值),但现代编译器上这个影响会很小。
2. 编译器角度的优化
1. 循环展开(loop Unrolling)
重组循环,以便每次迭代多次使用加载的值,让一拍流水线上尽可能满。在流水线中,会因为指令顺序安排不合理而导致CPU等待空转,影响流水线效率。循环展开为编译器进行指令调度带来了更大的空间。
如下示例:do j = 1,2*n do i = 1,m A(j) = A(j) + B(i) enddo enddo Unrolling之后: do j = 1,2*n by 2 do i = 1,m A(j) = A(j) + B(i) A(j+1) = A(j+1) + B(i) enddo enddo
2. 循环分块(loop tiling)
由于内存空间有限,代码访问的数据量过大时,无法一次性将所需要的数据加载到设备内存,循环分块能有效提高处理器 cache 上的访存效率,改善数据局部性。(分块应用于外部循环,它会增加计算的空间和时间局部性;分块应与缓存块一起使用,因为这样可以提高最内部软件流水线的效率)。示意如图:
如下示例:
do j = 1,2*n do i = 1,m A(j)= A(j) + B(i) enddo enddo Tiling之后: do jj = 1,2*n by 2 do i = 1,m do j = jj, jj+2-1 A(j)= A(j)+B(i) enddo enddo enddo Unroll and Jam之后: do jj = 1,2*n by 2 do i = 1,m A(j)= A(j)+B(i) A(j+1)= A(j+1)+B(i) enddo enddo
更多关于 loop tiling 的优化方法可参见论文:
《Augmenting Loop Tiling with data Alignment for Improved Cache Performance》
、《Automatic Tiling of Iterative Stencil Loops》
、《面向局部性和并行优化的循环分块技术》
3. 循环交换(loop interchange)
内外层循环交换,改善空间局部性,并最大限度地利用引入缓存的数据。对循环进行重新排序,以最大程度地减少跨步并将访问模式与内存中的数据存储模式对齐。
如下示例:do i=1,n do j=1,n A(i,j)=B(i,j)*C(i,j) enddo enddo interchange之后: do j=1,n do i=1,n A(i,j)=B(i,j)*C(i,j) enddo enddo
4. 循环融合(loop fusion)
将相邻或紧密间隔的循环融合在一起,减少的循环开销和增加的计算密度可改善软件流水线,数据结构的缓存局部性增加,编译器在某些情况下未执行融合,需要手动完成。
如下示例:for(i = 0; i < size; ++i){ A(i) = a(i) + b(i); c(i) = 2*a(i); } for(i = 1; i < size-1; ++i){ D(i) = c(i) + a(i); } fusion之后: A(0) = a(0) + b(0); c(0) = 2*a(0); A(size-1) = a(size-1) + b(size-1); c(size-1) = 2*a(size-1); for(i = 1; i < size-1; ++i){ A(i) = a(i) + b(i); c(i) = 2*a(i); D(i) = c(i) + a(i); }
5. 循环分裂(loop fission)
将循环分成多个循环,可以在有条件的循环中使用,分为无条件循环和含条件循环。
如下示例:for(i = 0; i < size; ++i){ A(i) = a(i) + b(i); c(i) = 2*a(i); if(temp[i] > data) d(i) = a(i); } fission之后: for(i = 0; i < size; ++i){ A(i) = a(i) + b(i); c(i) = 2*a(i); } for(i = 0; i < size; ++i){ if(temp[i] > data) d(i) = a(i); }
6. 循环剥离(loop peeling)
剥离 k 次迭代意味着从循环主体中删除这些迭代并将其放置在循环主体之前或之后。
如下示例:do i=1,n Y(i,n) = (1.0 - x(i,1))*y(1,n) + x(i,1)*y(n,n) enddo peeling之后: t2 = y(n,n) x(i,1) * y(n,n) y(1,n) = (1.0 - x(1,1))*y(1,n) + x(1,1)*t2 t1 = y(1,n) do i=2,n-1 Y(i,n) = (1.0 - x(i,1))*t1 + x(i,1)*t2 enddo y(n,n) = (1.0 - x(n,1))*t1 + x(n,1)*t2
7. 循环强度减弱(Strength reduction in loops)
使用简单的表达式来替换复杂的表达式。
例如,除法替换,如下示例:z(i) = x(i)/y(i) w(i) = u(i)/v(i) Strength reduction之后: tmp = 1.0/(y(i)*v(i)) z(i) = x(i)*v(i)*tmp w(i) = u(i)*y(i)*tmp
References:
双重for循环优化
双重for循环优化思想:主要是将某一层的数据转成map类型,用比较字段去map里面get,若拿到数据则匹配上了
由于是在云上开发,代码拿不下来(公司限制了),就只能截图了,希望读者将就着看。