李 策 章隆兵

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

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

0 引言

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

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

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

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

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

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

(2)提出了新的圖數(shù)據(jù)預(yù)取器設(shè)計(jì)方案。利用社區(qū)結(jié)構(gòu)中鄰頂點(diǎn)的存儲(chǔ)規(guī)律,對(duì)圖數(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ù)集上對(duì)上述預(yù)取器設(shè)計(jì)進(jìn)行驗(yàn)證。結(jié)果表明該預(yù)取器相對(duì)于現(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]等,通常通過(guò)學(xué)習(xí)地址流中的步長(zhǎng)歷史進(jìn)行訪存預(yù)取,無(wú)法識(shí)別圖計(jì)算中的間接訪存模式。

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

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

2 研究背景

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

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

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

圖1 CSR 存儲(chǔ)格式示例

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

如圖4 所示,GSP 預(yù)取器由3 部分組成,分別為圖數(shù)據(jù)地址寄存器、預(yù)取緩存隊(duì)列和預(yù)取地址生成器。其中圖數(shù)據(jù)地址寄存器用于存儲(chǔ)圖數(shù)據(jù)中3 類數(shù)組的起始地址與終止地址,判斷監(jiān)聽到的訪存地址是否屬于圖數(shù)據(jù),并參與預(yù)取地址的生成。本文通過(guò)軟硬件結(jié)合方式將程序運(yùn)行時(shí)的圖數(shù)據(jù)地址范圍配置到上述寄存器中。具體過(guò)程為:(1)將預(yù)取器內(nèi)的寄存器設(shè)計(jì)成用戶態(tài)可以讀寫的配置寄存器;(2)在程序代碼中添加相應(yīng)指令將圖數(shù)據(jù)的虛擬地址范圍寫入該類配置寄存器中。相對(duì)于圖計(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ù)取,不對(duì)偏移數(shù)組進(jìn)行預(yù)取。若實(shí)現(xiàn)對(duì)偏移數(shù)組的間接預(yù)取,需要在圖應(yīng)用代碼中添加相應(yīng)的數(shù)據(jù)結(jié)構(gòu)記錄待計(jì)算頂點(diǎn)編號(hào),對(duì)算法改動(dòng)較大。同時(shí)在規(guī)律性迭代類算法如PageRank 中,對(duì)偏移數(shù)組的預(yù)取可以通過(guò)處理器中原有的流式預(yù)取器實(shí)現(xiàn)。且偏移數(shù)組的訪存總量占比較小,因而無(wú)實(shí)現(xiàn)偏移數(shù)組間接預(yù)取的必要。緩存隊(duì)列用于緩存生成的預(yù)取請(qǐng)求,在處理器空閑時(shí)將預(yù)取請(qǐng)求發(fā)送到DTLB 中進(jìn)行虛實(shí)地址翻譯生成對(duì)應(yīng)的物理地址,然后發(fā)往一級(jí)及二級(jí)緩存。

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

為了評(píng)估預(yù)取器的設(shè)計(jì)開銷,本文使用Verilog編程語(yǔ)言在龍芯處理器核內(nèi)完成了GSP 預(yù)取器的寄存器傳輸級(jí)(RTL)實(shí)現(xiàn),并在28 nm 工藝下對(duì)該設(shè)計(jì)進(jìn)行了面積與功耗評(píng)估,處理器運(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ù)取器沒(méi)有進(jìn)行精確的RTL 級(jí)面積與時(shí)序評(píng)估。本文將從存儲(chǔ)容量角度進(jìn)行對(duì)比,GSP 預(yù)取器儲(chǔ)存開銷主要來(lái)自緩存隊(duì)列,用于緩存預(yù)取的虛擬地址,占用1 kB 的儲(chǔ)存空間(主要來(lái)自128 項(xiàng)64 bits 的寄存器),而DROPLET 預(yù)取器共使用了7.7 kB 的儲(chǔ)存空間。這是由于DROPLET 預(yù)取器需要在內(nèi)存控制處添加TLB 進(jìn)行虛實(shí)地址轉(zhuǎn)換,而GSP 預(yù)取器通過(guò)直接訪問(wèn)核內(nèi)DTLB 節(jié)省了上述存儲(chǔ)開銷。

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

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

4.1 測(cè)試輸入

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

表3 圖算法描述

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

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

4.2 測(cè)試平臺(tái)

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

表5 模擬器配置信息

4.3 性能對(duì)比與分析

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

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

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

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

表7 為各類預(yù)取器在不同圖算法下的平均性能提升,其中GHB 預(yù)取器性能表現(xiàn)最差,相對(duì)無(wú)預(yù)取情況性能提升最低,在PR 算法上甚至產(chǎn)生了性能下降。這是由于GHB 預(yù)取器對(duì)整個(gè)訪存歷史進(jìn)行緩存,不能識(shí)別圖數(shù)據(jù)中3個(gè)數(shù)組訪存規(guī)律的差異。但圖計(jì)算全局訪存行為是無(wú)規(guī)律的,導(dǎo)致GHB 預(yù)取器無(wú)法在圖應(yīng)用上取得性能提升。而stream 預(yù)取器能夠?qū)崿F(xiàn)對(duì)不同地址范圍的訪存流的同時(shí)預(yù)取,因而可以識(shí)別CSR 格式中的3 個(gè)數(shù)組,實(shí)現(xiàn)了對(duì)邊數(shù)組部分地址的準(zhǔn)確預(yù)取。同時(shí)在社區(qū)中,由于鄰頂點(diǎn)的密集存儲(chǔ),部分情況下,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)了最高的性能提升,相對(duì)于TGP 預(yù)取器的性能提升分別為4.23%(PR)、9.72%(BFS)、18.08%(CC)、7.74%(BC)、15.4%(SSSP)。產(chǎn)生該性能提升有2 個(gè)原因:一是GSP 實(shí)現(xiàn)了對(duì)頂點(diǎn)數(shù)組的猜測(cè)預(yù)取,提升了該類數(shù)據(jù)的預(yù)取及時(shí)性;二是GSP 對(duì)邊數(shù)組進(jìn)行了間接與流式混合預(yù)取,相比TGP 進(jìn)一步提升了邊數(shù)組預(yù)取的準(zhǔn)確性和覆蓋率。從圖算法的角度看,GSP 在PR 算法上性能相對(duì)提升最小,因?yàn)镻R 算法訪存行為規(guī)律性最強(qiáng),邊數(shù)組的訪存接近流式訪存。頂點(diǎn)數(shù)組順序處理,隨機(jī)性最弱,因而GSP 預(yù)取器相對(duì)提升最小。而在其他算法中,由于頂點(diǎn)處理具有較強(qiáng)的隨機(jī)性,導(dǎo)致邊數(shù)組和頂點(diǎn)數(shù)組的訪問(wèn)不規(guī)律,GSP 預(yù)取器能更好地發(fā)揮自身的優(yōu)勢(shì)。

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

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

將TGP 預(yù)取器和GSP 預(yù)取器在5 個(gè)圖算法上的預(yù)取準(zhǔn)確率進(jìn)行了對(duì)比。結(jié)果如圖8 所示,TGP預(yù)取器在所有測(cè)試點(diǎn)上的準(zhǔn)確率皆高于GSP 預(yù)取器,這是由于GSP 預(yù)取器相對(duì)TGP 預(yù)取器對(duì)邊數(shù)組進(jìn)行了間接預(yù)取,對(duì)頂點(diǎn)數(shù)據(jù)進(jìn)行了猜測(cè)預(yù)取。后者由于是猜測(cè)預(yù)取,會(huì)導(dǎo)致部分錯(cuò)誤預(yù)取請(qǐng)求的發(fā)出,降低了GSP 預(yù)取器的準(zhǔn)確率。因而GSP 預(yù)取器將頂點(diǎn)數(shù)組的猜測(cè)預(yù)取放入二級(jí)緩存處,一定程度地降低了錯(cuò)誤預(yù)取帶來(lái)的性能損失。從圖算法的角度看,GSP 在5 類圖算法上的平均準(zhǔn)確率分別為85.22% (PR)、82.36% (BFS)、74.16% (CC)、38.05%(BC)、74.46%(SSSP)。對(duì)PR 算法的預(yù)取準(zhǔn)確率最高,因?yàn)镻R 算法對(duì)頂點(diǎn)進(jìn)行順序處理,隨機(jī)性最小。而BC 算法的預(yù)取準(zhǔn)確率最低,該算法對(duì)頂點(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é)果?？梢钥吹?在所有測(cè)試點(diǎn)處,GSP 預(yù)取器的預(yù)取及時(shí)率皆高于TGP 預(yù)取器。GSP 預(yù)取器通過(guò)對(duì)頂點(diǎn)數(shù)組進(jìn)行猜測(cè)預(yù)取,有效利用了圖數(shù)據(jù)中鄰頂點(diǎn)的存儲(chǔ)規(guī)律,及時(shí)發(fā)出了對(duì)頂點(diǎn)數(shù)組的預(yù)取。大幅度縮減了訪存延遲,是GSP 預(yù)取器相對(duì)于TGP 預(yù)取器產(chǎn)生性能提升的主要原因。

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

5 結(jié)論

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