賈朝陽(yáng)，張敦博，王 瓊，沈 立

(國(guó)防科技大學(xué)計(jì)算機(jī)學(xué)院,湖南 長(zhǎng)沙 410073)

1 引言

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

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

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

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

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

2 CPWC的結(jié)構(gòu)

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

2.1 虛擬地址分析

本文采用GPGPU-Sim[14]模擬器，使用GTX 480 GPU架構(gòu)進(jìn)行模擬。模擬器采用默認(rèn)硬件配置，通過(guò)配置選項(xiàng)輸出測(cè)試程序執(zhí)行過(guò)程中的虛擬地址流，并分析這些地址流的特征[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)基準(zhǔn)程序包中隨機(jī)選擇了17個(gè)基準(zhǔn)程序進(jìn)行分析。在本文統(tǒng)計(jì)的基準(zhǔn)程序的整個(gè)生命周期中，不同L4、L3和L2級(jí)索引出現(xiàn)的頻度不同，表1列出了統(tǒng)計(jì)結(jié)果。

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

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

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

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

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

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

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

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

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

2.2 CPWC結(jié)構(gòu)

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

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

Figure 1 Structure of CPWC圖1 CPWC的結(jié)構(gòu)

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

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

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

第1步，分別在L4、L3、L2 PWC中查找，請(qǐng)注意這3個(gè)查找是并行的：使用L4標(biāo)識(shí)查找L4 PWC，同時(shí)使用L3標(biāo)識(shí)查找L3 PWC，同時(shí)并行查找L2 PWC中所有PWC塊，將L2 PWC塊的命中結(jié)果輸入多路選擇器，作為備選輸出。

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

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

2.4 CPWC的訪問(wèn)過(guò)程

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

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

Figure 2 CPWC structure after three virtual addresses are written圖2 3個(gè)虛地址寫(xiě)入后的CPWC結(jié)構(gòu)

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

2.5 CPWC優(yōu)勢(shì)分析

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

3 性能測(cè)試與分析

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

基準(zhǔn)程序采用第2節(jié)中分析虛擬地址特征時(shí)使用的測(cè)試集，各個(gè)基準(zhǔn)程序的詳細(xì)信息請(qǐng)參見(jiàn)第2節(jié)。為了體現(xiàn)CPWC相比之前結(jié)構(gòu)的提升，本文進(jìn)行以下3個(gè)方面的測(cè)試與分析：(1)信息冗余度與空間開(kāi)銷分析；(2)CPWC命中率分析；(3)地址轉(zhuǎn)換開(kāi)銷分析。

3.1 信息冗余度與空間開(kāi)銷

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

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

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

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

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

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

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

3.2 CPWC的命中率

圖3展示了各個(gè)測(cè)試程序在相同存儲(chǔ)開(kāi)銷情況下的L2索引命中率，存儲(chǔ)開(kāi)銷都為5 280 bit(PWC 24項(xiàng)、CPWC 62項(xiàng))。根據(jù)2.1節(jié)中的分析，所有程序都只出現(xiàn)1～3個(gè)不同的L4、L3級(jí)索引，因此L4與L3級(jí)索引的命中率都接近于100%(除了強(qiáng)制失效)。故本節(jié)只對(duì)L2級(jí)索引的命中率進(jìn)行測(cè)試與分析。從圖3中可以看出，所有程序都可以從CPWC結(jié)構(gòu)中獲益。其中pathfinder、3DC、2DC、hotspot、backprop、b+tree、gemm、3mm、2mm、BFS可以從CPWC中獲得2倍乃至3倍的L2索引命中率提升，這是因?yàn)橄嗤萘肯翪PWC所能覆蓋的地址范圍已經(jīng)接近程序的地址分布范圍，而PWC只能覆蓋小部分。STO、AES、RAY、dwt2d、streamcluster、MUM的L2索引命中率提升沒(méi)有上一組程序明顯。從2.1節(jié)中可以發(fā)現(xiàn)，這些程序的地址覆蓋范圍相較于上一組程序來(lái)說(shuō)更廣泛，當(dāng)前CPWC所能覆蓋的地址范圍仍然不能很好地滿足程序的需求，因此命中率提升有限。對(duì)于gramschmidt程序來(lái)說(shuō)，原本的PWC幾乎覆蓋了程序中所有的地址分布范圍，L2級(jí)索引命中率已經(jīng)接近100%，因此CPWC對(duì)此程序的提升并不明顯。綜上所述，在空間開(kāi)銷為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 地址轉(zhuǎn)換開(kāi)銷

表8對(duì)比了PWC與CPWC中各個(gè)測(cè)試程序地址轉(zhuǎn)換所需的訪問(wèn)頁(yè)表(訪存)次數(shù)。表8中所有的訪存都是由TLB失效后的地址轉(zhuǎn)換請(qǐng)求引起的，對(duì)于不同程序CPWC所能帶來(lái)的性能提升也不同。根據(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類測(cè)試程序只減少了2.18%的訪存，這是由于程序本身的L2級(jí)索引命中率就很好，地址轉(zhuǎn)換性能已經(jīng)接近理想性能，因此很難再獲提升。第II類程序平均減少了15.11%的訪存，由于這些測(cè)試程序虛擬地址分布范圍已經(jīng)超過(guò)了當(dāng)前PWC和CPWC所能覆蓋的頁(yè)表范圍，PWC容量失效影響了性能的提升，因此CPWC所能帶來(lái)的性能提升并不明顯。第III類程序平均減少了32.2%的訪存，由于這些測(cè)試程序的虛擬地址分布范圍超過(guò)了PWC覆蓋的范圍，而沒(méi)有超過(guò)CPWC覆蓋的地址范圍，性能提升接近于L2級(jí)索引命中率的提升，不會(huì)受到容量失效的影響。

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

針對(duì)CPWC結(jié)構(gòu)命中時(shí)間問(wèn)題，本文做了以下實(shí)驗(yàn):采用SMIC 16 nm標(biāo)準(zhǔn)CMOS工藝，在Cadence軟件中完成了64項(xiàng)直接映射PWC和64項(xiàng)CPWC的設(shè)計(jì)，并測(cè)試了兩者的命中時(shí)間。實(shí)驗(yàn)結(jié)果表明，直接映射PWC和CPWC的命中時(shí)間分別為147 ps和154 ps。因此，全相聯(lián)的L2 PWC塊對(duì)地址轉(zhuǎn)換性能幾乎沒(méi)有影響。

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

4 結(jié)束語(yǔ)

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