分支處理勞民傷財

電腦依據用來儲存下一個指令所在記憶體位址的「程式位址計數器(Program Counter,在x86的世界稱為Instruction Pointer「指令指標器」)」,依循記憶體位址,循序地擷取(Fetch)指令、解碼(Decode)、執行(Execute)並將結果寫回程式指定的記憶體位址(Write Back)。

如發生條件判斷的分支或無條件判斷的跳躍,就會變更指令流。換言之,記憶體內存放的指令碼,並非依據真正的程式執行流程而「排排站」,而是分散在記憶體位址的四處,預言了記憶體效能不足以外的潛在障礙物。

處理分支指令也會造成額外負擔,當處理器擷取到一個編碼後的指令,怎樣偵測這是不是分支指令?一般而言,讀取指令並將其解碼到一定程度後,即可分曉,確定是分支指令之後,分支預測緩衝器就檢查是否有該指令的記錄(從被擷取的記憶體位址)進行預測。

難以預設的特殊分支行為

但知道分支指令是一回事,如何預測分支目標與妥善處理其「行為特質」卻又是另一回事。至少有三種分支行為模式相當難以預測:第一種:具有「相依性」的分支,第一個分支發生了、後面第二個分支也一定會發生,好比你判斷站在眼前的是正妹,那她的隨行好友也一定是正妹,兩個分支本質上是同一個程式碼基本區塊(Basic Block,區塊中除最後一道指令外,其餘指令都不能是分支指令)。

這時候我們就需要多層分支預測器、利用其他的分支歷史紀錄來應付這種狀況,這就是Intel在Pentium Pro的Yeh Method,修過計算機組織結構的資訊科班背景讀者不可能沒聽過。

第二種:「迴圈(Loop)」,這就不難理解了,就是反覆執行、直到條件達成才會終止,打個比方,假設「正妹群聚效應」的理論上限是六個,那表示,你逐人判斷下一個是否正妹的過程,是一個執行六次的迴圈,合計有七次條件判斷,前六次發生,第七次避不開預測錯誤。此時此刻,你就需要在預測位元的欄位中,實作一個計數器來記錄其重複執行的次數,下次碰到相同的分支就沒問題了。Intel在90nm製程Pentium 4「Prescott」和首款Pentium M「Banias」引進這種方法。

第三種:「間接分支(Indirect Branch)」,這有點像參加化裝舞會、你必須一頭鑽進由一票女性同胞組成且時時改變的人群中,判斷你在某個位置撿到的舞伴是否正妹,且這個「跳躍的目標」隨時會被更動,簡而言之,這個分支的目標是「動態」的。

一個分支指令有多個目標位址的間接分支,並沒有完美的預測方式,Intel在Pentium M首度引入間接分支預測,說穿了就是暴力法硬幹、分支預測表就為單一間接分支打開多個目標位址記錄點,並增加一些協助判斷用的額外資訊欄位,如歷史流程等。

延伸閱讀:如果你想多了解動態分支預測的基礎知識…雖然這篇只涵蓋了筆者想寫的四成不到…

44

2008三月

番外篇:完全看懂動態分支預測

P186-P190

但回過頭來思索在Intel的x86處理器發展史,筆電導向的Pentium M為何是新型分支預測的先行者?道理很簡單,分支預測錯誤意味著「暮然回首」清空管線,該指令後方正在被擷取、解碼中的指令要被清除掉,重新計算目標位址,更新程式計數器,再重頭從記憶體擷取指令,不但降低處理器運算效能,本身更是浪費電力的行為。

講白了,越精準的分支預測,代表更高的「效能/功耗」比。不限Intel Pentium M,AMD當年也曾在K6採取近似的思維,而在公元2000年後x86處理器紛紛「炎上」變身成破百瓦的不發光燈泡,分支預測的重要性更是天元突破、水漲船高。

另類思考:很多以追求多執行緒輸出量為前提打造的處理器微架構(偏向高密度多核心多執行緒),會盡力縮短指令管線深度,因為這可減輕分支預測錯誤後的代價,尤其當沒太多電晶體預算和研發資源砸在分支預測的時候,這是另一種面對分支問題的角度。

指令快取不是萬能,對推土機更是萬萬不能

但再精準的分支預測,仍無法避免一個先天的障礙:就算猜中、並根據定址模式計算出有效位址,處理器不見得能立即擷取到存放下一個指令的記憶體區塊。此外,越精準的分支預測,也帶來更長的判斷延遲。

當然,你可能會馬上質疑:我們不是還有第一階指令快取可用嗎?但問題是:天底下沒有命中率100%的快取記憶體,即便命中,讀取指令快取SRAM陣列的內容也並非毫無延遲,基於成本考量,你不會有無止盡的存取埠可用(按慣例,L1-I有兩埠就算不錯了)。動態分支預測的本質也是快取的另類應用,相同的問題一樣存在。

這些疑慮對兩個整數運算核心共用指令解碼器的AMD推土機更是天殺的敏感:都已經兩個核心按不同時脈輪流分著用了,指令快取和分支預測出了亂子,給不了解碼器足夠的彈藥,豈不是要後端執行單元彈盡援絕束手就擒,活活被亂槍打死壯烈犧牲嗎?事後證明,推土機的確很爭氣的化身成眾人景仰的烈士,但這卻不代表,AMD對於降低指令快取誤失的傷害,並非沒有應對手段,反倒讓人耳目一新,但是不是「原創」就很值得探討了。

延伸閱讀:快取記憶體的基礎知識,與資料一致性協定的概念…

64

2009十一月

你所不知的伺服器(二)之最後兩頁附錄

 

102

2013一月

[推土機行進曲] 伺服器CPU關鍵架構:快取記憶體一致性協定

118-125

讓動態分支預測與指令擷取「脫鉤」

雖然自立自強的AMD並不像台灣滿山滿谷整天抱怨草莓族這裡不好那裏不行的慣老闆,呼籲政府讓外勞薪資與本地草莓員工「脫鉤」、以便與「史上表現最佳的政府」一同「拼經濟」,但AMD應該早已察覺結構過度簡單的2-way組關連性指令快取,利於最低成本最高容量外,毫無任何優點,發生衝突性誤失(Conflict Miss)的機會實在太大了,後端執行單元爆發世紀大饑荒的機率也隨之高漲。

延伸閱讀:AMD剛在處理器業界年度盛事IEEE ISSCC 2014公布Steamroller技術細節,第一階指令快取從Bulldozer/Piledriver的64kB/2-way升級成96kB/3-way,宣稱可降低30%的誤失率。

AMD索性不等發生指令快取誤失時、才手忙腳亂去抓東西,乾脆放手讓指令擷取單元「盡量往前跑」,可依據分支預測研判出的實際執行指令流,「先斬後奏」提前擷取未來需要解碼指令的記憶體位址,即使發生指令快取誤失,或多或少減少重新從其他記憶體(如下一層快取)擷取的時間。

換句話說,AMD想做的事情是:在擷取指令前就執行分支預測,提前把未來可能碰到的分支指令-抓到指令快取內,這更可爭取到足夠的時間,讓分支預測盡其所能的做到盡善盡美。下期我們就從基礎面出發,一步一腳印的接近AMD選擇的途徑。糟糕,我寫不出來跳票該怎麼辦?(編輯部:啊,所以從頭到尾你根本就一個人用鍵盤幻想啊!)

AMD推土機最大的祕密:Decoupled Front-end Architecture

RIP這三個字母雖然看來深具不祥之兆,但相信各位看倌已經猜到AMD在幹什麼了。

延伸閱讀:

解決手機、相機水波紋現象,全是日光燈頻率在搞鬼

比特幣的架構、演算與經濟,為什麼AMD比NVIDIA還好挖?安全有什麼漏洞

飛機上哪來的Wi-Fi無線網路?陸基3G、衛星網路架構原理

電腦待機、睡眠、休眠分不清楚?P、T、S、G、C 電源狀態一次看懂

本文同步刊載於電腦王雜誌
  AMD推土機最大的祕密:Decoupled Front-end Architecture
歡迎加入電腦王雜誌粉絲團

使用 Facebook 留言

PCABC
1.  PCABC (發表於 2014年4月21日 15:44)
有沒有建議的入門參考用書

這篇有點難懂 希望增加更多詳盡的解釋與圖解

發表回應

謹慎發言,尊重彼此。按此展開留言規則