Back
Featured image of post 编译优化
HPC

编译优化

编译器角度来优化程序

讨论一些编译器会做的优化，这些优化一般不需要我们自己来做。

但是我们讨论时从源码角度来模拟，实际上编译器是在中间代码（IR）层进行优化的。

分四部分：

IR optimisations

Basic optimisations

Constant folding

将一些变量转换为常量，这有助于减少内存的访问。 且常量相关的求值是可以在编译阶段就确定，不必等待运行阶段。

转换前：

integer, parameter :: n=100
do i=1,n
....
end do

转换后：

do i=1,100
....
end do

Algebraic simplifications

简化算术运算，包括了运用结合，交换和分配律等：

(i-j)+(i-j)+(i-j) ——> 3*i - 3*i

但是要注意浮点数操作，它不遵循结合律：

1.0 + (MF - MF) = 1.0

(1.0 + MF) - MF = 0.0

这个例子里MF比1.0大，1.0在和MF结合后会被舍去，所以第二个结果出来就是0.0了，这是因为浮点运算会先算出精确值然后舍去多余位，所以结合律失效。

Copy propagation

拷贝出来的变量在后续的使用中可以被原来的变量替代，那就少用一个寄存器。

x = y
c = x + 3
d = x + y
-------->
x = y
c = y + 3
d = y + y

这里x这个变量就不需要了。

Constant propagation

一个常量的值，在后续的使用中可以直接被一个常量替换掉。

x = 4
c = x + 3
d = x + y
---------------->
x = 4
c = 4 + 3
d = 4 + y

Redundancy elimination

Common subexpression elimination (CSE)

有重复使用的表达式可以被替换为一次表达式运算，然后存储他的结果，后续的重复表达式运算直接使用第一次得到的结果就可以。

a = b + (c - 2)
d = 4 * b
e = d + (c - 2)
------------>
t1 = c - 2
a = b + t1
d = 4 * b
e = d + t1

Loop invariant code motion

在所有循环中结果都一样的表达式直接放到循环外来计算。

do i = 1,n
    do j = 1,n
        a(j,i)=2*b(i+1)+j-(m*5)
    end do
end do
------------------->
t1 = m*5
do i = 1,n
    t2 = 2*b(i+1)
    do j = 1,n
        a(j,i)=t2 + j - t1
    end do
end do

Algebraic simplification in redundancy elimination

再做一下算术运算的简化。

do i=1,n
    a=b+i
    c=a-i
    d=a
end do
------------->
do i=1,n
    a=b+i
    c=b
    d=a
end do

Dead code elimination

去掉结果从不使用的代码。

loop optimisations

Strength reduction

简化计算，将每次循环的计算强度降低。尽量将基于迭代变量的运算转化为单纯的加法递增。

for (i=0;i<n;i++){
    j = 3*i+2;
    a[j] = b[i];
}
--------------->
j=2;
for (i=0;i<n;i++){
    a[j] = b[i];
    j+=3;
}

Induction variable removal

Induction variable归纳变量，指随着迭代连续变化的变量。

有可能的话，使用一个（迭代变量）来表示所有的归纳变量，减少寄存器的使用。

for (i=0;i<n;i++){
j = 3*i+2;
    a[j] = b[i];
}
---------->
j=2;
for (i=0;i<n;i++){
    a[j] = b[i];
    j+=3;
}

Bounds checking elimination

int a[n];
for (i=lo;i<hi;i++){
    a[i] = i;
}

拿这个举例子，每次循环都需要检查i是否越界，这很耗费时间，其实只需要在一开始检查一下lo和hi是否满足：

lo < n
hi < n
lo < hi

就行。

Procedure call optimisations

Inlining

内联，即提示编译器去将函数以类似宏定义的形式展开在调用处。

可能使代码量增大，使用寄存器的数量也会增多。

Expansion

Inlining是编译器在IR这里做的事情，但是expansion是在汇编/机器码这里做的事情。

它是将函数调用改为一系列指令的组合，层次更低，可以利用一些特别的指令序列。

Instruction scheduling

这是编译器应该在source level做的优化

指令可以重排序，只要维持寄存器的依赖图不变就行了。

而且有一些指令是不能pipeline的比如sqrt，那就需要在sqrt计算和结果之间插入一些指令来充分利用cpu。

目标：

  1. 减少执行的指令
  2. 减少流水线停顿（data hazards, control hazards, structural hazards）
  3. 使用多发射(VLIW, superscalar)

Branch scheduling

分支会导致流水线停顿，两种方案：

  1. delayed branches（编译器来做，引入分支延迟槽，流水线中，分支指令执行时因为确定下一条指令的目标地址（紧随其后 or 跳转目标处？）一般要到第 2 级以后，在目标确定前流水线的取指级是不能工作的，即整个流水线就“浪费”（阻塞）了一个时间片，为了利用这个时间片，在体系结构的层面上规定跳转指令后 面的一个时间片为分支延迟槽（branch delay slot）。位于分支延迟槽中的指令总是被执行，与分支发生与否没有关系。这样就有效利用了一个时间片，消除了流水线的一个“气泡”。）
  2. 分支预测(依赖硬件Reorder Buffer，用于rollback结果)

编译器就找一些可以放到分支延迟槽的指令，把它们放进去就更有效地利用了流水线，消除了stall。当然可能还要尝试找一些可以忽视分支的指令。

Loop unrolling

就是展开循环，因为小的循环中花费在分支上的代价太大，把他们展开，可能耗费更多寄存器但是减少了stall。

同时一些特殊指令也可以被使用进去。

有几点需要注意：

unroll factor选择很重要，大了会用完寄存器，数量的选择可以考虑cache line，提高缓存的命中

Outer loop unrolling： 在unroll的时候对于多层循环，尽量去unroll外层的循环，这有助于提升代码的局部性

就类似内存读取时读取连续的值一样，有助于缓存命中

Variable expansion

用于解除展开循环中的数据依赖：

for (i=0,i<n,i+=2){
    b+=a[i];
    b+=a[i+1];
}
--------------------->
for (i=0,i<n,i+=2){
    b1+=a[i];
    b2+=a[i+1];
}
b=b1+b2;

Register renaming

在一个block中寄存器可能被重用，这会带来不必要的依赖。

使用多个寄存器可以提供更多的scheduling flexibility、

有些CPU在硬件上实现了寄存器raname，但是这些都是对编译器不可见的。

add %f2,1,%f1
st [%o1],f1
add %f3,2,%f1
st [%o2],f1
---------------->rename
add %f2,1,%f1
st [%o1],f1
add %f3,2,%f27
st [%o2],f27
---------------->reschedule
add %f2,1,%f1
add %f3,2,%f27
st [%o1],f1
st [%o2],f27

Software pipelining

软件层面实现流水线来解决循环，看例子：


for (i=0;i<n;i++){
    a(i) += b;
}
------------------------>
for (i=0;i<n;i++){
    t1 = a(i); //L i
    t2 = b + t1; //A i
    a(i) = t2; //S i
}
--------------------------->
//prologue
t1 = a(0); //L 0
t2 = b + t1; //A 0
t1 = a(1); //L 1
for (i=0;i<n-2;i++){
    a(i) = t2; //S i
    t2 = b + t1; //A i+1
    t1 = a(i+2); //L i+2
}
//epilogue
a(n-2) = t2; //S n-2
t2 = b + t1; //A n-1
a(n-1) = t2; //S n-1

这样搞对向量化的架构很有好处（superscalar and VLIW），因为：

• large loop body • few dependencies between instructions • lots of scope for multiple issue

optimisations for the memory hierarchy

这一层级的优化就很大可能要自己手动实现

Loop interchange

多层循环，交换循环次数，这个很熟悉了，为了cache命中率：


for (j=0;j<n;j++){
    for (i=0;i<m;i++){
        a[i][j]+=b[i][j];
    }
}
------------------------------>
for (i=0;i<m;i++){
    for (j=0;j<n;j++){
        a[i][j]+=b[i][j];
    }
}

Loop reversal

交换循环的次序，从前到后，从后到前，可以利用在array比cache大一点的时候，在循环开始前array末尾刚存进cache，先从末尾开始访问，命中率高

for(i=0;i=<m;i++){
    a[i]+=b[i];
}
---------------------->
for(i=m;i>=0;i--){
    a[i]+=b[i];
}

Loop skewing

for (j=0;j<n;j++){
    for (i=0;i<m;i++){
        a[j]+=b[i+j]+1;
    }
}
-------------------------->
for (j=0;j<n;j++){
    for (i=j;i<m+j;i++){
        a[j]+=b[i]+1;
    }
}

转化成这种形式，可以惠及其他的转化方式。这种转化本身一般不会带来直接的好处。

Unimodular transformations

Loop skewing，Loop reversal，Loop interchange都是Unimodular transformations

Loop fusion

将俩循环合并：

for(j=0;j<n;j++){
    a[j]+=1;
}
for(i=0;i<n;i++){
    b[i]=a[i]*2;
}
------------------------------------>
for(j=0;j<n;j++){
    a[j]+=1;
    b[j]=a[j]*2;
}

可能可以减少内存访问的次数，比如这里a的访问放到一起去了

循环块加大了，对于scheduler的优化也有更大的发挥空间

附上dalao写的：https://zhuanlan.zhihu.com/p/315041435

Loop distribution

Loop fusion的反向操作，一般用来减轻寄存器pressure

Loop tiling

for (i=0;i<n;i++){
    for (j=0;j<n;j++){
        a[i][j]+=b[i][j];
    }
}
------------------------->
for (ii=0;ii<n;ii+=B){
    for (jj=0;jj<n;jj+=B){
        for (i=ii;i<ii+B;i++){
            for (j=jj;j<jj+B;j++){
                a[i][j]+=b[i][j];
            }
        }
    }
}

这个比较复杂，直接看dalao写的： https://zhuanlan.zhihu.com/p/292539074

https://zhuanlan.zhihu.com/p/301905385

Array padding

根据cache的映射规则，加上padding的话，连续访问的元素也许就不会造成大量的cache conflict

float a[2][4096];
for (j=0;j<n;j++){
a[1][j]+=1;
a[2][j]*=2;
}
--------------->
float a[2][4096+64];
for (j=0;j<n;j++){
a[1][j]+=1;
a[2][j]*=2;
}
comments powered by Disqus
© 2020 - 2022 Gao's Happy Day
Built with Hugo
Theme Stack designed by Jimmy