读书笔记第七周《深入理解计算机系统》之分支预测

读书笔记《深入理解计算机系统》PB14214061 张士龙

本周看的是优化的关于分支预测的部分以及存储器相关部分。

关于分支预测

第三章提到，现代处理器是通过流水线来提高性能，在流水线中，每一条指令处理需要一定的阶段，取指令，确定指令类型，内存读数据，进行运算，向内存写数据，更新程序计数器，因为这些步骤几乎是确定的，处理器会重叠连续指令的步骤来以提高性能，比如说，在进行上一条指令的运算部分时候，同时进行下一条指令的载入，但是这样就对顺序提出了要求，必须知道接下来会执行哪些指令，才能将流水线填满，但是这种机制遇到分支时候就会出现困难，因为不知道接下来应该进行哪些指令。
但是处理器也并不会因为遇到分支而停止执行，而是根据经验选择一个分支继续执行，如果选择错误，则回到分支点，重新填充流水席线，如何回退机制在上周笔记中分析了，在此主要看看丢弃之前投机执行的结果打断流水线会带来多大的惩罚。

1 如何估计预测错误惩罚

这个是在前面第三章讲到的，一般是选择一组完全可预测的数据，比如几乎分支某个情况100%会出现，此时就几乎不会打断流水线，也就没有分支惩罚，假如所有分支的出现概率几乎相等，那么分支惩罚就几乎成为程序的瓶颈。具体的，我们可以这么估计，认为没有错误执行时间为Tok错误惩罚为Tmp,假如对于完全难以预测的二分支，平均执行时间为Tan的话，很容易得到，0.5Tok+0.5（Tok+Tmp）=Tan。

2 如何在某些情况下能避免这种惩罚

假如分支惩罚非常严重，成为性能瓶颈，那么书中讲述了一种备选的优化方法，这种方法在我的理解中就是，每个分支都算，最后进行判断选择某个分支的结果，这样就可以保证流水线一直都是满的。(在第三章的语境下，这样书写的代码，诱导编译器使用条件数据传送指令。) 例子：

void minmax1(long a[] ,long b[],long c){
    long i;
    for(i = 0; i < n; i++){
        if(a[i]<b[i]){
            long t =  a[i];
            a[i] = b[i];
            b[i] = t;
        }
    }
}
void minmax2 (long a[],long b[],long c){
    long i;
    for(i=0;i<n;i++){
        long min = a[i]<b[i]?a[i]:b[i];
        long max = a[i]<b[i]?b[i]:a[i];
        a[i]=min;
        b[i]=max;
    }
}


实践证明，1对于随机数据的性能的cpe大概13.5，对可预测2.5~3.5，错误惩罚大概20，2的性能对任何数据大概4，可见数据随机的话，代码2的优化还是很可观的。 但是注意，假如每个分支的运算都十分复杂，多算一个分支的时间超出了预测错误惩罚，就不要进行这种优化。

3 可预测分支几乎不会带来惩罚

这个情况最经典的应该算是循环的边界检查，这个几乎只有最后一次预测错误的时候才会引起错误惩罚。甚至有些边界内可以预测到的分支的边界检测几乎不会影响性能。比如

void combin(vec_ptr v ,data *dest){
    long i;
    long length = vec_length(v);
    data acc = IDENT;
    for(i = 0；i < length; i++){
        if(i>=0&&i<c->data){
            acc = acc op v->data[i];
        }
    }
    dest* = acc ;
}

一般都会觉得循环内的边界检查会影响程序性能，其实不然因为预测分支内的内容几乎是必然被执行的，而且边界检查的运算会跟里面的运算并行执行，只要循环内的运算稍微复杂点（这正是一般的情况），边界检查语句的影响就根本看不出来。

4 剖析工具

这个我们第一次作业就用到了，这个对于我们找寻代码性能瓶颈简直是利器，文中的例子甚至就类似于我们第一次作业的词频统计，也是从数据结构哈希函数的选择，排序算法选择（优化最大，果然算法才是真正的人类智慧的结晶）来提升性能。其实前面诱导编译器优化也是类似的，查看反汇编结果，反复更改语句诱导编译器使用某指令。

稍微总结下上周循环展开技巧

上周之后看了关于并行性的描述后，觉得非常有意思，就又看了一些提高代码并行性的方法细节。

1 增加累计变量进行循环展开的方法，利用的的是计算的并行性，但是展开的上线是处理器的功能单元，更高阶的技巧是对代码进行更不同寻常的编写，诱导编译器使用更高阶的如SIMD，如今的AVX指令提高并行性。
2具体的累计变量的数目，上限是功能单元数目*运算延时，（运算延时的概念为完成运算需要总时间），为什么这么算呢？因为这样能恰好保证功能单元流水线是满的。但是同时过多又会存在寄存器溢出，也就是累积变量过多的话编译器会把多出来得累加变量放到栈里，此时性能反而会下降。但是一般现代X86-64处理器已经有足够的寄存器使用，在溢出前就能达到吞吐量限制。