大家好，我的朋友們。

今天來聊一個(gè)硬核的話題，本文大約需要15min，認(rèn)真讀完一定會(huì)有收獲，走起！

通過本文你將了解以下內(nèi)容：

• stackoverflow的有趣問題
• CPU流水線機(jī)制和內(nèi)部數(shù)據(jù)流轉(zhuǎn)
• CPU流水線的三大冒險(xiǎn)
• CPU分支預(yù)測(cè)大揭秘

有趣的問題

前幾天摸魚的時(shí)候，我在stackoverflow發(fā)現(xiàn)一個(gè)有趣的問題：

https://stackoverflow.com/questions/11227809/why-is-processing-a-sorted-array-faster-than-processing-an-unsorted-array

提問者用C 寫了一個(gè)數(shù)組求和的函數(shù)，把數(shù)組排序后求和和無序求和的計(jì)算性能竟然相差6倍，十分詭異。

我們來看下代碼：

#include
#include
#include

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(clock()-start) / CLOCKS_PER_SEC;

std::cout << elapsedTime << '\n';
std::cout << "sum = " << sum << '\n';
代碼比較簡(jiǎn)單，先搞了個(gè)大數(shù)組，然后數(shù)組的元素是256以內(nèi)取模，所有元素都落在0-256之內(nèi)，接著在循環(huán)里面使用條件判斷求和。

提問者為了防止有單次誤差，做了10w次循環(huán)，發(fā)現(xiàn)運(yùn)行時(shí)間差別很大：

• 無序求和 累計(jì)耗時(shí) 11.54秒
• 排序求和 累計(jì)耗時(shí) 1.93秒

對(duì)呀，按理說加了個(gè)std:sort()耗時(shí)會(huì)增加，但是性能還是這么優(yōu)秀，真是奇怪呀!

提問者又用Java搞了一遍，現(xiàn)象和C 不能說一模一樣，但幾乎也是分毫不差。

究竟是咋回事呢？讀到這里的盆友，一定是個(gè)技術(shù)人兒，來吧，讓我們一探究竟。

洗車房的故事

前陣子我開著自己的捷達(dá)去洗車，車還挺多，排著隊(duì)一個(gè)個(gè)搞。

我發(fā)現(xiàn)洗車流程是這樣的：噴水、打泡沫、刷洗、擦拭、吹干。

車輛在外面排隊(duì)，依次是奧迪A6L、寶馬X5、奔馳C200L、捷達(dá)vs5。

就這樣一個(gè)工序完成后，車輛向下一個(gè)工序移動(dòng)，當(dāng)前工序又補(bǔ)進(jìn)來一輛車。

我原來以為是一輛車進(jìn)去 完成所有工序再出來，下一輛進(jìn)行完成全部工序，依次類推，沒想到洗車房還是流水線作業(yè)。

為啥是流水線呢？提高洗車數(shù)量，也就是吞吐量，單位時(shí)間賺取更多噻！

如果是完成所有工序再搞下一輛，這樣某個(gè)時(shí)刻5個(gè)工序只有1個(gè)在做，其他4共工序都是等待狀態(tài)，工人們都開始摸魚了，錢也沒賺到，客戶等待時(shí)間還長(zhǎng)。

生活中的智慧還真是不少呀，看到這里不禁要問，這和前面的數(shù)組求和有啥關(guān)系呢？別急，還真有關(guān)系。

CPU的內(nèi)部的那些事兒

我們先從一個(gè)宏觀角度去看下CPU內(nèi)部的結(jié)構(gòu)：

從兩個(gè)圖上，我們可以得到如下信息：

• CPU內(nèi)部的核心組件有各類寄存器、控制單元CU、邏輯運(yùn)算單元ALU、高速緩存
• CPU和外部交互的交通大動(dòng)脈就是三種總線：地址總線、數(shù)據(jù)總線、控制總線
• I/O設(shè)備、RAM通過三大總線和CPU實(shí)現(xiàn)功能交互

程序經(jīng)過編譯器處理成機(jī)器碼來執(zhí)行，程序會(huì)被翻譯成一條條的指令，為了簡(jiǎn)化問題，我們選擇5級(jí)流水線的CPU來說明問題：

• 取指令I(lǐng)F
  取指令（Instruction Fetch，IF）階段是將一條指令從主存中取到指令寄存器的過程。

  
  

• 指令譯碼ID
  取出指令后，計(jì)算機(jī)立即進(jìn)入指令譯碼（Instruction Decode，ID）階段。
  在指令譯碼階段，指令譯碼器按照預(yù)定的指令格式，對(duì)取回的指令進(jìn)行拆分和解釋，識(shí)別區(qū)分出不同的指令類別以及各種獲取操作數(shù)的方法。

  
  

• 指令執(zhí)行EX
  在取指令和指令譯碼階段之后，接著進(jìn)入執(zhí)行指令（Execute，EX）階段。
  此階段的任務(wù)是完成指令所規(guī)定的各種操作，具體實(shí)現(xiàn)指令的功能。為此，CPU的不同部分被連接起來，以執(zhí)行所需的操作。

  
  

• 訪存取數(shù)階段MEM
  根據(jù)指令需要，有可能要訪問主存讀取操作數(shù)，這樣就進(jìn)入了訪存取數(shù)（Memory，MEM）階段，此階段的任務(wù)是：根據(jù)指令地址碼，得到操作數(shù)在主存中的地址，并從主存中讀取該操作數(shù)用于運(yùn)算。

  
  

• 結(jié)果回寫WB
  作為最后一個(gè)階段，結(jié)果寫回（Writeback，WB）階段把執(zhí)行指令階段的運(yùn)行結(jié)果數(shù)據(jù)寫回到某種存儲(chǔ)形式。

  
  

上面的IF、ID、EX、MEM、WB就是CPU的5級(jí)流水線，這個(gè)流程和洗車房的流水線很相似：

沒錯(cuò)，CPU內(nèi)部處理一條條指令的過程和洗車房就非常相似，我們繼續(xù)深挖！

小結(jié)：CPU流水線技術(shù)是一種將指令分解為多步，并讓不同指令的各步操作重疊，從而實(shí)現(xiàn)幾條指令并行處理，以加速程序運(yùn)行過程的技術(shù)。
指令的每步有各自獨(dú)立的電路來處理，每完成一步，就進(jìn)到下一步，而前一步則處理后續(xù)指令，屬于CPU硬件電路層面的并發(fā)。

CPU流水線吞吐量和延遲

我們來看下引入流水線之后吞吐量的變化：未使用流水線時(shí)各個(gè)執(zhí)行部分組成了組合邏輯，執(zhí)行完成后寫寄存器，整個(gè)時(shí)間包括：組合邏輯時(shí)間300ps和寫寄存器20ps，這就類似于洗車房每次5個(gè)工序一起搞定一輛車的情況。

該模式下的吞吐量是1/(300 20)ps = 3.125GIPS(每秒千兆條指令)

使用流水線時(shí)，組合邏輯被拆分為3個(gè)部分，但是每個(gè)部分都需要寫寄存器，這樣就增加了整個(gè)流程的時(shí)間從320ps提高到了360ps。

拆分多出兩個(gè)邏輯和兩個(gè)寄存器寫，額外多出40ps。

此時(shí)的吞吐量是1/(100 20)ps = 8.333GIPS(每秒千兆條指令)，整個(gè)吞吐量是未使用流水線的2.67倍。

從上面的對(duì)比來看，增加了一些硬件和延遲帶來了吞吐量的提升，但是一味增加硬件不是萬金油，單純的寫寄存器延遲就很明顯。

流水線的級(jí)數(shù)也被稱為深度，當(dāng)前intel的酷睿i7采用了16級(jí)深度的流水線，在一定范圍內(nèi)提高流水線深度可以提高CPU的吞吐量，但是也為硬件設(shè)計(jì)帶來很大的挑戰(zhàn)，甚至降低吞吐量。

CPU流水線冒險(xiǎn)

通過流水線設(shè)計(jì)來提升 CPU 的吞吐率，是一把雙刃劍，在提高吞吐量的同時(shí)我們也在冒險(xiǎn)。

所謂的冒險(xiǎn)就是一帆風(fēng)順路上的磕磕絆絆，坑坑洼洼，流水線也并非一帆風(fēng)順的。

提到流水線設(shè)計(jì)需要解決的三大冒險(xiǎn)：結(jié)構(gòu)冒險(xiǎn)（Structural Hazard）、數(shù)據(jù)冒險(xiǎn)（Data Hazard）以及控制冒險(xiǎn)（Control Hazard）。

結(jié)構(gòu)冒險(xiǎn)

結(jié)構(gòu)冒險(xiǎn)本質(zhì)上是一種硬件沖突，我們以5級(jí)流水線為例來說，指令讀取IF階段和取數(shù)操作MEM，都需要進(jìn)行內(nèi)存數(shù)據(jù)的讀取，然而內(nèi)存只有一個(gè)地址譯碼器，只能在一個(gè)時(shí)鐘周期里面讀取一條數(shù)據(jù)。

換句話說就像洗車流水線的噴水和刷洗都要用到水管，但是只有一根水管，這樣就存在沖突，導(dǎo)致只能滿足一個(gè)噴水或者刷洗。

對(duì)于MEM階段和IF階段的沖突，一個(gè)解決方案就是把內(nèi)存分成兩部分：存放指令的內(nèi)存和存放數(shù)據(jù)的內(nèi)存，讓它們有各自的地址譯碼器，從而通過增加硬件資源來解決沖突。

沒錯(cuò)，這種將指令和數(shù)據(jù)分開存儲(chǔ)就是著名的哈佛結(jié)構(gòu)Harvard Architecture，指令和數(shù)據(jù)放在一起的就是馮諾依曼結(jié)構(gòu)/普林斯頓結(jié)構(gòu)Princeton Architecture。

這兩種結(jié)構(gòu)有各自優(yōu)缺點(diǎn)，現(xiàn)代CPU借鑒了兩種架構(gòu)采用一種混合結(jié)構(gòu)，并且引入高速緩存，來降低CPU和內(nèi)存的速度不匹配問題，如圖：

這種混合結(jié)構(gòu)就很好地解決了流水線結(jié)構(gòu)冒險(xiǎn)問題，只是硬件結(jié)構(gòu)更復(fù)雜了，屬于硬件層面的優(yōu)化。

數(shù)據(jù)冒險(xiǎn)

數(shù)據(jù)冒險(xiǎn)是指令之間存在數(shù)據(jù)依賴關(guān)系，就像這段代碼：

int a = 10;
int b = a   10;//語句2
int c = b   a;//語句3
語句3的計(jì)算依賴于b的值，在語句2對(duì)b進(jìn)行了計(jì)算，也就是語句3依賴于語句2，但是每一個(gè)語句都會(huì)被翻譯成很多的指令，也就是其中兩個(gè)指令存在依賴關(guān)系。

比如說指令3-3需要等待指令2-2完成WB階段才可以進(jìn)行EX階段，如果不等待得到的結(jié)果就是錯(cuò)誤的。

一種解決方案就是引入NOP操作，這個(gè)時(shí)鐘周期啥也不做，等到依賴的數(shù)據(jù)完成再繼續(xù)，這種通過流水線停頓解決數(shù)據(jù)冒險(xiǎn)的方案稱為流水線冒泡(Pipeline Bubble)。

流水線冒泡雖然簡(jiǎn)單，但是效率卻下降了，經(jīng)過大量的實(shí)踐發(fā)現(xiàn)，我們完全可以在第一條指令的結(jié)果數(shù)據(jù)傳輸給到下一條指令的 ALU，下一條指令不需要再插入NOP 階段，就可以繼續(xù)正常進(jìn)行了。

這種將結(jié)果直接傳輸?shù)募夹g(shù)稱為操作數(shù)前推/轉(zhuǎn)發(fā)Operand Forwarding，它可以和流水線冒泡NOP一起使用，因?yàn)閱渭兊牟僮鲾?shù)前推也無法完全避免使用NOP。

小結(jié)：操作數(shù)前推，就是通過在硬件層面制造一條旁路，讓一條指令的計(jì)算結(jié)果，可以直接傳輸給下一條指令，而不再需要指令 1 寫回寄存器，指令 2 再讀取寄存器,這樣多此一舉的操作。

ADD指令不需要等待WB完成再執(zhí)行EX，而是LOAD指令通過操作數(shù)轉(zhuǎn)發(fā)直接傳給ADD指令，減少了一個(gè)NOP操作，只需要1個(gè)NOP操作即可，提升了流水線效率。

控制冒險(xiǎn)

在流水線中，多個(gè)指令是并行執(zhí)行的，在指令1執(zhí)行的時(shí)候，后續(xù)的指令2和指令3可能已經(jīng)完成了IF和ID兩個(gè)階段等待被執(zhí)行，此時(shí)如果指令1一下子跳到了其他地方，那么指令2和指令3的IF和ID就是無用功了。

遇到這種指令轉(zhuǎn)移情況，處理器需要先排空指令2和指令3對(duì)應(yīng)的流水線，然后跳轉(zhuǎn)到指令1的新的目標(biāo)位置進(jìn)入新的流水線，這部分稱為轉(zhuǎn)移開銷，這也是產(chǎn)生性能損失的重要原因。

轉(zhuǎn)移指令本身和流水線的模式是沖突的，因?yàn)檗D(zhuǎn)移指令會(huì)改變指令的流向， 而流水線則希望能夠依次地取回指令，將流水線填滿的，但是轉(zhuǎn)移指令在實(shí)際程序中非常普遍，這也是CPU流水線必須要面對(duì)的問題。

轉(zhuǎn)移指令可以分為無條件轉(zhuǎn)移和條件轉(zhuǎn)移。

無條件轉(zhuǎn)移是確定發(fā)生的，并且跳轉(zhuǎn)地址在取指階段就能得到，我們?cè)?CPU 里面設(shè)計(jì)對(duì)應(yīng)的旁路電路，把計(jì)算結(jié)果更早地反饋到流水線中，這種屬于硬件方案稱為縮短分支延遲。

但是，對(duì)于條件轉(zhuǎn)移我們?cè)贗F階段并不能獲得跳轉(zhuǎn)位置，只能等EX階段才知道，這就引出了分支預(yù)測(cè)。

分支預(yù)測(cè)換句話說就是：流水線的上一個(gè)階段還沒有完成，但是下一個(gè)指令是啥要依賴于這個(gè)結(jié)果，為了效率，流水線不能停頓住，必須要做個(gè)選擇，向左走還是 向右走，選擇出下一條要執(zhí)行的指令，哪怕錯(cuò)了，也比等待好，萬一猜對(duì)了呢！

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

分支預(yù)測(cè)有：靜態(tài)分支預(yù)測(cè)和動(dòng)態(tài)分支預(yù)測(cè)。

靜態(tài)分支預(yù)測(cè)就是每次都選擇一個(gè)結(jié)果，就像拋硬幣每次都猜正面，對(duì)于CPU流水線來說都猜指令不跳轉(zhuǎn)，也就有50%的正確率了，這種預(yù)測(cè)方式簡(jiǎn)單但是不夠高效。

動(dòng)態(tài)分支預(yù)測(cè)會(huì)根據(jù)之前的選擇情況和正確率來預(yù)測(cè)當(dāng)前的情況，做出判斷是順序分支還是跳轉(zhuǎn)分支，因此仍然會(huì)有成功和失敗兩種情況。

比如分支預(yù)測(cè)選擇了跳轉(zhuǎn)分支之后：

• 預(yù)測(cè)成功時(shí)，盡快找到分支目標(biāo)指令地址，避免控制相關(guān)造成流水線停頓。
• 預(yù)測(cè)錯(cuò)誤時(shí)，要作廢已經(jīng)預(yù)取和分析的指令，恢復(fù)現(xiàn)場(chǎng)，并從另一條分支路徑重新取指令。

最簡(jiǎn)單的動(dòng)態(tài)分支預(yù)測(cè)器有1bit和2bit，其中2bit表示有2位標(biāo)記，分別記錄上一次預(yù)測(cè)狀態(tài)和上次預(yù)測(cè)結(jié)果，講到這里很多文章就一帶而過，給了一個(gè)狀態(tài)機(jī)遷移圖，就草草收尾了：

說實(shí)話，看到這圖，我仿佛懂了，又仿佛沒懂，于是我決定好好研究一下這個(gè)2bit分支預(yù)測(cè)器的一些原理，我們繼續(xù)：

• 兩種決策
  not taken代表選擇順序分支
  taken代表跳轉(zhuǎn)分支
• 四種狀態(tài)
  00 代表strongly not taken 強(qiáng)順序分支
  01 代表weakly not taken 弱順序分支
  10 代表weakly taken 弱跳轉(zhuǎn)分支
  11 代表strongly taken 強(qiáng)跳轉(zhuǎn)分支

我們繼續(xù)看2bit動(dòng)態(tài)分支預(yù)測(cè)是如果進(jìn)行狀態(tài)機(jī)遷移的：

• 當(dāng)前狀態(tài)處于00 強(qiáng)順序分支時(shí)
  必然預(yù)測(cè)下一次也是順序分支，此時(shí)會(huì)有兩種結(jié)果，預(yù)測(cè)成功了，下一次狀態(tài)仍然是00，預(yù)測(cè)失敗了，最終程序選擇了跳轉(zhuǎn)分支，下一次狀態(tài)變?yōu)?1。

  
  

• 當(dāng)前狀態(tài)處于01 弱順序分支時(shí)
  必然預(yù)測(cè)下一次也是順序分支，此時(shí)會(huì)有兩種結(jié)果，預(yù)測(cè)成功了，下一次狀態(tài)調(diào)整為00，預(yù)測(cè)失敗了，最終程序選擇了跳轉(zhuǎn)分支，下一次狀態(tài)變?yōu)?0。

  
  

• 當(dāng)前狀態(tài)處于10 弱跳轉(zhuǎn)分支時(shí)
  必然預(yù)測(cè)下一次也是跳轉(zhuǎn)分支，此時(shí)會(huì)有兩種結(jié)果，預(yù)測(cè)成功了，下一次狀態(tài)調(diào)整為11，預(yù)測(cè)失敗了，最終程序選擇了順序分支，下一次狀態(tài)變?yōu)?1。

  
  

• 當(dāng)前狀態(tài)處于11 強(qiáng)跳轉(zhuǎn)分支時(shí)
  必然預(yù)測(cè)下一次也是跳轉(zhuǎn)分支，此時(shí)會(huì)有兩種結(jié)果，預(yù)測(cè)成功了，狀態(tài)不變?nèi)匀皇?1，預(yù)測(cè)失敗了，最終程序選擇了順序分支，下一次狀態(tài)變?yōu)?0。

  
  

堅(jiān)持看到這里，說明你真是個(gè)愛學(xué)習(xí)的人兒啊，我們來畫一張完整的遷移圖：

從這張圖可以看到從順序分支改變?yōu)樘D(zhuǎn)分支，需要連續(xù)兩次預(yù)測(cè)失敗，同樣的跳轉(zhuǎn)分支變?yōu)轫樞蚍种?，也需要連續(xù)兩次預(yù)測(cè)失敗：

標(biāo)記分支狀態(tài)以及分支歷史的一段內(nèi)存被稱為BTB，這段內(nèi)存只存儲(chǔ)了分支指令地址，以及預(yù)測(cè)的目標(biāo)地址以及預(yù)測(cè)的位，這一塊內(nèi)容比較復(fù)雜，我們?cè)诖瞬徽归_了。

經(jīng)過前面的分析可以看到動(dòng)態(tài)分支預(yù)測(cè)器具有一定的容錯(cuò)性，并且波動(dòng)性較小，只有連續(xù)兩次預(yù)測(cè)失敗才會(huì)轉(zhuǎn)變選擇結(jié)果，整體正確率提升明顯。

從一些文章的數(shù)據(jù)顯示，大部分情況下2bit預(yù)測(cè)器準(zhǔn)確率可以達(dá)到95%以上：

回顧問題

經(jīng)過前面的一番分析，我們回到stackoverflow那個(gè)數(shù)組排序和無序耗時(shí)的問題上來，這個(gè)問題有兩個(gè)關(guān)鍵因素：

• 數(shù)組元素是完全隨機(jī)的，本次結(jié)果和上次結(jié)果是獨(dú)立分布的
• 大量循環(huán)結(jié)構(gòu)和條件判斷的存在

沒錯(cuò)，隨機(jī) 循環(huán) 條件就徹底命中了CPU流水線的軟肋。

• 數(shù)組排序之后的分支預(yù)測(cè)

• 數(shù)組未排序的分支預(yù)測(cè)

數(shù)組排序后，動(dòng)態(tài)分支預(yù)測(cè)會(huì)結(jié)合之前的結(jié)果做出判斷準(zhǔn)確率非常高，未排序時(shí)完全隨機(jī)和靜態(tài)分支預(yù)測(cè)差不多了，因此準(zhǔn)確率一般。

分支預(yù)測(cè)失敗就意味著流水線排空，廢棄已經(jīng)進(jìn)行IF和ID的指令，然后再選擇正確的指令，整個(gè)過程在目前CPU來說要來浪費(fèi)10-20個(gè)時(shí)鐘周期，這樣耗時(shí)就上來了。

總結(jié)

本文先從stackoverflow上一個(gè)關(guān)于隨機(jī)數(shù)組排序和未排序求和的問題來切入。

進(jìn)一步采用最簡(jiǎn)單的5級(jí)CPU流水線講述基本原理和流水線中存在的三者冒險(xiǎn)，及其各自的解決方法，特別是控制冒險(xiǎn)。

進(jìn)一步闡述了控制冒險(xiǎn)中的分支預(yù)測(cè)技術(shù)，并展開了對(duì)雙模動(dòng)態(tài)分支預(yù)測(cè)器基本原理的剖析。

最后結(jié)合stackoverflow的問題，揭露流水線分支預(yù)測(cè)和隨機(jī)數(shù)組排序/未排序在循環(huán)結(jié)構(gòu)下的不同決策結(jié)果帶來的巨大耗時(shí)影響。

本文先到這里，感謝朋友們的耐心閱讀，我們下期見！