一種高效的壓縮Page Walk Cache結構*

賈朝陽，張敦博，王 瓊，沈 立

(國防科技大學計算機學院,湖南 長沙 410073)

1 引言

通用圖形處理單元(GPGPU)已被廣泛應用于當前的異構高性能計算系統(tǒng)中，加速應用程序中的計算密集型任務。如何減少GPU與CPU之間傳遞數(shù)據(jù)的開銷，始終是研究者關注的焦點。按照之前的編程模型，GPU與CPU之間顯式地交換數(shù)據(jù)，不僅增加了編程復雜度，還需要程序員合理地安排計算和通信，以盡量隱藏通信延遲。當前主流的解決方案是GPU和CPU采用統(tǒng)一的虛擬地址空間[1]，將數(shù)據(jù)傳輸工作交給運行時系統(tǒng)自動管理，以降低編程的復雜性[2]。然而，在GPU和CPU構成的異構系統(tǒng)中引入統(tǒng)一虛擬地址空間又會帶來新的問題，即可能引入較大的虛實地址轉換開銷[3 - 5]。由于GPU采用單指令多線程SIMT(Single Instruction Multiple Thread)執(zhí)行模型，每次訪存都會并發(fā)大量地址轉換請求，導致快表TLB(Translation Lookaside Buffers)命中率比較低。以基準程序2mm為例，32項TLB的命中率是0.81%，64項TLB的命中率是1.54%。對于不規(guī)則應用，這一問題將更加嚴重。過低的TLB命中率勢必導致大量頁表訪問，大大增加虛實地址轉換的實際開銷。因此，虛實地址轉換已經(jīng)成為GPU一個重要的性能瓶頸[6，7]。虛擬地址按位從高到低依次由L4索引、L3索引、L2索引、L1索引和偏移位組成，對于出現(xiàn)的這些問題，現(xiàn)有解決方案主要有3種：提高TLB命中率、優(yōu)化IOMMU(Input Output Memory Management Unit) buffer中請求的調度策略，以及提高頁表遍歷緩存PWC(Page Walk Cache)命中率。

提高TLB命中率是最直接的一種方法[8,9]。Pham等人[10]提出的方案采用多粒度TLB結構，將TLB拆分為粗粒度和細粒度2部分。粗粒度部分覆蓋了更多的地址空間，可以有效提高命中率，用來執(zhí)行虛實地址轉換操作；細粒度部分負責CPU和GPU之間的數(shù)據(jù)傳輸，由于細粒度頁面減少了無用數(shù)據(jù)的傳輸，大大提高了總線帶寬利用率。不過，這種方案需要對TLB結構進行較大改動，導致硬件成本大幅增加。

優(yōu)化IOMMU buffer中請求的調度策略是另一種解決思路。GPU中沒有命中TLB的請求將被送入主機的IOMMU buffer中排隊，等待頁表遍歷部件PTW(Page Table Walker)空閑，以訪問內存中多級頁表，完成地址轉換。因此，可以通過調度這些請求的響應次序，縮短它們在IOMMU buffer中的平均等待時間，以減少地址轉換開銷。Shin等人[11]提出了一種buffer中請求重排序機制，優(yōu)先響應某個warp中的所有請求，這個warp中所有線程的地址轉換開銷之和最小。當buffer中來自這個warp的所有請求都被響應之后，再去響應來自其余warp的請求。經(jīng)過排序，開銷小的warp中請求的平均等待時間大大縮短，而其余warp請求的平均等待時間幾乎不變。雖然這種調度策略可以降低請求的排隊延遲，但是不能減少它們的實際訪存次數(shù)，所以該策略并沒有從根本上解決問題。

提高PWC的命中率也可以減少訪問頁表的次數(shù)[12]。PWC中記錄了之前被訪問過的頁表項，如果訪問PWC命中，就無需再去訪問高級別的頁表。當訪問高級頁表時，多個虛擬地址的高級索引會落在同一個頁表項中，這表明這些虛擬地址的高級索引是相同的。當訪問低級頁表時(如一級頁表)，多個虛擬地址的低級索引會落在多個不同的低級頁表中，上述情況導致PWC中存在很多冗余信息，尤以虛擬地址L4和L3索引的冗余情況最為嚴重。Intel公司的STC(Split Translation Cache)結構[13]，將L4～L2索引分為3個獨立存儲體，以實現(xiàn)3級索引并行查找，但是依然存在較多的信息冗余。為了消除冗余信息，AMD采用UPTC(Unified Page Table Cache)結構[13]，按照虛擬地址的高3級索引將PWC分為3個獨立的存儲器，并以頁表起始地址作為索引進行查找。這樣雖然消除了冗余，但不能對3級索引執(zhí)行并行查找操作，增加了PWC的命中時間。當前主流的PWC結構是TPC(Translation-Path Cache)[13]，TPC將L4～L2索引作為一個整體，可以實現(xiàn)PWC的3級索引并行查找。但是，這種結構中存在大量的冗余信息，冗余信息一般占據(jù)所有信息的45.8%～66.6%。

本文著重研究如何消除PWC中的冗余信息，使得相同容量的PWC能夠保存更多的頁表項，從而減少查找頁表的實際次數(shù)。本文首先分析了典型GPU基準測試集虛擬地址流的特征，發(fā)現(xiàn)在這些測試程序的生命周期中，所有虛擬地址的L4索引基本不會改變；L3索引改變很少，不超過4種取值；L2索引的變化相比L4、L3級索引要多很多，而L1索引的變化更多，基本沒有局部性可以利用?；谏鲜鲇^察，本文提出了一種壓縮的PWC結構，稱為CPWC(Compressed Page Walk Cache)。CPWC采用樹形結構，可以消除傳統(tǒng)PWC中的全部冗余，同時保持查找開銷不變。實驗表明，與TPC相比，CPWC可以減少25.4%的訪存。

2 CPWC的結構

減少GPU虛實地址轉換開銷的3個方案中，提高TLB命中率需要修改TLB結構或改變操作系統(tǒng)頁表生成策略，改變地址轉換流程，改動范圍大，開銷大；雖然優(yōu)化IOMMU buffer的調度策略可以有效改善請求在buffer中的平均等待時間，但是卻沒有從根本上解決地址轉換開銷過大的問題；提高PWC命中率會引入額外的冗余信息，由于存儲空間限制，傳統(tǒng)PWC的命中率并不是特別理想。因此，本文從消除PWC中的冗余信息入手，首先分析了GPU執(zhí)行過程中虛擬地址序列的特征。在此基礎上，本文提出CPWC結構來消除冗余信息，提高PWC的命中率，減少TLB失效時訪問頁表的次數(shù)，提高虛實地址轉換的效率。

2.1 虛擬地址分析

本文采用GPGPU-Sim[14]模擬器，使用GTX 480 GPU架構進行模擬。模擬器采用默認硬件配置，通過配置選項輸出測試程序執(zhí)行過程中的虛擬地址流，并分析這些地址流的特征[15]。本文從Rodinia 3.1(dwt2d、pathfinder、streamcluster、backprop、hotspot、b+tree)[16]、Polybench GPU-1.0(gramschmidt、2mm、3mm、2DC、3DC、gemm)[17]和ISPASS 2009(AES、BFS、STO、RAY、MUM)基準程序包中隨機選擇了17個基準程序進行分析。在本文統(tǒng)計的基準程序的整個生命周期中，不同L4、L3和L2級索引出現(xiàn)的頻度不同，表1列出了統(tǒng)計結果。

Table 1 Statistical results of virtual address characteristics表1 虛擬地址特征統(tǒng)計結果

根據(jù)表1中虛擬地址特征的統(tǒng)計結果，本文將這些基準程序分為3類：

第Ⅰ類：原始PWC即可獲得很好的命中率。由于這些基準程序中虛擬地址的高3級索引局部性很強，PWC在有限條目的情況下即可獲得接近100%的命中率。這類程序一般是規(guī)則的GPU應用。

第Ⅱ類：需要大幅增加PWC容量才能獲得理想的命中率。這類基準程序的虛擬地址特征也很明確，L4、L3級索引的局部性仍然很好，但是L2級索引的局部性很差，不同L2級索引的數(shù)目超過150個。由于L2級索引的局部性較差，需要很大容量(分布情況最差的程序STO至少需要300項的PWC，需占空間66 000 bit)的PWC才能獲得接近100%的命中率。要在此類基準程序中獲得良好的PWC命中率勢必導致硬件開銷大大增加。

第Ⅲ類：這類基準程序的L4、L3級索引局部性和前面2類一樣，但是L2級索引的局部性介于第Ⅰ類和第Ⅱ類之間。這類基準程序的PWC命中率隨PWC容量的增加表現(xiàn)出明顯的提升，因此只需要增加少量PWC存儲開銷即可獲得接近100%的命中率。

綜上所述，這3類基準程序的虛擬地址中L4和L3級索引的局部性都很好，不同的局部性體現(xiàn)在L2級索引上。本文通過本次實驗得出2個結論：

(1) 傳統(tǒng)PWC中高度冗余的信息是由L4和L3級索引導致的。3類基準程序的虛擬地址中高2級索引的變化很少，每次存儲L2級索引時都重復存儲L4和L3級索引，導致信息冗余。

(2) 傳統(tǒng)PWC的命中率由L2級索引的局部性決定。如果虛地址中L2級索引的局部性差(例如表1中的STO基準程序，不同的L2級索引數(shù)目達到了409個)，為了達到理想命中率，需要增加很多PWC存儲開銷。

本文通過消除PWC中相同的L4和L3級索引來消除冗余信息，并采用映射方式保持現(xiàn)有的3級索引并行查找過程不變。這樣既消除了PWC中的冗余，又可以保證PWC查找開銷不變，還可以將之前存儲冗余信息的空間用來緩存新PWC條目，從而在存儲開銷相同的條件下增加PWC命中率，減少地址轉換開銷。

2.2 CPWC結構

根據(jù)2.1節(jié)的統(tǒng)計結果，本文采用樹形結構存儲PWC中的條目，以消除冗余信息。由于TPC結構實現(xiàn)了3級索引并行查找，采用樹形結構的一個挑戰(zhàn)是如何維持3級索引的并行查找過程。為此，本文將PWC按照3級索引分成3個獨立的存儲體：L4 PWC、L3 PWC和L2 PWC，每部分分別緩存虛擬地址的L4、L3和L2級索引及其對應的頁表起始地址PBA(Page Base Address)。

本節(jié)以1個擁有2項L4索引、4項L3索引、32項L2索引和1個多路選擇器的CPWC為例進行介紹，其中L2 PWC分為4個PWC塊，每個塊包含8個條目，其具體結構如圖1所示。L4 PWC中每個條目緩存虛地址的L4索引(L4 Tag)和對應的L3級頁表起始地址(L3 PBA)。L3 PWC每個條目緩存虛地址的L3索引和L2級頁表起始地址，X位的Mask部分是1個位向量，用來指示當前L3條目對應哪些L2 PWC 塊。L2 PWC由多個PWC 塊和1個多路選擇器構成，每個PWC塊中的條目緩存虛地址的L2索引和L1級頁表起始地址，多路選擇器使用L3條目中的Mask向量從所有L2 PWC塊的匹配結果中篩選正確結果。本文在L4 PWC和L3 PWC中采用直接映射方式，L2 PWC的每個PWC塊內采用全相聯(lián)映射。

Figure 1 Structure of CPWC圖1 CPWC的結構

2.3 CPWC地址映射方式與查找方式

CPWC各部分的項數(shù)決定了它們的映射方式，在本文中，CPWC各部分的映射方式如表2所示。CPWC的映射方式也決定了它的查找方式。如圖1中的CPWC結構，由于L4 PWC中只有2項，所以采用直接映射并以L4索引的最低位作為L4標識。同理，L3 PWC只有4項，采用直接映射并將L4索引的最低位與L3索引的最低位拼接起來，形成2位的L3標識。L2 PWC 分為4塊，每塊的內部采用全相聯(lián)映射，整個L2 PWC使用4路選擇器選擇最終結果。下面介紹CPWC如何實現(xiàn)并行查找：當一個虛擬地址查找CPWC時，將虛擬地址分成L4索引、L3索引和L2索引3部分。

Table 2 CPWC configuration parameters 表2 CPWC配置參數(shù)

第1步，分別在L4、L3、L2 PWC中查找，請注意這3個查找是并行的：使用L4標識查找L4 PWC，同時使用L3標識查找L3 PWC，同時并行查找L2 PWC中所有PWC塊，將L2 PWC塊的命中結果輸入多路選擇器，作為備選輸出。

第2步，將L3中命中條目的Mask字段輸入多路選擇器作為選擇依據(jù)(Mask哪一位為1則輸出對應的PBA)，選擇多個L2 PWC塊查找結果中正確的結果，完成PWC查找過程。

保存L4、L3和L2的3個PWC有不同的命中結果處理策略。若L4 PWC失效，則整個CPWC失效，需要訪問4次頁表；若L4 PWC命中且L3 PWC失效，則L2 PWC也失效，得到了L3級頁表起始地址，從L3級頁表開始訪問3次頁表；若L4 PWC和L3 PWC命中且所有L2 PWC塊都未命中，多路選擇器沒有輸出，則L2 PWC失效。得到了L2級頁表起始地址，從L2級頁表開始訪問2次頁表；L4、L3 PWC均命中且多路選擇器有輸出結果，此時L2 PWC命中，得到了L1級頁表起始地址，只需要訪問1次頁表。

2.4 CPWC的訪問過程

本節(jié)以3個虛擬地址0x7F72B010F1F0、0x7F72BC30F1F0和0x7FF2FC30F1F0為例，描述CPWC的訪問過程。假設它們先后到達CPWC，3個虛擬地址的L4級、L3級和L2級索引如表3所示。

Table 3 L4,L3,and L2 indexes of virtual addresses表3 虛擬地址的L4級、L3級和L2級索引

Figure 2 CPWC structure after three virtual addresses are written圖2 3個虛地址寫入后的CPWC結構

第1條虛擬地址到來時CPWC為空，需要查詢4次頁表獲得物理地址信息完成地址轉換，然后將虛擬地址的高3級索引和對應的頁表起始地址分別存儲在L4 PWC、L3 PWC的第1個條目和L2 PWC第1個塊的第1項，并將L3中對應項的Mask字段置為0b1000。第2條虛擬地址到來時，并行查找L4、L3和L2 PWC。發(fā)現(xiàn)L4 PWC、L3 PWC都命中第1項。因為所有L2 PWC塊都未命中，所以將Mask信息輸入多路選擇器后發(fā)現(xiàn)沒有輸出，此時CPWC中L3 PWC命中，PTW執(zhí)行2次訪存，并將完成訪存后的L2索引和L1級頁表起始地址存儲在L2 PWC第1個塊的第2項。第3條虛擬地址到來時，發(fā)現(xiàn)L4～L2 PWC都未命中，完成地址轉換后將虛擬地址的L4索引填入L4 PWC的第2項，并根據(jù)L3標識(值為0b11)將L3索引填入L3 PWC的第4項。L2索引填入L2 PWC第2個塊的第1項，將L3中對應的Mask字段的值置為0b0100。這3個請求都響應后的CPWC如圖2所示。

2.5 CPWC優(yōu)勢分析

與傳統(tǒng)PWC相比，CPWC減少了緩存L4與L3級索引的空間。根據(jù)2.1節(jié)中虛擬地址各級索引分布特征的統(tǒng)計結果，由于L4與L3索引極強的局部性(在整個程序運行過程中，只會出現(xiàn)1～4個不同值)，因此傳統(tǒng)PWC中存在大量的冗余信息。CPWC采用分離式的PWC結構，將用于緩存重復L4與L3索引的空間改為緩存L1級頁表起始地址的空間，這樣相當于增加了PWC的整體容量。也就是說，采取CPWC的樹形結構可以在相同空間開銷的情況下，緩存更多的L2級頁表項，從而提高PWC的命中率，減少地址轉換開銷。

3 性能測試與分析

本文使用GPGPU-Sim模擬器，采用GTX 480 GPU架構配置，模擬基準程序執(zhí)行過程獲取虛擬地址流。隨后設計實現(xiàn)GPU-CPU地址轉換模擬器對所提出的壓縮PWC進行性能測試與分析。GPGPU-Sim的具體配置如表4所示。

基準程序采用第2節(jié)中分析虛擬地址特征時使用的測試集，各個基準程序的詳細信息請參見第2節(jié)。為了體現(xiàn)CPWC相比之前結構的提升，本文進行以下3個方面的測試與分析：(1)信息冗余度與空間開銷分析；(2)CPWC命中率分析；(3)地址轉換開銷分析。

3.1 信息冗余度與空間開銷

表5和表6都展示了PWC與CPWC的容量和所能緩存的頁表項數(shù)之間的關系。不同的是，表5展示了隨項數(shù)的增加PWC和CPWC容量的變化；表6展示了隨容量的增加PWC與CPWC能緩存的項數(shù)的變化。

Table 4 GPU configuration parameters for the experiment表4 實驗用GPU配置參數(shù)

Table 5 Space occupied (bits) by PWC and CPWC with the change of entry numbers表5 PWC與CPWC的占用空間隨項數(shù)的變化

Table 6 Entry number of PWC and CPWC with the change of space occupation (bits)表6 PWC與CPWC的項數(shù)隨占用空間的變化

PWC中的每一項可以分成3個索引以及對應的頁表起始地址，因此PWC的每一項所需要的空間開銷為：1位有效位(1 bit)、3個索引(3*9 bit)、3個頁表起始地址(3*64 bit)，共220 bit。CPWC中每一項包含：1位標識位(1 bit)、索引(9 bit)和頁表項(64 bit),其中L3 PWC每一項還需增加N位的Mask字段?；谔摂M地址各級索引的分布情況，N項的CPWC需要1個2項的L4 CPWC(2*74 bit)、1個4項的L3 CPWC(4*(74+N) bit)和1個N項的L2 CPWC(N*74 bit)。1個N項的PWC所需的空間開銷為：N*220 bit，而1個N項的CPWC所需的空間為：(6+N)*74+4*Nbit。通過這2個表可以看出,CPWC通過調整結構消除了冗余信息,兩者在相同項數(shù)下，隨著容納項數(shù)的增加,PWC所占用的空間接近CPWC的3倍；在相同容量的情況下，隨著容量的增加，CPWC所能緩存的項數(shù)也接近PWC的3倍。

表7展示了相同容量下PWC與CPWC中冗余信息所占的比例。1個虛擬地址可以被分為1～4級的索引和偏移量。在地址轉換時PTW會按照各級索引去遍歷頁表，由于L4、L3級索引的強局部性，導致地址轉換請求多次訪問同一個高級頁，而傳統(tǒng)的PWC將高3級索引作為一個整體進行處理。按照2.1節(jié)中的分析，L4與L3級索引局部性非常高，導致PWC中接近2/3的信息都是冗余的。隨著PWC的容量不斷增大，PWC中冗余信息所占的比例也在不斷增大，并且不斷逼近于66.6%，這相當于浪費了將近2/3的空間緩存重復信息。無論CPWC的容量多大，CPWC中都沒有冗余信息。CPWC在相同容量的情況下可以緩存更多不同的頁表項，進而提升命中率。

Table 7 Comparison of PWC and CPWC redundancy at the same capacity 表7 相同容量下PWC與CPWC冗余度對比

3.2 CPWC的命中率

圖3展示了各個測試程序在相同存儲開銷情況下的L2索引命中率，存儲開銷都為5 280 bit(PWC 24項、CPWC 62項)。根據(jù)2.1節(jié)中的分析，所有程序都只出現(xiàn)1～3個不同的L4、L3級索引，因此L4與L3級索引的命中率都接近于100%(除了強制失效)。故本節(jié)只對L2級索引的命中率進行測試與分析。從圖3中可以看出，所有程序都可以從CPWC結構中獲益。其中pathfinder、3DC、2DC、hotspot、backprop、b+tree、gemm、3mm、2mm、BFS可以從CPWC中獲得2倍乃至3倍的L2索引命中率提升，這是因為相同容量下CPWC所能覆蓋的地址范圍已經(jīng)接近程序的地址分布范圍，而PWC只能覆蓋小部分。STO、AES、RAY、dwt2d、streamcluster、MUM的L2索引命中率提升沒有上一組程序明顯。從2.1節(jié)中可以發(fā)現(xiàn)，這些程序的地址覆蓋范圍相較于上一組程序來說更廣泛，當前CPWC所能覆蓋的地址范圍仍然不能很好地滿足程序的需求，因此命中率提升有限。對于gramschmidt程序來說，原本的PWC幾乎覆蓋了程序中所有的地址分布范圍，L2級索引命中率已經(jīng)接近100%，因此CPWC對此程序的提升并不明顯。綜上所述，在空間開銷為5 280 bit的情況下，PWC的L2索引平均命中率為46.5%，CPWC的L2索引平均命中率為86.5%，平均提升了40%的PWC命中率。

Figure 3 Hit ratio of the L2 indexes圖3 L2索引的命中率

3.3 地址轉換開銷

表8對比了PWC與CPWC中各個測試程序地址轉換所需的訪問頁表(訪存)次數(shù)。表8中所有的訪存都是由TLB失效后的地址轉換請求引起的，對于不同程序CPWC所能帶來的性能提升也不同。根據(jù)第2節(jié)中的分類依據(jù)，本文將gramschmidt作為第I類,將STO、AES、RAY、dwt2d、MUM作為第II類，將pathfinder、3DC、2DC、hotspot、backprop、b+tree、gemm、3mm、2mm、BFS、streamcluster作為第III類。其中第I類測試程序只減少了2.18%的訪存，這是由于程序本身的L2級索引命中率就很好，地址轉換性能已經(jīng)接近理想性能，因此很難再獲提升。第II類程序平均減少了15.11%的訪存，由于這些測試程序虛擬地址分布范圍已經(jīng)超過了當前PWC和CPWC所能覆蓋的頁表范圍，PWC容量失效影響了性能的提升，因此CPWC所能帶來的性能提升并不明顯。第III類程序平均減少了32.2%的訪存，由于這些測試程序的虛擬地址分布范圍超過了PWC覆蓋的范圍，而沒有超過CPWC覆蓋的地址范圍，性能提升接近于L2級索引命中率的提升，不會受到容量失效的影響。

Table 8 Comparison between CPWC and PWC with the same capacity表8 同容量CPWC與PWC的對比

針對CPWC結構命中時間問題，本文做了以下實驗:采用SMIC 16 nm標準CMOS工藝，在Cadence軟件中完成了64項直接映射PWC和64項CPWC的設計，并測試了兩者的命中時間。實驗結果表明，直接映射PWC和CPWC的命中時間分別為147 ps和154 ps。因此，全相聯(lián)的L2 PWC塊對地址轉換性能幾乎沒有影響。

綜上所述，相比于PWC，CPWC能減少25.4%的訪存。

4 結束語

GPU的多線程執(zhí)行模型會同時發(fā)出多個虛實地址轉換請求，使得TLB的未命中率逐漸增加，虛實地址轉換的開銷也隨之增加。因此，用于減少TLB失效后訪存次數(shù)的PWC將發(fā)揮越來越重要的作用。傳統(tǒng)的PWC有一些不足，如容量有限和信息冗余，使它無法有效地減少實際頁表訪問次數(shù)。本文提出了一種新的PWC結構，稱為CPWC。CPWC以樹形結構組織頁表條目，完全消除了冗余的L4級和L3級索引，同時保持了3級索引并行查找。實驗結果表明，CPWC增加了PWC可緩存的頁表項數(shù)，平均減少了25.4%的頁表訪問次數(shù)，有效地減少了虛實地址轉換開銷。