天天看點
傳回

關于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全攻略

繼續閱讀