基于社區(qū)結(jié)構(gòu)的圖數(shù)據(jù)預(yù)取器設(shè)計①

李 策 章隆兵

(計算機體系結(jié)構(gòu)國家重點實驗室(中國科學(xué)院計算技術(shù)研究所) 北京100190)

(中國科學(xué)院大學(xué)計算機學(xué)院 北京100190)

0 引言

隨著大數(shù)據(jù)時代的到來,圖作為一種常見的數(shù)據(jù)結(jié)構(gòu),在社交網(wǎng)絡(luò)、網(wǎng)頁搜索、推薦系統(tǒng)等領(lǐng)域得到廣泛使用。由于圖數(shù)據(jù)的龐大規(guī)模,圖計算通常運行在分布式系統(tǒng)上,或借助片外磁盤系統(tǒng)存儲數(shù)據(jù)。許多工作[1-4]針對上述系統(tǒng)進行了優(yōu)化。但隨著內(nèi)存容量與處理器核數(shù)的增加,單機系統(tǒng)也可以高效運行圖計算應(yīng)用,且無須對圖數(shù)據(jù)進行分割,相對于分布式系統(tǒng),減少了額外的預(yù)處理開銷。

代表現(xiàn)實世界關(guān)系的圖數(shù)據(jù)具有稀疏性,對其進行計算時將產(chǎn)生大量無規(guī)則訪問,不具備時間局部性與空間局部性,通用處理器的片上緩存結(jié)構(gòu)無法發(fā)揮作用。導(dǎo)致圖計算運行時存在過多的長延遲內(nèi)存訪問,造成處理器內(nèi)的訪存阻塞,成為圖應(yīng)用在單機系統(tǒng)上運行的主要瓶頸[5]。而對訪存數(shù)據(jù)進行預(yù)取是緩解上述問題的有效方法。

傳統(tǒng)的數(shù)據(jù)預(yù)取器通過學(xué)習(xí)應(yīng)用內(nèi)訪存行為的規(guī)律,對未來的訪存地址進行預(yù)測,并將預(yù)測地址的數(shù)據(jù)從內(nèi)存或下級緩存中取回。等到真正的訪存請求到達時,相應(yīng)的數(shù)據(jù)已經(jīng)存儲在對應(yīng)級別的緩存中,達到了縮短訪存延遲的目的。但傳統(tǒng)的預(yù)取器只能識別地址間存在確定規(guī)律的訪存流,而圖計算中包含大量間接訪存行為,即訪存地址由其他訪存請求取回的數(shù)據(jù)內(nèi)容決定。傳統(tǒng)的預(yù)取器不能識別上述訪存模式,無法準確預(yù)取圖數(shù)據(jù)[6]。

許多研究設(shè)計了面向間接訪存以及圖數(shù)據(jù)的專用預(yù)取器,一定程度上緩解了圖計算的訪存壓力。而本文利用圖數(shù)據(jù)集內(nèi)社區(qū)中鄰頂點的儲存規(guī)律,設(shè)計了相應(yīng)的圖數(shù)據(jù)預(yù)取器,進一步提升了預(yù)取圖數(shù)據(jù)的性能收益。

本文的主要貢獻有以下3 個方面。

(1)通過對不同類型圖數(shù)據(jù)集的研究,發(fā)現(xiàn)了含有社區(qū)結(jié)構(gòu)的圖數(shù)據(jù)集的存儲規(guī)律。

(2)提出了新的圖數(shù)據(jù)預(yù)取器設(shè)計方案。利用社區(qū)結(jié)構(gòu)中鄰頂點的存儲規(guī)律,對圖數(shù)據(jù)中的頂點數(shù)據(jù)和邊數(shù)據(jù)進行了混合預(yù)取,提升了預(yù)取的及時性。同時修正現(xiàn)有圖數(shù)據(jù)預(yù)取器的設(shè)計缺陷,提升了預(yù)取的準確性和覆蓋率。

(3)在不同類型圖算法與圖數(shù)據(jù)集上對上述預(yù)取器設(shè)計進行驗證。結(jié)果表明該預(yù)取器相對于現(xiàn)有圖數(shù)據(jù)預(yù)取器實現(xiàn)了4 %～18 %的性能提升。

1 相關(guān)工作

數(shù)據(jù)預(yù)取器是體系結(jié)構(gòu)的熱點研究方向之一。但傳統(tǒng)的數(shù)據(jù)預(yù)取器如GHB[7]和VLDP[8]等,通常通過學(xué)習(xí)地址流中的步長歷史進行訪存預(yù)取,無法識別圖計算中的間接訪存模式。

除圖計算外,間接訪存模式也存在于許多大規(guī)模應(yīng)用中,因而許多研究[9-11]提出了面向間接訪存的預(yù)取器。該類預(yù)取器采用軟硬件結(jié)合的方式,通過對訪存取回的數(shù)據(jù)進行分析,可以識別多層級的間接訪存模式。但圖計算中的間接訪存只有兩級,當(dāng)該類預(yù)取器處理圖應(yīng)用時,往往會出現(xiàn)過度預(yù)取現(xiàn)象。這浪費了內(nèi)存帶寬,同時也增加了處理器運行功耗。為了減少錯誤預(yù)取,IMP[12]預(yù)取器通過對等步長訪存流的識別,將等步長訪存流的訪問數(shù)據(jù)與隨后的訪存地址進行對比。若存在對應(yīng)關(guān)系,則判斷當(dāng)前存在間接訪存模式,并發(fā)出相應(yīng)的預(yù)取請求。該預(yù)取器完全基于硬件實現(xiàn),無額外的軟件開銷。同時嚴格限制間接預(yù)取的發(fā)出條件,提升了預(yù)取的準確率。但它產(chǎn)生了額外的啟動開銷,降低了預(yù)取的覆蓋率,且無法識別除上述模式外的間接訪存,導(dǎo)致其不能準確預(yù)取圖計算中的全部訪存請求。

為了準確全面地預(yù)取圖計算中的訪存請求,文獻[13,14]分別設(shè)計了面向圖數(shù)據(jù)的專用預(yù)取器。其中文獻[13] 利用廣度優(yōu)先搜索(breadth-first search,BFS)類圖算法具有頂點處理順序可預(yù)測的特點,提升了圖數(shù)據(jù)預(yù)取的準確性。通過在算法中添加工作表結(jié)構(gòu),記錄當(dāng)前圖頂點的處理順序,準確地預(yù)測了以壓縮稀疏行(compress sparse row,CSR)格式存儲的圖數(shù)據(jù)的訪存行為。同時增加額外的硬件電路實現(xiàn)了對預(yù)取及時性的精確控制,極大地提升了BFS 類圖算法的運行性能。但由于需要在算法中添加額外的數(shù)據(jù)結(jié)構(gòu)以記錄圖頂點的處理順序,產(chǎn)生了對圖計算軟件框架的修改。面對不同的圖計算框架,該方法會造成大量的處理開銷。而DROPLET[14]預(yù)取器使用軟件方法在頁表緩存中對圖數(shù)據(jù)的虛地址范圍進行標記。當(dāng)標記地址被訪問時,觸發(fā)對圖數(shù)據(jù)的間接預(yù)取。該設(shè)計將預(yù)取器放置在內(nèi)存控制器附近,當(dāng)數(shù)據(jù)從內(nèi)存到達內(nèi)存控制器時便觸發(fā)預(yù)取請求,大幅提升了預(yù)取的及時性。但該預(yù)取器需要在內(nèi)存控制器處添加頁表緩存完成虛實地址轉(zhuǎn)換,增加了額外硬件開銷,同時隨著處理器核數(shù)增加,維護成本將越來越高。且該預(yù)取器只對頂點數(shù)組進行間接預(yù)取,而對邊數(shù)組采用流式預(yù)取,導(dǎo)致部分邊數(shù)組的訪存請求未能被準確識別,降低了預(yù)取覆蓋率。

2 研究背景

本節(jié)主要對圖計算的基礎(chǔ)知識和圖數(shù)據(jù)的存儲特點進行介紹。

2.1 圖數(shù)據(jù)存儲格式

CSR 是一種被廣泛使用的圖數(shù)據(jù)存儲格式,使用該格式存儲圖數(shù)據(jù)時空間利用率較高。圖1 為CSR 存儲模式示例,CSR 格式使用2 個數(shù)組存儲圖數(shù)據(jù)的空間結(jié)構(gòu)。其中偏移數(shù)組存儲每個頂點對應(yīng)的第一條邊在邊數(shù)組中的地址,邊數(shù)組則按照頂點順序存儲每個頂點作為源頂點時,連接的所有邊的目的頂點序號。而圖應(yīng)用運算時產(chǎn)生的數(shù)據(jù)則存儲在頂點數(shù)組中。不同的圖應(yīng)用對應(yīng)的頂點數(shù)據(jù)內(nèi)容有所不同,例如在PageRank 算法中頂點數(shù)組存儲的是每個頂點對應(yīng)的網(wǎng)頁權(quán)重,而單源最短路徑算法中存儲的則是路徑長度。同時在某些需要權(quán)重的算法中,每條邊的權(quán)值也會被存儲在邊數(shù)組中,便于運行時讀取。

圖1 CSR 存儲格式示例

2.2 圖計算訪存特點

目前許多圖計算框架[15]都采用以頂點為中心(vertex-centric)的計算模式。在該計算模式下,對每個頂點屬性值進行計算時,需要讀取該頂點相鄰頂點的屬性值。當(dāng)使用CSR 格式存儲圖數(shù)據(jù)時,以PageRank(PR)算法為例,訪存過程如下:(1)訪問偏移數(shù)組讀取計算頂點第一條邊的偏移地址;(2)在邊數(shù)組中獲取該邊的目的頂點編號;(3)讀取頂點數(shù)組中對應(yīng)的屬性值;(4)對圖中所有活躍頂點重復(fù)上述操作直至完成計算。

在上述訪存過程中,由偏移數(shù)組到邊數(shù)組的訪問是第一級間接訪存,而由邊數(shù)組到頂點數(shù)組的訪問是第二級間接訪存。同時每個頂點對應(yīng)的目的頂點編號順序存儲在邊數(shù)組中,對其訪問時將生成線性訪存流。圖數(shù)據(jù)專用預(yù)取器需要正確識別上述訪存模式,完成對間接訪存和線性訪存模式的準確預(yù)取。

2.3 圖數(shù)據(jù)存儲特點

社區(qū)結(jié)構(gòu)是許多代表現(xiàn)實世界關(guān)系的圖數(shù)據(jù)集的重要特征之一[16-18]。社區(qū)是指在圖數(shù)據(jù)中,相對其余頂點聯(lián)接更為緊密的部分頂點的集合。

本文通過分析不同類型圖數(shù)據(jù)集鄰節(jié)點的分布規(guī)律來研究圖數(shù)據(jù)中社區(qū)結(jié)構(gòu)的儲存特點。為了表征上述特點,本文提出了2 個統(tǒng)計指標:一是儲存每個頂點鄰節(jié)點實際所需緩存行數(shù)量A;二是儲存每個頂點鄰節(jié)點所需最小緩存行數(shù)量B,B等于鄰頂點數(shù)量除以每個緩存行所能容納的最大頂點數(shù)量。在圖數(shù)據(jù)集中對上述2 個指標分別求和,得出二者的比例C,用于表示圖數(shù)據(jù)中鄰節(jié)點存儲的稀疏度。具體公式如下。

其中n是圖中頂點數(shù)量。默認圖數(shù)據(jù)中每個頂點大小為4 bytes,處理器緩存行大小為64 bytes。每個緩存行可以存儲16 個頂點。當(dāng)所有鄰節(jié)點連續(xù)分布時,A等于B,C取得最小值1。當(dāng)每個頂點連接的所有鄰節(jié)點都屬于不同的緩存行時,C取得最大值16。C值越大表明鄰節(jié)點存儲越稀疏,反之鄰節(jié)點儲存越密集。圖2 是不同圖數(shù)據(jù)集中C值的統(tǒng)計結(jié)果,其中數(shù)據(jù)集berkstan、indochina、arabic 的C值皆小于2,說明在上述圖數(shù)據(jù)集中大部分頂點的鄰節(jié)點存儲在鄰近位置。數(shù)據(jù)集google 和livej 的C值皆高于10,表明其頂點鄰節(jié)點整體分布較為稀疏。而數(shù)據(jù)集hollywood 的C值介于二者之間,只有部分頂點的鄰節(jié)點存儲較為緊密。

圖2 圖數(shù)據(jù)集中C 值統(tǒng)計

圖數(shù)據(jù)集之所以存在上述鄰頂點密集存儲的特點,是由于社區(qū)中頂點的鄰節(jié)點大概率屬于本社區(qū)。在圖計算中,連續(xù)處理同一社區(qū)的頂點可以有效提升訪存的時間局部性,許多研究利用上述特點對圖計算進行了優(yōu)化[19-21]。因此儲存圖數(shù)據(jù)時,同一社區(qū)的頂點被放置在內(nèi)存中的鄰近區(qū)域。對于隸屬于社區(qū)的頂點,其鄰頂點大概率分布在相近的存儲空間內(nèi)。對應(yīng)CSR 格式儲存的圖數(shù)據(jù)集,相同社區(qū)的頂點的屬性值連續(xù)儲存在頂點數(shù)組中。

在間接預(yù)取過程中,圖數(shù)據(jù)預(yù)取器在利用邊數(shù)組取回的數(shù)據(jù)對頂點數(shù)組進行間接預(yù)取時,只能取回邊數(shù)組當(dāng)前讀取頂點編號對應(yīng)的頂點屬性值。但考慮到圖數(shù)據(jù)集中社區(qū)的上述存儲特點,預(yù)取器可以利用讀取的邊數(shù)組中的鄰頂點編號對其余鄰頂點儲存地址進行猜測,發(fā)出對猜測鄰頂點的預(yù)取,達到提升預(yù)取及時性的目的。

3 預(yù)取器設(shè)計

本節(jié)將介紹本文所提出的預(yù)取器的設(shè)計方案和預(yù)取過程。下面將本文提出的預(yù)取器稱為圖結(jié)構(gòu)預(yù)取器(graph structure prefetcher,GSP)。

3.1 預(yù)取器系統(tǒng)級設(shè)計

圖3 為本文預(yù)取器系統(tǒng)級設(shè)計方案。預(yù)取器位于一級數(shù)據(jù)緩存和二級私有緩存之間,需要監(jiān)聽一級數(shù)據(jù)緩存收到的核內(nèi)訪求請求地址,以及由內(nèi)存返回一級數(shù)據(jù)緩存的數(shù)據(jù),并根據(jù)監(jiān)聽到的結(jié)果判斷是否發(fā)射對邊數(shù)組或頂點數(shù)組的預(yù)取,如果需要則計算出預(yù)取的訪存地址并發(fā)射。同時將預(yù)取器放置于一級數(shù)據(jù)緩存處,可以節(jié)省額外的TLB(translation lookaside buffer)設(shè)計開銷。預(yù)取請求分為兩部分,一是根據(jù)內(nèi)存返回數(shù)據(jù)發(fā)出的對頂點數(shù)組和邊數(shù)組的間接預(yù)取請求,該類預(yù)取請求直接放入一級數(shù)據(jù)緩存,這樣可以最大程度地減少訪問緩存的延遲。同時由于上述間接預(yù)取基本是準確的,不會對一級數(shù)據(jù)緩存造成污染。二是根據(jù)邊數(shù)組返回數(shù)據(jù)生成的對頂點數(shù)組的猜測預(yù)取,該類預(yù)取有一定的錯誤概率,因而將其放入二級緩存。

圖3 預(yù)取器系統(tǒng)級設(shè)計

預(yù)取器與處理器核間有通路連接,圖計算運行時會將偏移數(shù)組、邊數(shù)組和頂點數(shù)組的起始地址以及終止地址配置到預(yù)取器內(nèi)的寄存器中。用于判斷當(dāng)前訪存地址是否屬于圖數(shù)據(jù),并計算預(yù)取的地址。同時預(yù)取器也會訪問DTLB(data translation lookaside buffer),預(yù)取器中存儲的數(shù)組地址和內(nèi)存返回數(shù)據(jù)生成的地址皆為虛擬地址,所以GSP 計算出的預(yù)取地址也為虛擬地址。需要通過DTLB 進行虛實地址轉(zhuǎn)換,將對應(yīng)的物理地址發(fā)往緩存。

3.2 預(yù)取器構(gòu)成

如圖4 所示,GSP 預(yù)取器由3 部分組成,分別為圖數(shù)據(jù)地址寄存器、預(yù)取緩存隊列和預(yù)取地址生成器。其中圖數(shù)據(jù)地址寄存器用于存儲圖數(shù)據(jù)中3 類數(shù)組的起始地址與終止地址,判斷監(jiān)聽到的訪存地址是否屬于圖數(shù)據(jù),并參與預(yù)取地址的生成。本文通過軟硬件結(jié)合方式將程序運行時的圖數(shù)據(jù)地址范圍配置到上述寄存器中。具體過程為:(1)將預(yù)取器內(nèi)的寄存器設(shè)計成用戶態(tài)可以讀寫的配置寄存器;(2)在程序代碼中添加相應(yīng)指令將圖數(shù)據(jù)的虛擬地址范圍寫入該類配置寄存器中。相對于圖計算的運行時間,配置圖數(shù)據(jù)虛擬地址所需的軟件開銷可以忽略不計。

圖4 預(yù)取器構(gòu)成

預(yù)取地址生成器用于計算預(yù)取發(fā)出的地址,包括邊數(shù)組地址生成器和頂點數(shù)組地址生成器,最終將生成的預(yù)取地址發(fā)送到緩存隊列中。GSP 中只實現(xiàn)邊數(shù)組和頂點數(shù)組的預(yù)取,不對偏移數(shù)組進行預(yù)取。若實現(xiàn)對偏移數(shù)組的間接預(yù)取,需要在圖應(yīng)用代碼中添加相應(yīng)的數(shù)據(jù)結(jié)構(gòu)記錄待計算頂點編號,對算法改動較大。同時在規(guī)律性迭代類算法如PageRank 中,對偏移數(shù)組的預(yù)取可以通過處理器中原有的流式預(yù)取器實現(xiàn)。且偏移數(shù)組的訪存總量占比較小,因而無實現(xiàn)偏移數(shù)組間接預(yù)取的必要。緩存隊列用于緩存生成的預(yù)取請求,在處理器空閑時將預(yù)取請求發(fā)送到DTLB 中進行虛實地址翻譯生成對應(yīng)的物理地址,然后發(fā)往一級及二級緩存。

3.3 頂點數(shù)組地址預(yù)取

如圖5 所示,在頂點數(shù)組預(yù)取地址生成器中,頂點數(shù)組的預(yù)取分成兩部分,分別為間接預(yù)取和猜測預(yù)取。由于圖計算中對頂點數(shù)組的訪問是完全隨機的,因而流式預(yù)取器無法識別頂點數(shù)組的訪問模式。如果開啟流式預(yù)取反而造成緩存污染,所以當(dāng)訪存地址范圍屬于頂點數(shù)組時需要關(guān)閉流式預(yù)取。

圖5 頂點數(shù)組地址生成器

(1) 間接預(yù)取。預(yù)取器對寫回一級數(shù)據(jù)緩存的地址進行監(jiān)聽,并在圖數(shù)據(jù)地址寄存器中進行比較。當(dāng)該地址屬于邊數(shù)組時,將被寫回的數(shù)據(jù)寫入到頂點數(shù)組地址生成器中,并啟動對頂點數(shù)組的間接預(yù)取。邊數(shù)組返回的數(shù)據(jù)存儲的是頂點編號,假設(shè)每個編號生成的預(yù)取地址為PV,則:

其中vertex_begin代表頂點數(shù)組起始地址,存儲在地址寄存器中。vertex_id為返回數(shù)據(jù)中儲存的頂點編號。默認每個頂點需要4 bytes 的存儲空間。需要說明的是,每個緩存行大小為64 bytes,對于無權(quán)重圖每個頂點編號占用4 bytes 的存儲空間。在有權(quán)重圖中每條邊的權(quán)重和鄰頂點編號組合存儲需占用8 bytes 的存儲空間。所以每個緩存行可以存儲8或16 個頂點編號,最多生成16 項預(yù)取請求。具體的編號大小可以在程序運行前配置到預(yù)取器中,用于判斷如何讀取頂點編號。

預(yù)取地址生成后,還需要對所有的預(yù)取地址進行比較,合并重復(fù)的預(yù)取地址。同時由于偏移數(shù)組返回的數(shù)據(jù)中包含每個頂點對應(yīng)的邊數(shù)組的起始和終止地址,對于邊數(shù)組中超過當(dāng)前終止地址的數(shù)據(jù)不進行預(yù)取,以減少錯誤預(yù)取的發(fā)射,提升預(yù)取準確率。

(2) 猜測預(yù)取。在含有較多社區(qū)結(jié)構(gòu)的圖數(shù)據(jù)集中,由于對頂點數(shù)組的間接預(yù)取發(fā)出的緩存請求數(shù)量較少,不能充分利用內(nèi)存帶寬,導(dǎo)致預(yù)取及時性較差。所以為了提升圖數(shù)據(jù)預(yù)取性能,本文提出了頂點數(shù)組的猜測預(yù)取。

假設(shè)取回邊數(shù)組數(shù)據(jù)中包含的鄰頂點編號為{V0,V1,…,V15}?；谏弦还?jié)的分析結(jié)果,對于不屬于社區(qū)的頂點,上述鄰頂點分布存儲在最多16 個不同緩存行內(nèi)。而對于屬于社區(qū)的頂點,上述頂點很可能存儲在少量緩存行內(nèi)。為了判斷當(dāng)前鄰頂點是否密集存儲,GSP 預(yù)取器計算了V15 與V0 之間的差值D(鄰頂點一般按編號大小順序存儲,V15 為當(dāng)前最大編號值,而V0 為最小編號值)。當(dāng)其差值小于48 時,說明當(dāng)前鄰頂點最多分布在3 個緩存行內(nèi),預(yù)取器判定當(dāng)前鄰頂點密集存儲在內(nèi)存中,生成對頂點數(shù)組的猜測預(yù)取。而當(dāng)差值大于等于48 時,預(yù)取器認為當(dāng)前鄰頂點稀疏分布,不進行猜測預(yù)取。

為了提升預(yù)取的及時性,并充分利用帶寬,猜測預(yù)取生成時,要考慮到D值的大小。設(shè)頂點V15 的間接預(yù)取地址為Paddr,則生成的猜測預(yù)取地址與D值范圍關(guān)系如表1 所示。對于不同的D值,基于返回的邊數(shù)據(jù),猜測預(yù)取都保證了預(yù)取器每次至少發(fā)出4 項對頂點數(shù)組的預(yù)取。在模擬器中的實驗結(jié)果表明,該數(shù)值可以較為充分地利用當(dāng)前處理器的帶寬,并保證頂點數(shù)組預(yù)取的及時性。

表1 猜測預(yù)取地址生成

同樣的,如果邊數(shù)組返回地址超出當(dāng)前處理頂點的邊界,則不發(fā)出猜測預(yù)取。同時由于猜測預(yù)取存在一定的不確定性,所以最終的預(yù)取數(shù)據(jù)將存入二級緩存中,減少對一級數(shù)據(jù)緩存的污染。需要說明的是,對頂點數(shù)據(jù)進行猜測預(yù)取的過程是自動識別的,不需要預(yù)先識別當(dāng)前處理圖數(shù)據(jù)集的性質(zhì),可以在含有較多社區(qū)的圖數(shù)據(jù)集上實現(xiàn)顯著的性能提升。同時對于其他圖數(shù)據(jù)集,猜測預(yù)取能夠識別其中存在的密集存儲的鄰頂點,并進行預(yù)取,而對稀疏存儲的鄰頂點則不生成猜測預(yù)取。

3.4 邊數(shù)組地址預(yù)取

如圖6 所示,邊數(shù)組的預(yù)取也分成兩部分,分別為間接預(yù)取和流式預(yù)取。預(yù)取器首先監(jiān)聽核內(nèi)發(fā)往一級數(shù)據(jù)緩存的請求,當(dāng)其地址屬于偏移數(shù)組時,將該地址對應(yīng)的物理地址記錄到預(yù)取地址生成器中。然后當(dāng)監(jiān)聽到該地址對應(yīng)的數(shù)據(jù)返回到一級數(shù)據(jù)緩存時,將數(shù)據(jù)存入到邊數(shù)組地址生成器中。上述數(shù)據(jù)存儲的是每個頂點對應(yīng)邊數(shù)組的起始地址偏移值,通過之前記錄的偏移數(shù)組訪問地址篩選出當(dāng)前處理頂點對應(yīng)的偏移地址值。并根據(jù)圖數(shù)據(jù)地址寄存器中的邊數(shù)組的起始地址計算出邊數(shù)組間接預(yù)取地址值,設(shè)預(yù)取地址為PE,則:

圖6 邊數(shù)組地址生成器

其中offset為偏移數(shù)組返回的偏移地址值,edge_beign為預(yù)取器中存儲的邊數(shù)組起始地址?？梢钥闯?與頂點數(shù)組的間接預(yù)取不同的是,邊數(shù)組的間接預(yù)取只生成一項,而不會對返回的數(shù)據(jù)中所有的偏移值進行預(yù)取。這是因為在很多圖算法中,不是所有頂點都需要進行運算的,所以邊數(shù)組地址生成器記錄當(dāng)前處理頂點對應(yīng)的偏移數(shù)組地址,用于篩選需要使用的偏移地址值。

理論上來看,偏移數(shù)組返回的地址中包含每個頂點對應(yīng)的邊數(shù)組的起始地址和終止地址,因而可以通過間接預(yù)取實現(xiàn)對當(dāng)前處理頂點對應(yīng)的全部邊數(shù)據(jù)的預(yù)取。但是如果按照上述模式進行間接預(yù)取,則部分邊數(shù)據(jù)過早地被存入一級數(shù)據(jù)緩存中,很可能在其被訪問時,已經(jīng)被替換出緩存,導(dǎo)致預(yù)取失效。為了解決上述問題,GSP 預(yù)取器只對每個頂點對應(yīng)邊數(shù)組的起始地址實現(xiàn)間接預(yù)取,因為該地址無法通過其他方式準確預(yù)測。而對于剩余的邊數(shù)組地址,GSP 采用流式預(yù)取方式,當(dāng)監(jiān)聽到來自核內(nèi)的訪存地址屬于邊數(shù)組時,發(fā)出的預(yù)取地址為該地址加256,即該地址后面第4 個緩存行的地址。這樣做的目的是保證預(yù)取的及時性,使得發(fā)出的預(yù)取能夠在真正請求到來前取回一級數(shù)據(jù)緩存。通常的流式預(yù)取中存在啟動開銷,即每個訪存流的前幾項不能及時被取回。為了緩解上述問題,GSP 預(yù)取器在生成對邊數(shù)組的間接預(yù)取的同時,完成對間接預(yù)取地址后3 個緩存行的預(yù)取,一定程度上減少了每個頂點對應(yīng)邊數(shù)組預(yù)取的啟動開銷。

3.5 預(yù)取器設(shè)計開銷

為了評估預(yù)取器的設(shè)計開銷,本文使用Verilog編程語言在龍芯處理器核內(nèi)完成了GSP 預(yù)取器的寄存器傳輸級(RTL)實現(xiàn),并在28 nm 工藝下對該設(shè)計進行了面積與功耗評估,處理器運行頻率為2.5 GHz。結(jié)果如表2 所示,GSP 預(yù)取器占核內(nèi)總面積的0.16%,運行功耗占核內(nèi)總功耗的0.23%。

表2 預(yù)取器面積功耗統(tǒng)計

由于DROPLET 預(yù)取器沒有進行精確的RTL 級面積與時序評估。本文將從存儲容量角度進行對比,GSP 預(yù)取器儲存開銷主要來自緩存隊列,用于緩存預(yù)取的虛擬地址,占用1 kB 的儲存空間(主要來自128 項64 bits 的寄存器),而DROPLET 預(yù)取器共使用了7.7 kB 的儲存空間。這是由于DROPLET 預(yù)取器需要在內(nèi)存控制處添加TLB 進行虛實地址轉(zhuǎn)換,而GSP 預(yù)取器通過直接訪問核內(nèi)DTLB 節(jié)省了上述存儲開銷。

4 實驗結(jié)果與分析

本節(jié)將介紹實驗所用數(shù)據(jù)和平臺,展示最終的實驗結(jié)果并進行分析。

4.1 測試輸入

為了驗證預(yù)取器的性能表現(xiàn),本文選取了GAP測試集內(nèi)的5 種常見圖算法。如表3 所示,其中PR算法為全部頂點參與計算的迭代算法,相對于其他算法訪存規(guī)律性更強。其余算法頂點處理較為隨機,間接預(yù)取可以實現(xiàn)更高的性能提升。而SSSP 算法需要在帶權(quán)重的圖數(shù)據(jù)集上運行。

表3 圖算法描述

表4 展示了本文選取的4 種不同類型的真實圖數(shù)據(jù)集,均來自社交網(wǎng)絡(luò)和網(wǎng)頁數(shù)據(jù)。頂點規(guī)模范圍為0.68 M～22 M,平均度數(shù)范圍為11～105。由于模擬器上運行時間的限制,實驗中沒有選取較大規(guī)模的圖數(shù)據(jù)集。但本文的預(yù)取器設(shè)計是基于圖數(shù)據(jù)鄰節(jié)點的存儲特點,與圖數(shù)據(jù)規(guī)模無關(guān)。且預(yù)取數(shù)據(jù)最終放入一級或二級緩存內(nèi),而選取的圖數(shù)據(jù)規(guī)模皆大于二者容量,可以驗證性能提升。同時本文的實驗結(jié)論將同樣適用于大規(guī)模圖數(shù)據(jù)集。

表4 圖數(shù)據(jù)集描述

4.2 測試平臺

本文使用的模擬器為sniper[28],是一款事件級精確的CPU 模擬器。相對其他周期級精確的模擬器,sniper 在保證一定模擬精度的前提下,能夠?qū)崿F(xiàn)更快的模擬速度,適合模擬運行時間較長的圖計算應(yīng)用。模擬器的配置如表5 所示,采用四核心結(jié)構(gòu)模擬圖計算并行運行情況,同時將算法代碼中關(guān)鍵部分標記為熱點區(qū)域,以縮短總的模擬時間。對于熱點區(qū)域,模擬時開啟detail 模式,精確模擬處理器各部分運行狀態(tài)。程序進入熱點區(qū)域前運行在cache warm-up 模式下,在熱點區(qū)域模擬開始前對緩存進行預(yù)熱,同時本文選取GAP 作為圖計算的軟件框架。相對于其他復(fù)雜框架如ligra 等,GAP 針對處理器進行的優(yōu)化更少,可以較好地反映圖計算運行時的真正瓶頸,便于驗證預(yù)取器改進對圖計算性能的影響。

表5 模擬器配置信息

4.3 性能對比與分析

為了驗證GSP 預(yù)取器的性能提升效果,本文選取了幾種預(yù)取器與其進行了性能對比,如表6 所示。其中TGP(traditional graph prefetcher)為傳統(tǒng)的圖數(shù)據(jù)預(yù)取器,其設(shè)計理念與最新的DROPLET 預(yù)取器相同,對頂點數(shù)組采用間接預(yù)取,對邊數(shù)組采用流式預(yù)取。但預(yù)取位置并非在內(nèi)存控制器處,因為該設(shè)計需要添加額外的TLB,且要在共享緩存處增加一致性判斷,較難在實際處理器中實現(xiàn)。因而本文將該預(yù)取器放置在一級緩存處,更好地與本文預(yù)取器進行對比,驗證GSP 預(yù)取器的相對性能提升。

表6 實驗預(yù)取器介紹

圖7 為上述預(yù)取器相對無預(yù)取情況的性能提升比例,在5 種圖算法和4 種圖數(shù)據(jù)集共20 個測試點中,本文預(yù)取器都實現(xiàn)了最高的性能提升。

圖7 性能提升比例統(tǒng)計結(jié)果

表7 為各類預(yù)取器在不同圖算法下的平均性能提升,其中GHB 預(yù)取器性能表現(xiàn)最差,相對無預(yù)取情況性能提升最低,在PR 算法上甚至產(chǎn)生了性能下降。這是由于GHB 預(yù)取器對整個訪存歷史進行緩存,不能識別圖數(shù)據(jù)中3個數(shù)組訪存規(guī)律的差異。但圖計算全局訪存行為是無規(guī)律的,導(dǎo)致GHB 預(yù)取器無法在圖應(yīng)用上取得性能提升。而stream 預(yù)取器能夠?qū)崿F(xiàn)對不同地址范圍的訪存流的同時預(yù)取,因而可以識別CSR 格式中的3 個數(shù)組,實現(xiàn)了對邊數(shù)組部分地址的準確預(yù)取。同時在社區(qū)中,由于鄰頂點的密集存儲,部分情況下,stream 預(yù)取器可以成功預(yù)取頂點數(shù)組的訪存地址,最終實現(xiàn)了較高的性能提升。TGP 預(yù)取器的性能提升高于stream 預(yù)取器。TGP 預(yù)取器能夠利用訪存數(shù)據(jù)準確預(yù)取頂點數(shù)組的訪存地址,預(yù)取準確性高于stream 預(yù)取器。但由于TGP 預(yù)取器需等到訪存數(shù)據(jù)返回才能發(fā)出間接預(yù)取,導(dǎo)致部分預(yù)取不能及時取回到相應(yīng)緩存,預(yù)取及時性弱于stream 預(yù)取器。

表7 不同算法平均性能提升

而本文提出的GSP 預(yù)取器在5 種圖算法上皆實現(xiàn)了最高的性能提升,相對于TGP 預(yù)取器的性能提升分別為4.23%(PR)、9.72%(BFS)、18.08%(CC)、7.74%(BC)、15.4%(SSSP)。產(chǎn)生該性能提升有2 個原因:一是GSP 實現(xiàn)了對頂點數(shù)組的猜測預(yù)取,提升了該類數(shù)據(jù)的預(yù)取及時性;二是GSP 對邊數(shù)組進行了間接與流式混合預(yù)取,相比TGP 進一步提升了邊數(shù)組預(yù)取的準確性和覆蓋率。從圖算法的角度看,GSP 在PR 算法上性能相對提升最小,因為PR 算法訪存行為規(guī)律性最強,邊數(shù)組的訪存接近流式訪存。頂點數(shù)組順序處理,隨機性最弱,因而GSP 預(yù)取器相對提升最小。而在其他算法中,由于頂點處理具有較強的隨機性,導(dǎo)致邊數(shù)組和頂點數(shù)組的訪問不規(guī)律,GSP 預(yù)取器能更好地發(fā)揮自身的優(yōu)勢。

4.4 預(yù)取及時性與準確性

評價預(yù)取器的性能有3 個指標,即準確率、及時率和覆蓋率。其中準確率是命中的預(yù)取數(shù)量與發(fā)出的預(yù)取數(shù)量的比值,準確率越高表明預(yù)取器發(fā)出的錯誤預(yù)取越少,對內(nèi)存帶寬浪費越小。而及時率是準確發(fā)出預(yù)取中已經(jīng)取回到對應(yīng)緩存的比率,及時率越高則真實請求命中預(yù)取后等待的時間越短,處理器內(nèi)數(shù)據(jù)供應(yīng)得更快。覆蓋率則是預(yù)取器發(fā)出的預(yù)取數(shù)量占程序中數(shù)據(jù)能夠被預(yù)取數(shù)量的比率,覆蓋率越高表明預(yù)取器的算法越準確。但對圖數(shù)據(jù)進行間接預(yù)取時,對于占較大訪存比例的頂點數(shù)組,其預(yù)取覆蓋率為100%。所以在對預(yù)取器進行性能分析時,本文不對覆蓋率進行統(tǒng)計。

將TGP 預(yù)取器和GSP 預(yù)取器在5 個圖算法上的預(yù)取準確率進行了對比。結(jié)果如圖8 所示,TGP預(yù)取器在所有測試點上的準確率皆高于GSP 預(yù)取器,這是由于GSP 預(yù)取器相對TGP 預(yù)取器對邊數(shù)組進行了間接預(yù)取,對頂點數(shù)據(jù)進行了猜測預(yù)取。后者由于是猜測預(yù)取,會導(dǎo)致部分錯誤預(yù)取請求的發(fā)出,降低了GSP 預(yù)取器的準確率。因而GSP 預(yù)取器將頂點數(shù)組的猜測預(yù)取放入二級緩存處,一定程度地降低了錯誤預(yù)取帶來的性能損失。從圖算法的角度看,GSP 在5 類圖算法上的平均準確率分別為85.22% (PR)、82.36% (BFS)、74.16% (CC)、38.05%(BC)、74.46%(SSSP)。對PR 算法的預(yù)取準確率最高,因為PR 算法對頂點進行順序處理,隨機性最小。而BC 算法的預(yù)取準確率最低,該算法對頂點的處理順序較為隨機,邊數(shù)組和頂點數(shù)組的訪存規(guī)律性較弱。

圖8 預(yù)取準確率統(tǒng)計結(jié)果

圖9 為2 類預(yù)取器預(yù)取及時性的統(tǒng)計結(jié)果?？梢钥吹?在所有測試點處,GSP 預(yù)取器的預(yù)取及時率皆高于TGP 預(yù)取器。GSP 預(yù)取器通過對頂點數(shù)組進行猜測預(yù)取,有效利用了圖數(shù)據(jù)中鄰頂點的存儲規(guī)律,及時發(fā)出了對頂點數(shù)組的預(yù)取。大幅度縮減了訪存延遲,是GSP 預(yù)取器相對于TGP 預(yù)取器產(chǎn)生性能提升的主要原因。

圖9 預(yù)取及時率統(tǒng)計結(jié)果

5 結(jié)論

本文通過對不同類型圖數(shù)據(jù)集儲存規(guī)律的研究,發(fā)現(xiàn)了圖數(shù)據(jù)集社區(qū)結(jié)構(gòu)中鄰頂點緊密存儲的特點,進而提出了利用該特性的圖數(shù)據(jù)預(yù)取器設(shè)計方案。通過實現(xiàn)頂點數(shù)組的猜測預(yù)取,大幅提升了圖數(shù)據(jù)預(yù)取的及時性,同時增加了對邊數(shù)組的間接預(yù)取,添加了頂點數(shù)組間接預(yù)取發(fā)出的限制條件,提升了圖數(shù)據(jù)預(yù)取的準確率和覆蓋率。最終在5 種圖算法和4 類圖數(shù)據(jù)集共20 個測試點上對本文提出的預(yù)取器進行了測試。實驗結(jié)果表明,本文提出的預(yù)取器相對于無預(yù)取情況實現(xiàn)了65%～176%的性能提升,相對于傳統(tǒng)圖數(shù)據(jù)預(yù)取器實現(xiàn)了4.32%～18.08%的性能提升。