李 策 章隆兵

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

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

0 引言

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

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

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

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

本文的主要貢獻(xiàn)有以下3 個方面。

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

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

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

1 相關(guān)工作

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

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

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

2 研究背景

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

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

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

圖1 CSR 存儲格式示例

2.2 圖計(jì)算訪存特點(diǎn)

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

4 實(shí)驗(yàn)結(jié)果與分析

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

4.1 測試輸入

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

表3 圖算法描述

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

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

4.2 測試平臺

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

表5 模擬器配置信息

4.3 性能對比與分析

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

表6 實(shí)驗(yàn)預(yù)取器介紹

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

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

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

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

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

4.4 預(yù)取及時(shí)性與準(zhǔn)確性

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

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

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

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

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

5 結(jié)論

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