偷偷摘套内射激情视频,久久精品99国产国产精,中文字幕无线乱码人妻,中文在线中文a,性爽19p

深入理解CPU的分支預(yù)測(cè)(Branch Prediction)模型

開發(fā) 開發(fā)工具
本文以stackoverflow上Why is it faster to process a sorted array than an unsorted array?為原型,翻譯了問題和高票回答并加入了大量補(bǔ)充說明,方便讀者理解。

說明: 本文以stackoverflow上Why is it faster to process a sorted array than an unsorted array?為原型,翻譯了問題和高票回答并加入了大量補(bǔ)充說明,方便讀者理解。

背景

先來(lái)看段c++代碼,我們用256的模數(shù)隨機(jī)填充一個(gè)固定大小的大數(shù)組,然后對(duì)數(shù)組的一半元素求和:

  1. #include <algorithm> 
  2. #include <ctime> 
  3. #include <iostream> 
  4.  
  5. int main() 
  6.     // 隨機(jī)產(chǎn)生整數(shù),用分區(qū)函數(shù)填充,以避免出現(xiàn)分桶不均 
  7.     const unsigned arraySize = 32768; 
  8.     int data[arraySize]; 
  9.  
  10.     for (unsigned c = 0; c < arraySize; ++c) 
  11.         data[c] = std::rand() % 256; 
  12.  
  13.     // !!! 排序后下面的Loop運(yùn)行將更快 
  14.     std::sort(data, data + arraySize); 
  15.  
  16.     // 測(cè)試部分 
  17.     clock_t start = clock(); 
  18.     long long sum = 0; 
  19.  
  20.     for (unsigned i = 0; i < 100000; ++i) 
  21.     { 
  22.         // 主要計(jì)算部分,選一半元素參與計(jì)算 
  23.         for (unsigned c = 0; c < arraySize; ++c) 
  24.         { 
  25.             if (data[c] >= 128) 
  26.                 sum += data[c]; 
  27.         } 
  28.     } 
  29.  
  30.     double elapsedTime = static_cast<double>(clock() - start) / CLOCKS_PER_SEC; 
  31.  
  32.     std::cout << elapsedTime << std::endl; 
  33.     std::cout << "sum = " << sum << std::endl; 
  34.  

編譯并運(yùn)行:

  1. g++ branch_prediction.cpp 
  2. ./a.out  

在我的macbook air上運(yùn)行結(jié)果:

  1. # 1. 取消std::sort(data, data + arraySize);的注釋,即先排序后計(jì)算 
  2. 10.218 
  3. sum = 312426300000 
  4.  
  5. # 2. 注釋掉std::sort(data, data + arraySize);即不排序,直接計(jì)算 
  6. 29.6809 
  7. sum = 312426300000  

由此可見,先排序后計(jì)算,運(yùn)行效率有進(jìn)3倍的提高。

為保證結(jié)論的可靠性, 我們?cè)儆胘ava來(lái)測(cè)一遍:

  1. import java.util.Arrays; 
  2. import java.util.Random; 
  3.  
  4. public class Main 
  5.     public static void main(String[] args) 
  6.     { 
  7.         // Generate data 
  8.         int arraySize = 32768; 
  9.         int data[] = new int[arraySize]; 
  10.  
  11.         Random rnd = new Random(0); 
  12.         for (int c = 0; c < arraySize; ++c) 
  13.             data[c] = rnd.nextInt() % 256; 
  14.  
  15.         // !!! With this, the next loop runs faster 
  16.         Arrays.sort(data); 
  17.  
  18.         // Test 
  19.         long start = System.nanoTime(); 
  20.         long sum = 0; 
  21.  
  22.         for (int i = 0; i < 100000; ++i) 
  23.         { 
  24.             // Primary loop 
  25.             for (int c = 0; c < arraySize; ++c) 
  26.             { 
  27.                 if (data[c] >= 128) 
  28.                     sum += data[c]; 
  29.             } 
  30.         } 
  31.  
  32.         System.out.println((System.nanoTime() - start) / 1000000000.0); 
  33.         System.out.println("sum = " + sum); 
  34.     } 
  35.  

在intellij idea中運(yùn)行結(jié)果:

  1. # 1. 先排序后計(jì)算 
  2. 5.549553 
  3. sum = 155184200000 
  4. # 2. 不排序直接結(jié)算 
  5. 15.527867 
  6. sum = 155184200000  

也有三倍左右的差距。且java版要比c++版整體快近乎1倍?這應(yīng)該是編譯時(shí)用了默認(rèn)選項(xiàng),gcc優(yōu)化不夠的原因,后續(xù)再調(diào)查這個(gè)問題。

問題的提出

以上代碼在數(shù)組填充時(shí)已經(jīng)加入了分區(qū)函數(shù),充分保證填充值的隨機(jī)性,計(jì)算時(shí)也是按一半的元素來(lái)求和,所以不存在特例情況。而且,計(jì)算也完全不涉及到數(shù)據(jù)的有序性,即數(shù)組是否有序理論上對(duì)計(jì)算不會(huì)產(chǎn)生任何作用。在這樣的前提下,為什么排序后的數(shù)組要比未排序數(shù)組運(yùn)行快3倍以上?

分析

想象一個(gè)鐵路分叉道口。

[[171601]]

 為了論證此問題,讓我們回到19世紀(jì),那個(gè)遠(yuǎn)距離無(wú)線通信還未普及的年代。你是鐵路交叉口的扳道工。當(dāng)聽到火車快來(lái)了的時(shí)候,你無(wú)法猜測(cè)它應(yīng)該朝哪個(gè)方向走。于是你叫停了火車,上前去問火車司機(jī)該朝哪個(gè)方向走,以便你能正確地切換鐵軌。

要知道,火車是非常龐大的,切急速行駛時(shí)有巨大的慣性。為了完成上述停車-問詢-切軌的一系列動(dòng)作,火車需耗費(fèi)大量時(shí)間減速,停車,重新開啟。

既然上述過車非常耗時(shí),那是否有更好的方法?當(dāng)然有!當(dāng)火車即將行駛過來(lái)前,你可以猜測(cè)火車該朝哪個(gè)方向走。

  • 如果猜對(duì)了,它直接通過,繼續(xù)前行。
  • 如果猜錯(cuò)了,車頭將停止,倒回去,你將鐵軌扳至反方向,火車重新啟動(dòng),駛過道口。

如果你不幸每次都猜錯(cuò)了,那么火車將耗費(fèi)大量時(shí)間停車-倒回-重啟。如果你很幸運(yùn),每次都猜對(duì)了呢?火車將從不停車,持續(xù)前行!

上述比喻可應(yīng)用于處理器級(jí)別的分支跳轉(zhuǎn)指令里:

原程序:

  1. if (data[c] >= 128) 
  2.     sum += data[c];    

匯編碼:

  1. cmp edx, 128 
  2. jl SHORT $LN3@main 
  3. add rbx, rdx 
  4. $LN3@main:  

讓我們回到文章開頭的問題?,F(xiàn)在假設(shè)你是處理器,當(dāng)看到上述分支時(shí),當(dāng)你并不能決定該如何往下走,該如何做?只能暫停運(yùn)行,等待之前的指令運(yùn)行結(jié)束。然后才能繼續(xù)沿著正確地路徑往下走。

要知道,現(xiàn)代編譯器是非常復(fù)雜的,運(yùn)行時(shí)有著非常長(zhǎng)的pipelines, 減速和熱啟動(dòng)將耗費(fèi)巨量的時(shí)間。

那么,有沒有好的辦法可以節(jié)省這些狀態(tài)切換的時(shí)間呢?你可以猜測(cè)分支的下一步走向!

如果猜錯(cuò)了,處理器要flush掉pipelines, 回滾到之前的分支,然后重新熱啟動(dòng),選擇另一條路徑。

如果猜對(duì)了,處理器不需要暫停,繼續(xù)往下執(zhí)行。

如果每次都猜錯(cuò)了,處理器將耗費(fèi)大量時(shí)間在停止-回滾-熱啟動(dòng)這一周期性過程里。如果僥幸每次都猜對(duì)了,那么處理器將從不暫停,一直運(yùn)行至結(jié)束。

上述過程就是分支預(yù)測(cè)(branch prediction)。雖然在現(xiàn)實(shí)的道口鐵軌切換中,可以通過一個(gè)小旗子作為信號(hào)來(lái)判斷火車的走向,但是處理器卻無(wú)法像火車那樣去預(yù)知分支的走向--除非最后一次指令運(yùn)行完畢。

那么處理器該采用怎樣的策略來(lái)用最小的次數(shù)來(lái)盡量猜對(duì)指令分支的下一步走向呢?答案就是分析歷史運(yùn)行記錄: 如果火車過去90%的時(shí)間都是走左邊的鐵軌,本次軌道切換,你就可以猜測(cè)方向?yàn)樽螅粗?,則為右。如果在某個(gè)方向上走過了3次,接下來(lái)你也可以猜測(cè)火車將繼續(xù)在這個(gè)方向上運(yùn)行...

換句話說,你試圖通過歷史記錄,識(shí)別出一種隱含的模式并嘗試在后續(xù)鐵道切換的抉擇中繼續(xù)應(yīng)用它。這和處理器的分支預(yù)測(cè)原理或多或少有點(diǎn)相似。

大多數(shù)應(yīng)用都具有狀態(tài)良好的(well-behaved)分支,所以現(xiàn)代化的分支預(yù)測(cè)器一般具有超過90%的命中率。但是面對(duì)無(wú)法預(yù)測(cè)的分支,且沒有識(shí)別出可應(yīng)用的的模式時(shí),分支預(yù)測(cè)器就無(wú)用武之地了。

關(guān)于分支預(yù)測(cè)期,可參考維基百科相關(guān)詞條"Branch predictor" article on Wikipedia..

文首導(dǎo)致非排序數(shù)組相加耗時(shí)顯著增加的罪魁禍?zhǔn)妆闶莍f邏輯:

  1. if (data[c] >= 128) 
  2.     sum += data[c];  

注意到data數(shù)組里的元素是按照0-255的值被均勻存儲(chǔ)的(類似均勻的分桶)。數(shù)組data有序時(shí),前面一半元素的迭代將不會(huì)進(jìn)入if-statement, 超過一半時(shí),元素迭代將全部進(jìn)入if-statement.

這樣的持續(xù)朝同一個(gè)方向切換的迭代對(duì)分支預(yù)測(cè)器來(lái)說是非常友好的,前半部分元素迭代完之后,后續(xù)迭代分支預(yù)測(cè)器對(duì)分支方向的切換預(yù)測(cè)將全部正確。

簡(jiǎn)單地分析一下:有序數(shù)組的分支預(yù)測(cè)流程:

  1. T = 分支命中 
  2. N = 分支沒有命中 
  3.  
  4. data[] = 0, 1, 2, 3, 4, ... 126, 127, 128, 129, 130, ... 250, 251, 252, ... 
  5. branch = N  N  N  N  N  ...   N    N    T    T    T  ...   T    T    T  ... 
  6.  
  7.        = NNNNNNNNNNNN ... NNNNNNNTTTTTTTTT ... TTTTTTTTTT  (非常容易預(yù)測(cè))  

無(wú)序數(shù)組的分支預(yù)測(cè)流程:

  1. data[] = 226, 185, 125, 158, 198, 144, 217, 79, 202, 118,  14, 150, 177, 182, 133, ... 
  2. branch =   T,   T,   N,   T,   T,   T,   T,  N,   T,   N,   N,   T,   T,   T,   N  ... 
  3.  
  4.        = TTNTTTTNTNNTTTN ...   (完全隨機(jī)--無(wú)法預(yù)測(cè))  

在本例中,由于data數(shù)組元素填充的特殊性,決定了分支預(yù)測(cè)器在未排序數(shù)組迭代過程中將有50%的錯(cuò)誤命中率,因而執(zhí)行完整個(gè)sum操作將會(huì)耗時(shí)更多。

優(yōu)化

利用位運(yùn)算取消分支跳轉(zhuǎn)?;局R(shí):

  1. |x| >> 31 = 0 # 非負(fù)數(shù)右移31為一定為0 
  2. ~(|x| >> 31) = -1 # 0取反為-1 
  3.  
  4. -|x| >> 31 = -1 # 負(fù)數(shù)右移31為一定為0xffff = -1 
  5. ~(-|x| >> 31) = 0 # -1取反為0 
  6.  
  7. -1 = 0xffff 
  8. -1 & x = x # 以-1為mask和任何數(shù)求與,值不變  

故分支判斷可優(yōu)化為:

  1. int t = (data[c] - 128) >> 31; # statement 1 
  2. sum += ~t & data[c]; # statement 2  

分析:

  1. data[c] < 128, 則statement 1值為: 0xffff = -1, statement 2等號(hào)右側(cè)值為: 0 & data[c] == 0;
  2. data[c] >= 128, 則statement 1值為: 0, statement 2等號(hào)右側(cè)值為: ~0 & data[c] == -1 & data[c] == 0xffff & data[c] == data[c];

故上述位運(yùn)算實(shí)現(xiàn)的sum邏輯完全等價(jià)于if-statement, 更多的位運(yùn)算hack操作請(qǐng)參見bithacks.

若想避免移位操作,可以使用如下方式:

  1. int t=-((data[c]>=128)); # generate the mask 
  2. sum += ~t & data[c]; # bitwise AND  

結(jié)論

  • 使用分支預(yù)測(cè): 是否排序嚴(yán)重影響performance
  • 使用bithack: 是否排序?qū)erformance無(wú)顯著影響

這個(gè)例子告訴給我們啟示: 在大規(guī)模循環(huán)邏輯中要盡量避免數(shù)據(jù)強(qiáng)依賴的分支(data-dependent branching).

補(bǔ)充知識(shí)

Pipeline

先簡(jiǎn)單說明一下CPU的instruction pipeline(指令流水線),以下簡(jiǎn)稱pipeline。 Pipieline假設(shè)程序運(yùn)行時(shí)有一連串指令要被運(yùn)行,將程序運(yùn)行劃分成幾個(gè)階段,按照一定的順序并行處理之,這樣便能夠加速指令的通過速度。

絕大多數(shù)pipeline都由時(shí)鐘頻率(clock)控制,在數(shù)字電路中,clock控制邏輯門電路(logical cicuit)和觸發(fā)器(trigger), 當(dāng)受到時(shí)鐘頻率觸發(fā)時(shí),觸發(fā)器得到新的數(shù)值,并且邏輯門需要一段時(shí)間來(lái)解析出新的數(shù)值,而當(dāng)受到下一個(gè)時(shí)鐘頻率觸發(fā)時(shí)觸發(fā)器又得到新的數(shù)值,以此類推。

而借由邏輯門分散成很多小區(qū)塊,再讓觸發(fā)器鏈接這些小區(qū)塊組,使邏輯門輸出正確數(shù)值的時(shí)間延遲得以減少,這樣一來(lái)就可以減少指令運(yùn)行所需要的周期。 這對(duì)應(yīng)Pipeline中的各個(gè)stages。

一般的pipeline有四個(gè)執(zhí)行階段(execuate stage): 讀取指令(Fetch) -> 指令解碼(Decode) -> 運(yùn)行指令(Execute) -> 寫回運(yùn)行結(jié)果(Write-back).

分支預(yù)測(cè)器

分支預(yù)測(cè)器是一種數(shù)字電路,在分支指令執(zhí)行前,猜測(cè)哪一個(gè)分支會(huì)被執(zhí)行,能顯著提高pipelines的性能。

條件分支通常有兩路后續(xù)執(zhí)行分支,not token時(shí),跳過接下來(lái)的JMP指令,繼續(xù)執(zhí)行, token時(shí),執(zhí)行JMP指令,跳轉(zhuǎn)到另一塊程序內(nèi)存去執(zhí)行。

為了說明這個(gè)問題,我們先考慮如下問題。

沒有分支預(yù)測(cè)器會(huì)怎樣?

加入沒有分支預(yù)測(cè)器,處理器會(huì)等待分支指令通過了pipeline的執(zhí)行階段(execuate stage)才能把下一條指令送入pipeline的fetch stage。

這會(huì)造成流水線停頓(stalled)或流水線冒泡(bubbling)或流水線打嗝(hiccup),即在流水線中生成一個(gè)沒有實(shí)效的氣泡, 如下圖所示:

 

圖中一個(gè)氣泡在編號(hào)為3的始終頻率中產(chǎn)生,指令運(yùn)行被延遲。

Stream hiccup現(xiàn)象在早期的RISC體系結(jié)構(gòu)處理器中常見。

有分支預(yù)測(cè)期的pipeline

我們來(lái)看分支預(yù)測(cè)器在條件分支跳轉(zhuǎn)中的應(yīng)用。條件分支通常有兩路后續(xù)執(zhí)行分支,not token時(shí),跳過接下來(lái)的JMP指令,繼續(xù)執(zhí)行, token時(shí),執(zhí)行JMP指令,跳轉(zhuǎn)到另一塊程序內(nèi)存去執(zhí)行。

加入分支預(yù)測(cè)器后,為避免pipeline停頓(stream stalled),其會(huì)猜測(cè)兩路分支哪一路最有可能執(zhí)行,然后投機(jī)執(zhí)行,如果猜錯(cuò),則流水線中投機(jī)執(zhí)行中間結(jié)果全部拋棄,重新獲取正確分支路線上的指令執(zhí)行。可見,錯(cuò)誤的預(yù)測(cè)會(huì)導(dǎo)致程序執(zhí)行的延遲。

由前面可知,Pipeline執(zhí)行主要涉及Fetch, Decode, Execute, Write-back幾個(gè)stages, 分支預(yù)測(cè)失敗會(huì)浪費(fèi)Write-back之前的流水線級(jí)數(shù)?,F(xiàn)代CPU流水線級(jí)數(shù)非常長(zhǎng),分支預(yù)測(cè)失敗可能會(huì)損失20個(gè)左右的時(shí)鐘周期,因此對(duì)于復(fù)雜的流水線,好的分支預(yù)測(cè)器非常重要。

常見的分支預(yù)測(cè)器

  • 靜態(tài)分支預(yù)測(cè)器

靜態(tài)分支預(yù)測(cè)器有兩個(gè)解碼周期,分別評(píng)價(jià)分支,解碼。即在分支指令執(zhí)行前共經(jīng)歷三個(gè)時(shí)鐘周期。詳情見圖:

 

  • 雙模態(tài)預(yù)測(cè)器(bimodal predictor)

也叫飽和計(jì)數(shù)器,是一個(gè)四狀態(tài)狀態(tài)機(jī). 四個(gè)狀態(tài)對(duì)應(yīng)兩個(gè)選擇: token, not token, 每個(gè)選擇有兩個(gè)狀態(tài)區(qū)分強(qiáng)弱:strongly,weakly。分別是Strongly not taken,Weakly not taken, Weakly taken, Strongly taken。

狀態(tài)機(jī)工作原理圖如下:

 

 

圖左邊兩個(gè)狀態(tài)為不采納(not token),右邊兩個(gè)為采納(token)。由not token到token中間有兩個(gè)漸變狀態(tài)。由紅色到綠色翻轉(zhuǎn)需要連續(xù)兩次分支選擇。

技術(shù)實(shí)現(xiàn)上可用兩個(gè)二進(jìn)制位來(lái)表示,00, 01, 10, 11分別對(duì)應(yīng)strongly not token, weakly not token, weakly token, strongly token。 一個(gè)判斷兩個(gè)分支預(yù)測(cè)規(guī)則是否改變的簡(jiǎn)單方法便是判斷這個(gè)二級(jí)制狀態(tài)高位是否跳變。高位從0變?yōu)?, 強(qiáng)狀態(tài)發(fā)生翻轉(zhuǎn),則下一個(gè)分支指令預(yù)測(cè)從not token變?yōu)閠oken,反之亦然。

據(jù)評(píng)測(cè),雙模態(tài)預(yù)測(cè)器的正確率可達(dá)到93.5%。預(yù)測(cè)期一般在分支指令解碼前起作用。

其它常見分支預(yù)測(cè)器如兩級(jí)自適應(yīng)預(yù)測(cè)器,局部/全局分支預(yù)測(cè)器,融合分支預(yù)測(cè)器,Agree預(yù)測(cè)期,神經(jīng)分支預(yù)測(cè)器等。

責(zé)任編輯:龐桂玉 來(lái)源: segmentfault
相關(guān)推薦

2022-06-22 08:02:11

CPU操作系統(tǒng)Java

2023-11-05 12:05:35

JVM內(nèi)存

2019-05-06 14:36:48

CPULinux寄存器

2016-12-08 15:36:59

HashMap數(shù)據(jù)結(jié)構(gòu)hash函數(shù)

2010-06-01 15:25:27

JavaCLASSPATH

2020-07-21 08:26:08

SpringSecurity過濾器

2025-03-06 08:20:00

RAG嵌入模型

2017-12-18 16:33:55

多線程對(duì)象模型

2012-11-22 10:11:16

LispLisp教程

2015-03-24 13:28:52

Java Java Strin內(nèi)存模型

2023-10-19 11:12:15

Netty代碼

2021-02-17 11:25:33

前端JavaScriptthis

2009-09-25 09:14:35

Hibernate日志

2013-09-22 14:57:19

AtWood

2020-09-23 10:00:26

Redis數(shù)據(jù)庫(kù)命令

2019-06-25 10:32:19

UDP編程通信

2017-01-10 08:48:21

2025-05-06 00:43:00

MySQL日志文件MIXED 3

2017-08-15 13:05:58

Serverless架構(gòu)開發(fā)運(yùn)維

2025-06-05 05:51:33

點(diǎn)贊
收藏

51CTO技術(shù)棧公眾號(hào)