天天看点
返回

关于cpu 分支预测 以及 cpu pipeline 的一些思考

文章目录

  • ​​从rocksdb代码看到的分支预测开始​​
  • ​​关于__builtin_expect 的说明​​
  • ​​关于cpu pipeline机制的说明​​
  • ​​Cpu 为什么需要时钟​​
  • ​​单周期cpu​​
  • ​​多周期cpu​​
  • ​​pipeline cpu​​
  • ​​关于分支预测 如何在 CPU pipeline机制中工作​​
  • ​​友好的分支预测对程序性能有多大影响呢​​
  • ​​总结​​
  • ​​reference​​

从rocksdb代码看到的分支预测开始

熟悉rocksdb代码的同学 再看到今天所分享的这个主题，就知道我说的是rocksdb中的LIKELY/UNLIKELY函数。

这个宏的详细定义是这样的:

#if defined(__GNUC__) && __GNUC__ >= 4
#define LIKELY(x)   (__builtin_expect((x), 1))
#define UNLIKELY(x) (__builtin_expect((x), 0))

rocksdb 作为 各个newsql/nosql 以及相关分布式存储的 存储内核，必然对性能有极高的要求，而这一些细节则会直接体现在rocksdb的代码中。

同样，以上​

​LIKELY/UNLIKELY​

​这样的宏 被应用在了rocksdb代码中的主要流程，像memtable->add, process_write这样的请求必经之路上，那这个宏相比于原本只需要用if/else这样的代码肯定有自己的独特之处。

// Memtable->Add
bool res = table->InsertKeyConcurrently(handle);
if (UNLIKELY(!res)) {
  return res;
}

接下来详细分析一下分支预测对程序性能的影响，希望能够回答如下几个问题。

  • 分支预测 是什么？
  • cpu pipeline架构是如何演进的？
  • CPU分支预测是如何体现在 pipeline 执行指令 的过程中的？
  • 对CPU友好的分支预测 能够有多少的性能提升？

关于__builtin_expect 的说明

它是gcc编译器引入的一个指令，允许程序员将代码中最有可能执行的分支告诉编译器。具体的写法

__builtin_expect(EXP,N) // 其中EXP可以为变量，也可以为表达式

意思是，EXP==n的概率很大。

rocksdb中做了一个封装，​

​LIKELY(x) (__builtin_expect((x), 1))​

​ ，即LIKELY表示x为真的概率很大；相反，UNLIKELY表示x为假的概率很大。

当然这一些编译器指令需要 gcc版本 在2.96以上才支持，gcc会将代码中的调用的“分支转移”指令 编译成能够减少CPU跳转的汇编指令，方便后续的CPU执行。

如下代码：

int x, y;
 if(UNLIKELY(x > 0))
    y = 1; 
else 
    y = -1;

这个事例中,上面的代码中 gcc 编译的指令会预先读取 y = -1 这条指令，这适合 x 的值大于 0 的概率比较小的情况。如果 x 的值在大部分情况下是大于 0 的，就应该用 Likely(x > 0)，这样编译出的指令是预先读取 y = 1 这条指令了。这样系统在运行时就会减少重新取指了。

关于cpu pipeline机制的说明

Cpu 为什么需要时钟

我们在看CPU型号的时候 可以看到有如下这样的配置

Intel(R) Xeon(R) Gold 5218 CPU @ 2.30GHz
  • Intel 代表厂商，除了Intel还有AMD
  • Xeon 表示cpu的一种型号系列： 至强型号，除了这个型号还有core(酷睿)，PenTIum(奔腾)，Atom（凌动）等
  • Gold 5218 表示 至强 系列中的一种型号，数字越大，表示型号越新，也就是性能越好。
  • 2.30GHz 表示CPU的主频上限，也就是我们要说的时钟频率/周期。

时钟在CPU中的重要性不言而喻，像DRAM, DMA 等都可以看作是CPU的外设，这一些外设通过CPU的调度有序“和谐”运行，而这个有序 则就是通过CPU的时钟周期来控制的。

关于cpu 分支预测 以及 cpu pipeline 的一些思考

如上图，一个clock period 可以表示一个时钟周期。

总结来说，CPU时钟周期的主要作用：

  1. 协调 外设组件工作

    无固定频率的CPU和周边工作单元协同工作时，因为大家步调不一致，沟通起来效率会打折扣（通才采用应答的模式来进行速度匹配，类似于TCP）。

    有的器件它的工作速度可能非常快（比如说一个单纯的PC，最简单的情况下它只会对上一个上升沿或下降沿到来时自己的值+4），而这个快可以通过时钟周期来表示，比如1.5个时钟周期。

    同时，有的器件它工作的速度可能会非常慢（比如说FPU在计算一个极其复杂的浮点数除法时，再如DIV模块进行32位除法的时候一般需要32个周期），当然这个 慢 也可以用时钟周期来表示，比如 4。这样，CPU能够通过时钟周期知道其他组件的运行情况，其他组件也能通过统一的CPU 时钟周期知道各自的运行情况，从而让整个计算机系统更加协调得运行。

  2. “同步”地工作

    例如CPU从寄存器中读取一个32位的数据，此时要求32位数据同时读入而不能有先后顺序，于是就需要有同一个时钟信号，让部件在同一个上升沿（或下降沿）去读取出这样一个数据。

接下来可以看看CPU pipeline 架构 是如何从 单周期cpu --> 多周期cpu --> pipeline cpu的。

指令执行的各个过程会在pipeline 处详细描述。

单周期cpu

单周期CPU在一个时钟周期内完成所有的工作。例如指令取出，得到结果等，它们全部都在一个时钟周期内完成。

关于cpu 分支预测 以及 cpu pipeline 的一些思考

如上图，一个时钟周期内完成一个指令不同阶段的完整执行，后续的每一个指令都会消耗一个时钟周期。

在单周期cpu中时钟周期就是指令周期，因此每个指令周期都是固定的时长；

单周期的缺点：

由于不同的指令执行快慢是不一样的，导致指令周期必须取决于执行时间最长的指令，因此执行较为简单的指令时会浪费时间，处理器的主频也难以提高。

优点：

CPU架构简单，执行的执行不需要复杂的控制逻辑。

多周期cpu

多周期CPU将整个CPU的执行过程分成几个阶段，每个阶段用一个时钟去完成。在多周期CPU中，一个指令周期可以由数个时钟周期组成，不同的指令可以占用不同的时钟周期数，从而提高了时间片的利用率，不仅能提高CPU主频，还为组成指令流水线提供了基础。

关于cpu 分支预测 以及 cpu pipeline 的一些思考

但是存在的问题仍然是 部分指令的阶段执行较快，而时钟周期仍然是选择指令阶段执行最长的时钟作为时钟周期，所以此时cpu还是会存在等待的问题。

相比于单周期cpu，主频明显提高了，但是仍然存在等待的情况，即时间利用率并不高，对应的cpu性能也不会很高（很多时间都是在空闲等待）。

为了充分提高cpu的时钟频率，提升CPU性能，研究员研究出了更高性能的CPU架构 – pipeline

pipeline cpu

先总体介绍CPU 指令执行的五个阶段（如下图）：

关于cpu 分支预测 以及 cpu pipeline 的一些思考

  • IF(Instruction fetch) 取指：从 Instruction-Memory 中读取指令，并在下一个时钟上升沿到来时把指令送

    到 ID 级的指令缓冲器 id_ir 中。该级控制信号决定下一个指令指针的 pc 信号(即 Instruction-Memory 的指令地址 i_addr)

  • ID(Instruction decode)指令译码： 对 IF 级的指令进行译码，根据指令操作码获取操作数read reg_1、read reg_2 或者要 直接储存的数据内容 smdr，并在下一个时钟上升沿到来前把指令 id_ir(前 8 位，操作码+operand1)送 到 EX 级的指令缓冲器 ex_ir 中
  • EX(Execute)执行：该级进行算术运算(加、减)、简单传输(JUMP 操作)、逻辑运算(与、或、异或) 或移位操作(逻辑左移、逻辑右移、算术左移、算术右移)。算术逻辑单元 ALU 根据指令对两个操作数 reg_A、 reg_B 进行操作，将获得的结果 ALUo 送到下一级的 reg_C，在此过程中，控制标志信号 cf、nf、zf 并将 其传到相应的缓冲寄存器 ;或者产生存储数据的使能信号 d_we，同时将要直接储存的数据内容 smdr 传到 MEM 级的 smdr1。在下一个时钟上升沿到来前把指令 ex_ir 送到 MEM 级的指令缓冲器 mem_ir 中。总的来说就是拿到译码后的数据在ALU中进行计算，并将计算的结果放在MEM中的缓冲区中。
  • MEM(Memory Access)：数据存储器访问: 根据指令处理 reg_C 获取需要的内容存储到缓冲器 reg_C1，并在下 一个时钟上升沿到来前把指令 mem_ir 送到 WB 级的指令缓冲器 wb_ir 中。只有在执行 LOAD、STORE 指令 时才对存储器进行读、写操作，对于此之外的其他指令，MEM 级只起到一个周期的作用。
  • WB(Write Back) 写回：对于需要刷新通用寄存器的操作，WB级把指令执行的结果回写到通用寄存器中

简化版的指令流水线作业如下（wikibook中的图）：

关于cpu 分支预测 以及 cpu pipeline 的一些思考

流水线能够极大得提升CPU执行效率的原因所在 是 让CPU的各个组件每时每刻都在工作，充分提升了CPU的时钟频率。

也就是我们上面说到CPU执行过程的每个阶段都有各自的执行区域，可以将每个执行区域看作一个汽车零件加工厂，每个加工厂只需要负责自己组件的加工，不需要考虑其他的组件是如何加工的。当所有加工厂全速运转时，整个指令从开始到结束会经过每个加工厂，都最后完成汽车的组装的时候整个工厂并没有休息。类比于CPU的话，就是每个阶段的CPU组件都在全力运行。

关于分支预测 如何在 CPU pipeline机制中工作

  • 分支预测器位于整个CPU核心流水线的差不多最前端部分，靠近IF的级。从指令缓存里面读取指令时，需要由分支预测器来判断从哪里读取。
  • 分支预测器维护一个历史记录表，记录以往执行过的分支指令的偏向情况，帮助未来的预测，本质上也是一块高速缓存。另一块是预测器的逻辑部分，依据记录表里面的记录情况预测将来的分支走向。

比如一条指令执行十几次都是跳转，那么分支预测器预测将来碰到这条指令时仍然会跳转。如果预测的这个结果连续两次出错，那么预测器则跳转预测结果，改为不跳转。

如果反复的预测不准确，即如果满足要求，则JMP到另一部分内存执行。

如果不满足要求，跳过接下来的JMP指令。

可见分支预测失败 会导致整个指令重新执行，即之前指令执行的几个阶段都会被从流水线抛弃掉，重新放入新的指令到流水线，这样的情况会大大降低CPU的 pipeline效率，相当于汽车工厂 中起始零件加工老是投放劣质材料，导致后续的零件加工发现问题，那这个零件加工到现在 即使快成为汽车了也会被直接回收。

友好的分支预测对程序性能有多大影响呢

接下来通过程序模拟分支预测成功和失败，来看看频繁失效的分支预测会对性能有多大的影响。

如下代码：

#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#include <sys/time.h>
 
double now() {
  struct timeval t;
  double result;
  gettimeofday(&t, NULL);
  result = (t.tv_sec)*1000000 + t.tv_usec;
  return result; 
}

int cmp(const void*a,const void*b)//用来做比较的函数。
{
    return *(int*)a-*(int*)b;
}

int main()
{
    // 随机产生整数，用分区函数填充，以避免出现分桶不均
    const unsigned arraySize = 32768;
    int data[arraySize];
    srand((unsigned int)time(0));
 
    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = rand() % 256;
 
    // !!! 排序后下面的Loop运行将更快
    // qsort(data, arraySize, sizeof(unsigned), cmp);
 
    // 测试部分
    double start = now();
    long long sum = 0;
 
    for (unsigned i = 0; i < 100000; ++i)
    {
        // 主要计算部分，选一半元素参与计算
        for (unsigned c = 0; c < arraySize; ++c)
        {
          // 如果data 没有经过排序，分支预测失效的概率会高很多 data在256内分布不均匀
          // 如果data 经过排序，那么就类似于  1,2,3,3,..45,46..126,126,...255 这样有序的
          // 分支预测器能够快速生效
            if (data[c] >= 128) 
                sum += data[c];
        }
    }
 
    double elapsedTime = (now() - start) / CLOCKS_PER_SEC;
 
    printf("%.2fs\n", elapsedTime);
    printf("sum = %lld\n", sum);
}

将数组排序 来提供友好的分支预测 与 不排序 所体现的性能：

1. no sort
17.40s
sum = 312786000000
2. sort
5.93s
sum = 312083300000

排序与不排序之间的执行时间差了三倍。

同样的代码分别用C++ 和 Go 再确认一下性能：

C++

#include <algorithm>
#include <ctime>
#include <iostream>
 
int main()
{
    // 随机产生整数，用分区函数填充，以避免出现分桶不均
    const unsigned arraySize = 32768;
    int data[arraySize];
 
    for (unsigned c = 0; c < arraySize; ++c)
        data[c] = std::rand() % 256;
 
    // !!! 排序后下面的Loop运行将更快
    // std::sort(data, data + arraySize);
 
    // 测试部分
    clock_t start = clock();
    long long sum = 0;
 
    for (unsigned i = 0; i < 100000; ++i)
    {
        // 主要计算部分，选一半元素参与计算
        for (unsigned c = 0; c < arraySize; ++c)
        {
            if (data[c] >= 128)
                sum += data[c];
        }
    }
 
    double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC;
 
    std::cout << elapsedTime << "s" << std::endl;
    std::cout << "sum = " << sum << std::endl;

    return 0;
}

C++实现的 排序和不排序的执行时间差异同样有接近三倍：

# no sort
19.5751s
sum = 312426300000
# sort
6.00991
sum = 312426300000

再看看Go的实现：

package main

import (
  "math/rand"
  "sort"
  "fmt"
  "time"
)

func branch() {
  var size int = 32768
  testArr := make([]int, size)
  rand.Seed(1)

  for i := 0; i < size; i++ {
    testArr[i] = rand.Intn(256)
  }
  
  // sort 
  sort.Ints(testArr)

  var sum int
  now := time.Now()

  for j := 0; j < 100000; j++ {
    for i := 0; i < size; i++ {
      if testArr[i] >= 128 {
        sum += testArr[i]
      }
    }
  }

  end := time.Since(now)
  fmt.Println("time : ", end.Seconds(), "s sum = ", sum)
}

func main() {
  branch()
}

输出如下, go 的性能差异体现的尤为明显（Go执行过程中使用的是协程机制，每一个内核线程可以多个用户线也就是goroutine 程绑定，这样频繁出错的分支预测必然会对执行性能有更加严重的影响）

# sort
time :  1.351624114 s sum =  312457800000
# no sort
time :  12.331254251 s sum =  312457800000

总结

通过对CPU pipeline 原理描述，加上 不友好的分支预测 对性能产生的严重影响，我们能够体会到系统设计的复杂和精妙。但核心也非常简单，一切都是追求极致的性能。

reference

分支预测 时钟周期 #include
上一篇: 重做 USACO 1.1 你的飞碟在这儿
下一篇: [一卡多号]第三步：GSM SIM卡破解KI全攻略

继续阅读