CPU流水線與指令亂序執行

青蛙見了蜈蚣，好奇地問："蜈蚣大哥，我很好奇，你那麼多條腿，走路的時候先邁哪一條啊？"

蜈蚣聽後說："青蛙老弟，我一直就這麼走路，從沒想過先邁哪一條腿，等我想一想再回答你。"

蜈蚣站立了幾分鐘，它一邊思考一邊向前，蹣跚了幾步，終於趴下去了。

它對青蛙說：「請你再也別問其它蜈蚣這個問題了！我一直都在這樣走路，這根本不成問題！可現在你問我先移動哪一條腿，我也不知道了。搞得我現在連路都不會走了，我該怎麼辦呢？」

這個小故事屬實反映了我最近的心態：

越學越不會了。。。

本來synchronized和volatile關鍵字用得好好的，我非要深入研究一下他們的原理，所以研究了記憶體屏障，又研究了和記憶體屏障相關的MESI，又研究了Cache Coherence和Memory Consistency，發現一切問題都出在CPU身上。於是又驚歎Java一次編寫到處執行的特性，最終又研究到JMM。

說是研究，其實就是把學習過程中自己丟擲來的問題解決掉，把所有知識穿成一條線罷了。

這條線的線頭就從指令的亂序執行開始了。

經典的指令亂序執行的原因有兩種，分別是Compiler Reordering和CPU Reordering。

1. Compiler Reordering

編譯器會對高階語言的程式碼進行分析，如果它認為你的程式碼可以優化，那麼他會對你的程式碼進行各種優化然後生成組合指令。當然，本文說的優化主要是指令重排（Compiler Reordering）。

但是編譯器的優化必須滿足特定的條件，一個非常重要的原則就是as-if-serial語意：

Allows any and all code transformations that do not change the observable behavior of the program.

編譯器必須遵守as-if-serial語意，也就是編譯器不會對存在資料依賴關係的操作做重排序，因為這種重排序會改變執行結果。但是，如果操作之間不存在資料依賴關係，這些操作就可能被編譯器和處理器重排序。

我們用非常簡單的C++程式碼舉個例子（因為編譯更簡單，看起來也更直觀）。

int a,b,c;

void bar()
{
        a = c + 1;
        b = 1;
}

int main()
{
        bar();
        return 0;
}

我們對這段程式碼進行變異，讓編譯器在O2級別優化的情況下編譯程式碼，我擷取其中的bar()的組合程式碼，如下所示：

_Z3barv:
.LFB0:
        .cfi_startproc
        endbr64
        movl    $1, b(%rip)      #將1的值賦給b，即b = 1
        movl    c(%rip), %eax		 #將c的值放到暫存器%eax中
        addl    $1, %eax         #將暫存器%eax的值+1，即c + 1
        movl    %eax, a(%rip)    #將暫存器%eax的值賦給a，即a = c + 1
        ret

我們發現，編譯得到的組合程式碼和我們原本的C語言程式碼順序並不一致。

組合指令先執行了b = 1，之後才執行了a = c + 1。說明變數a和b的store操作並沒有按照他們在程式中定義的順序來執行。

既然組合指令被重排了，CPU的執行順序自然是根據組合指令對應的機器指令執行的，大概率也會被重排。其實除此之外，CPU本身也會對指令進行重排（CPU Reordering）。

2. CPU 流水線

談及處理器必談及流水線，處理器的流水線結構是處理器微架構最基本的一個要素，也是造成CPU Reordering的主要因素。

2.1. 從汽車裝配談起

流水線的概念始於工業製造領域，但是鑑於大部分人其實都沒接觸過流水線，我們不妨舉一個汽車生產的例子來解釋流水線的誕生。

我們首先粗淺地認為汽車的裝配需要兩個步驟：

製作零件：製作車身外殼、發動機和各種其他部件；
組裝：將各零部件（自己製作和外採的所有零部件）組裝成車。

假設一個工人進行每個步驟都佔用1個月，如果不採用流水線，而採用序列方式來執行的話，一年時間可以裝配6輛汽車，過程見下圖：

序列的效率實在是太有限了，根本原因就是裝配的兩個步驟都是由一個人完成的。如果有人能在組裝進行的同時製作零件，效率會大大提升，也就是每個流程只專注一件事情，我們再引入一個工人。

這樣一個人專門負責製作零件，另一個人專門組裝零件，兩個工作交疊進行，過程見下圖：

增加一個人手之後，除了第一個月，每一個月都有完整的製作零件和組裝流程，因此一年內可以完成11臺汽車的裝配（相比於序列方式的6臺，幾乎翻倍了），從第二年開始，每年就能裝配12臺了（直接翻倍）。

這個過程就是流水線的執行過程，因為我們把汽車的製作過程分成了兩個步驟，因此以上流水線成為二級流水線。

我們繼續優化，我們將製作零件的步驟分成時間週期更短的衝壓和焊接兩步，將組裝步驟分為時間週期更短的塗裝和總裝兩步，並且假設每個步驟的時間週期為0.5個月。

當然嘍，我們得再僱傭倆人。

現在就是四級流水線了，神奇的事情發生了，四級流水線使得原本需要一年時間的任務現在只需要4.5個月便可以完成，再次提升了效率。如下圖所示：

2.2. 現代CPU的流水線

現代 CPU 支援多級指令流水線，例如支援同時執行 取指令 - 指令譯碼 - 執行指令 - 記憶體存取 - 資料寫回的處理器，就可以稱之為五級指令流水線。

這時 CPU 可以在一個時鐘週期內，同時執行五條指令的不同階段，其中每個階段的都佔用一個或多個指令週期（CPU以執行時間最長），本質上，流水線技術井不能縮短單條指令的執行時間，但它變相地提高了指令的吞吐率。

上面的CPU流水線圖並非特定型號的CPU的範例，而是為了說明幾個問題特意畫成了這個樣子。

通常而言，CPU設計者會選擇執行時間最長的流水線階段作為一個時鐘週期，這樣能保證其他階段能在一個時鐘週期內完成，避免出現流水線斷流。
每一個流水線級的時間都是一個時鐘週期，但是其中實際操作的時間，可能短於一個時鐘週期。比如譯碼器其實就是一個組合邏輯電路，門延遲很低，就不需要一個完整的時鐘週期就能完成自己的任務，任務完成之後CPU其實是在「等待」。

很多人可能會問，既然流水線這麼好用，那為什麼CPU設計者不設計一個超長流水線呢？這就需要說明一下超長流水線的瓶頸了。

3. 超長流水線的瓶頸

3.1. 效能瓶頸

流水線長度的增加，是有效能成本的。

每一級流水線的輸出都需要放在流水線暫存器中，然後再下一個時鐘週期，交給下一個流水線級去處理。每增加一級流水線，就要多一級寫入流水線暫存器的操作。

以多執行緒為例，數量合適的多執行緒會提高資料的處理速度，但是當執行緒數量太多，執行緒之間的時間切換成本就無法被忽視，執行緒的增加甚至可能成為效能提升的負擔。

3.2. 功耗瓶頸

提升流水線的深度，需要同步提高CPU的主頻。再看一下這個圖：

由於流水線的每一級被分得特別細，甚至有的還沒有完全佔滿單個時鐘週期，也就意味著單個時鐘週期內能完成的事情變少了，因此只有提升主頻，CPU 在指令的響應時間這個指標上才能保持和原來相同的效能。

提升主頻和流水線深度就以為這電晶體的增加，也就以為這功耗變大。

沒人想擁有一臺「充電3小時，辦公20分鐘」的一臺筆記型電腦吧。

3.3. 指令亂序

還是以上面的圖為例（就不再貼一遍了），指令1的訪存操作使用了多個時鐘週期，導致指令2和指令3在指令1之前完成了。

如果是一般的程式碼還好，但如果是具有依賴性的程式碼，比如：

float a = 3.14159 * 0.2; // 指令1
float b = a * 2;         // 指令2
float c = b + 1;         // 指令3
float d = 10;            // 指令4

指令1、2、3的執行順序就絕不能向圖中表示的那樣亂序執行。其中有兩點需要我們注意：

由於上圖中情形的存在，導致CPU確實有可能出現亂序執行的情況；
CPU需要阻止具有依賴關係的指令亂序執行（指令1，2，3），轉而讓後續沒有依賴關係的指令（指令4）先執行。

對於第2條，如果流水線只有5級還好說，CPU自然有辦法判斷哪些指令具有依賴性，並拒絕做出指令亂序。但是如果有20條流水線，CPU肯定還有辦法判斷，但是可想而知，這種判斷勢必會影響CPU的效能。

回到本文一開始說的編譯器指令重排序，當然嘍，也包含Java的JIT將位元組碼編譯成機器碼時的指令重排序，就是為了把沒有依賴關係的指令放一起，本質上都是為了適配CPU，更好地發揮出CPU流水線的功能，從而提升效能罷了。

4. 總結

說了這麼多，很可能在我之後的文章中被一句話帶過。

其實我想表達的思想就是，實際程式碼執行的順序可能和我們程式碼編寫的順序並不一致。記住這句話很容易，但或許總會有人像我一樣想稍微深入一點來了解這句話的本質吧。

除了本文所述，CPU和快取記憶體之間的互動過程中，硬體工程師也著實給軟體開發者挖了不少坑，記憶體屏障就是在這種背景下產生的。

更多內容，下期見！