大家好，我的朋友們。
今天來聊一個硬核的話題，本文大約需要15min，認真讀完一定會有收獲，走起！
通過本文你将了解以下内容：
-
- stackoverflow的有趣問題
- CPU流水線機制和内部資料流轉
- CPU流水線的三大冒險
- CPU分支預測大揭秘
有趣的問題
前幾天摸魚的時候，我在stackoverflow發現一個有趣的問題：
https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array
提問者用C++寫了一個數組求和的函數，把數組排序後求和和無序求和的計算性能竟然相差6倍，十分詭異。
我們來看下代碼：
#include <algorithm>
#include <ctime>
#include <iostream>
int main()
{
// Generate data
const unsigned arraySize = 32768;
int data[arraySize];
for (unsigned c = 0; c < arraySize; ++c)
data[c] = std::rand() % 256;
// !!! With this, the next loop runs faster.
std::sort(data, data + arraySize);
// Test
clock_t start = clock();
long long sum = 0;
for (unsigned i = 0; i < 100000; ++i)
{
for (unsigned c = 0; c < arraySize; ++c)
{ // Primary loop
if (data[c] >= 128)
sum += data[c];
}
}
double elapsedTime = static_cast<double>(clock()-start) / CLOCKS_PER_SEC;
std::cout << elapsedTime << '\n';
std::cout << "sum = " << sum << '\n';
代碼比較簡單，先搞了個大數組，然後數組的元素是256以内取模，所有元素都落在0-256之内，接着在循環裡面使用條件判斷求和。
提問者為了防止有單次誤差，做了10w次循環，發現運作時間差别很大：
-
- 無序求和 累計耗時 11.54秒
- 排序求和 累計耗時 1.93秒
對呀，按理說加了個std:sort()耗時會增加，但是性能還是這麼優秀，真是奇怪呀!
提問者又用Java搞了一遍，現象和C++不能說一模一樣，但幾乎也是分毫不差。
究竟是咋回事呢？讀到這裡的盆友，一定是個技術人兒，來吧，讓我們一探究竟。
洗車房的故事
前陣子我開着自己的捷達去洗車，車還挺多，排着隊一個個搞。
我發現洗車流程是這樣的：噴水、打泡沫、刷洗、擦拭、吹幹。
車輛在外面排隊，依次是奧迪A6L、寶馬X5、奔馳C200L、捷達vs5。
就這樣一個工序完成後，車輛向下一個工序移動，目前工序又補進來一輛車。
我原來以為是一輛車進去 完成所有工序再出來，下一輛進行完成全部工序，依次類推，沒想到洗車房還是流水線作業。
為啥是流水線呢？提高洗車數量，也就是吞吐量，機關時間賺取更多噻！
如果是完成所有工序再搞下一輛，這樣某個時刻5個工序隻有1個在做，其他4共工序都是等待狀态，勞工們都開始摸魚了，錢也沒賺到，客戶等待時間還長。
生活中的智慧還真是不少呀，看到這裡不禁要問，這和前面的數組求和有啥關系呢？别急，還真有關系。
CPU的内部的那些事兒
我們先從一個宏觀角度去看下CPU内部的結構：
從兩個圖上，我們可以得到如下資訊：
-
- CPU内部的核心元件有各類寄存器、控制單元CU、邏輯運算單元ALU、高速緩存
- CPU和外部互動的交通大動脈就是三種總線：位址總線、資料總線、控制總線
- I/O裝置、RAM通過三大總線和CPU實作功能互動
程式經過編譯器處理成機器碼來執行，程式會被翻譯成一條條的指令，為了簡化問題，我們選擇5級流水線的CPU來說明問題：
-
-
取指令IF
取指令（Instruction Fetch，IF）階段是将一條指令從主存中取到指令寄存器的過程。
-
指令譯碼ID
取出指令後，計算機立即進入指令譯碼（Instruction Decode，ID）階段。
在指令譯碼階段，指令譯碼器按照預定的指令格式，對取回的指令進行拆分和解釋，識别區分出不同的指令類别以及各種擷取操作數的方法。
-
指令執行EX
在取指令和指令譯碼階段之後，接着進入執行指令（Execute，EX）階段。
此階段的任務是完成指令所規定的各種操作，具體實作指令的功能。為此，CPU的不同部分被連接配接起來，以執行所需的操作。
-
訪存取數階段MEM
根據指令需要，有可能要通路主存讀取操作數，這樣就進入了訪存取數（Memory，MEM）階段，此階段的任務是：根據指令位址碼，得到操作數在主存中的位址，并從主存中讀取該操作數用于運算。
-
結果回寫WB
作為最後一個階段，結果寫回（Writeback，WB）階段把執行指令階段的運作結果資料寫回到某種存儲形式。
上面的IF、ID、EX、MEM、WB就是CPU的5級流水線，這個流程和洗車房的流水線很相似：
沒錯，CPU内部處理一條條指令的過程和洗車房就非常相似，我們繼續深挖！
小結：
CPU流水線技術是一種将指令分解為多步，并讓不同指令的各步操作重疊，進而實作幾條指令并行處理，以加速程式運作過程的技術。
指令的每步有各自獨立的電路來處理，每完成一步，就進到下一步，而前一步則處理後續指令，屬于CPU硬體電路層面的并發。
CPU流水線吞吐量和延遲
我們來看下引入流水線之後吞吐量的變化：
未使用流水線時各個執行部分組成了組合邏輯，執行完成後寫寄存器，整個時間包括：組合邏輯時間300ps和寫寄存器20ps，這就類似于洗車房每次5個工序一起搞定一輛車的情況。
該模式下的吞吐量是1/(300+20)ps = 3.125GIPS(每秒千兆條指令)
使用流水線時，組合邏輯被拆分為3個部分，但是每個部分都需要寫寄存器，這樣就增加了整個流程的時間從320ps提高到了360ps。
拆分多出兩個邏輯和兩個寄存器寫，額外多出40ps。
此時的吞吐量是1/(100+20)ps = 8.333GIPS(每秒千兆條指令)，整個吞吐量是未使用流水線的2.67倍。
從上面的對比來看，增加了一些硬體和延遲帶來了吞吐量的提升，但是一味增加硬體不是萬金油，單純的寫寄存器延遲就很明顯。
流水線的級數也被稱為深度，目前intel的酷睿i7采用了16級深度的流水線，在一定範圍内提高流水線深度可以提高CPU的吞吐量，但是也為硬體設計帶來很大的挑戰，甚至降低吞吐量。
CPU流水線冒險
通過流水線設計來提升 CPU 的吞吐率，是一把雙刃劍，在提高吞吐量的同時我們也在冒險。
所謂的冒險就是一帆風順路上的磕磕絆絆，坑坑窪窪，流水線也并非一帆風順的。
提到流水線設計需要解決的三大冒險：結構冒險（Structural Hazard）、資料冒險（Data Hazard）以及控制冒險（Control Hazard）。
結構冒險
結構冒險本質上是一種硬體沖突，我們以5級流水線為例來說，指令讀取IF階段和取數操作MEM，都需要進行記憶體資料的讀取，然而記憶體隻有一個位址譯碼器，隻能在一個時鐘周期裡面讀取一條資料。
換句話說就像洗車流水線的噴水和刷洗都要用到水管，但是隻有一根水管，這樣就存在沖突，導緻隻能滿足一個噴水或者刷洗。
對于MEM階段和IF階段的沖突，一個解決方案就是把記憶體分成兩部分：存放指令的記憶體和存放資料的記憶體，讓它們有各自的位址譯碼器，進而通過增加硬體資源來解決沖突。
沒錯，這種将指令和資料分開存儲就是著名的哈佛結構Harvard Architecture，指令和資料放在一起的就是馮諾依曼結構/普林斯頓結構Princeton Architecture。
這兩種結構有各自優缺點，現代CPU借鑒了兩種架構采用一種混合結構，并且引入高速緩存，來降低CPU和記憶體的速度不比對問題，如圖：
這種混合結構就很好地解決了流水線結構冒險問題，隻是硬體結構更複雜了，屬于硬體層面的優化。
資料冒險
資料冒險是指令之間存在資料依賴關系，就像這段代碼：
int a = 10;
int b = a + 10;//語句2
int c = b + a;//語句3
語句3的計算依賴于b的值，在語句2對b進行了計算，也就是語句3依賴于語句2，但是每一個語句都會被翻譯成很多的指令，也就是其中兩個指令存在依賴關系。
比如說指令3-3需要等待指令2-2完成WB階段才可以進行EX階段，如果不等待得到的結果就是錯誤的。
一種解決方案就是引入NOP操作，這個時鐘周期啥也不做，等到依賴的資料完成再繼續，這種通過流水線停頓解決資料冒險的方案稱為流水線冒泡(Pipeline Bubble)。
流水線冒泡雖然簡單，但是效率卻下降了，經過大量的實踐發現，我們完全可以在第一條指令的結果資料傳輸給到下一條指令的 ALU，下一條指令不需要再插入NOP 階段，就可以繼續正常進行了。
這種将結果直接傳輸的技術稱為操作數前推/轉發Operand Forwarding，它可以和流水線冒泡NOP一起使用，因為單純的操作數前推也無法完全避免使用NOP。
小結
ADD指令不需要等待WB完成再執行EX，而是LOAD指令通過操作數轉發直接傳給ADD指令，減少了一個NOP操作，隻需要1個NOP操作即可，提升了流水線效率。
控制冒險
在流水線中，多個指令是并行執行的，在指令1執行的時候，後續的指令2和指令3可能已經完成了IF和ID兩個階段等待被執行，此時如果指令1一下子跳到了其他地方，那麼指令2和指令3的IF和ID就是無用功了。
遇到這種指令轉移情況，處理器需要先排空指令2和指令3對應的流水線，然後跳轉到指令1的新的目标位置進入新的流水線，這部分稱為轉移開銷，這也是産生性能損失的重要原因。
轉移指令本身和流水線的模式是沖突的，因為轉移指令會改變指令的流向， 而流水線則希望能夠依次地取回指令，将流水線填滿的，但是轉移指令在實際程式中非常普遍，這也是CPU流水線必須要面對的問題。
轉移指令可以分為無條件轉移和條件轉移。
無條件轉移是确定發生的，并且跳轉位址在取指階段就能得到，我們在 CPU 裡面設計對應的旁路電路，把計算結果更早地回報到流水線中，這種屬于硬體方案稱為縮短分支延遲。
但是，對于條件轉移我們在IF階段并不能獲得跳轉位置，隻能等EX階段才知道，這就引出了分支預測。
分支預測換句話說就是：流水線的上一個階段還沒有完成，但是下一個指令是啥要依賴于這個結果，為了效率，流水線不能停頓住，必須要做個選擇，向左走還是 向右走，選擇出下一條要執行的指令，哪怕錯了，也比等待好，萬一猜對了呢！
CPU分支預測
分支預測有：靜态分支預測和動态分支預測。
靜态分支預測就是每次都選擇一個結果，就像抛硬币每次都猜正面，對于CPU流水線來說都猜指令不跳轉，也就有50%的正确率了，這種預測方式簡單但是不夠高效。
動态分支預測會根據之前的選擇情況和正确率來預測目前的情況，做出判斷是順序分支還是跳轉分支，是以仍然會有成功和失敗兩種情況。
比如分支預測選擇了跳轉分支之後：
-
- 預測成功時，盡快找到分支目标指令位址，避免控制相關造成流水線停頓。
- 預測錯誤時，要廢棄已經預取和分析的指令，恢複現場，并從另一條分支路徑重新取指令。
最簡單的動态分支預測器有1bit和2bit，其中2bit表示有2位标記，分别記錄上一次預測狀态和上次預測結果，講到這裡很多文章就一帶而過，給了一個狀态機遷移圖，就草草收尾了：
說實話，看到這圖，我仿佛懂了，又仿佛沒懂，于是我決定好好研究一下這個2bit分支預測器的一些原理，我們繼續：
-
-
兩種決策
not taken代表選擇順序分支
taken代表跳轉分支
-
四種狀态
00 代表strongly not taken 強順序分支
01 代表weakly not taken 弱順序分支
10 代表weakly taken 弱跳轉分支
11 代表strongly taken 強跳轉分支
我們繼續看2bit動态分支預測是如果進行狀态機遷移的：
-
-
目前狀态處于00 強順序分支時
必然預測下一次也是順序分支，此時會有兩種結果，預測成功了，下一次狀态仍然是00，預測失敗了，最終程式選擇了跳轉分支，下一次狀态變為01。
圖解|30張圖，帶你深入了解CPU流水線和分支預測的那些事兒 -
目前狀态處于01 弱順序分支時
必然預測下一次也是順序分支，此時會有兩種結果，預測成功了，下一次狀态調整為00，預測失敗了，最終程式選擇了跳轉分支，下一次狀态變為10。
圖解|30張圖，帶你深入了解CPU流水線和分支預測的那些事兒 -
目前狀态處于10 弱跳轉分支時
必然預測下一次也是跳轉分支，此時會有兩種結果，預測成功了，下一次狀态調整為11，預測失敗了，最終程式選擇了順序分支，下一次狀态變為01。
圖解|30張圖，帶你深入了解CPU流水線和分支預測的那些事兒 -
目前狀态處于11 強跳轉分支時
必然預測下一次也是跳轉分支，此時會有兩種結果，預測成功了，狀态不變仍然是11，預測失敗了，最終程式選擇了順序分支，下一次狀态變為10。
圖解|30張圖，帶你深入了解CPU流水線和分支預測的那些事兒
堅持看到這裡，說明你真是個愛學習的人兒啊，我們來畫一張完整的遷移圖：
從這張圖可以看到從順序分支改變為跳轉分支，需要連續兩次預測失敗，同樣的跳轉分支變為順序分支，也需要連續兩次預測失敗：
标記分支狀态以及分支曆史的一段記憶體被稱為BTB，這段記憶體隻存儲了分支指令位址，以及預測的目标位址以及預測的位，這一塊内容比較複雜，我們在此不展開了。
經過前面的分析可以看到動态分支預測器具有一定的容錯性，并且波動性較小，隻有連續兩次預測失敗才會轉變選擇結果，整體正确率提升明顯。
從一些文章的資料顯示，大部分情況下2bit預測器準确率可以達到95%以上：
回顧問題
經過前面的一番分析，我們回到stackoverflow那個數組排序和無序耗時的問題上來，這個問題有兩個關鍵因素：
-
- 數組元素是完全随機的，本次結果和上次結果是獨立分布的
- 大量循環結構和條件判斷的存在
沒錯，随機+循環+條件就徹底命中了CPU流水線的軟肋。
- 數組排序之後的分支預測
- 數組未排序的分支預測
數組排序後，動态分支預測會結合之前的結果做出判斷準确率非常高，未排序時完全随機和靜态分支預測差不多了，是以準确率一般。
分支預測失敗就意味着流水線排空，廢棄已經進行IF和ID的指令，然後再選擇正确的指令，整個過程在目前CPU來說要來浪費10-20個時鐘周期，這樣耗時就上來了。
總結
本文先從stackoverflow上一個關于随機數組排序和未排序求和的問題來切入。
進一步采用最簡單的5級CPU流水線講述基本原理和流水線中存在的三者冒險，及其各自的解決方法，特别是控制冒險。
進一步闡述了控制冒險中的分支預測技術，并展開了對雙模動态分支預測器基本原理的剖析。
最後結合stackoverflow的問題，揭露流水線分支預測和随機數組排序/未排序在循環結構下的不同決策結果帶來的巨大耗時影響。