Linux下做性能分析6：理解一些基礎的CPU執行模型

[介紹]

前面介紹了兩個典型的調度模型，如果調度沒有問題，剩下的問題就是正面剛演算法了。那個不是我這裡要介紹的主題的。

但，Not Really。其實除了演算法在消耗CPU，CPU還是有很多餘力可以挖掘的，這一篇我們專門討論一下CPU的執行模型，看看我們在演算法本身以外，還可以怎麼優化我們程序的執行模型。

[流水線]

在不少軟體人員的想像中，似乎只要保證CPU的佔用率是100%，CPU應該是很忙的，應該在執行完一條指令，然後執行下一條指令，沒有空干別的事情。

但如果我們深入進去看，實際上CPU裡面也不是只有一個執行部件。假設有一個CPU上有4個執行部件，這些執行部件在CPU時鐘的驅動下，一跳一跳地完成每一個動作，並完成一個指令一個指令的執行，這個執行流程就會是這樣的：

看見了把，如果CPU真的這樣執行，「取指」這個部件在一條指令的執行中，有三跳（CPU稱為時鐘周期）其實是「閑」著的。

所以，合理的模型應該是這樣的：

也就是說，i1（被取指這個部件）執行後，取指部件反正閑著也是閑著，不如就直接執行下一條指令的取指就好了。這樣算起來，其實不是4個時鐘周期執行一條指令的，實際上是一個時鐘周期執行一條指令的。這個執行模型，我們就稱為「流水線」。它和工廠中的生產流水線的調度原理幾乎是一樣的。每個執行部件在一條指令中執行佔用的那個時間，稱為一個Stage，一條指令包含多個Stage，但第二條指令並不需要等待上一條指令的所有Stage都完成了才開始自己的stage。每條指令包含的Stage數目，我們稱為流水線的長度。流水線的長度決定了一條指令要多長時間才能完成，但如果流水線一切正常，平均起來，我們只需要一個stage的時間，就可以執行一條指令。

現代CPU的流水線是很長的，比如ARM的A57，流水線長度超過15。所以，看起來一條指令需要15個時鐘周期，實際上你只需要1個時鐘周期就可以執行一條指令。

[流水線的破壞1：指令依賴]

前面這個模型看起來很美，但實際上不是這樣的，有很多問題會破壞流水線。最常見的破壞是指令依賴。比如你寫如下彙編：

add r1, r2, r3 #r1=r2+r3nadd r1, 1 #r1=r1+1nadd r4, 2n

這裡第一條指令計算r1，第二條指令使用r1，第一條指令沒有執行完，第二條指令解碼完了，一看，我靠，要用r1，前面的還沒有搞完，等等吧，就成這樣了：

你看，CPU其實又閑下來了。(註：有人私信我說，這個地方處理器可以通過寄存器改名實現不用等待，這句話沒有錯，但其實還不止這一種優化方法呢，在主線邏輯上拉這種邏輯沒有意義，我們還是先聚焦原理，如果你有興趣討論這種細節，我們可以單獨拉線索來討論）

高級的CPU，編譯器，都會進行指令調度。比如我們看到第三條指令跟誰沒有沒有依賴，我們可以把它調整到第二條的前面，這樣可以填補一定的時間空間，這個執行會變成這樣：

這個效率就又高了一點了。

流水線是個很麻煩的事情，不到嚴重破壞的程度，我們不會在設計的時候就考慮它，盡量把它交給編譯器和CPU自己。很多半桶水的程序員，會以為用彙編寫的程序比用C寫的程序效率高，其實這個基本上都是錯的。因為你寫彙編代碼很難考慮流水線（特別是這裡不光有指令的調度，還有寄存器的調度，用不同的寄存器，可能可以造成不同的依賴，從而優化流水線的執行），如果你強行考慮流水線了，你的代碼也沒法看了，因為它不是以人腦為對象的了，完全是機器的思維），而編譯器考慮這樣的東西，毫無壓力。所以，我們只在流水線特別糟糕的地方考慮用彙編優化一下，而不會吃飽沒事到處寫彙編。這也是為什麼多言數窮，不如守中。大家都想耍小聰明，這個系統就不聰明了，各守本分才「合道」。

[流水線的破壞2：跳轉]

跳轉指令也會引起流水線的破壞。考慮如下序列：

1：n...nadd r1, r2, r3njmp 1b #jump back to label 1nadd r2, 1nadd r3, 2n

流水線確實把4條指令都執行了，但沒有什麼鬼用，因為第二條指令跳轉到別的地方去了，後面兩條指令執行了也是白執行。這種情況叫「指令預測失效」，也是破壞流水線的行為。

所以你經常看到一些高性能程序裡面寫這樣的代碼：

for(i=0; i<800; i+=4) {n a[i] = x;n a[i+1] = x;n a[i+2] = x;n a[i+3] = x;n}n

這個代碼看起來完全可以用這樣一個簡單的代碼代替：

for(i=0; i<800; i++) {n a[i] = x;n}n

而作者要寫成上面那個鬼樣子，很多時候就是為了優化流水線。讓跳轉不要那麼快發生。但還是那句話，不要在開始設計的時候就優化，否則自取其辱。

如果讀者習慣Linux的代碼，會經常看到likely和unlikely這個宏，它的作用也是這個，考慮一下如下彙編：

xor r1, r1, r1njz 2f #jump forward to label 2 if zeronadd r2, r2, 1n...n2:n

我們把分支放在jz後面還是放在2:後面呢？放在jz後面預測就會成功，放到2:後面預測就會失敗。那我們就應該把最可能的結果放在jz後面，所以我們才有likely和unlikely，通知編譯器，誰才是最有可能的，這樣也能有效提高CPU的執行效率。

[流水線的破壞3：內存訪問和Cache模型]

指令依賴中， 有一種依賴是要特別注意的，就是訪存指令。訪問內存是很慢的，你這樣想像一下吧：我們執行一條指令可能就是幾個時鐘周期，但訪問一次內存的時間可能就是幾百個時鐘周期。想像一下下面這個執行過程：

ldr r1, [addr1]nadd r1, r1, 3nadd r2, r2, 4nadd r3, r3, 5n

你以為這4條指令在一個流水線周期里就可以執行完了，實際是幾百個時鐘周期。這個效率一下就慢下來了。

我們當然可以把第三，四條指令提前，勉強填補一下中間的等待，但杯水車薪，也沒有什麼用。

這種時候，我們就要依賴Cache了，現代CPU系統有多級Cache，類似這樣：

L1 Cache中有的，就從L1取，沒有的就從L2取，……如此類推。這個問題考慮到他們的速度的時候，你就會發現其實是很嚴重的。

我們這樣考慮這個問題吧：L1 Cache的訪問速度是幾個時鐘周期（常常會是1個），L2是十幾個，L3是幾十個，到了內存上，就是幾百個，如果是多道系統，插幾個CPU，跨Socket的時候，就會更慢。

如果我們保證我們的執行盡量都在Cache的範圍內，我們的性能就會提高。Cache Line的長度常常比寄存器的長度長，比如64位系統一個寄存器是8個位元組，而Cache Line的長度常常可以達到128個位元組。如果你的訪問是對齊的，很多一次內存操作可以完成了動作，就不需要兩次才能完成，這會大大提高執行的效率。另外，如果你在訪存之前還有很多準備動作要做（memcpy一類的程序經常如此），你還可以通過Cache預取指令提前把內存的數據拉到Cache中，這也能大大提高效率。

還有一種會嚴重破壞性能的模型。稱為Cache污染，大概的模型是：你的演算法做得不好，總是訪問一個Cache剛剛乾掉的數據，每次訪問都導致一次Cache刷新，性能就會嚴重下降。這個有很多論文了，我就不介紹了。基本上不是專業的研究者，我們也不用專門去記住這些模型，我們只要按功能，按軟體構架的要求，把代碼寫出來，然後通過profiling工具去發現密集出現branch-miss，cache-miss的地方，根據情況作出優化就好了。

[非同步調度模型]

上面我們給了一個基本的流水線模型。但實際上……呵呵，又來了……這種叫同步模型，現代的CPU，基本上不是這樣的同步模型。現在CPU是非同步調度模型。類似下面這樣（網上隨便找的圖，侵刪）：

從中間開始，CPU的執行分成了兩段。前面一段是取指有關的操作，後面一段是執行有關的操作。CPU有很多的執行通道，可以有多個定點或者浮點加法器，幾個取指器等等。這樣，實際上整個CPU就像一個多線程的軟體程序：有一組線程負責把指令讀出來，解碼，然後送入隊列，另一組線程負責從隊列中把指令取出來，投入執行。這個執行並非嚴格的流水線模型，而更像我們這個系列文章最前面提到的那個隊列模型。

在晶元的優化手冊中，會給出前端和後端有哪些執行部件（比如一個比較新的RISC CPU上的前端是Fetch, Decode/Rename/Dispatch和Issue，後端是Branch, Int0, Int1, Int Multi-Cycle，FP0, FP1, Load, Store）。然後它還會給出每個指令需要佔用哪些執行部件，已經這個指令的執行時延和執行通量。如果你要進行彙編一級的優化（比如為這個CPU配套編譯器），你就需要根據這個優化手冊對指令進行重排。而對於優化者，則首先看重程序的IPC（每個cycle執行多少條指令），然後查對應的stall參數，看有沒有機會特別重排程序特定的部分，從而加快執行效率。

下面這個是Intel的一個Top Down模型（侵刪）：

前面一段就是取指有關的，是In-Order的操作，這部分是符合原來的流水線模型的。後面一段就是純粹的調度。這個性能就不能完全按嚴格的流水線模型來考慮（加上超線程技術就會更加複雜）。所以現在你用perf stat執行一個程序，它會給你這個總結（不是每個CPU都支持這兩個統計）：

你可以看到了，它首先給你統計了一個stalled-cycles-frontend，和一個stalled-cycles-backend，通過這兩個統計，你可以看到，無論你如何執行，你的系統到底有多少花在了前端的等待上，多少花在在後端的執行上。前者說明你供指令的速度不夠快，後者說明你CPU處理不過來。我們可以以這個為基礎，進一步找到系統的執行瓶頸。

Intel處理器上，這個模型稱為Top-Down模型，以這個為分界，可以一步步分解下去，最終找到執行瓶頸在什麼地方，我們從而可以找到合適的軟體執行模型，提高系統的執行效率。這些模型首先和CPU的微架構是相關的，但基於我們原來的流水線中形成的經驗，我們在一定程度上，到都有相當的機會了解到我們可以調整軟體的什麼設計來讓CPU執行得更快。

[小結]

本文介紹了一些基礎的CPU執行模型，一定程度上了解CPU的執行模型，有助於我們正確找到系統的性能瓶頸。但從這些模型中，我們也看到了，其實整個系統的每個模塊都在嘗試優化自己的執行效率，而作為最高層的軟體，其實是最需要遵守「多言數窮，不如守中」策略的角色。從設計的角度，軟體引導了整個需求的響應方法，軟體守不穩，所有其他的小九九都是水月鏡花，留不住的，我們不能理解這一點，也就不能理解為什麼軟體架構這麼重要。

越是混沌的系統，越需要我們守得住基本面。

很多人也許覺得這裡討論的問題都很簡單，但越是簡單的東西你越守不住，當你被眼花繚亂的變化吸引了大部分的注意力的時候，你回過頭來想一想，你當初的需求到底是什麼。這就是守弱。也就是我們說的：執古之道，以御今只有，能知古始，是謂道紀。我們能掌握現在的複雜局面，我們必須回到最開始解決的問題上，我們才有可能理解現在的一切變化。

推薦閱讀：