国产99久久久精品,西西裸体人体做爰大胆久久久,一区二区国产视频

大家好，我的朋友們。

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

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

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

有趣的問題

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

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

提問者用C++寫了一個數(shù)組求和的函數(shù)，把數(shù)組排序后求和和無序求和的計(jì)算性能竟然相差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';

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

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

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

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

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

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

洗車房的故事

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

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

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

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

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

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

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

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

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

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

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

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

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

取指令I(lǐng)F
取指令（Instruction Fetch，IF）階段是將一條指令從主存中取到指令寄存器的過程。
指令譯碼ID
取出指令后，計(jì)算機(jī)立即進(jìn)入指令譯碼（Instruction Decode，ID）階段。
在指令譯碼階段，指令譯碼器按照預(yù)定的指令格式，對取回的指令進(jìn)行拆分和解釋，識別區(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
作為最后一個階段，結(jié)果寫回（Writeback，WB）階段把執(zhí)行指令階段的運(yùn)行結(jié)果數(shù)據(jù)寫回到某種存儲形式。

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

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

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

CPU流水線吞吐量和延遲

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

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

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

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

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

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

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

CPU流水線冒險

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

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

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

結(jié)構(gòu)冒險

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

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

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

沒錯，這種將指令和數(shù)據(jù)分開存儲就是著名的哈佛結(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)冒險問題，只是硬件結(jié)構(gòu)更復(fù)雜了，屬于硬件層面的優(yōu)化。

數(shù)據(jù)冒險

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

int a = 10;
int b = a + 10;//語句2
int c = b + a;//語句3

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

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

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

流水線冒泡雖然簡單，但是效率卻下降了，經(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指令，減少了一個NOP操作，只需要1個NOP操作即可，提升了流水線效率。

控制冒險

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

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

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

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

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

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

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

CPU分支預(yù)測

分支預(yù)測有：靜態(tài)分支預(yù)測和動態(tài)分支預(yù)測。

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

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

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

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

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

說實(shí)話，看到這圖，我仿佛懂了，又仿佛沒懂，于是我決定好好研究一下這個2bit分支預(yù)測器的一些原理，我們繼續(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動態(tài)分支預(yù)測是如果進(jìn)行狀態(tài)機(jī)遷移的：

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