資源描述：
《代碼優(yōu)化之條件分支預(yù)測》由會員上傳分享，免費在線閱讀，更多相關(guān)內(nèi)容在行業(yè)資料-天天文庫。
1、代碼優(yōu)化之優(yōu)化條件分支預(yù)測關(guān)鍵詞:代碼優(yōu)化，條件分支，飽和，MMX，CMOV，掩碼條件分支是編程中經(jīng)常使用的基本操作，然而在某些時候它確可能帶來嚴(yán)重的性能問題。當(dāng)前的CPU都能對條件分支做預(yù)測(動用了龐大的晶體管資源)，如果分支預(yù)測正確，那么條件指令一般只需要花費一個CPU周期，而如果預(yù)測錯誤，那么將可能花費幾十個CPU周期。本文將討論條件分支的一些有效優(yōu)化方法。文章為收集加經(jīng)驗編輯而成的文章，對優(yōu)化條件分支做了較全面的闡述。文章假定的CPU為x86，示例代碼為CC++。A．什么是分支?處理器中分支預(yù)測器設(shè)
2、計的本質(zhì)是在對分支指令行為認(rèn)識的基礎(chǔ)上，提出分支指令的預(yù)測機制，從而減少分支懲罰，也就是分支預(yù)測失敗時導(dǎo)致的流水線清空。一組分支指令組合起來就成為程序的分支行為。分支是編程語言中的常見結(jié)構(gòu)。分支可以分為條件分支和非條件分支。條件分支舉例:條件判斷:if(a>255)a=255;elseif(a<0)a=0;循環(huán):for(i=0;i<1000;++i){...;}while(!bOk){bOk=...;}...對應(yīng)匯編指令的jnz,jg等等非條件分支舉例:函數(shù)調(diào)用(call)、函數(shù)返回(returnret)、
3、軟件中斷(int3)、直接跳轉(zhuǎn)(jmp)...非條件分支又可以進一步分為立即分支指令、間接分支指令和返回分支指令。立即分支指令就是分支的地址就在分支指令中，一般都是直接跳轉(zhuǎn)，比如跳轉(zhuǎn)（jump）這類指令；間接分支就是分支的目標(biāo)地址不在分支指令中，而是從其他寄存器中取得；返回型分支的分支目標(biāo)地址是從鏈接寄存器（Linkregister）或者堆棧中得到，一般是程序返回使用。統(tǒng)計分析程序結(jié)果表明，分支指令中72%是條件分支，17％是無條件立即跳轉(zhuǎn)指令，10％是返回指令，1％是間接分支指令。其中立即分支跳轉(zhuǎn)可以采用B
4、TB（BranchTargetBuffer，分支預(yù)測緩沖區(qū)）這種方式精確預(yù)測，返回型跳轉(zhuǎn)可以采用返回地址棧(RAS1)精確預(yù)測，間接分支跳轉(zhuǎn)的預(yù)測一直沒什么好的辦法。所以分支預(yù)測大量的工作是進行條件分支預(yù)測。B．CPU分支預(yù)測錯誤的懲罰由來流水線是指在程序執(zhí)行時多條指令重疊進行操作的一種技術(shù)。指令流水執(zhí)行是將指令執(zhí)行分成幾個子過程，每個子過程對應(yīng)一個工位，稱為流水級或流水節(jié)拍，這個工位在計算機里就是可以重疊工作的功能部件，稱為流水部件。這些不同的功能部件同時處理不同指令的不同子過程。流水級一個連著一個形成一個
5、流水線，一條指令流過所有的流水級，就完成了他的任務(wù)。他通過提高各流水部件的利用率提高指令的平均執(zhí)行速度。我們先對流水線的級數(shù)與其周期的關(guān)系給出一個公式，一個k級流水線，處理n個任務(wù)總共需要花費“k+(n-1)”個周期，這是因為先是處理第一個任務(wù)就需要k個時鐘周期，k個周期后流水線被裝滿，剩余n－1個任務(wù)只需n-1個周期就能完成。如果同樣數(shù)量的n個任務(wù)不采用流水線處理，那么就需要n＊k個周期，我們把兩者做比，得到另一個概念，叫做流水線加速比C，所以C＝n*k/[k+(n-1)]，當(dāng)n遠遠大于k時，C的值趨進于k
6、，也就是說，理論上k級流水線幾乎可以提高k倍速度，但這僅限于理論。為了加快CPU的處理頻率，現(xiàn)代CPU都設(shè)計了多級流水線，有的甚至有20級以上；當(dāng)CPU遇到分支跳轉(zhuǎn)指令的時候，會做一個預(yù)測，把預(yù)測的分支代碼載入流水線，當(dāng)發(fā)現(xiàn)預(yù)測錯誤的時候，需要清空流水線，重新載入正確的分支到流水線。那么預(yù)測錯誤的代價周期數(shù)至少應(yīng)該和流水線長度相當(dāng)。然而考慮到各級的緩存失效、指令解碼等等，實際損失的周期數(shù)有可能是流水線長度的幾倍！對于非條件分支，一般來說CPU都能得到相當(dāng)高的預(yù)測準(zhǔn)確率，我們主要來討論一下條件分支的預(yù)測。有人可
7、能會說，當(dāng)CPU遇到條件分支時不做預(yù)測不就沒有預(yù)測錯誤的懲罰了嗎?這種流水線空著的懲罰實質(zhì)和每次都預(yù)測錯誤然后清空流水線的代價相當(dāng)，退一步說就算每次隨機選擇一個分支來執(zhí)行也有50%的收益。C．需要優(yōu)化的條件分支當(dāng)前的CPU對各種簡單的條件分支模式都能做出很的預(yù)測，比如奇偶模式：for(inti=0;i<1000;++i){if(a%2==0)do0();elsedo1();}而對于隨機的分支模式，再好的預(yù)測器也不可能做出好的預(yù)測；我們要優(yōu)化條件分支，這些分支代碼應(yīng)該滿足：該分支處于時間熱點上，并且分支預(yù)測錯誤
8、率較高；這樣我們才能得到優(yōu)化的收益(intel的VTune工具可以采樣分支預(yù)測錯誤率)。1．把條件分支移動到熱點外比如前面的那個奇偶循環(huán)模式，假設(shè)CPU不能正確預(yù)測，那么可以嘗試改寫為兩個for循環(huán)，一個處理偶數(shù)，一個處理奇數(shù)。一些圖像處理算法里(比如模板運算卷積運算形態(tài)學(xué)運算等)，經(jīng)常需要判斷邊界像素點，進行特殊處理，可以考略的優(yōu)化方案是把邊界區(qū)域和內(nèi)部區(qū)域分開處理，或者條件允許的話，可以擴大
