x86高性能編程箋注(2)-流水線
性能優(yōu)化，關(guān)鍵在于伺候好CPU。作為一個追求性能極致的程序員，了解CPU的內(nèi)部機(jī)制是一個不可回避的話題。這是一個需要日積月累的持續(xù)的過程，但也并不需要深入到數(shù)字電路的程度，就像一個設(shè)計(jì)CPU的專家并不一定精通軟件設(shè)計(jì)一樣，你也并不需要成為一個CPU專家才能寫出高性能的軟件。
作為一小撮人類精英送給普羅大眾的珍貴禮物，能在市場上隨意購買到的CPU其實(shí)和買不到的核武器一樣代表了人類最尖端的科技水平。即便是一位x86 CPU專家也只能無一遺漏地講清楚他所專攻的那一部分內(nèi)容。對于我們來說，雖然不可能盡懂，但有三個部分的內(nèi)容十分關(guān)鍵：流水線、緩存和指令集。這三個部分之中，“流水線”可以作為一條貫穿的線索。因此，承接上一篇文章中的示例，我們先來了解一下流水線。
基本概念
CPU的主要工作是依據(jù)指令執(zhí)行對數(shù)據(jù)的操作。這句話基本上解釋了什么是流水線。我知道能點(diǎn)開這篇文章的人都不可能對“流水線”這個概念一無所知，我也不想一上來就鋪陳大段大段教科書式的文本，羅列各個概念的定義，這完全是在一心一意地舍本逐末。技術(shù)的發(fā)展只是事物矛盾的一種運(yùn)動形式，這次我們將嘗試從CPU的歷史沿革的角度切入對流水線各個組件的介紹。
從40年前Intel生產(chǎn)第一顆8086處理器直到今天，CPU的變化已經(jīng)讓你覺得以前的處理器都只能叫做“單片機(jī)”。但即便真的是淘寶上幾毛錢一個的單片機(jī)，也有和今天的i7處理器相通的地方。8086處理器有14個今天仍在使用的寄存器：4個通用寄存器(General Purpose Register)，4個段寄存器(Segment Register)，4個索引寄存器(Index Register)，1個標(biāo)志位寄存器(EFLAGS Register)用于標(biāo)示CPU狀態(tài)，以及最后一個，指令指針寄存器(Instruction Pointer Register)，用來保存下一個需要執(zhí)行的指令的地址。這個指令指針寄存器，就直接涉及到流水線的操作過程，它的持續(xù)存在，也表明了流水線基本原理的時間一致性。
從40年前到現(xiàn)在，所有CPU執(zhí)行過的指令都遵循以下的流程：CPU首先依據(jù)指令指針取得(Fetch)將要執(zhí)行的指令在代碼段的地址，接下來解碼(Decode)地址上的指令。解碼之后，會進(jìn)入真正的執(zhí)行(Execute)階段，之后會是“寫回”(Write Back)階段，將處理的最終結(jié)果寫回內(nèi)存或寄存器中，并更新指令指針寄存器指向下一條指令。這基本上是一個完全符合人類邏輯的設(shè)計(jì)方案。
最初，也是最自然地，CPU會一個接一個地處理全部指令。每一個指令都按上面的過程執(zhí)行完畢，然后執(zhí)行下一個指令。那個時候的主要矛盾還是軟件日益增長的性能需求同落后的CPU處理速度之間的矛盾。在摩爾定律的正確指導(dǎo)下，CPU建設(shè)工作取得了歷史性成果，主要矛盾發(fā)生了轉(zhuǎn)移：CPU的執(zhí)行速度慢慢快過了內(nèi)存讀寫的速度。所以每次都去內(nèi)存讀取指令越來越成為不能承受之重，因此在1982年，處理器中引入了指令緩存。
當(dāng)CPU的速度越來越快，數(shù)據(jù)緩存作為矛盾雙方互相妥協(xié)的產(chǎn)物也引入到處理器之中。但這些都不是治本之法。矛盾的主要方面在于，CPU并沒有以飽和的狀態(tài)運(yùn)轉(zhuǎn)。于是在1989年，i486處理器建設(shè)性地引入了五級流水線。其思路就是以拉動內(nèi)需的方式消化CPU的過剩產(chǎn)能：改一次只能處理一條指令為一次處理五條。
從網(wǎng)上以“CPU pipeline”為關(guān)鍵字搜索總會找到類似下圖的圖片：
我不知道諸位怎么看，反正我對著這幅圖理解起來總是有困難。提供一個簡單的理解：將每條指令都想象為一個待加工的產(chǎn)品，在一條有5個加工工序的流水線上魚貫而入。這樣可以讓CPU的每一道工序始終保持工作量飽和，也就從根本上提升了指令的吞吐和程序的性能。
流水線引入的問題
考慮一個簡單的交換變量值的代碼：
a = a ^ b;
b = a ^ b;
a = b ^ a;
如果簡單地將每一行代碼抽象為一個XOR指令，按上圖i486流水線的示意，第一條指令進(jìn)入流水線Fetch階段，然后進(jìn)入D1階段，此時第二條指令進(jìn)入Fetch。在下一個機(jī)器周期，第一條指令進(jìn)入D2，第二條進(jìn)入D1，同時Fetch第三條指令。到此為止一切正常，但下一個機(jī)器周期，當(dāng)?shù)谝粭l指令進(jìn)入Execute階段的時候，第二條指令并不能繼續(xù)進(jìn)入下一階段，因?yàn)樗枰淖兞?code>a的最終結(jié)果，必須在第一條指令執(zhí)行完畢之后才能獲得。所以第二條指令會阻塞在流水線之上，等第一條指令執(zhí)行完畢才會繼續(xù)。而在第二條指令執(zhí)行的過程中，第三條指令也會有類似的遭遇。當(dāng)出現(xiàn)了流水線阻塞的情況，指令的流水線式執(zhí)行就會與單獨(dú)執(zhí)行之間拉開距離，這被稱為流水線“氣泡”(bubble)。
Side Notes:
時鐘周期：也叫震蕩周期。是時鐘頻率（主頻）的倒數(shù)，是最小的時間周期
機(jī)器周期：流水線中的每個階段稱為一個基本操作，完成一個基本操作所需要的時間為機(jī)器周期
指令周期：執(zhí)行一條指令所需要的時間，一般由多個機(jī)器周期組成
除了上面的情況，還有一種常見的原因?qū)е職馀莸漠a(chǎn)生。執(zhí)行每條指令所需要消耗的時間（指令周期）是不同的。當(dāng)一條簡單指令前面是一條耗時較長的復(fù)雜指令的時候，簡單指令不得不等待復(fù)雜指令。另外，如果程序里出現(xiàn)if這類分支呢？這些情況都會導(dǎo)致流水線不能滿負(fù)荷工作，從而導(dǎo)致性能的相對下降。
在面對問題的時候，人總是會傾向于引入一個更復(fù)雜的機(jī)制來解決問題，多級流水線就是一個例子。復(fù)雜可以反映出技術(shù)的改良，但“復(fù)雜”本身就是一個新的問題。這也許就是矛盾永遠(yuǎn)不會消失，技術(shù)也不會停止進(jìn)步的原因。但“為學(xué)日益，為道日損”，愈發(fā)復(fù)雜的機(jī)制總會在某個時機(jī)之下發(fā)生大破大立，但可能現(xiàn)在時機(jī)還沒有到來:D面對“氣泡”問題，處理器又引入了一個更復(fù)雜的解決方案——1995年Intel發(fā)布Pentium Pro處理器時，加入了亂序執(zhí)行核心(Out-of-order core, OOO core)。
亂序執(zhí)行核心（OOO core)
其實(shí)亂序執(zhí)行的思想很簡單：當(dāng)下一條指令被阻塞的時候，從后面的指令里再找一條能執(zhí)行的就好了嘛。但要完成這個工作卻相當(dāng)復(fù)雜。首先要保證程序的最終結(jié)果與順序執(zhí)行一致，同時要識別各類數(shù)據(jù)依賴。要達(dá)到理想的效果，除了并行執(zhí)行之外，還需要對指令的粒度進(jìn)一步細(xì)化，以達(dá)到以無厚入有間的效果，這樣就引入了“微操作”(micro-operations, μ-ops)的概念。在流水線的Decode階段，匯編指令又被進(jìn)一步拆解，最終的產(chǎn)物就是一系列的微操作。
上圖就是引入亂序處理核心之后的指令μ-ops處理流程。不同顏色的模塊對應(yīng)第一張圖中不同顏色的流水線處理階段。
Fetch階段沒有太多變化，在Decode階段，可以并行對四條指令解碼，解碼的最終產(chǎn)物就是上面提到的μ-ops。后面的Register Alias Table和Reorder Buffer可以當(dāng)做是亂序執(zhí)行核心的預(yù)處理階段。
對于并行執(zhí)行的微操作，或者亂序執(zhí)行的操作，很有可能會同時讀寫同一個寄存器。所以在處理器內(nèi)部，原始的寄存器便被“別名”(aliased)為內(nèi)部對軟件工程師不可見的寄存器，這樣原本在同一個寄存器上執(zhí)行的操作便可以在臨時性的不同的寄存器上執(zhí)行，無論讀寫，互不干擾(注意：這里要求兩個操作沒有數(shù)據(jù)依賴)。而對應(yīng)的微操作的操作數(shù)也變?yōu)榱伺R時性的別名寄存器，相當(dāng)于一種空間換時間的策略，并且同時對微指令進(jìn)行了一次基于別名寄存器的轉(zhuǎn)譯。
之后微操作進(jìn)入Reorder Buffer。至此，微指令已經(jīng)準(zhǔn)備就緒。它們會被放入Reservation Station(RS)并被并行執(zhí)行。從圖中可以看到相當(dāng)多的執(zhí)行單元(Port X)。每一個執(zhí)行單元都執(zhí)行一個特定的任務(wù)，比如讀取(Load)，寫入(Store)，整數(shù)計(jì)算（ALU, SEE）等等。而每一條相關(guān)的微指令都可以在它所需要的數(shù)據(jù)準(zhǔn)備好之后執(zhí)行。這樣耗時較長的指令和有數(shù)據(jù)依賴關(guān)系的指令，雖然單從其自身的角度看，并沒有任何變化，但它們所帶來的阻塞的開銷，被后續(xù)指令的并行及亂序（提前）執(zhí)行所分?jǐn)偅麨榱?，帶來整體吞吐的提升。
亂序執(zhí)行核心的神奇之處就在于，它能夠最大限度地提升這套機(jī)制的效率，并且在外界看來，指令是在順序執(zhí)行。這里面的詳細(xì)細(xì)節(jié)不在本文的討論范疇。但亂序執(zhí)行核心是如此成功，以至于引入該機(jī)制的CPU即便是在大工作負(fù)載的情況下亂序執(zhí)行核心仍會在大部分時間處于空閑的狀態(tài)，遠(yuǎn)未飽和。因此，又引入了另外一個前端(Front-end,包括Fetch和Decode)給該核心輸送μ-ops，在系統(tǒng)看來，便可以抽象為兩個處理核心，這也就是超線程(Hyper-thread)N個物理核心，2N個邏輯核心的由來。
Side Note:亂序執(zhí)行也并不一定100%達(dá)到順序執(zhí)行代碼的效果。有些時候確實(shí)需要程序員引入內(nèi)存屏障來確保執(zhí)行的先后順序。
但復(fù)雜的事物總會引入新的問題，這次矛盾轉(zhuǎn)移到了Fetch階段。如何在面對分支的時候選取正確的路？如果指令選取錯誤，整條流水線需要首先等待剩余指令執(zhí)行完畢，清空之后再重新從正確的位置開始。流水線的層次越深，造成的傷害越大。后續(xù)的文章，將會介紹一些在編程層面優(yōu)化的方法。
