• <tr id="yyy80"></tr>
  • <sup id="yyy80"></sup>
  • <tfoot id="yyy80"><noscript id="yyy80"></noscript></tfoot>
  • 99热精品在线国产_美女午夜性视频免费_国产精品国产高清国产av_av欧美777_自拍偷自拍亚洲精品老妇_亚洲熟女精品中文字幕_www日本黄色视频网_国产精品野战在线观看 ?

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

    2022-03-23 07:33:12章隆兵
    高技術(shù)通訊 2022年12期
    關(guān)鍵詞:數(shù)組頂點內(nèi)存

    李 策 章隆兵

    (計算機體系結(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%的性能提升。

    猜你喜歡
    數(shù)組頂點內(nèi)存
    JAVA稀疏矩陣算法
    電腦報(2022年13期)2022-04-12 00:32:38
    過非等腰銳角三角形頂點和垂心的圓的性質(zhì)及應(yīng)用(下)
    JAVA玩轉(zhuǎn)數(shù)學(xué)之二維數(shù)組排序
    電腦報(2020年24期)2020-07-15 06:12:41
    “春夏秋冬”的內(nèi)存
    關(guān)于頂點染色的一個猜想
    尋找勾股數(shù)組的歷程
    基于內(nèi)存的地理信息訪問技術(shù)
    VB數(shù)組在for循環(huán)中的應(yīng)用
    考試周刊(2012年88期)2012-04-29 04:36:47
    數(shù)學(xué)問答
    上網(wǎng)本為什么只有1GB?
    日韩av不卡免费在线播放| 国产老妇伦熟女老妇高清| 一二三四在线观看免费中文在| 在线天堂中文资源库| 欧美精品亚洲一区二区| 亚洲图色成人| 丝袜喷水一区| www.精华液| 涩涩av久久男人的天堂| 少妇精品久久久久久久| 国产日韩一区二区三区精品不卡| 久久中文字幕一级| 国产女主播在线喷水免费视频网站| 国产熟女午夜一区二区三区| 人人澡人人妻人| www日本在线高清视频| 91字幕亚洲| av欧美777| 99精国产麻豆久久婷婷| 亚洲国产av新网站| 一区二区三区四区激情视频| 丰满饥渴人妻一区二区三| 亚洲精品一区蜜桃| 国产在线视频一区二区| 青草久久国产| av天堂久久9| 不卡av一区二区三区| 在线亚洲精品国产二区图片欧美| 久久久欧美国产精品| 最近中文字幕2019免费版| 欧美精品一区二区免费开放| av天堂久久9| 老司机深夜福利视频在线观看 | 久久人人爽人人片av| 国产在线观看jvid| 欧美人与善性xxx| 男女下面插进去视频免费观看| 日韩制服骚丝袜av| 午夜日韩欧美国产| 国产亚洲av高清不卡| 久久国产精品男人的天堂亚洲| 捣出白浆h1v1| 久9热在线精品视频| 激情五月婷婷亚洲| 欧美 亚洲 国产 日韩一| 自线自在国产av| 十八禁网站网址无遮挡| 欧美日韩视频精品一区| 久久热在线av| 久久久久久免费高清国产稀缺| 80岁老熟妇乱子伦牲交| 久久99一区二区三区| 欧美日韩成人在线一区二区| 在线av久久热| 超色免费av| 人人妻人人添人人爽欧美一区卜| 18在线观看网站| 国产精品 国内视频| 免费观看人在逋| 亚洲国产欧美一区二区综合| 在线观看免费午夜福利视频| 免费av中文字幕在线| 日韩 亚洲 欧美在线| 久久久精品免费免费高清| 男的添女的下面高潮视频| 日韩av免费高清视频| 成年人午夜在线观看视频| 国产一区有黄有色的免费视频| 久久人妻福利社区极品人妻图片 | 欧美 日韩 精品 国产| 十八禁网站网址无遮挡| bbb黄色大片| 久久精品久久精品一区二区三区| 999久久久国产精品视频| 在线精品无人区一区二区三| 日韩制服骚丝袜av| 欧美人与性动交α欧美软件| 成人午夜精彩视频在线观看| 大香蕉久久成人网| 高清不卡的av网站| av在线老鸭窝| 久久精品成人免费网站| 高潮久久久久久久久久久不卡| 妹子高潮喷水视频| 久久精品人人爽人人爽视色| xxx大片免费视频| 咕卡用的链子| 国产成人av激情在线播放| 在线观看免费视频网站a站| 国产片特级美女逼逼视频| 手机成人av网站| 国产无遮挡羞羞视频在线观看| 韩国高清视频一区二区三区| 飞空精品影院首页| 亚洲少妇的诱惑av| 国产亚洲av片在线观看秒播厂| 亚洲精品一区蜜桃| 韩国精品一区二区三区| 乱人伦中国视频| 国产精品麻豆人妻色哟哟久久| 免费在线观看完整版高清| 国产在线免费精品| 精品国产乱码久久久久久男人| 国产有黄有色有爽视频| 一二三四社区在线视频社区8| 免费高清在线观看日韩| 精品福利永久在线观看| 亚洲熟女精品中文字幕| 可以免费在线观看a视频的电影网站| 2021少妇久久久久久久久久久| 国产又爽黄色视频| 久久99一区二区三区| 多毛熟女@视频| 又紧又爽又黄一区二区| 亚洲久久久国产精品| 在线观看免费午夜福利视频| 亚洲自偷自拍图片 自拍| 男人添女人高潮全过程视频| 成人手机av| 亚洲,一卡二卡三卡| 男人舔女人的私密视频| 久久99一区二区三区| 国产片内射在线| 久久久久久免费高清国产稀缺| 看免费成人av毛片| 成年女人毛片免费观看观看9 | 少妇精品久久久久久久| 91国产中文字幕| 亚洲精品av麻豆狂野| 亚洲图色成人| 日韩av在线免费看完整版不卡| 久久久久久久久免费视频了| videos熟女内射| 亚洲国产最新在线播放| 97在线人人人人妻| 麻豆av在线久日| 青青草视频在线视频观看| 亚洲 国产 在线| 视频区欧美日本亚洲| 国产麻豆69| 亚洲精品av麻豆狂野| 亚洲av在线观看美女高潮| 99精国产麻豆久久婷婷| 久久久精品94久久精品| 国产精品一二三区在线看| 大香蕉久久网| 一级片'在线观看视频| 欧美成人午夜精品| 国产一卡二卡三卡精品| 亚洲av男天堂| 韩国高清视频一区二区三区| 午夜福利在线免费观看网站| 伦理电影免费视频| 嫩草影视91久久| 久久精品国产亚洲av高清一级| 欧美国产精品一级二级三级| 亚洲精品一区蜜桃| 麻豆av在线久日| av国产精品久久久久影院| av在线app专区| 欧美在线一区亚洲| 99国产精品99久久久久| 美女中出高潮动态图| 十八禁人妻一区二区| 中文字幕av电影在线播放| 91成人精品电影| 国产精品久久久久久人妻精品电影 | 不卡av一区二区三区| 国产精品香港三级国产av潘金莲 | av线在线观看网站| 电影成人av| 欧美大码av| 天天躁夜夜躁狠狠躁躁| a级毛片在线看网站| 亚洲欧洲日产国产| 丰满人妻熟妇乱又伦精品不卡| 亚洲少妇的诱惑av| 天天躁夜夜躁狠狠躁躁| 精品一区二区三卡| 一二三四社区在线视频社区8| 99精国产麻豆久久婷婷| 国产黄频视频在线观看| 我的亚洲天堂| 纯流量卡能插随身wifi吗| 成年人免费黄色播放视频| 波多野结衣一区麻豆| 天天躁日日躁夜夜躁夜夜| 久久久精品免费免费高清| 欧美日韩一级在线毛片| 国产精品一区二区精品视频观看| 国产av精品麻豆| 久久久国产一区二区| 国产片特级美女逼逼视频| 十八禁网站网址无遮挡| 亚洲国产欧美在线一区| 久久人人97超碰香蕉20202| 一级毛片黄色毛片免费观看视频| 亚洲,一卡二卡三卡| 日韩视频在线欧美| 亚洲欧洲国产日韩| 国产黄色视频一区二区在线观看| 久久国产精品大桥未久av| 伦理电影免费视频| 99久久人妻综合| 美女大奶头黄色视频| 国产av国产精品国产| 精品一区二区三卡| 两人在一起打扑克的视频| 精品少妇一区二区三区视频日本电影| 51午夜福利影视在线观看| 国产高清videossex| 亚洲国产精品国产精品| 欧美精品一区二区免费开放| 最近手机中文字幕大全| 亚洲av综合色区一区| 一本大道久久a久久精品| 性少妇av在线| 欧美亚洲 丝袜 人妻 在线| 国产成人91sexporn| 99久久99久久久精品蜜桃| 纯流量卡能插随身wifi吗| 免费在线观看完整版高清| 如日韩欧美国产精品一区二区三区| 99热网站在线观看| 少妇 在线观看| 人人妻人人爽人人添夜夜欢视频| 别揉我奶头~嗯~啊~动态视频 | 久久久久视频综合| 一边摸一边抽搐一进一出视频| 久久狼人影院| 国产不卡av网站在线观看| 成人手机av| 久久 成人 亚洲| 欧美成人精品欧美一级黄| 国产一卡二卡三卡精品| 亚洲精品日韩在线中文字幕| 99热国产这里只有精品6| 国产男人的电影天堂91| 丰满人妻熟妇乱又伦精品不卡| 91精品伊人久久大香线蕉| 免费高清在线观看视频在线观看| av片东京热男人的天堂| av国产久精品久网站免费入址| 999精品在线视频| 中文字幕人妻丝袜一区二区| 成人手机av| 国产精品一区二区在线不卡| 亚洲精品在线美女| 免费少妇av软件| 欧美日韩av久久| 亚洲精品国产区一区二| 午夜福利,免费看| 精品一区二区三区四区五区乱码 | 色视频在线一区二区三区| 欧美成人精品欧美一级黄| 男女无遮挡免费网站观看| 这个男人来自地球电影免费观看| 免费久久久久久久精品成人欧美视频| 午夜激情av网站| 一级毛片电影观看| 国产成人精品久久二区二区免费| 老司机靠b影院| 国产精品久久久人人做人人爽| 成人亚洲欧美一区二区av| 欧美日韩成人在线一区二区| 少妇人妻久久综合中文| xxx大片免费视频| 成人18禁高潮啪啪吃奶动态图| 久久久久久免费高清国产稀缺| 日韩电影二区| 亚洲成色77777| 99精品久久久久人妻精品| 亚洲欧美清纯卡通| 国产又色又爽无遮挡免| 欧美精品一区二区免费开放| 国产极品粉嫩免费观看在线| 亚洲国产精品成人久久小说| 黑人巨大精品欧美一区二区蜜桃| 深夜精品福利| 99热国产这里只有精品6| 2021少妇久久久久久久久久久| 精品亚洲乱码少妇综合久久| 国产亚洲欧美在线一区二区| 人人妻人人澡人人看| 国产免费视频播放在线视频| 亚洲av综合色区一区| 人人妻人人澡人人爽人人夜夜| 国产成人影院久久av| 伦理电影免费视频| 午夜两性在线视频| 国产午夜精品一二区理论片| 天堂中文最新版在线下载| 肉色欧美久久久久久久蜜桃| 午夜av观看不卡| 午夜老司机福利片| 午夜免费鲁丝| 侵犯人妻中文字幕一二三四区| 久久久精品免费免费高清| 少妇裸体淫交视频免费看高清 | 欧美精品亚洲一区二区| 亚洲专区中文字幕在线| 免费少妇av软件| 免费在线观看完整版高清| 麻豆av在线久日| 国产一区二区 视频在线| 国产精品国产三级国产专区5o| 男女无遮挡免费网站观看| 色94色欧美一区二区| 国产成人精品无人区| 操出白浆在线播放| 国产人伦9x9x在线观看| 亚洲精品日本国产第一区| 久久精品久久久久久久性| 欧美97在线视频| 亚洲美女黄色视频免费看| av又黄又爽大尺度在线免费看| 亚洲色图综合在线观看| 国产xxxxx性猛交| 五月开心婷婷网| 热99久久久久精品小说推荐| 美女午夜性视频免费| 亚洲av欧美aⅴ国产| 男女高潮啪啪啪动态图| 久久久久久免费高清国产稀缺| 午夜福利免费观看在线| 亚洲综合色网址| 久久久久久免费高清国产稀缺| 国产精品av久久久久免费| 国产激情久久老熟女| 啦啦啦啦在线视频资源| 大香蕉久久成人网| 精品国产超薄肉色丝袜足j| 美女大奶头黄色视频| 久久久久网色| 纵有疾风起免费观看全集完整版| a 毛片基地| 亚洲欧美一区二区三区黑人| 欧美人与性动交α欧美软件| av国产精品久久久久影院| 日韩 欧美 亚洲 中文字幕| av片东京热男人的天堂| 极品少妇高潮喷水抽搐| 亚洲精品乱久久久久久| 国产一区有黄有色的免费视频| 最新在线观看一区二区三区 | 热99久久久久精品小说推荐| 国产人伦9x9x在线观看| a级片在线免费高清观看视频| 日韩av免费高清视频| 亚洲第一av免费看| 大片电影免费在线观看免费| avwww免费| 亚洲综合色网址| 国产日韩欧美在线精品| 在线av久久热| 国产日韩欧美在线精品| 一边亲一边摸免费视频| 精品视频人人做人人爽| 一级毛片电影观看| 1024香蕉在线观看| 久久热在线av| 精品人妻熟女毛片av久久网站| 黄片播放在线免费| 高清视频免费观看一区二区| 我的亚洲天堂| 国产在线免费精品| 精品少妇内射三级| 性高湖久久久久久久久免费观看| 国产1区2区3区精品| 亚洲男人天堂网一区| 久久国产精品人妻蜜桃| 深夜精品福利| 国产av国产精品国产| 看免费成人av毛片| 啦啦啦视频在线资源免费观看| 日本黄色日本黄色录像| 午夜福利视频精品| 成人亚洲欧美一区二区av| 一区二区三区乱码不卡18| 亚洲人成77777在线视频| 99九九在线精品视频| 午夜福利在线免费观看网站| 我要看黄色一级片免费的| 性色av乱码一区二区三区2| 女人爽到高潮嗷嗷叫在线视频| 国产熟女欧美一区二区| 成年人午夜在线观看视频| 亚洲黑人精品在线| 精品久久久久久久毛片微露脸 | 亚洲成人手机| 99精国产麻豆久久婷婷| 热99国产精品久久久久久7| 男女下面插进去视频免费观看| 曰老女人黄片| 亚洲av日韩在线播放| 一边摸一边抽搐一进一出视频| 亚洲av欧美aⅴ国产| 亚洲专区国产一区二区| 久久性视频一级片| 国产高清视频在线播放一区 | 天堂8中文在线网| 亚洲精品久久成人aⅴ小说| 嫁个100分男人电影在线观看 | a级毛片黄视频| 成在线人永久免费视频| av在线播放精品| 国产欧美日韩精品亚洲av| 国产精品人妻久久久影院| 99久久人妻综合| 人人妻人人澡人人看| 丝袜在线中文字幕| 精品国产一区二区三区久久久樱花| 黑人猛操日本美女一级片| 久久精品国产a三级三级三级| 汤姆久久久久久久影院中文字幕| 老司机深夜福利视频在线观看 | 老司机影院毛片| 亚洲欧美日韩高清在线视频 | 亚洲精品成人av观看孕妇| 在线观看免费日韩欧美大片| 晚上一个人看的免费电影| 国产国语露脸激情在线看| 新久久久久国产一级毛片| 可以免费在线观看a视频的电影网站| 日韩电影二区| 国产一区二区 视频在线| 欧美日本中文国产一区发布| 王馨瑶露胸无遮挡在线观看| 在线看a的网站| 一二三四在线观看免费中文在| 久久性视频一级片| www.自偷自拍.com| 桃花免费在线播放| 一区福利在线观看| 男女国产视频网站| 天天影视国产精品| 国产一区二区在线观看av| xxxhd国产人妻xxx| 99国产精品一区二区三区| 深夜精品福利| svipshipincom国产片| 国产亚洲av片在线观看秒播厂| 麻豆国产av国片精品| 99国产精品一区二区三区| 久久久国产精品麻豆| 久久热在线av| 午夜福利一区二区在线看| 精品久久蜜臀av无| 午夜免费成人在线视频| 99热国产这里只有精品6| 久久久精品区二区三区| 69精品国产乱码久久久| 十八禁高潮呻吟视频| 大片电影免费在线观看免费| 一本一本久久a久久精品综合妖精| av国产精品久久久久影院| 成在线人永久免费视频| 777久久人妻少妇嫩草av网站| 亚洲人成电影观看| 成人国产一区最新在线观看 | 在现免费观看毛片| 久久精品aⅴ一区二区三区四区| 国产一区亚洲一区在线观看| 啦啦啦啦在线视频资源| 新久久久久国产一级毛片| 制服诱惑二区| 一级黄色大片毛片| 亚洲av日韩在线播放| 9191精品国产免费久久| 十八禁网站网址无遮挡| 亚洲av电影在线观看一区二区三区| 久久狼人影院| 亚洲av男天堂| 亚洲 国产 在线| 只有这里有精品99| a级毛片黄视频| 成人免费观看视频高清| 国产日韩一区二区三区精品不卡| 精品一品国产午夜福利视频| 免费久久久久久久精品成人欧美视频| 亚洲成av片中文字幕在线观看| 午夜日韩欧美国产| 天天操日日干夜夜撸| 国产精品一二三区在线看| 午夜老司机福利片| 日韩欧美一区视频在线观看| 久久99热这里只频精品6学生| 丝袜美腿诱惑在线| 久热爱精品视频在线9| 美女主播在线视频| 巨乳人妻的诱惑在线观看| 精品第一国产精品| 成在线人永久免费视频| 亚洲五月色婷婷综合| 婷婷色综合大香蕉| 精品一区二区三卡| 脱女人内裤的视频| 亚洲七黄色美女视频| 久久精品久久久久久久性| 国产成人91sexporn| 国产av一区二区精品久久| 国产99久久九九免费精品| 久久人妻熟女aⅴ| 侵犯人妻中文字幕一二三四区| 18禁黄网站禁片午夜丰满| 亚洲国产看品久久| 午夜免费鲁丝| 国产免费福利视频在线观看| 欧美亚洲日本最大视频资源| 国产一区亚洲一区在线观看| 欧美人与善性xxx| av电影中文网址| 又大又爽又粗| av线在线观看网站| 激情五月婷婷亚洲| 亚洲人成77777在线视频| 一级a爱视频在线免费观看| bbb黄色大片| 成年动漫av网址| 日日夜夜操网爽| 国产成人精品久久二区二区91| 国产精品久久久久久精品古装| 一级毛片 在线播放| 欧美黑人精品巨大| 国产1区2区3区精品| 人成视频在线观看免费观看| 一区二区三区激情视频| 一本色道久久久久久精品综合| 熟女av电影| netflix在线观看网站| 精品福利永久在线观看| 天天躁夜夜躁狠狠躁躁| 夫妻午夜视频| 亚洲av电影在线进入| 侵犯人妻中文字幕一二三四区| 精品一区二区三区四区五区乱码 | 国产色视频综合| 一个人免费看片子| 我的亚洲天堂| 最近最新中文字幕大全免费视频 | 可以免费在线观看a视频的电影网站| 亚洲av美国av| 高清欧美精品videossex| 中文欧美无线码| 国产精品麻豆人妻色哟哟久久| 欧美日韩视频高清一区二区三区二| 男女之事视频高清在线观看 | 汤姆久久久久久久影院中文字幕| 男女午夜视频在线观看| 欧美久久黑人一区二区| 一级毛片黄色毛片免费观看视频| av有码第一页| 久久国产精品影院| 日韩制服骚丝袜av| 国产伦理片在线播放av一区| 亚洲精品国产av成人精品| 久久九九热精品免费| 国产日韩欧美在线精品| av国产精品久久久久影院| 交换朋友夫妻互换小说| 狠狠精品人妻久久久久久综合| 国产男女内射视频| 国产精品.久久久| 九色亚洲精品在线播放| 色婷婷av一区二区三区视频| 宅男免费午夜| 久久精品亚洲熟妇少妇任你| 婷婷色麻豆天堂久久| 日本91视频免费播放| 日本av手机在线免费观看| cao死你这个sao货| 老熟女久久久| 欧美大码av| 国产亚洲精品久久久久5区| 亚洲国产欧美日韩在线播放| 日本猛色少妇xxxxx猛交久久| 午夜福利免费观看在线| 日韩中文字幕欧美一区二区 | 欧美黑人欧美精品刺激| 在线 av 中文字幕| 免费在线观看黄色视频的| 热99久久久久精品小说推荐| 一本大道久久a久久精品| 69精品国产乱码久久久| 午夜福利一区二区在线看| 91精品伊人久久大香线蕉| 国产成人影院久久av| 国产在线观看jvid| 国产免费视频播放在线视频| 亚洲精品久久久久久婷婷小说| 国产精品久久久av美女十八| 久久 成人 亚洲| 十八禁人妻一区二区| 国产日韩欧美在线精品| 午夜福利视频精品| 亚洲五月婷婷丁香| 国产真人三级小视频在线观看| xxxhd国产人妻xxx| 男女边摸边吃奶| 波多野结衣av一区二区av| 高清不卡的av网站| 十八禁人妻一区二区| 精品国产一区二区三区四区第35| 99久久综合免费| 制服诱惑二区| 80岁老熟妇乱子伦牲交| 无限看片的www在线观看| 最黄视频免费看| kizo精华| 免费日韩欧美在线观看| 久久久精品国产亚洲av高清涩受| 人人妻人人爽人人添夜夜欢视频| 欧美日韩av久久| 一级毛片 在线播放| 国产精品九九99|