基于狀態機控制的硬件Page Walk 方案與實現?

路冬冬 王炳凱 杜 鑫，

（1.上海高性能集成電路設計中心 上海 201204）（2.電子科技大學電子科學與工程學院 成都 610054）

1 引言

現代操作系統通常采用頁表結構管理每個進程的虛地址空間，實現虛地址到物理地址的映射。在微處理器中，訪問物理地址標記（Physical Tag，PTag）的Cache時，虛實地址代換通常處于Cache訪問的關鍵路徑上，為提高虛地址到物理地址代換的速度，高性能處理器通常會使用旁路轉換緩沖（Translation Lookaside Buffer，TLB）緩存虛實地址的映射關系。TLB 通常采用全相聯或組相聯的結構實現，訪存請求在訪問Cache 的同時，并行查找TLB 進行虛實地址代換，將訪問TLB 代換得到的物理地址與Cache 的PTag 進行比較，判斷是否命中Cache，以及組相聯Cache 的命中路號［2］。由于TLB的訪問處于Cache命中判斷以及組相聯Cache讀出數據路選的關鍵路徑上，因此其訪問延遲直接影響微處理器的性能及工作頻率。

當訪存請求不命中TLB（TLB Miss）時，通常需要通過逐級查找頁表（Page Walk）的方式，獲取代換后的物理地址，并將查找頁表得到的物理地址和虛地址的映射關系裝入TLB 中。頁表查找的開銷通常是很大的，例如，在一個支持4 級頁表的處理器中，Page Walk 通常需要4 次訪存［1］，在支持虛擬化的處理器中，Page Walk的訪存次數會更多，相關研究表明，實際應用課題的很大一部分運行時間被用于Page Walk（最高可達50%［3］）。發生TLB Miss時的處理有兩種基本思路，一種是完全交給軟件處理，顯式使用訪存指令逐級訪問頁表，典型代表是Sparc 處理器和MIPS 處理器［4］；另外一種是硬件自動生成訪存請求，逐級訪問頁表，并負責將虛地址和物理地址的映射關系裝入TLB 中，典型代表是x86處理器［4］。

本文提出一種基于狀態機控制的硬件自動查找頁表并裝填TLB 的方案，同時，結合頁表結構Cache（Page Structure Cache，PSC），對Page Walk 的控制狀態機進行優化，進一步提升硬件Page Walk的性能。

2 相關研究工作

TLB 是微處理器中一個十分重要的部件，對于物理地址標記的Cache，其每一次訪問都需要同時訪問TLB 進行虛實地址代換，因此，TLB 的訪問延遲、命中率及不命中時處理開銷對處理器的性能具有十分重要的影響。

2.1 提高TLB的命中率

使用大頁，可以在保持TLB容量相對不變的情況下，有效提升TLB 的命中率，采用大頁的負面影響是存儲空間的管理不夠靈活，特別是當前操作系統普遍以頁面為粒度管理存儲空間，大頁的使用會造成多方面的負面影響［5］，因此，現代微處理器普遍支持多種粒度的頁面，操作系統可以根據具體課題的實際需求自主選擇頁面的粒度［6］。

當支持多種粒度的頁面時，TLB 一般采用全相聯的結構實現。全相聯結構的缺點是訪問延遲和功耗較大，特別是對于大容量的TLB，其訪問延遲往往是處理器頻率提升的瓶頸。為了在保持較低訪問延遲的同時，能夠使用較大TLB容量以提高其命中率，大多數處理器會使用兩級或三級TLB的結構，容量較小的一級TLB 采用全相聯的結構，容量較大的二級TLB和三級TLB采用組相聯的結構。

TLB 的預取是另外一種能夠有效提升TLB 命中率的技術，TLB 預取和數據預取具有很多相似之處，一種常見的思路都是通過對訪存地址的數據流模式進行識別，預測并預取即將訪問頁面；常見的模式包括順序地址流、跨步地址流以及鏈式地址流等。Kandiraju［7］等提出一種對頁面間隔進行預測（Distance Prefetching，DP）的預取技術，例如，發生TLB Miss的頁面虛地址分別是“10，11，13，14，16”，可以發現頁面間隔分別是“1，2，1，2，…”，因此，可以預測即將發生TLB Miss 的頁面時17 和19；TLB預取可以有效降低TLB Miss率。

2.2 降低TLB Miss的處理開銷

相比軟件處理TLB Miss 的方式，硬件處理TLB Miss可以顯著降低TLB Miss對性能的影響，以Intel 和AMD 為代表的處理器，均采用硬件處理TLB Miss 的方法。為了進一步加快硬件Page Walk的速度，主流的商業處理器普遍會使用存儲管理單元 Cache（Memory Manager Unit Cache，MMU Cache）。

以Intel 為代表處理器采用頁表結構Cache（Page Structure Cache，PSC）加速硬件Page Walk 的速度。頁表結構Cache 的結構類似于TLB，存儲部分虛地址及對應的頁表基地址的映射關系；其優點是在進行Page Walk 時，命中頁表結構Cache 可以直接減少訪存的次數。

以AMD 為代表的處理器采用頁表查找過程Cache（Page Walk Cache，PWC）加速硬件Page Walk的速度。頁表查找過程Cache 實際上是一個專用Cache，組織結構與數據Cache類似，存儲Page Walk過程中訪問過的數據；其優點是在進行Page Walk時，命中頁表查找過程Cache 可以有效降低訪存延遲。

3 基于狀態機控制的硬件Page Walk方案

本文提出一種基于狀態機控制的硬件Page Walk 方案，并在頁面粒度最小為8KB、頁表按3 級組織的情況下，具體描述狀態機的設計及狀態跳轉。3 級頁表分別是：頁全局目錄（Page Global Directory，PGD），頁中間目錄（Page Middle Directory，PMD），以及頁表（Page Table，PT）。如圖1 所示，專用寄存器“頁表基址寄存器（Page-table Base Register，PTBR）”存儲PGD的基地址，虛地址VA［42：33］用于索引PGD 條目，VA［32：23］用于索引PMD 條目，VA［22：13］用于索引PT條目。

3.1 Page Walk控制狀態機的設計

硬件Page Walk控制狀態機的狀態跳轉圖如圖2所示。

當請求不命中TLB 時，硬件Page Walk 的具體流程如下所示：

1）首先，跳轉到AccPGD 狀態，根據寄存器PTBR的值和虛地址VA［42：33］計算對應PGD條目地址，產生并發出對PGD 條目的訪存請求后，狀態機跳轉到WTPGDAck狀態，等待訪存響應返回；

圖1 3級頁表下的虛實地址代換流程

圖2 硬件Page Walk的控制狀態機

2）在WTPGDAck 狀態，收到訪問PGD 條目的訪存響應后，狀態機跳轉到AccPMD狀態；

3）在AccPMD 狀態，根據訪問PGD 條目得到的數據，結合虛地址VA［32：23］計算對應PMD 條目的地址，產生并發出對PMD 條目的訪存請求后，狀態機跳轉到WTPMDAck狀態，等待訪存響應返回；

4）在WTPMDAck 狀態，收到訪問PMD 條目的訪存響應后，狀態機跳轉到AccPT狀態；

5）在AccPT 狀態，根據訪問PMD 條目得到的數據，結合虛地址VA［22：13］計算對應PT 條目的地址，產生并發出對PT條目的訪存請求后，狀態機跳轉到WTPTAck狀態，等待訪存響應返回；

6）在WTPTAck 狀態，收到訪問PT 條目的訪存響應后，狀態機跳轉到FillTLB狀態；

7）在FillTLB 狀態，將訪問PT 得到的數據與虛地址的頁內偏移VA［12：0］進行拼接，得到最終代換出的物理地址PA，并將虛地址VA 和PA 同時裝填到TLB中。

在采用3 級頁表結構的情況下，硬件Page Walk 時逐級訪問PGD、PMD 和PT，共需3 次訪存，其優點是無需軟件參與，且相比軟件處理TLB Miss的方式，TLB Miss 的處理開銷較小；缺點是頁表結構對硬件必須可見，且不能隨意更改。

3.2 頁表結構Cache的設計

基于訪存行為的時間局部性和空間局部性，設置一定規模的頁表結構Cache，可以有效提高硬件Page Walk的性能，減少TLB Miss處理的開銷；分別設置PGD Cache和PMD Cache兩部分。

PGD Cache 采用全向聯的組織結構和最近未使用（Least Recent Use，LRU）淘汰算法，每個條目存儲虛地址VA［42：33］和對應PGD 條目的映射關系。PMD Cache 也采用全向聯的組織結構和LRU淘汰算法，每個條目存儲虛地址VA［42：23］和對應PMD條目的映射關系。

選取Spec2006 課題458.sjeng 作為實驗對象，在國產申威處理器SW411 上記錄發生TLB Miss 的訪存地址流，編寫腳本對TLB Miss的地址流進行分析，計算頁表結構Cache 設置為不同條目數時的命中率，實驗結果表1所示。

表1 不同PGD Cache條目和PMD Cache條目配置下的命中率

由表1 可見，當PGD Cache 設置為4 條目，PMD Cache 設置為32 條目時，兩者均具有較高的命中率，且硬件開銷相對較小。

3.3 Page Walk控制狀態機的優化

增加頁表結構Cache 后，對Page Walk 的控制狀態機進行優化，優化后的狀態機跳轉圖如圖3 所示。

如圖3 所示，當請求不命中TLB 時，硬件Page Walk的具體流程如下所示：

1）首先，進入AccPSC 狀態，并行訪問PGD Cache 和PMD Cache，并根據命中結果決定狀態機的跳轉：

（1）若命中PMD Cache，命中數據即是對應PT的基址，狀態機跳轉到AccPT狀態；

圖3 增加頁表結構Cache后硬件Page Walk的控制狀態機

（2）若不命中PMD Cache，命中PGD Cache，命中數據即是對應PMD 的基址，狀態機跳轉到AccPMD狀態；

（3）若不命中PMD Cache 和PGD Cache，狀態機跳轉到AccPGD狀態；

2）在AccPGD 狀態，根據寄存器PTBR 的值和虛地址VA［42：33］計算對應PGD 條目地址，產生并發出對PGD 條目的訪存請求后，狀態機跳轉到WTPGDAck狀態，等待訪存響應返回；

3）在WTPGDAck 狀態，收到訪問PGD 條目的訪存響應后，狀態機跳轉到AccPMD 狀態，同時將虛地址VA［42：33］和響應數據裝填到PGD Cache中；

4）在AccPMD 狀態，根據PGD 條目的內容，結合虛地址VA［32：23］計算對應PMD 條目的地址，產生并發出對PMD 條目的訪存請求后，狀態機跳轉到WTPMDAck狀態，等待訪存響應返回；

5）在WTPMDAck 狀態，收到訪問PMD 條目的訪存響應后，狀態機跳轉到AccPT 狀態，同時將虛地址VA［42：23］和響應數據裝填到PMD Cache中；

6）在AccPT 狀態，根據PMD 條目的內容，結合虛地址VA［22：13］計算對應PT 條目的地址，產生并發出對PT 條目的訪存請求后，狀態機跳轉到WTPTAck狀態，等待訪存響應返回；

7）在WTPTAck 狀態，收到訪問PT 條目的訪存響應后，狀態機跳轉到FillTLB狀態；

8）在FillTLB 狀態，將訪問PT 得到的響應與虛地址的頁內偏移VA［12：0］進行拼接，得到最終代換出的物理地址PA，并將虛地址VA 和PA 同時裝填到TLB中。

相比3.1節中的處理，當請求不命中TLB時，首先訪問頁表結構Cache，并根據頁表結構Cache 的命中情況進行Page Walk，當命中PMD Cache 時，Page Walk只需一次訪存就能得到代換后的物理地址；當命中PGD Cache 時，Page Walk 需要兩次訪存就能到的代換后的物理地址。只有不命中頁表結構Cache時，Page Walk才需要三次訪存。通過選擇合理的結構和條目數，在頁表結構Cache 命中率較高時，可以有效降低Page Walk的訪存次數，顯著減低TLB Miss的處理開銷。

4 結語

TLB 作為處理器中的重要部件，其訪問延遲、命中率及不命中處理開銷對處理器的性能具有重要影響。本文首先對三級頁表結構下的虛實地址代換流程進行了研究分析，并提出一種基于狀態機控制的硬件Page Walk方案，同時，通過使用頁表結構Cache，對Page Walk 的控制狀態機進行了優化；當命中頁表結構Cache時，可以顯著減少Page Walk的訪存次數，降低TLB Miss的處理開銷。高性能處理器普遍采用硬件Page Walk 的方式處理TLB Miss，本文提出的基于狀態機控制的硬件Page Walk方案及頁表結構Cache的設計，對于國產高性能微處理器的設計具有一定的指導意義。