譚弘澤 王 劍

（處理器芯片全國重點(diǎn)實(shí)驗(yàn)室（中國科學(xué)院計算技術(shù)研究所）北京 100190）

（中國科學(xué)院大學(xué) 北京 100049）

分支預(yù)測普遍應(yīng)用于現(xiàn)代CPU 設(shè)計，為處理器提供對分支指令行為的猜測，允許處理器并行執(zhí)行分支之后的指令，從而可提高其指令級并行性，是一項(xiàng)重要而傳統(tǒng)的性能優(yōu)化技術(shù)，至今仍受學(xué)術(shù)界和工業(yè)界的關(guān)注[1-3].一旦發(fā)生錯誤預(yù)測，處理器需要清除其指令執(zhí)行路徑在錯誤預(yù)測后的部分.這些需被清除的部分為錯誤預(yù)測路徑，會浪費(fèi)執(zhí)行資源和功耗.高準(zhǔn)確率的分支預(yù)測可在減少功耗浪費(fèi)的同時保護(hù)指令級并行有效性，從而充分釋放硬件資源的工作潛力，使處理器獲得性能和功耗方面的雙重好處.此外，由于超標(biāo)量技術(shù)提升了處理器指令帶寬，亂序執(zhí)行技術(shù)需要通過指令調(diào)度窗口發(fā)揮作用，這些被普遍采用的技術(shù)進(jìn)一步提高了現(xiàn)代處理器對分支預(yù)測的準(zhǔn)確率要求.

在所預(yù)測分支當(dāng)中，一類特殊的分支為過程返回，由于其返回地址遵循后入先出的順序，具有高度的可預(yù)測性[4].通過對調(diào)用棧的模擬，其專用預(yù)測器將過程返回與其調(diào)用一一匹配，可有效利用其可預(yù)測性，從而被稱為返回地址棧（return-address stack，RAS）[5].由于僅需按照先驗(yàn)規(guī)則匹配返回地址，無需學(xué)習(xí)有關(guān)分支模式的后驗(yàn)知識，該類預(yù)測器擁有理論準(zhǔn)確率高和存儲資源需求小的特點(diǎn).

實(shí)際上，處理器環(huán)境限制了過程返回的預(yù)測準(zhǔn)確率，導(dǎo)致RAS 難以充分利用上述可預(yù)測性，所包含4 類限制因素[6]如表1 所示.其中，錯誤路徑指處理器在錯誤分支后取出的多余指令，可產(chǎn)生對RAS的污染，導(dǎo)致過程返回預(yù)測錯誤.

Table 1 Limiting Factors of RAS Accuracy表1 RAS 準(zhǔn)確率的限制因素

1 相關(guān)工作

1.1 指 令

RAS 可通過指令識別函數(shù)調(diào)用并對函數(shù)返回進(jìn)行預(yù)測.這依賴于現(xiàn)代指令集架構(gòu)（instruction set architecture，ISA）在應(yīng)用程序二進(jìn)制接口（application binary interface，ABI）中為函數(shù)調(diào)用和返回定義了標(biāo)準(zhǔn)行為.例如，根據(jù)各自的ABI 標(biāo)準(zhǔn)，RISCV[7]、OpenRISC[8]和LoongArch[9]等架構(gòu)都允許RAS 通過指令識別函數(shù)調(diào)用并對函數(shù)返回進(jìn)行預(yù)測.其中，各架構(gòu)中指令對應(yīng)的RAS 操作如表2 所示.本文不增加特殊指令，保證設(shè)計可以應(yīng)用在各架構(gòu)中.

1.2 功能分類

若按照功能進(jìn)行分類，RAS 存在分支預(yù)測和安全檢測2 類應(yīng)用方向：

1）分支預(yù)測方向較為傳統(tǒng)，通常保證軟件透明性，關(guān)注面積資源的利用.此類設(shè)計可通過后備預(yù)測[10]方法復(fù)用間接跳轉(zhuǎn)預(yù)測取得性能提升，其涉及文獻(xiàn)[4-5,10-14].

2）安全檢測方向主要將RAS 用于棧溢出攻擊的檢測，其涉及文獻(xiàn)[6,15-21].在此方向，RAS 需要對比確認(rèn)?？臻g返回地址的完整性.其中，文獻(xiàn)[16-21]都使用非猜測RAS，其更新和存儲與用于分支預(yù)測的RAS相獨(dú)立.文獻(xiàn)[6]通過影子狀態(tài)寄存器（shadow state register，SSR）的配合實(shí)現(xiàn)了同時允許分支預(yù)測和安全檢測的RAS.SRAS[17]（secure returnaddress stack）和RASE[6]（return-address stack engine）等設(shè)計通過與內(nèi)存交換數(shù)據(jù)消除棧溢出和上下文切換問題，但需要操作系統(tǒng)內(nèi)核支持.

本文主要探討用于分支預(yù)測的RAS，不引入編譯器和內(nèi)核修改，保證設(shè)計便于工業(yè)界使用.

1.3 存儲結(jié)構(gòu)

若根據(jù)棧的存儲結(jié)構(gòu)進(jìn)行分類，RAS 包含傳統(tǒng)棧和持久化棧[22]2 類：

1）傳統(tǒng)棧按照棧深度存儲返回地址.當(dāng)傳統(tǒng)棧彈出返回地址后，新寫入的返回地址可覆蓋其原有的內(nèi)容，節(jié)約存儲空間.然而，猜測執(zhí)行可能導(dǎo)致有效返回地址則被錯誤地覆蓋，從而引起誤預(yù)測污染.Skadron 等人[12]和Wang 等人[14]提出了對傳統(tǒng)棧地址被污染的修復(fù)方案，但在面積開銷過大的同時仍有性能損失.Sun 等人[13]通過在預(yù)測和提交階段各存儲一套返回地址，實(shí)現(xiàn)了返回地址修復(fù)，但在亂序處理器中無法準(zhǔn)確修復(fù)返回地址.

2）持久化棧按照進(jìn)入順序存儲返回地址.與傳統(tǒng)棧相反，持久化棧先彈出再寫入的新返回地址不會覆蓋原先棧頂，而是占用新的存儲空間.不同于傳統(tǒng)棧，持久化棧的溢出是根據(jù)嵌套個數(shù)而非嵌套層數(shù)，即只要函數(shù)調(diào)用的嵌套個數(shù)超過容量就會發(fā)生溢出.Jourdan 等人[11]所提出的設(shè)計直接使用持久化棧進(jìn)行預(yù)測，雖然避免了誤預(yù)測污染，但是遭受了更嚴(yán)重的棧溢出問題.

傳統(tǒng)棧和持久化棧可以相互搭配.Park 等人[6]利用SSR 存儲對RAS 的修改，從而在允許RAS 使用最新信息的同時避免了誤預(yù)測污染.

1.4 對 比

表3 總結(jié)對比了各RAS 結(jié)構(gòu)的特征，可分為4類問題.

Table 3 Comparison of RAS Structures表3 RAS 結(jié)構(gòu)對比

1）早期RAS 設(shè)計[4-5,11-12]受溢出和誤預(yù)測污染影響，準(zhǔn)確率表現(xiàn)不佳.

2）后續(xù)RAS 設(shè)計[13-14]提高了RAS 的準(zhǔn)確率，但對處理器提了更多的限制.

3）文獻(xiàn)[6]通過SSR 保證了RAS 準(zhǔn)確，但其SSR保存全部飛行指令返回地址的特性要求更大的存儲空間.

4）非猜測RAS[16-21]使用獨(dú)立與分支預(yù)測的存儲空間，存在信息冗余.

為解決這4 類問題，本文提出了一種基于持久化棧的返回地址預(yù)測器——混合返回地址棧（hybrid returnaddress stack，HRAS）.HRAS 對處理器不存在如文獻(xiàn)[13-14]的限制問題.類似于結(jié)合RAS 和SSR[6]的設(shè)計，本文結(jié)合傳統(tǒng)棧、持久化棧和后備預(yù)測[10]3 種預(yù)測方式，同時解耦傳統(tǒng)棧和持久化棧2 部分設(shè)計，不必保存全部飛行指令返回地址.在此設(shè)計的基礎(chǔ)上，本文定量分析返回地址誤預(yù)測的來源，提出一種RAS 同面積準(zhǔn)確率的優(yōu)化方式.此外，傳統(tǒng)棧部分非猜測更新的特性允許與用于安全檢測的非猜測RAS[16-21]共用存儲空間.

2 HRAS 結(jié)構(gòu)設(shè)計

2.1 HRAS 結(jié)構(gòu)總覽

HRAS 包含提交棧（retired stack，RS）和猜測隊列（speculative queue，SQ）2 個子模塊，總體結(jié)構(gòu)如圖1所示.HRAS 通過將子模塊預(yù)測與間接跳轉(zhuǎn)預(yù)測相結(jié)合.子模塊預(yù)測通過組合可在及時更新的同時提供精確的錯誤路徑恢復(fù)，間接跳轉(zhuǎn)預(yù)測緩解了RAS 的容量限制.

Fig.1 The overall structure of HRAS圖1 HRAS 總體結(jié)構(gòu)

HRAS 根據(jù)處理器猜測和提交階段的特點(diǎn)為子模塊選擇了高效的數(shù)據(jù)結(jié)構(gòu).處于猜測階段的指令可被隨時取消.當(dāng)處理器取消部分指令時，為防止錯誤路徑污染，RAS 需要將棧狀態(tài)恢復(fù)為所取消指令的對應(yīng)版本.而可持久化棧能以最小的存儲空間保留棧的中間版本并通過指針指示當(dāng)前版本.通過采用這一數(shù)據(jù)結(jié)構(gòu)，SQ 可通過指針實(shí)現(xiàn)棧版本的精確恢復(fù).與此相反，提交階段的指令總是精確的，不會被取消.根據(jù)這一特點(diǎn)，RS 可采用傳統(tǒng)棧結(jié)構(gòu)，回收歷史版本的存儲資源.

2.2 RS

RS 存儲已提交返回地址，采用傳統(tǒng)棧結(jié)構(gòu)，根據(jù)過程的調(diào)用和返回加減棧頂指針，通過將更新推遲到提交階段避免錯誤路徑污染，包含寫棧頂（top of stack to write，TOSW）指針、讀棧頂（top of stack to read，TOSR）指針、棧底（bottom of stack，BOS）指針、提交表和溢出判斷邏輯5 部分，其結(jié)構(gòu)如圖2 所示.

為在猜測階段提供預(yù)測，RS 根據(jù)猜測控制信號更新選擇TOSR 指針，追蹤猜測階段的過程調(diào)用棧層次，根據(jù)TOSR 指針讀出用于預(yù)測的返回地址.為清除錯誤路徑污染，RS 根據(jù)錯誤恢復(fù)信息或TOSW 指針恢復(fù)其TOSR 指針，保證無猜測過程調(diào)用或返回時其讀寫指針相同.只要中間實(shí)際執(zhí)行的指令不會導(dǎo)致溢出，無論內(nèi)部嵌套的過程調(diào)用或返回是否提交、無論中間有無錯誤預(yù)測路徑，RS 總能根據(jù)TOSR 指針讀出正確的返回地址.例如，錯誤預(yù)測路徑產(chǎn)生的返回地址D，E被取消，而TOSR 也被恢復(fù)到指向返回地址C.此時，無論C是否已提交，只要執(zhí)行流再次返回到了需要返回地址B的位置，RS 就能根據(jù)TOSR提供所需返回地址.

RS 通過溢出判斷邏輯檢查其指針的相對位置關(guān)系，從而檢測返回地址的有效性，在SQ 無效的情況下為HRAS 提供用于選擇最終預(yù)測結(jié)果的有效位.棧的最新和最舊有效元素分別由其TOSW 指針和BOS指針指示.其BOS 指針根據(jù)棧的溢出和下溢出被相應(yīng)加減.二者形成的有效區(qū)間（BOS, TOSW]表示了有效返回地址范圍，可用于溢出判斷邏輯，根據(jù)TOSR 指針判斷返回地址有效性，從而在其失效時，HRAS 可借助間接跳轉(zhuǎn)地址嘗試修復(fù)返回地址.

2.3 SQ

SQ 存儲未提交返回地址，采用支持精確恢復(fù)的持久化棧結(jié)構(gòu)，通過增量更新維護(hù)了猜測執(zhí)行中棧的各個版本，避免對舊有數(shù)據(jù)的修改，包含隊尾指針、隊首指針、棧頂[11]（top of stack，TOS）指針、猜測表和溢出判斷邏輯5 部分，其結(jié)構(gòu)如圖3 所示.其中，隊尾指針、隊首指針和猜測表組成一個循環(huán)隊列，其元素可通過NOS 指針鏈接為單向鏈表，而其TOS 指針指向鏈?zhǔn)綏５漠?dāng)前棧頂.

Fig.3 The structure of SQ圖3 SQ 結(jié)構(gòu)

由于猜測表僅存儲未提交返回地址，其循環(huán)隊列元素的生命周期從進(jìn)入猜測執(zhí)行開始到退出猜測執(zhí)行結(jié)束.在收到猜測過程調(diào)用信號時，為存儲新的猜測返回地址，SQ 分配新的結(jié)點(diǎn)并將之入隊，即在將隊尾指針加1 的同時，將結(jié)點(diǎn)寫入原隊尾指針指向的表項(xiàng).由于指令提交時順序和取指時相同，結(jié)點(diǎn)遵守先入先出的順序，從而，當(dāng)收到提交過程調(diào)用信號時，SQ 通過將隊首指針加1 依次令隊首結(jié)點(diǎn)出隊.此外，當(dāng)復(fù)位或例外等事件發(fā)生時，由于處理器不再有任何未提交的指令，SQ 清空其循環(huán)隊列.

循環(huán)隊列中的鏈?zhǔn)綏１硎玖诉壿婻AS，通過TOS指針指示其棧頂，可提供用于預(yù)測的返回地址.在取指階段，當(dāng)過程調(diào)用時，SQ 創(chuàng)建新的結(jié)點(diǎn)，并將TOS指針指向該結(jié)點(diǎn).其NOS 指針指向原棧頂，即原TOS 指針?biāo)?而當(dāng)過程返回時，SQ 可根據(jù)TOS 指針讀出當(dāng)前棧頂結(jié)點(diǎn)并將其返回地址用于預(yù)測，為實(shí)現(xiàn)彈棧操作，僅需將其TOS 指針指回其讀出的NOS 指針.例如，若SQ 中當(dāng)前鏈?zhǔn)綏ｍ敺祷氐刂窞镈，而新的猜測返回地址為E，則其新建結(jié)點(diǎn)存儲返回地址E和指向D所在表項(xiàng)的指針&D.此后，過程返回可將新結(jié)點(diǎn)的NOS 指針&D重新恢復(fù)到其TOS 指針，從而重新讀出正確的返回地址D.在彈棧后，SQ 隊尾不變，棧頂返回地址恢復(fù)為D.

SQ 在隊列中分配結(jié)點(diǎn)，通過指針鏈接棧結(jié)構(gòu)，實(shí)質(zhì)上是一種持久化棧結(jié)構(gòu)，可通過指針精確恢復(fù)其狀態(tài)，無需恢復(fù)其猜測表數(shù)據(jù)，可節(jié)約功耗和硬件復(fù)雜度.作為持久化棧，SQ 可通過TOS 指針訪問棧的中間版本，使得其找回邏輯棧版本只需恢復(fù)TOS指針.與此同時，為保證取指時進(jìn)入SQ 的返回地址可在提交時按序退出，通過在分支誤預(yù)測后恢復(fù)隊尾指針，該設(shè)計可回收隊尾的無效結(jié)點(diǎn).以圖3為例，猜測表通過4 個結(jié)點(diǎn)分別表示了（D），（E，D），（F，D），（G，F(xiàn)，D）4 個版本的邏輯棧.若從當(dāng)前狀態(tài)取消1 次彈棧操作，SQ 僅需將TOS 指針從&F恢復(fù)為&G.從而，其邏輯棧內(nèi)容會被從（F，D）恢復(fù)為（G，F(xiàn)，D）.又如，若從當(dāng)前狀態(tài)取消2 次壓棧操作，SQ 僅需在恢復(fù)TOS 指針的同時再將隊尾指針從&G后恢復(fù)為&E后.

應(yīng)該借這輛車，能多裝人。北美洲多米尼加警察巡邏時發(fā)現(xiàn)一輛可疑車輛，命令所有乘客下車。這個過程讓所有人大吃一驚，一輛小小的轎車乘坐了18個人，而世界紀(jì)錄才17人！

為提供返回地址的選擇依據(jù)，SQ 通過溢出判斷邏輯計算有效位.其隊尾指針和隊首指針分別指示了循環(huán)隊列的隊尾和隊首，標(biāo)記了其有效區(qū)域.有效位有效即TOS 指針位于循環(huán)隊列有效區(qū)域，可表明所讀出返回地址尚未被提交.其中，猜測表項(xiàng)數(shù)無需超過其有效區(qū)域最大項(xiàng)數(shù)，即處理器猜測執(zhí)行的分支指令容納數(shù)量.然而，當(dāng)猜測表項(xiàng)數(shù)較少時，循環(huán)隊列新分配的隊尾元素可能覆蓋隊首元素，導(dǎo)致返回地址失效.為檢測此類溢出，SQ 可通過額外引入的Max 指針[10]記錄SQ 隊尾的覆蓋位置，并在棧頂處于被覆蓋但尚未被提交的情況下無效化RS 的預(yù)測.

2.4 HRAS 結(jié)果選擇

HRAS 最終預(yù)測結(jié)果選自SQ、RS 和間接跳轉(zhuǎn)預(yù)測器3 處.其選擇根據(jù)預(yù)設(shè)優(yōu)先級和子模塊判斷的有效性.如果SQ 的返回地址有效，那么當(dāng)前棧層次的最新返回地址就是SQ 的返回地址，從而選擇邏輯會優(yōu)先使用來自SQ 的返回地址；否則當(dāng)前棧層次的最新返回地址已提交，從而選擇邏輯需要從RS 獲取返回地址.然而，當(dāng)二者無法提供有效的返回地址時，選擇邏輯使用外部的間接跳轉(zhuǎn)地址作為補(bǔ)充.

利用選擇邏輯，HRAS 可通過猜測和提交2 階段更新信息相互補(bǔ)充，結(jié)合傳統(tǒng)棧、持久化棧和間接跳轉(zhuǎn)預(yù)測器3 種結(jié)構(gòu)的優(yōu)點(diǎn)準(zhǔn)確預(yù)測返回地址.猜測更新具有及時性，但需要棧支持版本恢復(fù).借助于持久化棧結(jié)構(gòu)，通過留存猜測階段指令執(zhí)行窗口中可被恢復(fù)的返回地址，SQ 支持了對棧的恢復(fù).注意到指令一經(jīng)提交則不再會被取消，RAS 不再需要棧的歷史版本，其額外留存返回地址的特性會浪費(fèi)存儲空間.利用提交階段的更新信號的準(zhǔn)確性，RS 避免了對可恢復(fù)性的要求，從而可以采用更加緊湊的傳統(tǒng)棧結(jié)構(gòu).此外，當(dāng)容量不足導(dǎo)致HRAS 失效時，間接跳轉(zhuǎn)預(yù)測器可根據(jù)失效的返回指令地址補(bǔ)充預(yù)測，從而緩解深層次過程調(diào)用返回的HRAS 失效.

3 實(shí)驗(yàn)及數(shù)據(jù)分析

3.1 實(shí)驗(yàn)配置

本文性能評估工作基于EVE（emulation verification engineering）仿真加速器.其中，EVE 仿真加速器是新思科技公司旗下一款硬件驗(yàn)證仿真加速平臺，已被全世界重要的半導(dǎo)體和電子系統(tǒng)公司所采用，可通過掛載文件系統(tǒng)在操作系統(tǒng)中運(yùn)行若干中小型測試程序[23].該平臺可搭載DDR3（double data rate 3）-1000雙通道內(nèi)存，仿真一款商業(yè)CPU 核心，啟動Linux 操作系統(tǒng)并運(yùn)行基準(zhǔn)測試，從而準(zhǔn)確地反映處理器結(jié)構(gòu)和操作系統(tǒng)行為等實(shí)際因素對返回預(yù)測的影響，并保證仿真時間可控.

該商業(yè)CPU 核心基于LoongArch 指令集，其基本配置如表4 所述，可為本設(shè)計提供真實(shí)的處理器核環(huán)境.

Table 4 Basic Configuration Simulated by EVE表4 EVE 仿真基礎(chǔ)配置

為反映實(shí)際應(yīng)用負(fù)載中返回地址的預(yù)測準(zhǔn)確率及其對性能的影響，本文選擇標(biāo)準(zhǔn)性能評估公司（Standard Performance Evaluation Corporation，SPEC）CPU 2000 基準(zhǔn)測試，在真機(jī)上預(yù)先編譯其所有基準(zhǔn)測試程序.所用編譯器版本為GCC（GNU compiler collection）8.3.0.所用編譯選項(xiàng)統(tǒng)一為“-Ofast -static”.為節(jié)約測試時間，本文主要對比其中過程返回次數(shù)最多的9 個基準(zhǔn)測試.如無特殊說明，下文中平均返回誤預(yù)測率均指以上9 個基準(zhǔn)測試過程返回每千條指令誤預(yù)測（mis-predictions per kilo instructions，MPKI）的算術(shù)平均值.

為評估獲取各個基準(zhǔn)測試程序的運(yùn)行時間和返回MPKI，本文通過perf 工具獲取了運(yùn)行時間、動態(tài)指令數(shù)、過程返回次數(shù)和過程返回誤預(yù)測次數(shù)等性能事件計數(shù).其中，perf 是Linux 操作系統(tǒng)下的一款眾所周知的性能分析工具，其基于處理器硬件計數(shù)器.

基于上述評估平臺，本文測試了實(shí)際場景中的RAS 的MPKI.

3.2 重要性分析

本節(jié)分析實(shí)際系統(tǒng)運(yùn)行測試時返回MPKI 對性能的影響，從而說明返回預(yù)測對處理器性能的重要性.

圖4 分析了返回MPKI 對處理器每周期指令數(shù)（instructions per cycle，IPC）的影響，顯示了返回地址預(yù)測對性能的重要性.其中，為了分析從包含隨機(jī)因素的數(shù)據(jù)中提取RAS 結(jié)構(gòu)設(shè)計對性能的統(tǒng)計影響，該分析采用了線性回歸法.實(shí)驗(yàn)表明，當(dāng)返回MPKI值在0.2 以內(nèi)時，返回MPKI 值每增加1 可為該處理器的每周期指令數(shù)帶來約0.07 的損失.即平均每次誤預(yù)測約消耗23 個時鐘周期，其平均延遲明顯大于流水線深度.由于亂序處理器中返回指令前后的其他指令存在并行性，分支誤預(yù)測的實(shí)際性能損失除分支的執(zhí)行延遲外，還包含所破壞的并行性.若設(shè)計在誤預(yù)測時檢測棧溢出攻擊，每次返回誤預(yù)測的開銷可達(dá)500 個時鐘周期[16].

Fig.4 IPC comparison on different return MPKI values圖4 不同返回MPKI 值的IPC 比較

3.3 性能分析

首先，本節(jié)對函數(shù)返回進(jìn)行分類，提出一種返回誤預(yù)測的分解方式.然后，本節(jié)評估了RS 項(xiàng)數(shù)和SQ項(xiàng)數(shù)分別對2 類函數(shù)返回誤預(yù)測的影響.最后，本節(jié)驗(yàn)證了所提分解方式并優(yōu)化了HRAS 的等面積性能.

函數(shù)返回指令可根據(jù)其對應(yīng)調(diào)用指令提交的時間順序分為長距離和短距離2 種延遲類型.其中，長距離返回指直到對應(yīng)調(diào)用指令提交后才需要進(jìn)行預(yù)測的返回指令，短距離返回反之.在本設(shè)計中，長、短距離返回分別需要由RS 和SQ 進(jìn)行預(yù)測.若忽略返回地址預(yù)測對返回指令延遲類型的影響，各返回指令可被固定劃分為長、短距離返回，從而其誤預(yù)測率MRS與MSQ分別只與RS 和SQ 的項(xiàng)數(shù)NRS和NSQ相關(guān).因此，HRAS 的總誤預(yù)測率M近似分解為誤預(yù)測率MRS與MSQ之和，有

為提高等面積性能，HRAS 需要為SQ 和RS 合理分配存儲空間，使得總項(xiàng)數(shù)NRS+NSQ一定時總誤預(yù)測率M最低.根據(jù)式（1）分解關(guān)系，本文可分別測試RS 項(xiàng)數(shù)和SQ 項(xiàng)數(shù)與誤預(yù)測的關(guān)系，并以此計算出最小化總誤預(yù)測率的項(xiàng)數(shù)取值.

在RS 項(xiàng)數(shù)固定為32 的情況下，圖5 對比了不同SQ項(xiàng)數(shù)的返回MPKI 值.測試結(jié)果顯示，SQ＝8 時即可正確猜測實(shí)際測試中的短距離返回，而項(xiàng)數(shù)更小的SQ 會開始產(chǎn)生誤預(yù)測，并在項(xiàng)數(shù)減少到4 時產(chǎn)生的MPKI 值為0.05.因此，根據(jù)評估結(jié)果，即使每4 條飛行分支指令共享1 項(xiàng)猜測表，SQ 都能給出正確的預(yù)測結(jié)果.相比為每條分支指令存儲1 個返回地址的設(shè)計[6,12,14]，該設(shè)計只需25%的存儲空間.

Fig.5 Return MPKI values comparison on different numbers of SQ圖5 不同SQ 項(xiàng)數(shù)的返回MPKI 值比較

在SQ 項(xiàng)數(shù)固定為16 的情況下，圖6 對比了RS不同項(xiàng)數(shù)的返回MPKI 值.結(jié)果顯示，RS 項(xiàng)數(shù)的增加可有效抑制棧溢出，其返回MPKI 值在項(xiàng)數(shù)為32 時可降至0.002.

Fig.6 Return MPKI values comparison on different numbers of RS圖6 RS 不同項(xiàng)數(shù)的返回MPKI 值比較

配合圖5、6 的數(shù)據(jù)，本文通過測試其他配置的MPKI 驗(yàn)證了式（1）的分解關(guān)系.實(shí)驗(yàn)表明，在所測范圍內(nèi)，其預(yù)估的MPKI 值相比于實(shí)際的MPKI 值誤差小3%，遠(yuǎn)小于項(xiàng)數(shù)變化帶來的MPKI 變化，適用于項(xiàng)數(shù)配置的選取.進(jìn)而，本文估計了使得MPKI 值最低的存儲項(xiàng)數(shù)配置并驗(yàn)證了其MPKI 符合預(yù)期.所得各規(guī)模HRAS 中RS 和SQ 的最優(yōu)配置如表5 所示.

Table 5 Best Configures of RS and SQ on Different Sizes of HRAS表5 各規(guī)模HRAS 中RS 和SQ 的最優(yōu)配置

為進(jìn)一步分析HRAS 產(chǎn)生誤預(yù)測的原因，本文對仿真加速器波形進(jìn)行了離線分析.結(jié)果表明，所測系統(tǒng)在時鐘中斷時的上下文切換會污染RAS.若要消除此類誤預(yù)測，RS 需要獨(dú)立存儲內(nèi)核和用戶的返回地址.鑒于此類誤預(yù)測的MIPKI 值已經(jīng)不足0.001，本文沒有分離內(nèi)核和用戶的返回地址存儲.

3.4 性能對比

本節(jié)將HRAS 與已知設(shè)計進(jìn)行了性能對比.根據(jù)該處理器的條件，在現(xiàn)有設(shè)計中進(jìn)行了篩選.SCRAS相比CTRAS，同面積時MPKI 值更高[10]，無需重復(fù)測試.由于本處理器集成時的適配問題，本文也不測試其他設(shè)計.HRAS 存在的問題為：

1）文獻(xiàn)[13]要求處理器順序執(zhí)行分支指令；

2）文獻(xiàn)[14]要求處理器支持暫停取指的功能；

3）文獻(xiàn)[6]要求操作系統(tǒng)內(nèi)核支持；

4）文獻(xiàn)[16-21]不適用于分支預(yù)測.

綜上所述，在本商用處理器核中可用的SOTA 方案包括搭配了后備預(yù)測[10]的簡單RAS[4-5]和CTRAS[12]2 種設(shè)計.本文根據(jù)文獻(xiàn)描述對其進(jìn)行了實(shí)現(xiàn).

圖7 對比了HRAS、簡單RAS 和CTRAS 在項(xiàng)數(shù)同為32 時的返回MPKI.在全部SPEC CPU 2000 基準(zhǔn)測試中，254.gap 是過程返回預(yù)測最為困難的測試.在該測試中，HRAS 的MPKI 值僅為0.01，相比其他預(yù)測器降低了90%以上.綜上所述，HRAS 可有效利用過程返回的可預(yù)測性，在任何測試中均比現(xiàn)有RAS 設(shè)計具有更高的等面積準(zhǔn)確率.

Fig.7 Returning MPKI values comparison among different RAS implementations圖7 各RAS 實(shí)現(xiàn)的返回MPKI 值比較

根據(jù)設(shè)計編譯器的時序檢查，RAS 設(shè)計均不影響處理器的時序關(guān)鍵路徑，不會限制所測處理器的主頻.這主要基于訪問延遲和流水線結(jié)構(gòu)2 方面因素.在訪問延遲方面，HRAS 與其他可用現(xiàn)有方案一樣可并行進(jìn)行溢出檢測與返回地址讀取，且相比處理器中物理寄存器堆等其他結(jié)構(gòu)延遲明顯較??；在結(jié)構(gòu)方面，RAS 可提前將棧頂返回地址鎖存到寄存器中用于預(yù)測，使得其訪問延遲不影響外部結(jié)構(gòu).

3.5 開銷對比

為準(zhǔn)確評估RAS 電路實(shí)現(xiàn)的面積，假設(shè)其目標(biāo)頻率為2.0 GHz，基于設(shè)計編譯器（design compiler, DC）以28 nm 工藝綜合了簡單RAS、CTRAS-1、CTRS-2和HRAS，并進(jìn)行了面積評估.而所評估項(xiàng)數(shù)介于8～32 之間，為處理器中的典型項(xiàng)數(shù)[10].

圖8 對比了多種RAS 設(shè)計在不同面積配置下的MPKI.其中，HRAS 采用如表5 的最優(yōu)配置.在面積約為4.5×103μm2時，HRAS 相比于簡單RAS，MPKI可降低約52%.在面積約為1.1×104μm2時，HRAS 相比簡單RAS 和CTRAS，MPKI 可分別降低約99%和96%.對比結(jié)果表明，HRAS 在相同面積下具有最高準(zhǔn)確率.

Fig.8 Return MPKI values comparison on different areas of RAS implementations圖8 各RAS 實(shí)現(xiàn)在不同面積配置下的返回MPKI 值比較

相比現(xiàn)有設(shè)計，HRAS 具有更好的可擴(kuò)展性.由于更激進(jìn)的現(xiàn)代亂序處理器可容納多達(dá)100 條分支，設(shè)計應(yīng)盡量減少每條分支固定的存儲開銷.HRAS 對處理器檢查點(diǎn)的存儲需求與簡單RAS 相近，無需為每條分支存儲返回地址，可避免在處理器規(guī)模擴(kuò)展時引入過多硬件資源開銷.此外，由于RS 在提交時更新的特性，可以與用于棧溢出攻擊檢測的RAS[16-21]共享存儲空間.

相比現(xiàn)有設(shè)計，HRAS 在同等準(zhǔn)確率時系統(tǒng)開銷更小.相比文獻(xiàn) [13]，HRAS 無需限制處理器分支指令的執(zhí)行順序，適用于現(xiàn)代的亂序處理器.相比文獻(xiàn) [14]，HRAS 避免了多周期修復(fù)帶來的額外阻塞控制，簡化了處理器的設(shè)計要求.相比文獻(xiàn) [6]，HRAS由純硬件實(shí)現(xiàn)，無需操作系統(tǒng)支持，相比本研究所用處理器的取指模塊，即使將返回MPKI 降至0.01 以下，HRAS 仍僅需其面積的4%.

相比其他設(shè)計，HRAS 在功耗方面沒有明顯缺點(diǎn).由于分猜測和提交2 階段存儲，HRAS 在每次過程調(diào)用時需要2 次寫，而在每次過程返回時需要同時讀2 張表.相比于簡單RAS，HRAS 雖然增加了動態(tài)功耗，但是其帶來的準(zhǔn)確率提高能夠降低整個處理器核在錯誤路徑上所消耗的能量.相比于CTRAS，HRAS 將對處理器檢查點(diǎn)返回地址的讀寫換為了對SQ 的讀寫，不會增加動態(tài)功耗.

以上分析和DC 評估實(shí)驗(yàn)的結(jié)果表明，HRAS 在同準(zhǔn)確率時面積最小，同面積時準(zhǔn)確率最高，且具有可擴(kuò)展性.

4 總結(jié)與展望

本文提出了一種混合返回地址棧（HRAS），其基于可持久化棧實(shí)現(xiàn)了精確恢復(fù)，結(jié)合傳統(tǒng)棧結(jié)構(gòu)實(shí)現(xiàn)了高效的返回地址存儲，并基于實(shí)際的處理器核和操作系統(tǒng)測試環(huán)境對其進(jìn)行了評估.結(jié)果表明，該返回地址?？上e誤路徑污染，從而充分利用過程返回的可預(yù)測性，在1.1×104μm2的設(shè)計面積下相比現(xiàn)有RAS 降低96%的返回誤預(yù)測，同面積每周期指令數(shù)相比帶后備預(yù)測的簡單RAS 可提升1%.

作者貢獻(xiàn)聲明：譚弘澤負(fù)責(zé)全文的設(shè)計和實(shí)現(xiàn)，以及文章的撰寫和修改；王劍提出指導(dǎo)意見.