看完PCADV雜誌感想~動態分支預測之補充

作者：無痕之音│2008-12-27 17:40:16│巴幣：102│人氣：2933

‧‧‧‧‧‧‧‧‧‧‧‧‧‧‧

癡漢水球他所寫的深度討論 CPU 微架構文章看了好幾個月
，也就是好幾期。
每篇對 NETBURST 都有獨到精闢的見解，且跟軍事互相對
照做比喻。

●以下就把46、51期的內容做精簡整理，看不懂沒關係，反
　正這篇我發文純自ＨＩＧＨ。
　以下內容相當精深，若消化不良或散熱不良，請別忘了加
　裝散熱器，以下我推薦幾款好散熱器，免的腦袋承受不及
　瞬間燒掉

+++++++++++++++++++++++++++++++++++++++++++++++++++++++
－＞４４期 NetBurst 動態分支預測

簡單的劃分思想：
電腦(computer)跟計算機(calculator)最大之不同，在於前者具備
邏輯 "條件判斷" 的能力，後者則無。

同樣地，我們的頭腦及眼睛也內建相同的條件判斷過濾能力。
這也就是說，當一位可愛的妹妹走過我們身邊時，我們跟本不
用捨身犯難到她身邊，問她是『恐龍』還是『正妹』這個找死
的問題。

。。。。。。。。。。。。。。
分支有兩種(Branch)，一種是跳躍(Jump)，一種則是有條件分支
(Conditional Branch)；條件分支好比 if-then-else，跳躍則好比goto
語法，前者是具備條件判斷，後者則直接跳躍一定發生。

也許跳躍(Jump)看起來一定會發生跟本沒有預測的必要，不過
要記住『分支指令是管線化的麻煩』，也是說管線深度也會加
深造成控制危障的影響。

何以分支指令會是管線化指令的頭號麻煩人物？
原因在於，只要執行一個簡單的跳躍指令，該指令正在後端被
擷取；但相對地正在解碼中的指令就要被清除掉、然後清空整
條管線、更新程式計數器(Program Counter)，從記憶體中擷取
指令。

管線全部清空意味前面的動作全部報銷，重新啟動擷取指令更
是一個耗電的行為，且管線越深，造成的效能傷害也越大。
然而管線化是X86不可缺少的方案，因為X86指令集的特色是長
度混亂不堪、格式紊亂、定義暫存器少的可憐、高度相依需求
定址模式的記憶體存取密集機制、以及僅定義２運算元Ａ＋Ｂ
＝Ａ等。

若是條件分支(Conditional Branch)則傷害就更大了，因為還必需
等待執行判斷的結果才能進行下一步，這期中所有動作只能停
擺，若是遇上浮點除法運算，更是延遲高達數十個時脈週期。
所以就衍生出一個『先斬後奏』的思維及理論及實作，那就是
『動態分支預測』機制，若預測成功率越高，對於管線造成的
傷害也就越小，甚至微乎其微。

《範例》
這邊舉個簡單的例子計算了解一下造成的分支傷害(Branch Penalty)
有多大，這邊先假設無預測及有預測機制來互相做個比較：

→　Pentium 一代
　　分支傷害約３．５時脈週期，執行之程式碼有１／７是分支

3.5/7=0.5 　　　　　：每個指令延遲 0.5時脈
1/(1+0.5)=0.66=66%　：效能只有原來的66%

→　Pentium   Pro
　　分支傷害達１５時脈週期，執行之程式碼有１／７是分支
　　管線深度 12-14階

15/7=2.14　　　　　　　：每個指令延遲 2.14時脈
1/(1+2.14)=0.318=31.8%　：效能只有原來的31.8%

只剩下31.8%這樣的效能已完全崩潰，這就是完全不做分支預測
造成的下場，災情極度慘重。

好；換有分支預測的話會如何，就看看一下吧：

→　Pentium 一代
　　分支傷害約３．５時脈週期，執行之程式碼有１／７是分支
　　分支預測命中率約８０%

0.8x0+0.2x3.5= 0.7　：分支傷害為 0.7
0.7/7=0.1　　　　　：每個指令延遲 0.1時脈
1/(1+0.1)=0.909　　：效能是原來的 90.9%，效能提升約２４%

→　Pentium   Pro
　　分支傷害達１５時脈週期，執行之程式碼有１／７是分支
　　管線深度 12-14階，分支預測命中率約９０％

0.9x0+0.1x15=1.5　　：分支傷害為 1.5
1.5/7=0.214　　　　：每個指令延遲 0.214時脈
1/(1+0.214)=0.82=82%：效能是原來的 82%，效能提升達５０%！

如此可見，分支預測機制對於程式語言及處理器而言有多麼重要了。

。。。。。。。。。。。。。。
《動態分支實做─以古鑑今》

當然，要有效率地在預先得知該指令是否分支，最主要還是透過記
錄程式的行為跟常見指令的分支情況，那就是ＢＴＢ表。
ＢＴＢ(Branch Target Buffer)─分支目標緩衝區，或BTB記錄表。
主要是透過預測位元，來命中(HIT)標示該程式指令及其記憶體位址
是否有分支行為，預測之基準在於靠記憶體位址進行判斷。

若表格中並無記錄，則還可以依據程式指令目標之型態來決定是否
分支，只是必須提醒的是：一但分支發生，重新啟動擷取指令是一
件非常勞民傷財的事。

目前上分支預測機制實作上，INTEL 採用二位元四種狀態來標定。
AMD 則使用三種狀態來標示分支發生(Taken)或不發生，其實作應
用之演算法，就是眾所週知的史密斯演算法(Smith Algorithm)。
這邊有進階之比喻說明：淺論DynamicPrediction的演算法(頁庫存檔)

。。。。。。。。。。。。。。
《三種特別分支》

1)相依性分支
》若有A便有B→若有B便有C；若A不成立，B也不成立

如：(個人修改以 autoit 腳本做範例，可能與原文不同，舉例不好請指正)
If $var > 0 Then
    MsgBox(4096,"", "Value is positive.")
ElseIf $var < 0 Then
    MsgBox(4096,"", "Value is negative.")
Else

代表的演算法：YEH METHOD
目前初始應用：Pentium   Pro

2)迴圈 LOOP
》不斷地執行重覆指令，直到目地達成

這是很常見的指令... 此類指令為何也算分支呢？
原因很簡單，若照迴圈來看，若有 28次計算，那
前27次都能成功預測，第28次肯定猜不到出錯。

如：
;Print all numbers from 1 to 10 except number 7
For $i = 1 to 10
    If $i = 7 Then ContinueLoop
    MsgBox(0, "The value of $i is:", $i)
Next
;Example of using level is needed.

目前初始應用：Pentium  M(Banias)、Prescott

3)間接分支
》一個指令無固定之記憶體位址，其位址會因為暫存
　器內容及計算結果而有所不同
這部份主要就以 jump[register]、switch-case 等屬之。

如：
Switch @HOUR
Case 6 To 11
    $msg = "Good Morning"
Case 12 To 17
    $msg = "Good Afternoon"
Case 18 To 21
    $msg = "Good Evening"
Case Else
    $msg = "What are you still doing up?"
EndSwitch

特別一提的是，Switch...Case...EndSwitch這類的間接分支
指令，屬於『單一指令多重目標位址』間接分支；
這類的分支，並不像DLL及系統呼叫(SYSTEM CALL)是
『單一指令單一位址』那麼單純。

目前 Intel 還是用 BTB 表記錄多重分支位址及歷史記錄來
硬幹的方式，說真的，一丁點效果也沒有...　
完完全全被 AMD Opteron 給擊敗，Xeon 在伺服端的表現
還遠不如今日的 Merom 65nm核心。

+++++++++++++++++++++++++++++++++++++++++++++++++++++++
－＞４６期 NetBurst 微架構的悲歌(二)─trace cache的價值

軍事思想：
民主思想是要被奴役的人民獲得自由，和平是一種種目地，
也是戰爭的停止。

蘇聯共產主義的思想就是利用階級鬥爭為手段，對他們而言，
所謂的和平不過是另一種形式而已。
美國的國社黨人則認為和平就是孕育戰爭的時期。

這兩者的思想是全球性的。戰爭是連續性的，對民主國家的威
脅也就更大，也是說，一個人的目標對民主的生活方式具備較
大的危險性。

。。。。。。。。。。。。。。
《ｘ８６　缺陷無所不在》

trace cache 其設計之本意在於解決 x86 指令集長度不一、解碼
時間長、與複數指令解碼器的高熱量與高成本。
相對於處理 self-modifying 編碼修正錯誤，讓原本就很難搞的
『修改快取記憶中的指令內容』惡化成『設法從亂成一團的
trace cache 中找出對應指令群，且一次就要改整條trace cache。

也許對於 self-modifying 對於處理器而言並不重要，可是卻也必
須大費周章確保它的相容性。
而要改善這個缺點，就只能『將電晶體砸到刀口上』反樸歸真
不失為一個從頭檢視問題所在的好方法。
由於處理器常要應付如 LOOP 迴圈這類的指令，若 trace cache
空間不足，無法一次吞下整個迴圈，就必須不斷地擷取/解碼
造成效能的浪費跟嚴重延遲，最重要的是額外耗電量。
這個現象在高階伺服端商業應用軟體更是明顯，大量的間接分
支應用操爆了NetBurst微架構trace cache，也因此 INTEL Xeon
各方面的表現均不如 AMD Opteron...

簡言之，被 INTEL 腰斬的 Tejas 其 trace cache 16k、快取達200k
，值得一提的是，TNI指令集=SSSE3， SSSE3 其原始來自當時
的『胎死腹中的老祖宗』：Tejas New Instructions(TNI)。

目前已出爐的 Merom/Penryn 採用替代 trace cache 這種勞民傷財
、耗費巨額成本、高熱量及耗電量、龐大的體積，所以回歸最
單純的本質，而創造了一個奇蹟：LSD (Loop Stream Detector)
顧名思義，LSD可以先行過濾留下不超過 18個的loop迴圈微指令
，這麼一來，只需要從LSD擷取及解碼執行微指令，省下從第一
階快取擷取，也不必動用耗電傷財的分支預測機制。

至於 Nehalem 則變相地讓『trace cache』借屍還魂重生，可以解
碼 28 個 loop 微指令，與前代LSD更強悍之處在於，將LSD改置
於指令解碼器後端，自然『指令解碼器』也可用不到一起裝死。

最簡單的方法，往往也是最直接的解決方式。
堅清壁野頑固不化、過於鑽牛角尖的觀念做法，往往成效不彰呢。
既然怕飛彈射出去後飛不遠，不必費盡心思去加強燃料及推進系
統，也許只要一個簡單的抗甘擾裝置確保『精確度』即可，就可
達到一樣的目標和效果。

+++++++++++++++++++++++++++++++++++++++++++++++++++++++
－＞５１期 NetBurst 微架構的悲歌─ 被腰斬Tejas的真面目

『胎死腹中的老祖宗─Tejas處理器』面貌：
死因：耗電量驚人、DIE面積龐大(2XXmm)、成本高昂、熱量完全失控

１．基於 90nm時代的應變矽晶圓(strained silicon)、低介電質絕緣
　　層(Low-K inter layer)，９０nm 製程。
２．將 Prescott 第二階快取加大一倍，快取似乎增加不好，影響不很大。
３．加深管線深度，可能達４０階以上，只能以『大興土木』來形容...。
４．『trace cache』及『SRAM快取』達到規格驚人卻無用武之地的１６Ｋ、２００Ｋ。
５．加掛了一個『全功能指令解碼器』，超級增肥藥，well done！

NetBurst 詳細規格表‧圖片可能看不到請直接點一下開新視窗：
NetBurst 微架構核心規格

┌────────────┐
│老祖宗　ＴＥＪＡＳ規格　│
├────────────┤
│第一階快取：２４Ｋ　　　│
│第二階快取：２Ｍ　　　　│
│微指令數量：１６Ｋ uOp　│
│ＳＲＡＭ：２００Ｋ　　　│
├────────────┤
│Ｐｒｅｓｃｏｔｔ　規格　│
├────────────┤
│第一階快取：１６Ｋ　　　│
│第二階快取：１Ｍ　　　　│
│微指令數量：１２Ｋ uOp　│
│指令碼長度：６４位元　　│
│ＳＲＡＭ：１２８Ｋ　　　│
└────────────┘

三太子上身的痴漢水球 blog─ 看不懂嗎？看不懂嗎？看不懂...嗎
我想是 xbox360 吧 ...XD

喜歡 5 收藏引用留言推上首頁檢舉

引用網址：https://home.gamer.com.tw/TrackBack.php?sn=720676
All rights reserved. 版權所有，保留一切權利

相關創作

同標籤作品搜尋：癡漢水球|動態分支|PCADV|NetBurst

【書語】事態每況愈下，觀眾著迷下注「簡輯」

留言共 5 篇留言

林禾：
好專業喔@@

12-27 18:55

無痕之音：
是阿，他的文章專業、幽默、風趣，把這種深奧難懂的東西
寫的很好理解易讀，我是真的這麼認為的。

剩下要寫的還有分支預測機制的精簡文章，比起『trace cache』
追蹤快取的做法，它也是x86程式效能不可或缺的大功臣之一。
x86 目前雖被大量應用在我們個人電腦及IBM 高階伺服器CISC
指令集電腦，但朽木可凋，百足之蟲，死而不僵阿。12-28 00:58