寄存器重命名

寄存器重命名是計算機CPU的微體系結構（Microarchitecture）中的一種技術，避免了機器指令或者微操作不必要的順序化執行，從而提高了處理器的指令級並行的能力。

問題定義

計算機的CPU往往用寄存器來保存指令的操作數與結果。x86指令集體系結構有8個整數寄存器，x86-64指令級體系結構有16個整數寄存器，許多RISC體系結構有32個整數寄存器，IA-64有128個整數寄存器. 在小型處理器，這些指令集體系結構寄存器直接對應於寄存器堆中的物理寄存器。

不同的指令可以有不同的執行時間，特別是CISC指令集體系結構上更為明顯。例如，一條讀內存的指令的執行時間，足夠執行幾百條其它指令。因此，在允許多條指令並行執行的情況下，那些指令地址順序靠後的指令，比讀取內存指令更早完成，這就形成了指令執行順序不同於其在程序中的順序。這種亂序執行是高性能CPU提高運算速度的關鍵辦法之一。

考慮下述代碼片段在亂序執行CPU上的運行：

1. R1=M[1024]

2. R1=R1+2

3. M[1032]=R1

4. R1=M[2048]

5. R1=R1+4

6. M[2056]=R1

第4、第5、第6條指令在功能上是不依賴於第1、第2、第3條指令的。但是處理器卻不能在第3條指令完成前去完成第4條指令（在指令流水線上，不能在第3條指令完成前，就提交第4條指令的結果），因為這可能會導致第3條指令把錯誤的數據寫入內存。

通過改變一些寄存器的名字，可以使上例中指令並行執行所受的限制：

1. R1=M[1024]	4. R2=M[2048]
2. R1=R1+2	5. R2=R2+4
3. M[1032]=R1	6. M[2056]=R2

現在，4、5、6號指令可以與1、2、3號指令並行執行，二者沒有依賴問題。這使得程序可以用更短時間完成。

編譯器會盡力檢測出類似這樣的問題，並把不同的寄存器分配給不同的指令使用。但是，受指令集體系結構的限制，匯編程序可以使用的寄存器名字的數量是有限的。很多高性能CPU的實現—微體系結構—有很多物理寄存器，可以在處理器指令流水線執行時把這些指令集體系結構寄存器映射為不同的物理寄存器，從而在硬件級提供了額外的並行能力。

數據衝突

主條目：數據衝突

如果多條指令使用了同一個存儲位置，這些指令如果不按程序地址順序執行可能會導致3種數據衝突（data hazard）:

• 先寫後讀（Read-after-write，RAW）:從寄存器或者內存中讀取的數據，必然是之前的指令存入此處的。直接數據相關（true data dependency）
• 先寫後寫（Write-after-write，WAW）：連續寫入特定的寄存器或內存，那麼該存儲位置最終只包含第二次寫的數據。這可以取消或者廢除第一次寫入操作。WAW相關也被說成是「輸出相關」（output dependencies）。
• 先讀後寫（Write-after-read，WAR）：讀操作獲得的數據是此前寫入的，而不是此後寫操作的結果。因此並行和亂序時無法改善的資源衝突（antidependency）。WAW和WAR可以通過寄存器重命名解決（register renaming），不必等待所有讀操作完成後再執行寫操作，可以保持這個存儲位置的兩份副本：老值與新值。讀老值的操作可以繼續進行，無需考慮那些寫新值甚至寫新值之後的讀新值的操作。產生了額外的亂序執行機會。當所有讀老值操作被滿足後，老值所使用的寄存器既可以釋放。這是寄存器重命名的實質。

任何被讀或寫的存儲都是可以被重名。最常考慮的是通用整數寄存器與浮點寄存器。標誌寄存器、狀態寄存器甚至單個狀態位也是常見的重命名的對象。

內存位置也可以被重命名，雖然這麼做不太常見。全美達的Crusoe處理器的gated store buffer是一種內存重命名。

如果程序沒有立即重用寄存器，它就不需要寄存器重命名這種機制。例如IA-64指令集體系結構提供了128個通用寄存器，就是出於此考慮。但這種努力也遇到了困難：

• 編譯器很難完全避免在不導致程序尺寸大增的同時避免重用寄存器。程序的循環的連續迭代執行就需要複製循環體的代碼以使用不同的寄存器，這種技術叫做循環展開。
• 大量的寄存器，需要在指令的操作數中用很多位去指出，導致程序尺寸變大。
• 很多指令集在歷史上就使用了很少的寄存器，出於兼容原因現在也很難改變。

程序的代碼尺寸增加，會導致指令高速緩存的未命中（cache miss）增加，處理器執行停頓等待從低級存儲中讀入代碼。這對運算性能的影響是致命的。

體系結構寄存器與物理寄存器

編譯器或者匯編器生成的機器語言程序讀寫有限數量的指令集體系結構（ISA）寄存器。例如，Alpha ISA使用32個64位寬整數寄存器，32個64位寬浮點寄存器。這些體系結構寄存器，是程序可以直接訪問的邏輯上的寄存器。如果程序員在調試器中把這個程序暫停，可以觀察到這64個寄存器與一些狀態寄存器當前存儲的值。

一款特定的處理器，實現了這種處理器體系結構。例如Alpha 21264有80個整數寄存器、72個浮點寄存器，作為處理器內物理實現的寄存器。也就是說，Alpha 21264處理器有80個物理存在的位置存儲整數運算的結果，72個位置存放浮點運算的結果。實際上，該款處理器有更多的物理存在的存儲位置，但與寄存器重名關係不大。

下面介紹兩種寄存器重命名方法，區別於為執行單元準備數據的電路。處理器把指令流使用的體系結構寄存器改為用若干位表示的tags所索引的物理寄存器。

tag索引的寄存器堆（tag-indexed register file）是一個很大的寄存器堆，當一條指令發射（issue）給執行單元，源操作數的寄存器tags將發送給物理寄存器堆，其中該tags所對應的物理寄存器的內容被發送給該執行單元。

保留站（reservation station）方法，存在多個小型相關的寄存器堆，通常是每個執行單元的輸入口都有一個物理寄存器堆。發射隊列中的每條指令的每個操作數對應着這個物理寄存器堆的一個存儲位置。當一條指令發射給某個執行單元，執行單元對應的寄存器堆的相應條目被讀出發送給執行單元。

• 體系結構寄存器堆（Architectural Register File）或者引退寄存器堆（Retirement Register File，RRF）：存儲了被提交的體系寄存器的狀態。通過邏輯寄存器的號來查詢這個寄存器堆。重排序緩衝區（reorder buffer）中的引退（retired）或者說提交（committed）指令，把結果寫入這個寄存器堆。
• 遠期寄存器堆（Future File）：處理器對分支做投機執行的寄存器的狀態保存於此。使用邏輯寄存器號來索引訪問。在Intel P6微體系結構，稱之為Active Register File。
• 歷史緩衝區（History Buffer）：用於保存分支時的邏輯寄存器狀態。如果分支預測失敗，將使用歷史緩衝區的數據來恢復執行狀態。
• 重排緩衝區（Reorder Buffer，ROB）：為了實現指令的順序提交，處理器內部使用了一個Buffer。如果在該緩衝區中排在一條指令之前的所有都已經提交，沒有處於未提交狀態的（稱作in flight），則該指令也被提交（即確認執行完畢）。因此重排緩衝區是在遠期寄存器堆之後，體系結構寄存器堆之前。提交的指令的結果寫入體系寄存器堆。

重排緩衝區分為data-less與data-ful兩種。

Willamette's ROB，其條目指向物理寄存器堆（PRF）中的寄存器。此外還包括一些簙記數據。這是第一種亂序執行設計，由Andy Glew在Illinois用HaRRM完成。

Intel P6的ROB，條目包含了數據。沒有單獨的物理寄存器堆。來自ROB的數據在指令提交後將複製到引退寄存器堆（RRF）。

細節：tag索引寄存器堆

這種重命名模式用於MIPS R10000、Alpha 21264，以及AMD Athlon的浮點部分。

在重命名階段，每個被引用的體系結構寄存器（不論是讀還是寫）按其體系結構索引號到重命名文件（remap file）中查找，取出一個tag與一個ready位。如果一個排隊在前的寫操作要把數據寫入該寄存器，但該寫操作尚未執行完，則這個tag是未就緒的（non-ready）。

• 對於寄存器讀，這個tag替換了體系結構寄存器，即這種先寫後讀的寄存器數據相關必須恪守，該讀操作只有在該ready位是就緒之後才可以被分派執行。
• 對於寄存器寫，從一個空閒tag先進先出隊列（free tag FIFO）取出一個新的tag，且這項新的映射條目寫入重命名文件，未來的讀取該體系結構寄存器的指令將指向這個新的tag，即「寫後寫」是一種寄存器數據偽相關，用這種重命名就可去去掉偽相關。這個tag被標記為未就緒，因為寫操作尚未執行。以前為該體系結構寄存器分配的物理寄存器被保存在指令的重排緩衝區（reorder buffer）中；即：以前為該體系結構寄存器分配的物理寄存器可以從重排緩衝區中查到。重排緩衝區是一個先進先出隊列，依照指令解碼的順序（即指令在程序中的先後順序）安排指令引退的順序。

操作數寄存器被重命名後的指令將被放入不同的發射隊列（issue queues）。這些指令等待所需的各種資源（如源操作數對應的物理寄存器）就緒。

當指令執行完，其結果的tags將被公告，發射隊列中用這些公告的tags匹配那些未就緒的tags。一個匹配就意味着該操作數就緒了。重命名文件也去匹配這些公告的tags，從而標記哪些對應的物理寄存器是就緒的。

當發射隊列中的某條指令的所有操作數是就緒的，這條指令就是發射就緒。在每個周期，發射隊列撿出一些就緒指令，發送到功能單元。未就緒指令仍然留在發射隊列中。這種從發射隊列中無序刪除指令，使得發射隊列的電路實現占用面積大、功耗高。

被發射的指令讀取源操作數的tag索引在物理寄存器堆中對應的物理寄存器（忽略掉剛剛公告過的操作數），然後開始執行指令。

指令執行結果寫入目的操作數的tag索引在物理寄存器堆對應的物理寄存器，同時公告給每個功能單元輸入端的旁路網絡（bypass network，即把執行結果「直通」給流水線各個步驟的中間緩衝）。

寫寄存器的指令在引退時，把被寫的目的操作數寄存器使用過的上一個tag放入「空閒tag隊列」中，使得它可以被其它被解碼的指令重用。而該指令的目的操作數寄存器當前對應的tag仍然被占用，因為後面可能還有指令需要讀取當前tag對應的物理寄存器的內容。

一個異常（將導致中斷）或者分支預測失敗導致了重命名文件退回到最後一條有效的指令的重命名狀態，通過組合狀態的快照（在歷史緩衝區）與重排緩衝區中等待順序引退的指令的以前用過的tags。這種機制可以實現恢復任意時刻的重命名狀態。

細節：保留站

主條目：保留站

這種重命名模式用於AMD K7與K8的整數寄存器設計。

在重命名階段，作為源操作數的體系結構寄存器在遠期寄存器堆與重命名文件中查找對應的物理寄存器。如果沒有寫指令還沒有完成寫入該物理寄存器，則說明這個源操作數已經就緒。當這條指令被放入發射隊列，從遠期寄存器堆相應的物理寄存器讀出內容放入保留站中對應的條目。指令對目的寄存器的寫入，在重命名文件中的產生了一個新的、未就緒的tag。tag數通常是按照指令的順序分配，因此不需要空閒tag先進先出隊列。

如同tag索引模式，發射隊列中的未就緒操作數等待匹配的tag公告。但不同於tag索引模式，tag的匹配導致對應的內容數據寫入發射隊列對應的保留站的條目。

被發射的指令從保留站讀取它的操作數，忽略掉那些剛剛公告過的操作數，然後開始執行。保留站寄存器堆通常很小，可能只有8個條目。

指令執行結果寫入重排緩衝區，以及保留站（如果發射隊列有匹配的tags），以及遠期寄存器堆。

指令引退時，複製重排序緩衝區中的值到體系結構寄存器堆。體系結構寄存器堆用於從異常或者分支預測失敗時恢復。

在指令引退時可以識別出異常與分支預測失敗，引起體系結構寄存器堆覆蓋掉遠期寄存器堆的內容，並標記重命名文件中所有寄存器都是就緒。通常，沒有辦法為一條處於解碼與引退之間的指令恢復遠期寄存器堆，因此通常沒有辦法在更早期為分支預測失敗做恢復工作。

比較兩種模式

在兩種模式下，指令被順序送入發射隊列，但從發射隊列移出是亂序的。

保留站具有更好的延遲（latency）性能。因為重命名階段直接獲得寄存器內容，而不是獲得物理寄存器號，再用這個號去獲得內容值。

保留站具有更好的從指令發射到執行的延遲性能。因為每個本地寄存器堆遠小於那種大型的用tag索引的中央寄存器堆。tag產生與異常處理也更為簡單。

與tag索引的簡單的寄存器堆相比，保留站的物理寄存器堆的總規模更大，功耗更大，更為複雜。更糟糕的是，每個保留站的每個條目可以被每條結果總線寫入。例如，每個功能單元具有8條發射隊列條目的處理器，相比於tag索引的模式有9倍的旁路網絡，結果直通（forwarding）需要更大的功耗與面積。

保留站模式在4個位置（遠期寄存器堆，保留站，重排序區、系統結構寄存器堆）保存結果值。而tag索引模式只需要在物理寄存器堆保存結果值。由於結果值來自功能單元，保留站模式必須公告結果到許多存儲位置，用掉了非常多的功耗、面積、時間。如果處理器具有非常精確的分支預測、非常關注執行延遲，保留站也是個很好的選擇。

歷史

IBM System 360 Model 91是早期支持亂序執行的計算機。它使用Tomasulo算法用到了寄存器重命名。

1990，POWER1是第一種使用了寄存器重命名與亂序執行的微處理。

最初的R10000設計既沒有發射隊列壓偏（collapsing），也沒有可變優先權編碼，因此遇到了寄存器資源餓死（starvation）—最老的指令在隊列中一直沒有被發射，直到解碼指令因為缺乏可重命名的物理寄存器而完全停頓，而所有就緒指令都已經發射了。後來修改設計的R12000使用了部分可變優先級編碼來克服此問題。

早期亂序執行處理器並不區分重命名與重排序緩衝區/物理寄存器堆的功能。因此，某些最早期的產品，如Sohi的RUU，Metaflow DCAF，組合了調度、重命名，存儲在一個結構中。

大多數現代處理器的重命名使用了一個映射表，用邏輯寄存器號去索引。例如Intel P6微體系結構。遠期寄存器堆也是如此，並在此存放數據。

但是，更早的處理器使用內容尋址存儲技術實現重命名，例如HPSM RAT，以及存儲器別名表（Register Alias Table）。

某種程度上，亂序執行的微體系結構的故事就是這些內容尋址存儲如何逐步被清除。

Intel P6微體系結構是Intel處理器中第一種亂序執行、寄存器重命名。P6發展出了Pentium Pro、Pentium II、Pentium III、Pentium M、Core、Core 2等處理器系列。

參考文獻

• Smith, J. E.; Pleszkun, A. R. Implementation of precise interrupts in pipelined processors (PDF). Proceeding ISCA '85 Proceedings of the 12th annual international symposium on Computer architecture. 1985 [2012-09-08]. doi:10.1145/327010.327125. （原始內容 (PDF)存檔於2007-04-11）.