基于狀態(tài)機控制的硬件Page Walk 方案與實現(xiàn)?

路冬冬 王炳凱 杜 鑫，

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

1 引言

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

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

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

2 相關(guān)研究工作

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

2.1 提高TLB的命中率

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

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

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

2.2 降低TLB Miss的處理開銷

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

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

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

3 基于狀態(tài)機控制的硬件Page Walk方案

本文提出一種基于狀態(tài)機控制的硬件Page Walk 方案，并在頁面粒度最小為8KB、頁表按3 級組織的情況下，具體描述狀態(tài)機的設(shè)計及狀態(tài)跳轉(zhuǎn)。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控制狀態(tài)機的設(shè)計

硬件Page Walk控制狀態(tài)機的狀態(tài)跳轉(zhuǎn)圖如圖2所示。

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

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

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

圖2 硬件Page Walk的控制狀態(tài)機

2）在WTPGDAck 狀態(tài)，收到訪問PGD 條目的訪存響應后，狀態(tài)機跳轉(zhuǎn)到AccPMD狀態(tài)；

3）在AccPMD 狀態(tài)，根據(jù)訪問PGD 條目得到的數(shù)據(jù)，結(jié)合虛地址VA［32：23］計算對應PMD 條目的地址，產(chǎn)生并發(fā)出對PMD 條目的訪存請求后，狀態(tài)機跳轉(zhuǎn)到WTPMDAck狀態(tài)，等待訪存響應返回；

4）在WTPMDAck 狀態(tài)，收到訪問PMD 條目的訪存響應后，狀態(tài)機跳轉(zhuǎn)到AccPT狀態(tài)；

5）在AccPT 狀態(tài)，根據(jù)訪問PMD 條目得到的數(shù)據(jù)，結(jié)合虛地址VA［22：13］計算對應PT 條目的地址，產(chǎn)生并發(fā)出對PT條目的訪存請求后，狀態(tài)機跳轉(zhuǎn)到WTPTAck狀態(tài)，等待訪存響應返回；

6）在WTPTAck 狀態(tài)，收到訪問PT 條目的訪存響應后，狀態(tài)機跳轉(zhuǎn)到FillTLB狀態(tài)；

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

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

3.2 頁表結(jié)構(gòu)Cache的設(shè)計

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

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

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

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

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

3.3 Page Walk控制狀態(tài)機的優(yōu)化

增加頁表結(jié)構(gòu)Cache 后，對Page Walk 的控制狀態(tài)機進行優(yōu)化，優(yōu)化后的狀態(tài)機跳轉(zhuǎn)圖如圖3 所示。

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

1）首先，進入AccPSC 狀態(tài)，并行訪問PGD Cache 和PMD Cache，并根據(jù)命中結(jié)果決定狀態(tài)機的跳轉(zhuǎn)：

（1）若命中PMD Cache，命中數(shù)據(jù)即是對應PT的基址，狀態(tài)機跳轉(zhuǎn)到AccPT狀態(tài)；

圖3 增加頁表結(jié)構(gòu)Cache后硬件Page Walk的控制狀態(tài)機

（2）若不命中PMD Cache，命中PGD Cache，命中數(shù)據(jù)即是對應PMD 的基址，狀態(tài)機跳轉(zhuǎn)到AccPMD狀態(tài)；

（3）若不命中PMD Cache 和PGD Cache，狀態(tài)機跳轉(zhuǎn)到AccPGD狀態(tài)；

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

3）在WTPGDAck 狀態(tài)，收到訪問PGD 條目的訪存響應后，狀態(tài)機跳轉(zhuǎn)到AccPMD 狀態(tài)，同時將虛地址VA［42：33］和響應數(shù)據(jù)裝填到PGD Cache中；

4）在AccPMD 狀態(tài)，根據(jù)PGD 條目的內(nèi)容，結(jié)合虛地址VA［32：23］計算對應PMD 條目的地址，產(chǎn)生并發(fā)出對PMD 條目的訪存請求后，狀態(tài)機跳轉(zhuǎn)到WTPMDAck狀態(tài)，等待訪存響應返回；

5）在WTPMDAck 狀態(tài)，收到訪問PMD 條目的訪存響應后，狀態(tài)機跳轉(zhuǎn)到AccPT 狀態(tài)，同時將虛地址VA［42：23］和響應數(shù)據(jù)裝填到PMD Cache中；

6）在AccPT 狀態(tài)，根據(jù)PMD 條目的內(nèi)容，結(jié)合虛地址VA［22：13］計算對應PT 條目的地址，產(chǎn)生并發(fā)出對PT 條目的訪存請求后，狀態(tài)機跳轉(zhuǎn)到WTPTAck狀態(tài)，等待訪存響應返回；

7）在WTPTAck 狀態(tài)，收到訪問PT 條目的訪存響應后，狀態(tài)機跳轉(zhuǎn)到FillTLB狀態(tài)；

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

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

4 結(jié)語

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