偷懶的BTB ？ARM Cortex X1 初探

JamesAslan喜歡畫畫和攝影的硅工碼農(nóng)（滑稽）

前言

隨著現(xiàn)代程序體量的膨脹，處理器面臨越發(fā)巨大的前端壓力；BTB作為前端的核心組件之一，在微架構(gòu)的演進(jìn)中也備受廠商重視。本專欄也不是第一次涉獵BTB相關(guān)的話題了：

JamesAslan：I炮碎碎念：AMD就是遜啦——為什么需要巨大的BTB194 贊同 · 24 評(píng)論文章

為了應(yīng)對(duì)巨大的程序代碼段帶來(lái)的海量跳轉(zhuǎn)指令，大部分高性能處理器核心的BTB容量都在不斷擴(kuò)展，前有IBM z系列史詩(shī)級(jí)的16K+128K（用于mainframe，純服務(wù)器環(huán)境），后有Intel GoldenCove、RaptorCove的6K+12K（用于包括消費(fèi)級(jí)在內(nèi)的商業(yè)環(huán)境）。其他主流廠家也不逞多讓，AMD Zen4（1K+7K）、胎死腹中的三星貓鼬M5、M6等等無(wú)一例外擁有巨大的BTB；唯一的例外恐怕是蘋果，由于其采用了不一樣的前端設(shè)計(jì)故BTB容量較小，這里暫且不討論。ARM公版核心主攻移動(dòng)市場(chǎng)并正向服務(wù)器市場(chǎng)進(jìn)軍，不妨看看ARM在BTB設(shè)計(jì)上采用了什么策略。

本文在8cx Gen3平臺(tái)上探究了ARM Cortex X1 BTB的基本構(gòu)造，并對(duì)其部分怪異表現(xiàn)作出了猜想，對(duì)其部分算法給出了粗糙刻畫；結(jié)論并不收斂，歡迎討論。

背景故事

一臺(tái)開發(fā)機(jī)（Microsoft windows dev kit 2023）的奇妙旅程：康涅狄格 → 紐約 → 香港 → 澳門 → 湛江 → 廣州 → 北京。個(gè)人對(duì)此類設(shè)備抱有極大的好奇與好感，無(wú)論是當(dāng)初的zen/zen+還是后來(lái)的m1；而8cx gen3算是第一代真正可用的高通desktop soc了，自然不能錯(cuò)過。但是微軟在國(guó)內(nèi)并不對(duì)個(gè)人出售dev kit，故只能代購(gòu)轉(zhuǎn)運(yùn)，也就有了它跋山涉水游歷四方的傳奇旅途。我們的實(shí)驗(yàn)平臺(tái)便是8cx gen3，其配備了4顆Cortex X1和4顆Cortex A78，本次我們專注于Cortex X1（下文簡(jiǎn)稱X1）的表現(xiàn)。

正文

測(cè)試構(gòu)建

為了反應(yīng)BTB的容量和速度，我們需要盡量構(gòu)建一個(gè)只有分支指令的測(cè)試；根據(jù)處理器執(zhí)行分支指令的性能，BTB的行為可以被大致推演。BTB的設(shè)計(jì)千奇百怪，其中的學(xué)問也十分深?yuàn)W；但是其基本原理并不復(fù)雜，為了構(gòu)建測(cè)試我們需要用到幾個(gè)BTB的基本特性（簡(jiǎn)略的）：

1. 每個(gè)表項(xiàng)記錄一條（不一定，比如Zen4在部分情況下可以記錄兩條）分支指令的PC（不一定是全PC）和其對(duì)應(yīng)的跳轉(zhuǎn)目標(biāo)地址（不一定是全PC）。

2. 只有Taken分支會(huì)被BTB記錄（不一定）。

既然如此，我們不妨使用一連串非條件跳轉(zhuǎn)，每一條分支指令直接跳轉(zhuǎn)到下一條分支指令。

1: b 1f // b即非條件跳轉(zhuǎn)指令，1f（1 forward）即下一個(gè)標(biāo)號(hào)11: b 1f1: b 1f1: b 1f1: b 1f1: b 1f

BTB的設(shè)計(jì)維度很寬廣，那么會(huì)影響B(tài)TB性能的除了物理上確定的容量和延遲還有什么呢？

1. 組織形式。組相聯(lián)、全相聯(lián)。

2. 索引（index）算法。如果BTB使用了組相聯(lián)設(shè)計(jì)，為了提高其在面對(duì)不同指令排布時(shí)的性能表現(xiàn)，往往會(huì)對(duì)Set的索引index進(jìn)行Hash處理。

3. Tag 算法。為了減少BTB的存儲(chǔ)開銷，其往往不會(huì)存儲(chǔ)分支指令的全PC，因此Tag經(jīng)歷了Hash處理。

4. 替換算法。

5. 預(yù)取算法。

前3點(diǎn)都與指令的PC息息相關(guān)，而指令的PC是由指令的排布決定的，我們只需要改變指令的排布即可。為了改變指令的排布我們可以在分支指令間插入一定數(shù)量的nop指令，它們不會(huì)影響處理器的其他行為，因?yàn)楝F(xiàn)代處理器往往配備了nop指令消除機(jī)制（本專欄中的其他文章介紹過），nop指令在經(jīng)過譯碼級(jí)以后即被消除，不需要被重命名和執(zhí)行。ARM是定長(zhǎng)指令集，指令長(zhǎng)度為4 Byte；在不插入nop指令時(shí)分支指令的密度為1 br per 4 Byte，即緊緊相連。倘若我們想讓所有分支指令的PC的差值為8 Byte，只需在相鄰分支指令間插入1條nop指令。

1: b 1f // b即非條件跳轉(zhuǎn)指令，1f（1 forward）即下一個(gè)標(biāo)號(hào)1 ? nop1: b 1f ? nop1: b 1f ? nop1: b 1f ? nop

讓所有分支指令的PC的差值為16 Byte，只需在相鄰分支指令間插入3條nop指令。

1: b 1f // b即非條件跳轉(zhuǎn)指令，1f（1 forward）即下一個(gè)標(biāo)號(hào)1 ? nop ? nop ? nop1: b 1f ? nop ? nop ? nop1: b 1f ? nop ? nop ? nop1: b 1f ? nop ? nop ? nop

• 對(duì)于全相聯(lián)的BTB，Tag Hash算法會(huì)影響其實(shí)際可用容量。倘若分支指令A(yù)與分支指令B的PC經(jīng)過hash之后的值相等，那它們會(huì)被視為同一條分支指令，進(jìn)而產(chǎn)生沖突。

• 對(duì)于組相聯(lián)的BTB，Index與Tag Hash算法會(huì)影響其實(shí)際可用容量。Index決定了指令會(huì)進(jìn)入哪一個(gè)set；每一個(gè)set的容量上限為路數(shù)，下限由Tag的Hash算法決定，倘若分支指令A(yù)與分支指令B的PC經(jīng)過hash之后的值相等，那它們會(huì)被視為同一條分支指令，進(jìn)而產(chǎn)生沖突導(dǎo)致每個(gè)set的容量小于路數(shù)。

那么隨著我們改變總的分支指令數(shù)和它們的排布時(shí)，BTB的有效容量會(huì)出現(xiàn)抖動(dòng)；一旦有分支指令經(jīng)歷了BTB miss就會(huì)導(dǎo)致分支預(yù)測(cè)錯(cuò)誤，進(jìn)而導(dǎo)致流水線回滾，每條分支指令的平均執(zhí)行時(shí)長(zhǎng)會(huì)間接反映這些事件。實(shí)際上大部分平臺(tái)上可以直接通過perf stat抓取相關(guān)事件來(lái)確認(rèn)BTB行為，但是本人是在dev kit 2023的WSL2內(nèi)進(jìn)行實(shí)驗(yàn)（本就不方便，即便安裝了microsoft wsl的perf也無(wú)法正確識(shí)別8cx gen3的性能計(jì)數(shù)器），X1的perf event又懶得去找（嘿嘿），所以就只能通過執(zhí)行時(shí)長(zhǎng)這一較為間接的指標(biāo)來(lái)判斷了。但是這也導(dǎo)致了本文只能給出極為粗糙的刻畫，因?yàn)橛绊懘蠖畏种е噶顖?zhí)行速度的因素遠(yuǎn)不止BTB，還包括：ICacha，uopCache，ITLB等；想要得到相對(duì)精確的結(jié)論只能通過觀察BTB的性能計(jì)數(shù)器。

此類測(cè)試的構(gòu)建細(xì)節(jié)在本專欄的其他文章內(nèi)有詳細(xì)講解。簡(jiǎn)而言之，整個(gè)程序分為外循環(huán)與內(nèi)循環(huán)，內(nèi)循環(huán)為N組b指令和用于填充的nop指令（指令塊）；我們不僅僅使用1個(gè)指令塊，否則循環(huán)相關(guān)的指令占比過大，它們不是我們計(jì)時(shí)的對(duì)象，需要通過通過放置N個(gè)指令塊稀釋。外循環(huán)為M次循環(huán)（多次執(zhí)行使得總執(zhí)行時(shí)間足夠長(zhǎng)，方便計(jì)時(shí)），則共會(huì)執(zhí)行N*M次指令塊；我們將總執(zhí)行時(shí)長(zhǎng)除以N*M，再通過頻率信息就可以得出每個(gè)指令塊執(zhí)行所需的cycle數(shù)，而每個(gè)指令塊中僅包含1條b指令。

//測(cè)試程序示意，實(shí)際程序?yàn)榍度雲(yún)R編：for(int i=0;i<M;i++){ ? ?//共N組b和nop ? ?1: b 1f ? ? ? nop ? ?1: b 1f ? ? ? nop ? ?...... ? ?1: b 1f ? ? ? nop ? ?1: b 1f ? ? ? nop ? ?1:}

注意：

• 尾部需要放置一個(gè)標(biāo)號(hào)1以便最后一個(gè)b跳轉(zhuǎn)到正確的位置。

• for循環(huán)部分需要使用嵌入式匯編實(shí)現(xiàn)，否則會(huì)引入巨量的棧相關(guān)代碼影響N較小時(shí)的計(jì)時(shí)精確性；倘若使用的是性能計(jì)數(shù)器指標(biāo)而非執(zhí)行時(shí)長(zhǎng)指標(biāo)則無(wú)需注意這一點(diǎn)。

基本信息

運(yùn)行測(cè)試后我們將數(shù)據(jù)整理并繪圖：

上圖包含了海量信息，我們不妨選定橘黃色曲線并觀察其延遲跳變的位置：

1. 當(dāng)分支指令數(shù)量小于96條時(shí)，平均每條分支指令的執(zhí)行延遲僅有0.5 cycle；即此時(shí)ARM Cortex X1每周期預(yù)測(cè)2條taken分支且代價(jià)為0。這是十分了不起的特性，并不是傳統(tǒng)BTB能夠?qū)崿F(xiàn)的?？紤]最樸素的設(shè)計(jì)，（每周期2 taken的BTB當(dāng)然不會(huì)簡(jiǎn)單得如此設(shè)計(jì)，只是借此說(shuō)明這一特性并不平凡）BTB的輸入為當(dāng)周期的PC0，一旦第一條分支指令taken，則PC0會(huì)覆寫為PC1；以PC1作為輸入再次查詢BTB，我們才能得到第二條分支，而這也是一條taken分支；那么我們需要將PC1更新為PC2再進(jìn)入下一周期。上述串行流程都需要在同一個(gè)時(shí)鐘周期內(nèi)完成，可想而知會(huì)給處理器帶來(lái)巨大的時(shí)序壓力，進(jìn)而導(dǎo)致產(chǎn)品無(wú)法運(yùn)行在高頻（ARM Cortex X1 能夠以短流水線運(yùn)行在3+GHz，每周期的時(shí)間并不寬裕）?，F(xiàn)如今的其他消費(fèi)級(jí)處理器中僅有Intel的新產(chǎn)品12代、13代酷睿（GoldenCove等）擁有與之匹敵的特性。96項(xiàng)也對(duì)應(yīng)著X1的L0 BTB容量。

2. 當(dāng)分支指令大于96條小于8192條時(shí)，平均每條分支指令的執(zhí)行延遲僅有1-2 cycle；即此時(shí)X1每周期預(yù)測(cè)1條taken分支的代價(jià)在0-1間波動(dòng)。8192項(xiàng)也對(duì)應(yīng)著X1的L1 BTB容量，容量如此巨大的BTB延遲卻如此之低（1-1.5）簡(jiǎn)直匪夷所思。作為參照，12K項(xiàng)的Intel GoldenCove BTB延遲為2，7K項(xiàng)的AMD Zen4 BTB延遲為1.5-2。

總體而言X1的BTB表現(xiàn)十分驚艷，我們也獲得了許多有趣的信息，比如：當(dāng)前的所有每周期2 taken分支設(shè)計(jì)都只能在L0 BTB的容量范圍內(nèi)生效，應(yīng)該是為此對(duì)L0 BTB進(jìn)行了特別優(yōu)化，用于處理較小的密集分支代碼塊，提高該場(chǎng)景的性能；這一取舍十分合理，密集的taken熱點(diǎn)代碼塊一般不會(huì)很大，提高容量更大的下級(jí)BTB吞吐量不但工程實(shí)現(xiàn)困難，收益也存疑。

疑點(diǎn)重重

仔細(xì)觀察上圖曲線，我們不難發(fā)現(xiàn)一些怪異的現(xiàn)象。在分支最密集的情況下X1的BTB性能特別低，L0 BTB的容量似乎也并不是上文所說(shuō)的96項(xiàng)（下圖所示）。

盡管其他密度曲線的跳變點(diǎn)都在8192附近，但是細(xì)節(jié)上的行為并不一致（如下圖所示）。

顯然是BTB的結(jié)構(gòu)導(dǎo)致了這些現(xiàn)象，那么會(huì)影響B(tài)TB性能表現(xiàn)的除了物理上確定的容量和延遲還有什么呢？

1. 組織形式。組相聯(lián)、全相聯(lián)。
2. 索引（index）算法。如果BTB使用了組相聯(lián)設(shè)計(jì)，為了提高其在面對(duì)不同指令排布時(shí)的性能表現(xiàn)，往往會(huì)對(duì)Set的索引index進(jìn)行Hash處理。
3. Tag 算法。為了減少BTB的存儲(chǔ)開銷，其往往不會(huì)存儲(chǔ)分支指令的全PC，因此Tag經(jīng)歷了Hash處理。
4. 替換算法。
5. 預(yù)取算法。

由于無(wú)法使用性能計(jì)數(shù)器，我們實(shí)驗(yàn)的精度無(wú)法完全解答這些問題；不過我們可以嘗試在有限的精度內(nèi)獲取一些力所能及的信息。

組相聯(lián)or全相聯(lián)

多層次BTB設(shè)計(jì)中大容量的BTB往往是組相聯(lián)的，因?yàn)槲锢砩想y以實(shí)現(xiàn)容量巨大的全相聯(lián)設(shè)計(jì)；小容量的BTB可以選擇全相聯(lián)的設(shè)計(jì)。那么X1的BTB是如何設(shè)計(jì)的呢？為了得出結(jié)論我們需要在更寬的分支間隔范圍內(nèi)進(jìn)行試驗(yàn)。對(duì)于全相聯(lián)BTB，影響其有效容量的只有實(shí)際的物理項(xiàng)數(shù)和Tag hash算法這兩大因素（當(dāng)然替換和預(yù)取算法也會(huì)影響，但目前商業(yè)實(shí)現(xiàn)的算法都較為簡(jiǎn)單，不會(huì)顯著改變有效容量）；只要Tag的Hash算法選取得當(dāng)，我們預(yù)期不會(huì)因?yàn)榉种чg隔的變化而觀測(cè)到有效容量的波動(dòng)。對(duì)于組相聯(lián)BTB，影響其有效容量的還有Set Hash算法這一因素。

在查詢BTB時(shí)，我們首先要獲得分支對(duì)應(yīng)的set號(hào)才能訪問Ram讀出Tag和其對(duì)應(yīng)的跳轉(zhuǎn)目標(biāo)，這就決定了Set號(hào)的生成是時(shí)序敏感的，算法不能過于復(fù)雜。而且Set號(hào)的位數(shù)是固定的，由Ram深度決定。這就意味著當(dāng)我們改變分支間隔時(shí)很容易觸及Set Hash算法的盲區(qū)，進(jìn)而使得部分Ram永遠(yuǎn)無(wú)法被索引，導(dǎo)致有效容量減少。以最簡(jiǎn)單的情形為例，我們截取PC的低2-3位共2 bit作為Set號(hào)（0-1位永遠(yuǎn)為0，因?yàn)槊織l指令的大小為4 Byte）。當(dāng)分支間隔為4 Byte時(shí)：

000000000: b // PC為000000000，二進(jìn)制，Set號(hào)為00000000100: b // Set號(hào)為01000001000: b // Set號(hào)為10000001100: b // Set號(hào)為11000010000: b // Set號(hào)為00000010100: b // Set號(hào)為01

循環(huán)往復(fù)，可知Set號(hào)也在0，1，2，3之間循環(huán)；每一個(gè)Set都有機(jī)會(huì)被訪問到。但是倘若分支間隔為8 Byte：

000000000: b // PC為000000000，二進(jìn)制，Set號(hào)為00000000100: nop000001000: b // Set號(hào)為10000001100: nop000010000: b // Set號(hào)為00000010100: nop000101000: b // Set號(hào)為10000101100: nop000110000: b // Set號(hào)為00000110100: nop000111000: b // Set號(hào)為10000111100: nop

循環(huán)往復(fù)，可知Set號(hào)僅會(huì)在0，2之間循環(huán)；只有一半的Set有機(jī)會(huì)被訪問到，有效容量?jī)H剩一半。我們觀察X1的相關(guān)結(jié)果，觀察的分支間隔范圍為4-2048 Byte：

可以看到L1 BTB有明顯的組相聯(lián)特征，在分支間隔到達(dá)一定程度后，間隔每擴(kuò)大1倍容量縮小1半：

而L0 BTB在（無(wú)視4 Byte時(shí)的情況）8-512 Byte時(shí)都穩(wěn)定表現(xiàn)出96項(xiàng)的有效容量，這似乎是全相聯(lián)的特征。那么為何在分支間隔達(dá)到1024 Byte及以后，L0 BTB的有效容量也出現(xiàn)了衰減了呢？觀察跳變點(diǎn)，每隔1024 Byte一條分支指令會(huì)使代碼段的總大小在跳變點(diǎn)處達(dá)到64 * 1024 = 64 KB；每隔2048 Byte一條指令會(huì)使得代碼段的總大小達(dá)到32 * 2048 = 64 KB；這是一個(gè)巧合嗎？各位可以自行思考（滑稽）。

ITLB

我們一直強(qiáng)調(diào)不使用性能計(jì)數(shù)器難以精確刻畫BTB行為，這里給出一個(gè)例子。

可以看到，在分支間隔較大時(shí)各線條都有多次階躍。以黃線為例，第一次階躍在96附近，超出L0 BTB容量；第二次階躍在128附近；第三次階躍在384；第四次階躍在512。那么第三次階躍為何存在呢？X1的ITLB容量為48 entry，在4KB頁(yè)下384個(gè)512 Byte的代碼塊會(huì)占據(jù)48個(gè)頁(yè)，正好超出ITLB容量，ITLB miss會(huì)極大影響程序運(yùn)行速度。因此使用平均執(zhí)行時(shí)長(zhǎng)會(huì)受到眾多因素干擾，難以精確刻畫BTB行為。

L1 BTB Index

整理我們獲得的數(shù)據(jù)，所有可以享受到8192項(xiàng)L1 BTB的分支間隔是8-32 Byte

分支間隔 （Byte）最大L1 BTB容量 （entry）40881921681923281926440961282048256102451251210242562048128

我們可以計(jì)算出此時(shí)代碼塊的PC bit（會(huì)發(fā)生變動(dòng)的bit的）分布。以8 Byte間隔為例，8192組分支指令會(huì)分布在8 * 8192 Byte的空間內(nèi)，涉及的PC bit為3-15bit（從bit 0開始計(jì)算）；以此類推可得：

分支間隔 （Byte）變動(dòng)PC bit483-15（8192組）164-16（8192組）325-17（8192組）646-18（8192組）1287-19（8192組）

但是當(dāng)分支間隔達(dá)到64 Byte時(shí)，L1 BTB容量只被使用到了1/2：

我們可以借此得知Set Hash算法開始出現(xiàn)瑕疵，一旦PC觸及bit 18的變動(dòng)就不能反映到Set號(hào)上，進(jìn)而導(dǎo)致只能索引到一半的Set號(hào)；隨著PC觸及的bit整體向大于bit 18的方向移動(dòng)，能夠索引到的Set號(hào)不斷減少。因此，樸素的猜想即X1只使用了bit 17及以下的部分進(jìn)行Index Hash，但折疊的方式并不平凡。各位可以自行推演，平凡的折疊方式并不能達(dá)到這樣的效果?？紤]到ARM在CMN-700上炫酷的折疊方式，這里就不展開推導(dǎo)了，會(huì)掉太多頭發(fā)。

L1 BTB Tag

我們之間就注意到，盡管分支間隔為8、16、32時(shí)都能使用到8192項(xiàng)的L1 BTB，但是細(xì)節(jié)行為并不相同：

這三條線之間似乎存在某種關(guān)系，它們的階躍點(diǎn)每次前移1/2，它們的延遲與1 cycle的差值每次提升1倍；這兩個(gè)數(shù)量關(guān)系并不是偶然，而是可能預(yù)示了Tag Hash算法的盲區(qū)。在PC觸及bit區(qū)間移動(dòng)時(shí)，Tag的沖突概率在不斷升高，致使執(zhí)行延遲出現(xiàn)抖動(dòng)。這一猜想目前無(wú)法證實(shí)，因?yàn)?.我們沒有性能計(jì)數(shù)器來(lái)確認(rèn)這是BTB獨(dú)自造成的。2.推演Hash算法會(huì)掉很多頭發(fā)（滑稽）。

L1 BTB way

為了驗(yàn)證路數(shù)我們更換測(cè)試方法，使用更大的分支間隔的同時(shí)只使用1-16條分支指令。這樣一旦出現(xiàn)Hash算法的沖突，執(zhí)行延遲就會(huì)陡增；同時(shí)由于使用的指令數(shù)量極少，無(wú)關(guān)因素也較少。

我們可以粗略得看到，無(wú)論分支間隔多大總有至少4條指令可以被BTB容納，即L1 BTB路數(shù)大于等于4路。觀察紅色部分可見交界處并非陡增，因此替換算法可能不是最樸素的LRU，而是考慮了use bit或其他指標(biāo)。

偷懶的BTB

為何分支間隔為4 Byte的情況下X1的L1 BTB似乎消失了，L0 BTB的容量也并不是上文所說(shuō)的96項(xiàng)呢？我們不妨做出一個(gè)大膽的猜想：PC的bit 2沒有參與Index或Tag的Hash，導(dǎo)致最密集的分支在L1 BTB中一定會(huì)不斷發(fā)生沖突，進(jìn)而無(wú)法有效訓(xùn)練L1 BTB。同樣，我們暫時(shí)無(wú)法驗(yàn)證這一猜想，但是它是符合推演的。從設(shè)計(jì)角度上來(lái)說(shuō)其并非完全不合理，考慮到ARM是使用compare bit的ISA，密集連續(xù)的分支指令可能是極少數(shù)情況。

L0 BTB

將之前的測(cè)試擴(kuò)展到96條指令（L0 BTB容量），

除了4 Byte的情況下X1的L0 BTB容量?jī)H有60項(xiàng)外，其似乎也展現(xiàn)出了組相聯(lián)設(shè)計(jì)的可能性。隨著分支間隔的不斷增加，L0 BTB的有效容量也在不斷減少，每次減少至之前的一半。但是需要注意的是，使用Set與Tag Hash的并不只有BTB，還有ICache與ITLB；從延遲判斷，此處也很可能是觸及了ICache的Hash算法盲區(qū)導(dǎo)致了取指miss；因此4路也可能僅僅代表了ICache的路數(shù)。

后記

從初步試驗(yàn)來(lái)看，Cortex X1的BTB不乏有趣的設(shè)計(jì)，反映了ARM對(duì)處理器前端演化的巧思；在諸如SPEC06、SPEC17的諸多測(cè)試中，Cortex X1的分支誤預(yù)測(cè)率也確實(shí)不遜于Intel等老牌勁旅，讓人十分期待X3乃至X4的前端表現(xiàn)。本次探究也留下了太多懸而未決、模棱兩可的論斷，希望能夠盡快使用性能計(jì)數(shù)器重測(cè)，得到更加可靠的結(jié)論。（本專欄干脆改名叫“我與性能計(jì)數(shù)器的那些事兒”算了23333）

編輯于 2023-02-04 11:23