超標量處理器中寄存器別名表恢復(fù)方法的改進研究

收稿日期：2022-04-13；修回日期：2022-06-08" 基金項目：軍隊科研資助項目

作者簡介：楊思博（1980-），男，北京人，高級工程師，博士研究生，主要研究方向為ASIC與SOC設(shè)計；黎煒桁（1997-），男，四川內(nèi)江人，碩士研究生，主要研究方向為ASIC與SOC設(shè)計；于敦山（1970-），男（通信作者），山東即墨人，教授，博導(dǎo)，博士，主要研究方向為數(shù)字集成電路設(shè)計方法（yuds@pku.edu.cn）；祖靖昭（1996-），女，河北石家莊人，本科，主要研究方向為計算機體系結(jié)構(gòu)；李世平（1987-），男，安徽安慶人，高級工程師，博士，主要研究方向為高性能嵌入式CPU/DSP/ASIC芯片設(shè)計.

摘 要：寄存器重命名是超標量處理器用于提升指令集并行度的重要方法，其基本實現(xiàn)方式是通過寄存器別名表來記錄邏輯寄存器和物理寄存器的映射關(guān)系，當發(fā)生分支預(yù)測錯誤時需要對寄存器別名表中的內(nèi)容進行恢復(fù)。針對于現(xiàn)有的恢復(fù)方法沒有利用重命名的局部性特征，在處理器的指令窗口增加時暴露出實現(xiàn)代價過大的問題，提出了一種基于區(qū)間進行寄存器別名表恢復(fù)的改進型恢復(fù)方法，通過對walk方法的改造，使用區(qū)間計分板來確定需要掃描的地址范圍，并精確地控制每個區(qū)間的掃描，可以大大減小資源浪費。通過對邏輯綜合結(jié)果和性能進行分析，相比于檢查點恢復(fù)的傳統(tǒng)設(shè)計，這種方法使用更少的面積和功耗，達到與檢查點方式恢復(fù)接近的性能，也具有更好的擴展?jié)摿Α?/p>

關(guān)鍵詞：寄存器重命名；寄存器別名表；計分板；重命名歷史掃描

中圖分類號：TN47"" 文獻標志碼：A

文章編號：1001-3695（2022）12-027-3701-05

doi：10.19734/j.issn.1001-3695.2022.04.0222

Improvement study on recovery method of RAT in superscalar processors

Yang Sibo1，Li Weiheng1，Yu Dunshan1，Zu Jingzhao2，Li Shiping2

（1.School of Software amp; Microelectronics，Peking University，Beijing 102600，China；2.Jiangsu Huachuang Microsystem Co.Ltd.，Nanjing 210000，China）

Abstract：Register renaming is a critical component of modern superscalar processor to exploit the instruction level paralle-lism，the foundation of it is to record the mappings between logical registers and physical registers in the RAT.If the branch prediction is error，the RAT needs to recover to the status at the branch.The commonly used recovery methods don’t take advantage of the locality of renaming，as instruction window size increases，all of them exposit the problem of too costly.This paper proposed a region-based rename recovery method，by modify the walk method，used region scoreboards to determine the range of addresses to be scanned，and precisely controlled the scan process in each region，resource waste could be greatly reduced.Through the analysis of synthesis and performance reports，this method’s performance is close to the traditional checkpoint recovery method with much less area and power，and has better expansion potential.

Key words：register renaming；register alias table（RAT）；scoreboard；rename history scan

0 引言

寄存器重命名是超標量處理器挖掘指令級并行性的重要手段，它通過為不同指令的同一邏輯寄存器分配不同的物理寄存器的方式來消除指令流中的WAR相關(guān)和WAW相關(guān)，從而允許更多的指令提前執(zhí)行或并行執(zhí)行［1］。

現(xiàn)代的超標量處理器普遍采用猜測執(zhí)行技術(shù)，即根據(jù)分支預(yù)測的結(jié)果，在尚不能確定預(yù)測是否正確時先執(zhí)行被預(yù)測要執(zhí)行的指令從而提升性能［2］。當分支預(yù)測錯誤出現(xiàn)錯誤或有異常產(chǎn)生時，需要取消所有猜測執(zhí)行的指令，將處理器的狀態(tài)回退到猜測執(zhí)行之前。寄存器重命名單元通過寄存器別名表（RAT）存儲邏輯寄存器與物理寄存器的對應(yīng)關(guān)系，在重命名時會改寫RAT中對應(yīng)項的內(nèi)容，因此在分支預(yù)測錯誤時需要將RAT回退到修改之前的正確狀態(tài)［3，4］。

常用的對RAT進行恢復(fù)的方法有以下三種：

a）通過檢查點為分支指令保存當前RAT狀態(tài)的備份［5］，如果發(fā)現(xiàn)分支預(yù)測錯誤，就使用之前保存的檢查點覆蓋當前的RAT，檢查點的控制簡單，可以快速實現(xiàn)RAT的恢復(fù)，因此得到了廣泛應(yīng)用，IBM的POWER8處理器［6］和加州大學(xué)伯克利分校的BOOM處理器［7］都采用了這種方法。

b）按順序保存重命名操作過程中的所有歷史記錄信息，包括邏輯地址和重命名后的物理地址，在分支預(yù)測發(fā)生錯誤時對重命名歷史記錄表順序掃描來重建RAT的內(nèi)容，這種方法被稱為walk［8］。

c）在ROB中為每條改寫寄存器的指令記錄之前RAT中對應(yīng)項的值，當分支預(yù)測錯誤時順序讀出被取消的項，根據(jù)這些項的記錄對RAT進行恢復(fù)，這種方法稱為ROB回讀［9］。

為了挖掘指令間的并行度，現(xiàn)代處理器普遍有更大的指令窗口，即允許更多的指令同時處于可亂序執(zhí)行的狀態(tài)［10］。指令窗口的擴大需要更多的物理寄存器以進行重命名操作，在進行RAT恢復(fù)時的復(fù)雜度也會上升，此時以上三種方法都暴露出了局限性：檢查點要為每一個分支基本塊都保存一份RAT備份，隨著指令窗口的擴大，指令窗口內(nèi)容納的基本塊數(shù)量也會增加，由此需要更多的檢查點；walk的方法對資源的需求比檢查點少，但是指令窗口的擴大導(dǎo)致重命名歷史記錄項數(shù)的增加，增加了掃描邏輯的時序路徑長度；ROB回讀的項數(shù)受ROB讀端口的限制，指令窗口增大使得回讀的項數(shù)增加，RAT恢復(fù)的時間加長從而阻塞后繼指令的重命名。

針對現(xiàn)有重命名恢復(fù)技術(shù)存在的局限，本文提出了一種基于區(qū)間進行重命名恢復(fù)的設(shè)計方法。該設(shè)計基于傳統(tǒng)的walk重命名恢復(fù)機制，采用多個區(qū)間計分板對重命名歷史表對應(yīng)區(qū)間的具體邏輯寄存器的重命名情況進行記錄，精確地控制每個區(qū)間的掃描，可以大大減小資源浪費，同時減少RAT恢復(fù)過程對性能的影響。

1 相關(guān)工作

RAT的組成結(jié)構(gòu)可以分為RAM型和CAM型兩種，RAM型通過索引邏輯寄存器號得到所需物理寄存器號，CAM型通過索引每一項中保存的數(shù)據(jù)得到所需物理寄存器號。RAM型RAT的項數(shù)是邏輯寄存器的數(shù)目，每項保存當前對應(yīng)的物理寄存器地址，檢查點需要存儲RAT的完整備份；CAM型RAT的項數(shù)是物理寄存器的數(shù)目，每項保存當前對應(yīng)的邏輯寄存器地址和有效位，檢查點只需要保存RAT中每一項的有效位即可［11］。相對于RAM型RAT，CAM型RAT因為需要對每項的內(nèi)容對比要進行索引，在正常進行重命名工作時時序路徑較長，不利于物理寄存器數(shù)量的增長和每周期重命名數(shù)量的增加；但是由于檢查點的實現(xiàn)代價小，對RAT的恢復(fù)開銷無論是面積上還是時序上都更小。

為了在利用CAM型RAT優(yōu)勢的同時避免它的劣勢，Petit等人［12］提出了hybrid RAM-CAM寄存器重命名方法。它使用RAM型RAT進行正常的重命名操作，而采用CAM型的RAT保存檢查點。RAM型RAT的每一項增加了一個有效位，當出現(xiàn)分支預(yù)測錯誤時，RAM型RAT里所有項的有效位被設(shè)為無效，同時使用CAM型RAT保存的檢查點進行恢復(fù)。當后繼的重命名操作訪問到無效的RAT項時，重命名操作被暫停，同時訪問CAM型RAT獲得正確的映射關(guān)系，用這個映射關(guān)系更新RAM型RAT后對應(yīng)項的有效位被設(shè)為有效，重命名繼續(xù)進行。這種方法減少了檢查點的資源消耗，同時避免了CAM型RAT在正常重命名操作時時序路徑過長的問題，但是由于在分支預(yù)測錯誤時整個RAM型RAT無效，而在訪問到無效的RAT項時需要暫停重命名操作進行恢復(fù)，會造成程序運行的停頓，降低了處理器的性能。

Xiao等人［13］根據(jù)大部分分支預(yù)測是正確的情況，提出了根據(jù)分支預(yù)測的信心度，只為部分分支指令保存檢查點的方法。當分支預(yù)測錯誤正好命中保存的檢查點時，可以直接使用檢查點進行恢復(fù)；如果沒有命中檢查點時，先恢復(fù)到最近的檢查點，再使用walk的方式進行恢復(fù)。這種方法結(jié)合了檢查點和walk的恢復(fù)方法，通過檢查點恢復(fù)提高了恢復(fù)速度，通過walk方式在檢查點不能直接恢復(fù)時保證可以正確恢復(fù)，從而減少了檢查點數(shù)量，降低了面積和功耗。但是這種方法在檢查點未命中時使用walk進行恢復(fù)所需時間較長，在分支預(yù)測命中率低的場景下影響處理器性能。

Asilioglu等人［8］提出了為每個邏輯寄存器地址設(shè)立一個重命名FIFO的方法，每一次重命名操作的記錄都被送到FIFO中保存起來，F(xiàn)IFO的尾部是當前最新的映射關(guān)系，當分支預(yù)測錯誤發(fā)生時，通過對FIFO尾指針的恢復(fù)來達成對RAT的恢復(fù)。在這種方法中，檢查點中保存的是RAT中各個重命名FIFO的指針，當FIFO的深度較小時，F(xiàn)IFO指針的寬度小于物理地址的寬度，因此可以縮小檢查點的容量。這種方法有兩個缺點：a）在正常的重命名時需要先根據(jù)邏輯寄存器地址找到對應(yīng)的FIFO，再根據(jù)FIFO的尾指針讀出最新的映射關(guān)系；b）當FIFO滿時重命名工作必須暫停，由于程序中的重命名分布是不均勻的，可能在某段時間內(nèi)會對某些寄存器進行連續(xù)的重命名操作［14］，在這種情況下性能會受到較大的影響。

2 寄存器別名表恢復(fù)的改進方法

2.1 寄存器重命名的局部性

程序?qū)?nèi)存中的數(shù)據(jù)訪問具有局部性，包括時間局部性、空間局部性和程序局部性，而對寄存器的使用也同樣有類似的局部性原理。

圖1是一處理器運行100輪CoreMark［15］基準測試程序時對各個邏輯寄存器重命名恢復(fù)次數(shù)的統(tǒng)計。由圖中可見，RAT的恢復(fù)存在較明顯的局部性特征。這導(dǎo)致了一個現(xiàn)象：當分支預(yù)測錯誤發(fā)生時，往往在RAT中只有部分項失效，對RAT的恢復(fù)實際上只需要對這些項進行，如果能夠在硬件設(shè)計上利用這一點，可以大大減少所需要的硬件資源。

2.2 RAT恢復(fù)時的資源浪費和時間浪費

由于寄存器重命名具有局部性的特性，所以對RAT的恢復(fù)如果不能利用這種特性，則會存在一定程度的資源浪費，即保存了不需要的信息或設(shè)置了不需要的恢復(fù)邏輯；也會存在一定程度的時間浪費，即不必要的恢復(fù)過程。

傳統(tǒng)的檢查點方法對每一個基本塊保存RAT的全部內(nèi)容的備份，但在大多數(shù)程序中大部分分支預(yù)測都是正確的，而且即使預(yù)測錯誤的基本塊可能也只改寫了部分邏輯寄存器地址，因此存在著大量的資源浪費。

采用walk的方式恢復(fù)RAT的內(nèi)容，主要的硬件資源是重命名歷史表的掃描邏輯，掃描鏈的數(shù)量和長度決定了所需的硬件資源。當分支預(yù)測發(fā)生錯誤時，由于局部性可能只有部分邏輯地址需要進行掃描，重命名記錄表中也只有部分項還保持有效，如果要對重命名記錄的所有項掃描，同時要掃描所有的邏輯地址，則掃描鏈的長度、數(shù)量會產(chǎn)生資源浪費，而縮短掃描鏈的長度和數(shù)量雖然會減少資源浪費，但是可能會增加恢復(fù)時間，產(chǎn)生時間浪費。

ROB回讀的方法占用了ROB的端口反復(fù)進行ROB讀取，由于重命名的局部性，可能數(shù)次讀取的內(nèi)容中邏輯地址是重復(fù)的，而真正需要被恢復(fù)的RAT項不能及時得到恢復(fù)，存在著嚴重的時間浪費。

2.3 對walk方法進行改進

如上文所述，寄存器重命名存在局部性，而現(xiàn)有的RAT恢復(fù)方法沒有很好地利用局部性從而存在著資源浪費和時間浪費。在已有的RAT恢復(fù)方法中，walk方法在利用局部性上具有更大潛力，因為walk方法可以通過改變掃描鏈數(shù)量和長度的方式靈活地在硬件資源和恢復(fù)效率中進行權(quán)衡，通過對局部性的探索和利用，用盡可能少和盡可能短的掃描鏈對RAT進行恢復(fù)，可以同時減少資源浪費和時間浪費，從而用較少的硬件資源實現(xiàn)較高的RAT恢復(fù)性能。

walk方法的資源浪費和時間浪費主要體現(xiàn)在兩點：

a）掃描鏈過多。對實際上不需要恢復(fù)的邏輯寄存器地址進行掃描浪費了資源和時間。

b）掃描鏈過長。每次掃描只使用最新的歷史記錄進行恢復(fù)，比它舊的歷史記錄實際上不需要掃描。

要解決問題a），需要在分支預(yù)測出錯時能夠知道哪些邏輯地址需要掃描，又有哪些邏輯地址不需要掃描。要做到這一點，就要能夠?qū)Ω鱾€邏輯地址的重命名信息進行記錄，并根據(jù)記錄推導(dǎo)出需要掃描的邏輯地址列表。

而要解決問題b），就要將重命名歷史記錄表分成多個區(qū)間，每次只掃描其中一個區(qū)間，這樣縮短了掃描鏈的長度，自然節(jié)省了硬件資源，也縮短了時序路徑。

但是當上述兩個問題結(jié)合在一起考慮時出現(xiàn)了新的問題：對重命名記錄表劃分的區(qū)間越小則掃描鏈越短，但是由于每周期掃描項數(shù)減少了，對于給定的邏輯地址，掃描不到需要信息的概率增加了，可能需要更多次的掃描從而增加恢復(fù)時間；對重命名情況進行更精確的記錄可以過濾掉一些不需要的掃描地址，但是又需要更多的硬件資源。

在本文中，對重命名記錄劃分掃描區(qū)間來分別記錄重命名情況，記錄的載體稱為區(qū)間計分板。區(qū)間計分板是一個按邏輯地址排序的位圖，每一位代表對應(yīng)的邏輯地址是否在本區(qū)間內(nèi)進行過改寫。按照對典型程序中分支指令的統(tǒng)計，分支指令的占比在20%～30%，這意味著基本塊的平均長度只有4、5條指令，而掃描區(qū)間的長度根據(jù)掃描鏈的時序要求一般在16～32，這使得按照區(qū)間保存重命名信息的方法相對按照分支指令保存可以大大減少所需要的硬件資源，并精確地控制需要掃描哪些地址。

圖2是對重命名歷史表分區(qū)間進行掃描的示意圖，圖中重命名歷史表被劃分為四個區(qū)間，當進行掃描時，根據(jù)區(qū)間選擇信號控制區(qū)間多選器將被選中區(qū)間中的內(nèi)容整體送到比較器中，與當前的搜索地址進行對比，對比的結(jié)果還需要和各自的區(qū)間使能位相與才能輸出最終的命中信息。

掃描應(yīng)該按照重命名歷史在程序中從新到舊的順序進行，用最新的命中項的內(nèi)容恢復(fù)RAT，但是當掃描按照區(qū)間進行時，掃描鏈與應(yīng)該被掃描的內(nèi)容沒有直接對應(yīng)關(guān)系，在掃描時需要根據(jù)區(qū)間使能位排除不需要掃描的歷史項。區(qū)間使能位有兩個來源：a）重命名歷史記錄的有效位，即重命名指針和釋放指針之間的歷史項；b）由于重命名歷史表是一個循環(huán)利用的隊列，最新的歷史項可能和最老的歷史項出現(xiàn)在同一區(qū)間內(nèi)，比如圖3中最新的基本塊4和最老的基本塊0都在區(qū)間1中，如果基本塊4被取消，則在區(qū)間1中需要分別掃描基本塊4和基本塊0，這兩次掃描的項也需要通過區(qū)間使能位來分別標識。

以區(qū)間為單位進行掃描，可能導(dǎo)致某一邏輯地址需要多次掃描才能獲得結(jié)果，而且掃描鏈數(shù)量減少導(dǎo)致每次掃描的邏輯地址數(shù)量也減少，以上兩點對處理器性能是不利的，需要采用各種優(yōu)化手段來避免負面影響。

2.4 研究基礎(chǔ)平臺

本文對一個基于RISC-V指令集的4發(fā)射的超標量處理器展開，每周期最多需要進行8次讀操作的重命名和4次寫操作的重命名。處理器包含一個64項的ROB，采用統(tǒng)一的物理寄存器文件，物理寄存器數(shù)量為96個，其中動態(tài)分配的32個物理寄存器為與邏輯寄存器對應(yīng)的體系結(jié)構(gòu)寄存器，另外64個物理寄存器為重命名寄存器。

當分支預(yù)測發(fā)生錯誤時，處理器核要取消掉從錯誤分支上取到的指令，并從正確的地址重新加載指令。新加載的指令到達重命名模塊一般需要幾個周期，在此期間進行的RAT恢復(fù)操作不會引起重命名操作的停頓。在參考設(shè)計中，指令重新加載需要3個周期，也就是說在分支預(yù)測錯誤發(fā)生后的3個周期內(nèi)進行的RAT恢復(fù)操作是不會有性能損失的。

本文中作為性能對比的設(shè)計包括加州大學(xué)伯克利分校的BOOM處理器重命名設(shè)計以及基于研究基礎(chǔ)處理器實現(xiàn)的基礎(chǔ)重命名設(shè)計。兩者參數(shù)基本相同，均采用檢查點恢復(fù)方法，為每個分支基本塊保存一個檢查點，共有16個檢查點。當發(fā)生分支預(yù)測錯誤時，根據(jù)出錯預(yù)測所在的基本塊取出對應(yīng)的檢查點覆蓋RAT即完成了恢復(fù)過程。

3 實現(xiàn)方案

3.1 重命名單元基本結(jié)構(gòu)

寄存器重命名單元包含以下主要組件：

a）寄存器別名表（RAT）。保存邏輯寄存器到物理寄存器的最新映射關(guān)系。

b）空閑寄存器列表（free list）。保存當前物理寄存器的狀態(tài)，記錄哪些物理寄存器是沒有被分配的。

c）體系結(jié)構(gòu)寄存器映射表（ARMT）。根據(jù)指令的提交信息，記錄已經(jīng)確認過的邏輯寄存器和物理寄存器的映射關(guān)系，這種映射關(guān)系不會因為分支預(yù)測錯誤或者異常而被更改。

d）重命名歷史表（rename history list）。按照程序順序記錄對RAT的每一次改變，即寫操作的重命名，在ROB提交指令時，如果被提交的指令進行過寫重命名，則會用它的物理地址更新ARMT，而ARMT中對應(yīng)項的原有內(nèi)容會被送到free list作為新的空閑寄存器。

e）恢復(fù)模塊。用于在分支預(yù)測錯誤或異常發(fā)生時恢復(fù)RAT和free list的內(nèi)容。

圖3描繪了作為基礎(chǔ)設(shè)計的寄存器重命名單元的基本結(jié)構(gòu)。目標處理器的RAT是一個4寫8讀的寄存器文件，每周期可以支持8次讀重命名和4次寫重命名；重命名歷史表是一個64項4入4出的FIFO隊列，每周期可接受4個寄存器寫重命名的結(jié)果，并根據(jù)ROB的提交情況最多發(fā)出4個物理寄存器地址作為新的體系結(jié)構(gòu)寄存器進入ARMT；ARMT是一個4讀4寫的寄存器文件，每個周期從重命名歷史表獲得4個物理地址，并將對應(yīng)項原有的物理地址讀出來送到free list；free list是一個64項4入4出的FIFO隊列，每周期可以輸出四個空閑物理寄存器地址，并同時接受重命名歷史表釋放出來的4個物理地址作為新的空閑寄存器。

3.2 恢復(fù)模塊總體結(jié)構(gòu)

恢復(fù)模塊的主要結(jié)構(gòu)如圖4所示，它主要包含重命名歷史表、區(qū)間計分板、區(qū)間多選器、掃描地址產(chǎn)生器和重命名歷史掃描鏈。

當發(fā)生分支預(yù)測錯誤時，掃描地址產(chǎn)生器根據(jù)各個區(qū)間計分板產(chǎn)生各個掃描鏈的區(qū)間選擇信號和掃描地址；區(qū)間多選器根據(jù)區(qū)間選擇信號把選定區(qū)間的歷史記錄（包括使能位、邏輯地址和物理地址）送到區(qū)間掃描鏈；區(qū)間掃描鏈將掃描地址產(chǎn)生器產(chǎn)生的掃描地址和各項歷史記錄的邏輯地址進行比較，如果有命中項，選出最新的命中項的物理地址對RAT進行恢復(fù)；如果沒有命中項，則從ARMT中讀出與掃描地址對應(yīng)的物理地址對RAT進行恢復(fù)。

重命名歷史表共有64項，被平分成兩個區(qū)間。重命名歷史表有兩個指針：重命名指針指向下次重命名操作記錄將被存儲的位置；而釋放指針指向下一個將要從重命名歷史表中釋放的記錄所保存的位置。

重命名歷史掃描鏈一共有四個，它們彼此負責(zé)的邏輯地址互不重疊：掃描鏈0的地址從［0，4，8，12，16，20，24，28］中選擇；掃描鏈1的地址從［1，5，9，13，17，21，25，29］中選擇；掃描鏈2的地址從［2，6，10，14，18，22，26，30］中選擇；掃描鏈3的地址從［3，7，11，15，19，23，27，31］中選擇。每條掃描鏈每周期可掃描一個區(qū)間即32項，并輸出最新命中項的物理地址。由于不同的邏輯地址的重命名情況不同，同一時刻不同的掃描鏈可以掃描不同的區(qū)間，它們彼此是獨立工作的。

對RAT進行恢復(fù)的另一來源是ARMT，當掃描鏈在所有的區(qū)間都沒找到某一邏輯地址的命中項，會從ARMT中讀出當前對應(yīng)的物理地址寫入RAT中進行恢復(fù)。

3.3 區(qū)間計分板

區(qū)間計分板保存重命名歷史表中對應(yīng)區(qū)間的重命名位圖，每一位表示對應(yīng)的邏輯寄存器是否在本區(qū)間內(nèi)被改寫過。由于重命名歷史表是循環(huán)利用的，最新的重命名歷史項在回滾后可能和最老的歷史項處于同一個區(qū)間中，為了對它們進行區(qū)分，區(qū)間計分板的數(shù)目比重命名歷史區(qū)間多一個，這樣可以分別記錄同一區(qū)間中最老的項和回歸后的最新項的重命名情況，在掃描時也需要分別進行掃描。

由于掃描是按照重命名歷史記錄由新到舊的順序進行的，所以圖4中的3個區(qū)間計分板被按照從舊到新的順序分為3層，其中第0層對應(yīng)當前釋放指針所在的區(qū)間，第1、2層從順序上都比前一層更新。由于第0層記分板永遠對應(yīng)釋放指針所在區(qū)間，所以當釋放指針向下一個區(qū)間移動時，第0層記分板也換到下一個區(qū)間，它的內(nèi)容變?yōu)樵?層記分板的內(nèi)容，帶動第1層記分板的內(nèi)容變?yōu)樵?層記分板的內(nèi)容，而第2層記分板的內(nèi)容將被無效。

3.4 掃描地址產(chǎn)生器

掃描地址產(chǎn)生器控制各個掃描鏈的掃描過程，它要為每條掃描鏈提供掃描的區(qū)間選擇和掃描的邏輯地址兩個指示。掃描是從最新記錄所在的區(qū)間，即重命名指針所在的區(qū)間開始的。掃描地址根據(jù)重命名指針的位置和區(qū)間計分板的內(nèi)容為每一條掃描鏈產(chǎn)生各個區(qū)間的掃描列表，每個區(qū)間的掃描列表記錄該區(qū)間需要被掃描的所有邏輯地址，當一個區(qū)間的掃描列表內(nèi)所有的邏輯地址都完成掃描，就會掃描下一個掃描列表所對應(yīng)的區(qū)間。根據(jù)分支預(yù)測錯誤時回滾前后重命名指針所在的區(qū)間位置不同，掃描列表的數(shù)量和產(chǎn)生方式也不同，表1列出了不同情況下掃描列表的產(chǎn)生方式，表中橫縱坐標分別代表回滾前和回滾后重命名指針的位置，1st、2nd、3rd分別代表第1、2、3次掃描所依據(jù)的掃描列表，“amp;”代表對兩個區(qū)間計分板的內(nèi)容做邏輯與操作。

掃描地址產(chǎn)生器還要接收寫操作重命名的信息，如果那個邏輯地址在RAT恢復(fù)過程中進行了寫的重命名，則寫重命名的結(jié)果就是該地址最新的映射關(guān)系，因此該地址會被從所有的掃描列表中刪除。

由于對RAT的恢復(fù)和寫操作重命名復(fù)用RAT的寫端口，所以掃描地址產(chǎn)生器還要判斷寫端口是否發(fā)生沖突，當沖突產(chǎn)生時，寫操作重命名的優(yōu)先級更高，RAT的恢復(fù)將被暫時屏蔽，掃描到的地址不會被從掃描列表中刪除。

3.5 重命名歷史掃描鏈

重命名歷史掃描鏈內(nèi)部包含比較器陣列和選擇器陣列。比較器陣列將待掃描區(qū)間內(nèi)所有歷史項的邏輯地址分別于掃描地址進行比較，同時檢測對應(yīng)的區(qū)間使能位，只有地址相等且區(qū)間使能位為1時才被視為命中，掃描鏈按照比較項的排列順序進行掃描，當有多個命中項時，選擇序號最高的命中項作為恢復(fù)項。選擇器陣列根據(jù)比較器陣列輸出的恢復(fù)項序號選擇該項的物理地址，作為在RAT中與掃描地址對應(yīng)項的恢復(fù)內(nèi)容輸出。

當掃描鏈進行掃描時，掃描地址也會被用于讀取ARMT，如果掃描鏈沒有發(fā)現(xiàn)命中項，且之后的掃描列表中也沒有該地址，則會使用ARMT的讀出結(jié)果作為對RAT的恢復(fù)內(nèi)容。

重命名歷史掃描可以用較小的代價提升效率：由于一條掃描鏈的掃描地址只有八個候選項，且分別對應(yīng)于邏輯地址的［4：2］位，在掃描時可以分別對這3位的八個編碼進行對比，輸出命中結(jié)果，但是只有在命中當拍被選中的邏輯地址時會將對應(yīng)的物理地址輸出。由于物理地址的多選器數(shù)量并沒有增加，所以對面積的增加很小，卻可以立即獲知當前計分板之內(nèi)所有的寄存器地址是否命中，從而在下次掃描中直接排除掉不存在的地址。但是被排除的掃描地址要滿足兩個前提：a）第0層區(qū)間計分板中的地址不能被排除；b）被排除的地址一定要在下級區(qū)間計分板中存在。存在這兩個前提是因為在要恢復(fù)的內(nèi)容可能保存在ARMT中，因此必須保留讀取ARMT的機會。下文為了描述簡單，將上述方法稱為探針。

4 測試及優(yōu)化

4.1 定點程序初步測試

基于目標處理器，使用CoreMark測試程序評估其在定點程序中的表現(xiàn)。每次測試執(zhí)行100次循環(huán)，通過性能計數(shù)器在循環(huán)過程中獲取各種性能相關(guān)的數(shù)據(jù)，作為評估和改進的基礎(chǔ)。表2描述了獲得的性能數(shù)據(jù)，其中第1行是只使用記分板的情況，第2行是加入探針后的情況。

表中的數(shù)據(jù)最重要的是阻塞周期/預(yù)測錯誤次數(shù)，它描述了由于對RAT的恢復(fù)還沒有完成而阻塞新的重命名的嚴重程度。實驗結(jié)果表明，在不使用探針的情況下，新的重命名模塊平均每輪CoreMark測試程序阻塞173個周期，平均每次分支預(yù)測錯誤阻塞0.057個周期，在分支預(yù)測錯誤過程中重命名恢復(fù)所占用的時間基本可以忽略不計。而加入探針機制的改進型設(shè)計將平均每輪CoreMark循環(huán)的阻塞周期降為113個周期，平均每次分支預(yù)測錯誤阻塞周期降低到0.037 4，可見這個小改進可以極大地提高恢復(fù)效率，減少阻塞周期。

4.2 進一步改進

由于計分板與基本塊不存在直接對應(yīng)關(guān)系，導(dǎo)致會有一些計分板中記錄的寄存器映射關(guān)系實際上沒有受到分支預(yù)測錯誤的影響，不需要進行掃描。

考慮到這種情況，可以設(shè)置一個RAT項有效范圍表，它記錄的是RAT中的當前映射，即各個邏輯寄存器最后一次重命名所在的基本塊，當分支預(yù)測發(fā)生錯誤時，如果其最后一次重命名所在的基本塊沒有被取消，則該寄存器在RAT中的映射不需要被恢復(fù)。表2的第三行是進一步改進前后的CoreMark性能對比，從表中可以看出，在增加了RAT項有效范圍表后，平均每次分支預(yù)測錯誤的阻塞周期由0.037 4減少到了0.018 64，減少了超過50%，而執(zhí)行程序的時鐘周期數(shù)也進一步減少。

4.3 浮點程序測試

此設(shè)計同樣適用于浮點寄存器重命名，使用Whetstone［16］測試程序評估其在浮點程序中的表現(xiàn)，測試執(zhí)行100次循環(huán)，共1 187 055條指令，通過性能計數(shù)器收集數(shù)據(jù)進行評估。表3描述了浮點程序中重命名阻塞的情況。由表中數(shù)據(jù)可知，無論是哪種配置都基本上不存在阻塞。

4.4 面積和功耗測試

對包括基礎(chǔ)重命名，BOOM重命名設(shè)計在內(nèi)的不同設(shè)計方案進行邏輯綜合，對其面積、功耗進行評估。實驗采用Synopsys Design Compiler Q-2019.12綜合工具，臺積電TSMC 28 nm工藝庫進行綜合。表4描述了邏輯綜合的結(jié)果。

綜合結(jié)果表明，采用檢查點方案的BOOM重命名設(shè)計和基礎(chǔ)重命名設(shè)計的面積均在30 000 μm2以上，功耗也在20 mW以上。相比較，加入探針機制和RAT項有效范圍表后的改進型重命名設(shè)計的面積降低了36%，功耗降低了60%，而平均次分支預(yù)測錯誤只有0.018 6次阻塞。相對于傳統(tǒng)的檢查點恢復(fù)方式，新的RAT在對性能損失很小的情況下大大降低了面積和功耗。

5 結(jié)束語

本文針對傳統(tǒng)寄存器重命名無法充分利用寄存器重命名局部性，導(dǎo)致重命名恢復(fù)在時間和面積上存在浪費的問題，提出了一種基于區(qū)間進行重命名恢復(fù)的改進型設(shè)計。

該設(shè)計基于傳統(tǒng)的walk重命名恢復(fù)機制，采用多個區(qū)間計分板對重命名歷史表對應(yīng)區(qū)間的具體邏輯寄存器的重命名情況進行記錄，當發(fā)生分支預(yù)測錯誤時，根據(jù)計分板生成掃描列表，歷史表掃描鏈根據(jù)掃描列表從新到舊對重命名歷史表進行掃描。重命名恢復(fù)過程中不會阻塞正常指令重命名和提交，僅在讀操作重命名的邏輯寄存器與待恢復(fù)的邏輯寄存器相同，產(chǎn)生沖突時才會對重命名進行阻塞。

通過CoreMark基準測試程序?qū)υ撛O(shè)計性能進行評估，與全檢查點設(shè)計相比，在基本不增加關(guān)鍵路徑延遲的情況下，改進型設(shè)計具有較少的分支預(yù)測錯誤恢復(fù)阻塞周期數(shù)，達到與基礎(chǔ)設(shè)計基本一致的性能。邏輯綜合結(jié)果表明，此設(shè)計面積更小，功耗也更低。另外，對于更大深度的ROB，更多指令發(fā)射的處理器設(shè)計，基于區(qū)間的重命名恢復(fù)方式可以通過增加恢復(fù)區(qū)間的方式進行適配，在時序和面積上也有更好的擴展?jié)摿Α?/p>

參考文獻：

［1］Spasov D.Sequential register renaming［C］//Proc of the 43rd International Convention on Information，Communication and Electronic Technology.Piscataway，NJ：IEEE Press，2020：118-122.

［2］Kocher P，Horn J，F(xiàn)ogh A，et al.Spectre attacks：exploiting speculative execution［C］//Proc of IEEE Symposium on Security and Privacy.Piscataway，NJ：IEEE Press，2019：1-19.

［3］李文哲.亂序超標量處理器寄存器重命名機制的設(shè)計與優(yōu)化［D］.長沙：國防科學(xué)技術(shù)大學(xué)，2015.（Li Wenzhe.Design and optimization of the register renaming mechanism in an out-of-order superscalar processor［D］.Changsha：National University of Defense Technology，2015.）

［4］張軍超，張兆慶.指令調(diào)度中的寄存器重命名技術(shù)［J］.計算機工程，2005（23）：8-10.（Zhang Junchao，Zhang Zhaoqing.Register renaming in instruction scheduling［J］.Computer Engineering，2005（23）：8-10.）

［5］Akkary H，Rajwar R，Srinivasan S T.Checkpoint processing and recovery：towards scalable large instruction window processors［C］//Proc of the 36th Annual IEEE/ACM International Symposium on Microarchitecture.Washington DC：IEEE Computer Society，2004.

［6］Sinharoy B，Van Norstrand J A，Eickemeyer R J，et al.IBM POWER8 processor core microarchitecture［J］.IBM Journal of Research amp; Development，2015，59（1）：1- 21.

［7］Zhao J，Korpan B，Gonzalez A，et al.Sonic boom：the 3rd generation Berkeley out-of-order machine［C］//Proc of the 4th Workshop on Computer Architecture Research with RISC-V.2020.

［8］Asilioglu G，Kaya E M，Ergin O.Complexity-effective rename table design for rapid speculation recovery［C］//Proc of International Conference on Architecture of Computing Systems.Berlin：Springer，2010：15-24.

［9］Akl P，Moshovos A.Turbo-ROB：a low cost checkpoint/restore accele-rator［C］//Proc of the 3rd International Conference on High Performance Embedded Architectures amp; Compilers.Berlin：Springer，2008：258-272.

［10］Tabani H，Arnau J M，Tubella J，et al.A novel register renaming technique for out-of-order processors［C］//Proc of the 24th International Conference on High Performance Computer Architecture.Washington DC：IEEE Computer Society，2018：259-270.

［11］Safi E，Moshovos A，Veneris A G.A physical level study and optimization of CAM-based checkpointed register alias table［C］//Proc of ACM/IEEE International Symposium on Low Power Electronics amp; Design.New York：ACM Press，2008：233-236.

［12］Petit S，Ubal R，Sahuquillo J，et al.Efficient register renaming and recovery for high-performance processors［J］.IEEE Trans on Very Large Scale Integration Systems，2014，22（7）：1506-1514.

［13］Xiao Jianqing，Lou Mian，Li Wei，et al.Implementing fast recovery for register alias table in out-of-order processors［C］//Proc of the 2nd International Symposium on Instrumentation amp; Measurement，Sensor Network and Automation.Piscataway，NJ：IEEE Press，2013：821-824.

［14］Liu Xiahua，Yang Qinghong，Tao Miao，et al.An efficient register renaming technique with delayed allocation and register packing［C］//Proc of the 27th IEEE International Conference on Electronics，Circuits and Systems .Piscataway，NJ：IEEE Press，2020.

［15］王芳良，張偉功，于立新，等.基準集在嵌入式系統(tǒng)性能分析中的應(yīng)用［J］.計算機工程與設(shè)計，2015，36（1）：115-119，126.（Wang Fangliang，Zhang Weigong，Yu Lixin，et al.Applications of benchmark in embedded system performance analysis［J］.Computer Enginee-ring and Design，2015，36（1）：115-119，126.）

［16］Raju P S，Govindarajulu P.Performance improvement of multi-core architecture using whetstone application in Linux［J］.International Journal of Computer Science amp; Network Security，2013，13（10）：47-53.