优化程序性能 ¶

优化编译器的能力和局限 ¶

妨碍优化的因素 :

• 内存别名使用 (memory aliasing) 在只执行安全的优化中, 编译器必须假设不同的指针可能会指向内存中的同一个位置.

void twiddle1 (long *xp,long*yp)
{
    *xp+ = *yp;
    *xp+ = *yp;
}
void twiddle2(long *xp,long*yp)
{
    *xp+ = 2 * *yp;
}

• 函数调用

long f();
long func1() {
    return f() + f() + f() + f();
}
long func2() {
    return 4 * f();
}

但是当函数有副作用时 -- 它会改变全局程序状态的一部分 , 那么改变调用它的次数会改变程序的行为 . 因此大多数编译器也不会对此做优化 .

表示程序性能 ¶

程序性能衡量标准 : 每元素的周期数 (CPE i.e. Cycles Per Element).

Example

// Compute prefix sum of vector a
void psum1(float a[], float p[], long n)
{
    long i;
    p[0] = a[0];
    for (i = 1; i < n; i++)
        p[i] = p[i-1] + a[i];
}
void psum2(float a[], float p[], long n)
{
    long i;
    p[0] = a[0];
    for (i = 1; i < n-1; i+=2) {
        float  mid_val = p[i-1] + a[i];
        p[i] = mid_val;
        p[i+1] = mid_val + a[i+1];   
    }
    if (i < n)
        p[i] = p[i-1] + a[i];
}

psum1 每次计算向量的一个元素, psum2 每次计算两个元素(循环展开). 这样一个过程所需要的时间我们可以用最小二乘法来拟合 .
其中 psum1: 368+9.0n, psum2: 368+6.0n. 这些项中的系数称为 CPE.

消除循环的低效率 ¶

Example

void lower1(char *s)
{
    size_t i;
    for (i = 0; i < strlen(s); i++)
        if (s[i] >= 'A' && s[i] <= 'Z')
        s[i] -= ('A' - 'a');
}
void lower2(char *s)
{
    size_t i;
    size_t len = strlen(s);           /*放在函数体外*/
    for (i = 0; i < len; i++)
        if (s[i] >= 'A' && s[i] <= 'Z')
        s[i] -= ('A' - 'a');
}

由于循环结构的效率比较低, 初始代码 lower1 的运行时间是二次项的, 修改过的代码 lower2 的运行时间是线性的.
因为 lower1 的 n 次迭代每次迭代都会调用 strlen 函数, 而 strlen 所用时间又与 n 成正比, 因此整体运行时间是 n^2. 同时因为一个字符串的长度不会在运行中改变, 所以我们可以将 strlen 函数移到循环外.

上述方法称为代码移动 (code motion). 即识别要执行多次 ( 例如在循环里 ) 但是计算结果不会改变的计算 , 因而讲计算移动到代码前面不会被多次求值的部分 .
优化编译器不能可靠地发现函数是否有副作用, 所以程序员必须帮助编译器显示地完成代码的移动.

减少过程调用 ¶

Example

int get_vec_element(vec_ptr v, long index, data_t *dest)
{
    if (index < 0 || index >= v->len)
        return 0;       // 边界检查
    *dest = v->data[next];
    return 1;
}
/* Move call to vec_length out of loop */
void combine2 (vec_ptr v, data_t *dest)
{
    long i;
    long length vec_length(v);
    *dest = IDENT;
    for (i=0;i< length;i++)
    {
        data_t val;
        get_vec_element(v,i,&val);
        *dest = *dest OP val;
    }
}

这段代码中每次循环迭代都会调用 get_vec_element 来获取下一个向量元素, 而每次向量调用都有边界检查, 会造成低效率.
于是我们改为如下版本:

data_t *get_vec_start(vec_ptr v)
{
    return v-data;
}
/* Move call to vec_length out of loop */
void combine3 (vec_ptr v, data_t *dest)
{
    long i;
    long length vec_length(v);
    data_t *data = get_vec_start(v);
    *dest = IDENT;
    for (i=0;i< length;i++)
    {
        *dest = *dest OP data[i];
    }
}

但这样做没有带来性能上明显的提升 . 说明内循环中的其他操作形成了平静 , 限制性能超过了 get_vec_element.

消除不必要的内存引用 ¶

Example

#Inner loop of combines. data_t double, OP =
#dest in %rbx, data+i in %rdx, data+length in %rax 
.L17:
vmovsd (%rbx),%xmm()           # Read product from dest 
vmulsd (%rdx),%xmm0,%xmm0      # Multiply product by data[i]
vmovsd %xmm, (%rbx）           # Store product at dest
addq $8,%rdx                   # Increment data+i
cmp %rax,%rdx                  # Compare to data+length 
jne .L17

我们发现 combine3 的代码, 每次迭代时, 累积变量的数值都要从内存读出再写入到内存. 于是我们引用一个历史变量 acc 来表示在循环中累积计算的值.

#Inner loop of combines. data_t double, OP =
#dest in %rbx, data+i in %rdx, data+length in %rax 
.L25:
vmulsd (%rdx),%xmm0,%xmm0      # Multiply product by data[i]
addq $8,%rdx                   # Increment data+i
cmp %rax,%rdx                  # Compare to data+length 
jne .L25    

其修改部分:

// combine4
*data acc = IDENT;
for (i=0;i< length;i++)
{
    acc = acc OP data[i];
}

我们可以发现这样做程序性能有了显著提高:

注意的是 , 由于内存别名使用 , 优化后函数可能有不同的行为 ( 如上述例子中若我们将答案存在向量的最后一个位置 , combine3 和 combine4 就不会得到相同的答案 ), 因此一般来说编译器不会为我们做这一步优化 .

理解现代处理器 ¶

上述优化都不依赖于目标机器的任何特性 , 只是简单降低了过程调用的开销 , 以及消除了一些重大的妨碍优化的因素 . 要进一步提高性能 , 必须考虑利用处理器微体系结构的优化 .
在实际处理器中是同时对多条指令求值的, 这个现象称为指令级并行

整体操作 ¶

如上图所示是一个简化的 Intel 处理器的结构，包含两个特点：

• 超标量 (Superscalar)：处理器可以在每个时钟周期执行多个操作
• 乱序 (Out-of-order)：指令执行的顺序不一定和机器代码的顺序相同，提高指令级并行

整个设计主要分为两个部分 :

• 指令控制单元 (Instruction Control Unit)
  通过取值控制逻辑从指令高速缓存中读出指令序列, 并根据这些序列生成一组针对程序数据的基本操作, 然后发送到 EU 中.

  • 取值控制逻辑
    分支预测, 猜测是否会选择分支, 同时还预测分支的目标地址.
  • 指令高速缓存 (instruction cache)
    一个特殊的高速存储器, 包含最近访问的指令. ICU 会在当前正在执行的指令很早之前取指, 这样它才有足够的时间对指令译码.
  • 指令译码逻辑
    接受实际的程序指令, 并将它们转换成一组基本操作(微操作). 每个这样的操作都完成某个简单的计算任务. e.g. x86 中 addq %rax, %rdx 会被转化成一个操作但 addq %rax, 8(%rdx) 会被译码为三个操作 : 读内存值 , 做加法 , 存回内存 .

  • 退役单元
    记录正在进行的处理, 并确保它遵守机器级程序的顺序语义. 它包含并控制着寄存器文件的更新.
    指令在译码时, 指令信息被放在一个先进先出的队列中. 一旦一条指令的操作完成, 而且所有引起这条指令的分支点也都预测正确, 那么这条指令就可以退役了, 所有这条指令有关的对程序寄存器的更新都可以实际执行了; 如果某个分支点预测错误, 这条指令会被清空, 丢弃所有计算结果.

    Note

    任何对程序寄存器的更新都只会在指令退役时才会发生 . 为了加速指令到指令间结果的传送 , 许多此类信息是在执行单元间交换的 , 即图中的 " 操作结果 ".

• 执行单元 (Execution Unit)
  接收来自取指单元的操作, 通常每个周期会接受多个操作, 这些操作会被分派到一组功能单元中 .

  • 功能单元
    专门用来处理不同类型的操作. 一个功能单元可以执行多种操作, 多个功能单元可以执行同一种操作.
    • 读写内存是通过加载 / 存储模块完成的 . 这两个单元各包含一个加法器来完成地址计算 , 并通过数据高速缓存来读写内存 .
    • 算术运算模块

    • 分支模块
      确定分支预测是否正确(而非分支往哪执行), 如果预测错误, 执行单元会丢弃分支点之后计算出来的结果, 并发信号给分支单元, 并指出正确的分支目的. 这样分支单元会在新的位置取值.

      寄存器重命名

      控制操作数在执行单元间传送的最常见机制是寄存器重命名 (register renaming).
      当执行一条更新寄存器r的指令I1，会产生一个指向该操作结果的唯一标识符t，然后将(r, t)加入重命名表中. 当后续有需要用到寄存器r作为操作数的指令时，会将t作为操作数源的值输入到单元中进行执行, 当I1执行完成时，就会产生一个结果(v, t)，表示标识符t的操作产生了结果v，然后所有等待t作为源的操作都会使用v作为源值。
      意义：使用寄存器重命名机制，可以将值从一个操作直接转发到另一个操作，而无需进行寄存器文件的读写，使得后续的操作能在第一个操作 I1 完成后尽快开始。并且投机执行中，在预测正确之前不会将结果写入寄存器中，而通过该机制就可以预测着执行操作的整个序列 .
      注意：重命名表只包含未进行寄存器写操作的寄存器，如果有个操作需要的寄存器没有在重命名表中，就可以直接从寄存器文件中获取值 .

性能 ¶

刻画性能 :
延迟 (latency): 表示完成运算所需要的总时间
发射时间 (issue time): 表示两个连续的同类型的运算之间需要的最小周期数
容量 (capacity)*: 表示能够执行该运算的功能单元的数量

发射时间为 1 的功能单元被称为完全流水化的 (fully pipelined): 每个时钟周期都可以开始一个新的运算 . e.g. 一个典型的浮点加法器 ( 所以延迟是 3 个周期 ): 一个阶段处理指数 , 一个阶段相加小数 , 一个阶段对结果舍入 . 算术运算可以连续地通过各个阶段 , 不用等一个操作完成后再进行下一个 . 只有当要执行的运算是连续 , 逻辑上独立的时候才能利用这种功能 .
注意到除法器的发射时间等于延迟, 因此必须在完成整个除法后才能进行下一个除法.

我们更倾向于使用最大吞吐量来表示发射时间 , 定义为发射时间的倒数 . 对于一个容量为 C，发射时间为 I 的操作而言，其吞吐量为 C/I.

根据以上性能 , 我们得到 CPE 的两个基本界限 :
延迟界限
延迟界限给出了任何必须按照严格顺序完成合并运算的函数所需要的最小 CPE 值.
当存在数据相关时，指令是严格顺序执行的，意味着我们无法通过指令并行来进行加速。而通过参考机的运算性能知道执行每种运算所需的延迟，就确定了执行该运算所需的最小时钟周期数，此时 CPE 的延迟界限就是运算操作的延迟 .
吞吐量界限
根据功能单元产生结果的最大速率, 吞吐量界限给出了 CPE 的最小界限.
表示我们考虑系统中的所有的功能单元，计算出来运算结果的最大速率.

处理器操作的抽象模型 ¶

我们使用程序的数据流 (data-flow)表示 , 展示了不同操作之间的数据相关是如何限制他们的执行单元的 . 这些限制形成了图中的关键路径 (critical path), 这是执行一组机器指令所需时钟周期数的一个下界 .

这个例子中我们看到除了整数加法, 测量值与处理器的延迟界限是一样的, 这表明这些函数的性能是由求和/乘积运算主导, 而且存在数据相关.

从机器级代码到数据流图 ¶

对于形成循环的代码片段 , 我们将访问到的寄存器分为四类 :

• 只读 : 这些寄存器只用于源值 , 在循环中不会被修改 .
• 只写 : 这些寄存器作为数据传送操作的目的 .
• 局部 : 这些寄存器在循环内部被修改和使用 , 迭代和迭代之间不相关 .
• 循环 : 对循环来说这些寄存器既作为源值 , 又作为目的 , 一次迭代中产生的值会在另一次迭代中用到 .

循环寄存器之间的操作链决定了限制性能的数据相关 .

其他性能因素 ¶

数据流中的关键路径只是提供程序需要周期数的下界，还有很多其他因素会限制性能。e.g. combine4 中当我们将左侧的操作变为整数加法时，根据数据流预测的 CPE 应该为 1，但是由于这里的操作变得很快，使得其他操作供应数据的速度不够快，造成实际得到的 CPE 为 1.27.

练习题 5.5 & 5.6

double poly(double a[], double x, long degree)
{
    long i;
    double result = a[0];
    double xpwr = x;
    for(i=1; i<=degree; i++){
        result += a[i]*xpwr;
        xpwr = x*xpwr;
    }
    return result;
}
double polyh(double a[], double x, long degree)
{
    long i;
    double result = a[degree];
    for(i=degree-1; i>=0; i--){
        result = a[i]+x*result;
    }
    return result;
}

我们测量发现 poly 的 CPE 为 5.00, 但 polyh 的 CPE 为 8.00, 为什么?
polyh 不难理解, 因为乘法必须在加法完成后才能执行, 所以是 5+3=8. 而 poly 函数我们可以发现, a[i] * xpwr 和x * xpwe 的计算和 result 无关, 我们可以把 result 放在下一次循环中和两个乘法并行计算, 这样就不需要在这次循环中先乘法再加法了.
be like:
因此对一个数据流图, 我们只需要关注循环寄存器的数据相关链, 即它关键路径上的操作数.

上面的例子告诉我们 , 函数具有更少的操作不意味着具有更好的性能 .

循环展开 ¶

循环展开是一种程序变换 , 通过增加每次迭代计算的元素的数量 , 减少循环的迭代次数 .
它减少了不直接有助于程序结果的操作的数量, 例如循环索引计算和条件分支; 它提供了一些方法来进一步变化代码, 减少整个计算中关键路径上的操作数量.
这里使用一种"k*1 循环展开"的方法, 第一个循环每次处理数组的 k 个元素, 第二个循环处理剩下还没处理的元素(因为数组长度不一定是 k 的倍数).

Example

// 2 * 1 loop unrolling

void combine5(vec_ptr v, data_t *dest)
{
    long i;
    long length = vec_length(v);
    long limit = length-1;
    data_t *data = get_vec_start(v);
    data_t acc = IDENT;

    for(i=0; i<limit; i+=2){
        acc = (acc OP data[i]) OP data[i+1];
    }
    for(; i<length; i++){
        acc = acc OP data[i];
    }
    return acc;
}

此时我们可以看到, 整数加法的一个周期的延迟成为了限制性能的因素. 当我们不断增加 k 的大小时, 我们发现 CPE 的测量值没有一个低于延迟界限.
我们画出他简化后的数据流图:

虽然循环展开了 2 次, 但关键路径还是 n 个 mul 操作.

提高并行性 ¶

多个累积变量 ¶

假设这里有 \(a_0,a_1,\ldots,a_{n-1}\) 个元素 , 我们要计算 \(P_n=\prod\limits_{i=0}^{n-1}a_i\). 可以通过 \(PE_n=\prod\limits_{i=0}^{n/2-1}a_{2i}\quad PO_n=\prod\limits_{i=0}^{n/2-1}a_{2i+1}\) 则 \(P_n=PE_n\times PO_n\) 得到 .

推广上述思路 , 我们得到一种 "k*k 循环展开方法 "，将一个循环展开成了两部分，第一部分是每次循环处理 k 个元素，能够减少循环次数，并且引入 k 个变量保存结果；第二部分处理剩下还没计算的元素，是逐个进行计算的 .

当 k 足够大时 , 程序在所有情况几乎都能达到吞吐量界限.
为了接近吞吐量界限，我们需要使用系统中的所有功能单元，并且保证功能单元的流水线始终是慢的，所以对于容量为 C、延迟为 L 的操作而言，需要设置 \(k\geq C\cdot L\)(最快每个时钟周期执行一个操作).
但需要注意的是, 我们需要申请 k 个局部变量来保存中间结果. 但如果 k 大于了寄存器的数目, 结果就会被保存在堆栈中, 这就需要我们反复读写内存, 造成性能损失.

重新结合变换 ¶

我们改变合并执行的方式 , 也能极大地提高程序的性能 .

限制因素 ¶

寄存器溢出 ¶

如果我们的并行度 p 超过了可用的寄存器的数量 , 那么编译器会诉诸溢出 , 将某些临时之存放到内存中 , 通常是在堆栈上分配空间 .

分支预测和预测错误惩罚 ¶

当分支预测逻辑不能正确预测一个分支是否要跳转时 , 条件分支可能会招致很大的预测错误惩罚 .

不要过分关心可预测的分支 ¶

实际上 , 现代处理器中的分支预测逻辑非常善于辨别不同分支指令的有规律的模式和长期趋势 . 而且执行边界检测所需的额外运可以与合并操作并存执行 , 所以这些求值都不会对形成程序执行中关键路径的指令的取值和处理产生太大的影响 .

书写适合使用条件传送实现的代码 ¶

对于本质无法预测的情况 , 如果编译器能产生使用条件传送而不是使用条件控制转移的代码 , 可以极大地提高程序的性能 .
但要注意, 不是所有的条件行为都能用条件数据传送来实现.

理解内存性能 ¶

加载的性能 ¶

一个包含加载操作的程序的性能既依赖于流水线的能力 , 也依赖于加载单元的延迟 .
e.g. 我们的参考机包含两个加载功能单元，意味着当流水线完全时，一个时钟周期最多能够执行两个加载操作，由于每个元素的计算需要加载一个值，所以 CPE 的最小值只能是 0.5。对于每个元素的计算需要加载 k 个值的应用而言，CPE 的最小值只能是 k/2.
在之前我们的示例中, 加载操作只依赖循环索引 i, 不存在数据相关, 因此加载不会称为关键路径上的操作.

链表

typedef struct ELE {
    struct ELE *next;
    long data;
}list_ele, *list_ptr;

long list_len(list_ptr ls) {
    long len = 0;
    while (ls) {
        len++;
        ls = ls -> next;
    }
    return len;
}

其数据流图:

因此加载操作出现在关键路径上. 这个例子测出 CPE 为 4.0.

存储的性能 ¶

存储操作不会影响任何寄存器 , 因此一系列存储操作不会产生数据相关 . 只有加载操作会受存储操作影响 .
一个内存读的结果依赖于一个最近的内存写, 我们称之为写 / 读相关.

存储单元包含一个存储缓冲区, 它包含已经被发射到存储单元而又没有完成的存储操作的地址和操作 , 这里的完成包括更新数据高速缓存 . 当一个加载操作发生时 , 它必须检查存储缓冲区中的条目 , 看是否有地址相匹配 . 若有 ( 存在写 / 读相关 ) 就取出对应数据条目作为加载操作的结果 .

评论