• <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?
    国产人妻一区二区三区在| 中文精品一卡2卡3卡4更新| 日韩成人伦理影院| 亚洲av男天堂| 91精品一卡2卡3卡4卡| av卡一久久| 亚洲国产欧美在线一区| 亚洲人成网站在线播放欧美日韩| 99热精品在线国产| 26uuu在线亚洲综合色| 成人永久免费在线观看视频| 亚洲七黄色美女视频| www.色视频.com| 99久久九九国产精品国产免费| 欧美高清性xxxxhd video| 91久久精品国产一区二区成人| 国产女主播在线喷水免费视频网站 | 熟妇人妻久久中文字幕3abv| 成人鲁丝片一二三区免费| 午夜免费激情av| 天堂av国产一区二区熟女人妻| 1024手机看黄色片| 色播亚洲综合网| 亚洲最大成人av| 亚洲一级一片aⅴ在线观看| 97人妻精品一区二区三区麻豆| 日韩一本色道免费dvd| 免费无遮挡裸体视频| 国产精品国产高清国产av| 美女 人体艺术 gogo| 国产亚洲av嫩草精品影院| 国产精品乱码一区二三区的特点| 成人性生交大片免费视频hd| 亚洲欧洲日产国产| 少妇被粗大猛烈的视频| 国产精品1区2区在线观看.| 啦啦啦韩国在线观看视频| 欧美性感艳星| 欧美又色又爽又黄视频| 午夜视频国产福利| 免费观看的影片在线观看| 亚洲精品成人久久久久久| 婷婷亚洲欧美| 国产精品蜜桃在线观看 | 久久久午夜欧美精品| 日本三级黄在线观看| 亚洲激情五月婷婷啪啪| 免费观看精品视频网站| 一级av片app| 日本爱情动作片www.在线观看| 亚洲人成网站在线播放欧美日韩| 桃色一区二区三区在线观看| av国产免费在线观看| 亚洲人成网站在线观看播放| 国产亚洲av嫩草精品影院| 我要看日韩黄色一级片| 热99在线观看视频| 久久久久久九九精品二区国产| 尾随美女入室| 极品教师在线视频| 日韩欧美精品免费久久| 亚洲国产欧洲综合997久久,| 国产av在哪里看| 国内精品一区二区在线观看| 亚洲在线自拍视频| 69av精品久久久久久| 日韩一本色道免费dvd| 日韩在线高清观看一区二区三区| 国产精品野战在线观看| 麻豆av噜噜一区二区三区| 好男人在线观看高清免费视频| 最近视频中文字幕2019在线8| 欧美不卡视频在线免费观看| 中国美白少妇内射xxxbb| 国产人妻一区二区三区在| 有码 亚洲区| 亚洲真实伦在线观看| 在线观看免费视频日本深夜| 国产探花在线观看一区二区| 校园春色视频在线观看| 久久久国产成人精品二区| 岛国在线免费视频观看| 色噜噜av男人的天堂激情| ponron亚洲| 成人永久免费在线观看视频| 亚洲av电影不卡..在线观看| 人妻少妇偷人精品九色| 一级黄片播放器| 深夜a级毛片| 97超碰精品成人国产| 国产麻豆成人av免费视频| 色综合站精品国产| 91aial.com中文字幕在线观看| 99热这里只有精品一区| 免费观看人在逋| 18禁黄网站禁片免费观看直播| 三级男女做爰猛烈吃奶摸视频| 国产麻豆成人av免费视频| 国产美女午夜福利| 国产精品福利在线免费观看| 自拍偷自拍亚洲精品老妇| 亚洲电影在线观看av| 日韩国内少妇激情av| 99精品在免费线老司机午夜| 亚洲一区高清亚洲精品| 欧美性猛交黑人性爽| 国产精品一及| 亚洲精品日韩在线中文字幕 | 国产亚洲av嫩草精品影院| 欧美日本亚洲视频在线播放| 少妇的逼水好多| 国产91av在线免费观看| 人妻少妇偷人精品九色| 亚洲av中文av极速乱| 亚洲av中文字字幕乱码综合| 狠狠狠狠99中文字幕| 欧美最新免费一区二区三区| 欧美日本视频| 99久国产av精品| а√天堂www在线а√下载| 亚洲国产欧洲综合997久久,| 免费观看在线日韩| 亚洲性久久影院| 欧美另类亚洲清纯唯美| 99久久精品国产国产毛片| 成人漫画全彩无遮挡| 搡女人真爽免费视频火全软件| 日产精品乱码卡一卡2卡三| 日本黄色视频三级网站网址| 成熟少妇高潮喷水视频| 一级毛片我不卡| 噜噜噜噜噜久久久久久91| 欧美一区二区精品小视频在线| 亚洲在久久综合| 99热精品在线国产| 亚洲国产精品久久男人天堂| 亚洲成a人片在线一区二区| 午夜老司机福利剧场| 一个人免费在线观看电影| 亚洲欧洲日产国产| 国产成人91sexporn| 国产精品久久久久久亚洲av鲁大| 寂寞人妻少妇视频99o| 欧美最新免费一区二区三区| 日日摸夜夜添夜夜添av毛片| 久久草成人影院| 搡老妇女老女人老熟妇| 2021天堂中文幕一二区在线观| 欧美激情久久久久久爽电影| 一级毛片aaaaaa免费看小| 免费黄网站久久成人精品| 好男人在线观看高清免费视频| 狠狠狠狠99中文字幕| 26uuu在线亚洲综合色| 日本免费a在线| 国产午夜精品论理片| 午夜精品一区二区三区免费看| 大又大粗又爽又黄少妇毛片口| 美女 人体艺术 gogo| 免费观看的影片在线观看| 日韩av在线大香蕉| 国产真实伦视频高清在线观看| 亚洲欧美精品自产自拍| 亚洲人成网站在线观看播放| 久久久久久久亚洲中文字幕| 丝袜美腿在线中文| 国产一区二区三区av在线 | 一级黄色大片毛片| 99久久人妻综合| 如何舔出高潮| 99在线视频只有这里精品首页| 丰满的人妻完整版| 女的被弄到高潮叫床怎么办| 综合色丁香网| 国产私拍福利视频在线观看| 国产一区二区在线观看日韩| 国产亚洲精品av在线| 婷婷精品国产亚洲av| 久久久久久久久久成人| 亚洲人成网站高清观看| 国产精品久久电影中文字幕| 国模一区二区三区四区视频| 最近视频中文字幕2019在线8| 国产伦精品一区二区三区视频9| 欧美日本亚洲视频在线播放| 国产乱人视频| 国产成人精品久久久久久| 全区人妻精品视频| 欧美区成人在线视频| 久久亚洲国产成人精品v| 亚洲在线自拍视频| 亚洲国产精品国产精品| 99热6这里只有精品| 久久国内精品自在自线图片| 嫩草影院精品99| 床上黄色一级片| 老司机福利观看| 午夜a级毛片| 国产成人freesex在线| 尾随美女入室| 午夜视频国产福利| 真实男女啪啪啪动态图| 国产麻豆成人av免费视频| 最近2019中文字幕mv第一页| 精品欧美国产一区二区三| 成人无遮挡网站| 国产一区二区激情短视频| 亚洲精品粉嫩美女一区| 亚洲18禁久久av| 男女下面进入的视频免费午夜| 国产精品免费一区二区三区在线| 男女下面进入的视频免费午夜| 国产精品福利在线免费观看| 国产av在哪里看| 国产女主播在线喷水免费视频网站 | 亚洲av中文字字幕乱码综合| 亚洲人成网站高清观看| 亚洲国产精品国产精品| 晚上一个人看的免费电影| 午夜爱爱视频在线播放| 99在线视频只有这里精品首页| 亚洲精品影视一区二区三区av| 在线观看美女被高潮喷水网站| 免费看美女性在线毛片视频| 中国国产av一级| 亚洲精品粉嫩美女一区| 欧美精品国产亚洲| 长腿黑丝高跟| 国产国拍精品亚洲av在线观看| 亚洲国产欧洲综合997久久,| 2021天堂中文幕一二区在线观| 久久99精品国语久久久| 天天躁夜夜躁狠狠久久av| 亚洲激情五月婷婷啪啪| 国产老妇女一区| 你懂的网址亚洲精品在线观看 | 亚洲国产高清在线一区二区三| 99国产极品粉嫩在线观看| 蜜臀久久99精品久久宅男| 岛国毛片在线播放| 欧美日本视频| 波多野结衣巨乳人妻| 18+在线观看网站| 中国美白少妇内射xxxbb| 日本一本二区三区精品| 国产色爽女视频免费观看| 免费黄网站久久成人精品| 高清毛片免费看| 久久久久久久久久久丰满| 99热这里只有精品一区| 九九爱精品视频在线观看| 久久精品国产亚洲av天美| 内地一区二区视频在线| 成年av动漫网址| 国产视频内射| 91精品国产九色| 成人欧美大片| 99热这里只有是精品50| 99久久精品一区二区三区| 18+在线观看网站| 色5月婷婷丁香| 天堂网av新在线| 嘟嘟电影网在线观看| 嫩草影院入口| 尾随美女入室| 女的被弄到高潮叫床怎么办| 男人和女人高潮做爰伦理| 熟女人妻精品中文字幕| 国产人妻一区二区三区在| 一级黄片播放器| 蜜桃久久精品国产亚洲av| 国产高清三级在线| 免费一级毛片在线播放高清视频| 一级毛片aaaaaa免费看小| 国内久久婷婷六月综合欲色啪| 在线a可以看的网站| 免费av毛片视频| 国产视频首页在线观看| 日韩av在线大香蕉| 国产精品伦人一区二区| 中文资源天堂在线| 九九在线视频观看精品| 久久这里只有精品中国| 一级毛片久久久久久久久女| 国产淫片久久久久久久久| 十八禁国产超污无遮挡网站| 国产白丝娇喘喷水9色精品| 亚洲精品乱码久久久久久按摩| 国产一区亚洲一区在线观看| 成人特级av手机在线观看| 亚洲va在线va天堂va国产| 欧美xxxx性猛交bbbb| 老师上课跳d突然被开到最大视频| 亚洲,欧美,日韩| 国产午夜福利久久久久久| 国产爱豆传媒在线观看| 亚洲欧美成人综合另类久久久 | 美女脱内裤让男人舔精品视频 | 欧美一区二区精品小视频在线| avwww免费| 男女边吃奶边做爰视频| 一本久久中文字幕| 亚洲不卡免费看| 中文在线观看免费www的网站| 日韩一区二区视频免费看| 欧美日韩综合久久久久久| 自拍偷自拍亚洲精品老妇| 国产精品国产三级国产av玫瑰| 最近中文字幕高清免费大全6| 日韩一区二区三区影片| 黄色欧美视频在线观看| 国内精品一区二区在线观看| 日韩av不卡免费在线播放| 黄片wwwwww| 亚洲欧洲日产国产| 99久久精品国产国产毛片| 国产精品永久免费网站| 伦理电影大哥的女人| 欧美bdsm另类| 深爱激情五月婷婷| 麻豆精品久久久久久蜜桃| 国产在线男女| 亚洲中文字幕日韩| 亚洲自拍偷在线| 哪个播放器可以免费观看大片| 嫩草影院精品99| 女的被弄到高潮叫床怎么办| 国产亚洲精品久久久久久毛片| 精品久久久久久久久av| 国产淫片久久久久久久久| 国产免费男女视频| 草草在线视频免费看| 老司机影院成人| 欧美最黄视频在线播放免费| 亚洲一区二区三区色噜噜| 97人妻精品一区二区三区麻豆| 观看美女的网站| 亚洲av不卡在线观看| av黄色大香蕉| 女同久久另类99精品国产91| 国产高清视频在线观看网站| 热99re8久久精品国产| 岛国毛片在线播放| 精品国产三级普通话版| 日韩高清综合在线| 欧美潮喷喷水| eeuss影院久久| 国产精品久久视频播放| 99久久精品一区二区三区| av.在线天堂| 色吧在线观看| 一进一出抽搐动态| 久久久久久久久久成人| 搡女人真爽免费视频火全软件| 午夜激情欧美在线| 九草在线视频观看| 久久这里只有精品中国| 男人和女人高潮做爰伦理| 国产av麻豆久久久久久久| 日韩人妻高清精品专区| 亚洲精品国产成人久久av| 成熟少妇高潮喷水视频| 免费观看在线日韩| 热99在线观看视频| 成人无遮挡网站| 国产在线男女| 26uuu在线亚洲综合色| av女优亚洲男人天堂| 特级一级黄色大片| 精品人妻偷拍中文字幕| 日本免费a在线| 亚洲国产精品国产精品| 亚洲真实伦在线观看| 嫩草影院入口| 国产成人午夜福利电影在线观看| 欧美日本亚洲视频在线播放| 亚洲欧美清纯卡通| 国产亚洲av片在线观看秒播厂 | 亚洲,欧美,日韩| 长腿黑丝高跟| 麻豆av噜噜一区二区三区| 变态另类成人亚洲欧美熟女| 国产精品国产三级国产av玫瑰| 日韩 亚洲 欧美在线| 国产白丝娇喘喷水9色精品| 久久精品综合一区二区三区| 51国产日韩欧美| 看片在线看免费视频| 色哟哟哟哟哟哟| 九色成人免费人妻av| 一卡2卡三卡四卡精品乱码亚洲| 免费观看在线日韩| 国产精品人妻久久久影院| 国产美女午夜福利| 免费看光身美女| 免费观看a级毛片全部| 99riav亚洲国产免费| 国产久久久一区二区三区| 精品不卡国产一区二区三区| 国产精品三级大全| 免费看av在线观看网站| 男的添女的下面高潮视频| 欧美性感艳星| 国产在线精品亚洲第一网站| 亚洲成人久久性| 青青草视频在线视频观看| 亚洲第一电影网av| 九草在线视频观看| 亚洲自偷自拍三级| 非洲黑人性xxxx精品又粗又长| 岛国毛片在线播放| 亚洲美女视频黄频| 免费观看的影片在线观看| 国产亚洲精品av在线| 又粗又硬又长又爽又黄的视频 | 91精品一卡2卡3卡4卡| 最新中文字幕久久久久| 51国产日韩欧美| 在线a可以看的网站| 少妇裸体淫交视频免费看高清| 一卡2卡三卡四卡精品乱码亚洲| 成人特级黄色片久久久久久久| 嫩草影院新地址| 亚洲人成网站高清观看| 亚洲乱码一区二区免费版| 色播亚洲综合网| 精品久久久久久久人妻蜜臀av| 国产伦精品一区二区三区视频9| 乱系列少妇在线播放| 大香蕉久久网| 狂野欧美激情性xxxx在线观看| 国产av一区在线观看免费| 中文字幕av成人在线电影| 好男人视频免费观看在线| 日韩在线高清观看一区二区三区| 丰满人妻一区二区三区视频av| 欧美极品一区二区三区四区| 日本黄大片高清| 偷拍熟女少妇极品色| 男女那种视频在线观看| 草草在线视频免费看| 亚洲欧美精品综合久久99| 亚洲激情五月婷婷啪啪| 日韩亚洲欧美综合| 岛国毛片在线播放| 色哟哟·www| 亚洲人成网站在线播| 最好的美女福利视频网| 青春草亚洲视频在线观看| 亚洲天堂国产精品一区在线| 色噜噜av男人的天堂激情| 欧美丝袜亚洲另类| 久久精品91蜜桃| 男女视频在线观看网站免费| 国产精品一区二区在线观看99 | 成人无遮挡网站| 中文资源天堂在线| 欧美性猛交黑人性爽| 联通29元200g的流量卡| 爱豆传媒免费全集在线观看| av黄色大香蕉| av免费在线看不卡| 国产在视频线在精品| 草草在线视频免费看| 精品99又大又爽又粗少妇毛片| 91aial.com中文字幕在线观看| 美女cb高潮喷水在线观看| 看免费成人av毛片| 欧美性感艳星| 成人永久免费在线观看视频| 一级二级三级毛片免费看| 小蜜桃在线观看免费完整版高清| 少妇的逼好多水| 天堂av国产一区二区熟女人妻| 成人特级av手机在线观看| 天堂av国产一区二区熟女人妻| 床上黄色一级片| 日本一本二区三区精品| 国产精品免费一区二区三区在线| 精品日产1卡2卡| 国产精品无大码| 欧美xxxx性猛交bbbb| 国产精品综合久久久久久久免费| 在线免费十八禁| 女同久久另类99精品国产91| 男女视频在线观看网站免费| 亚洲经典国产精华液单| 日本av手机在线免费观看| 欧美变态另类bdsm刘玥| a级毛片a级免费在线| 97超碰精品成人国产| 亚洲无线在线观看| 人人妻人人看人人澡| 丰满乱子伦码专区| 国产在线男女| 国产黄a三级三级三级人| 久久这里有精品视频免费| 久久精品影院6| 成人美女网站在线观看视频| 天堂√8在线中文| 欧美潮喷喷水| 日韩强制内射视频| 18+在线观看网站| 欧美性猛交╳xxx乱大交人| 国产成人午夜福利电影在线观看| a级毛片免费高清观看在线播放| 成人综合一区亚洲| 丰满人妻一区二区三区视频av| 99热这里只有精品一区| 日本色播在线视频| 老司机福利观看| 久久精品国产亚洲av香蕉五月| av黄色大香蕉| 在线免费观看的www视频| 男人舔女人下体高潮全视频| 欧美丝袜亚洲另类| 日本与韩国留学比较| 少妇熟女欧美另类| 最好的美女福利视频网| 男人狂女人下面高潮的视频| 国产一区二区三区av在线 | 国产亚洲5aaaaa淫片| 又爽又黄无遮挡网站| 91aial.com中文字幕在线观看| 日韩一区二区三区影片| 亚洲欧美精品专区久久| 国产精品久久久久久久久免| 黄片wwwwww| 欧美高清性xxxxhd video| 亚洲av男天堂| 老师上课跳d突然被开到最大视频| eeuss影院久久| 尤物成人国产欧美一区二区三区| 亚州av有码| 国内精品久久久久精免费| 精品久久国产蜜桃| 在线国产一区二区在线| 我要看日韩黄色一级片| 久久这里有精品视频免费| 丰满乱子伦码专区| 国产免费男女视频| av在线播放精品| 欧美日韩综合久久久久久| 男人和女人高潮做爰伦理| 中文字幕av成人在线电影| 久久久久性生活片| 亚洲乱码一区二区免费版| 中出人妻视频一区二区| 国产高清激情床上av| 国产精品麻豆人妻色哟哟久久 | 九九在线视频观看精品| 亚洲欧美中文字幕日韩二区| 欧美又色又爽又黄视频| 女的被弄到高潮叫床怎么办| 亚洲综合色惰| 欧美最黄视频在线播放免费| 欧美一区二区亚洲| 国产精品.久久久| 69人妻影院| h日本视频在线播放| 久久九九热精品免费| 波多野结衣高清无吗| 婷婷色av中文字幕| 久久久成人免费电影| 国产日韩欧美在线精品| 国国产精品蜜臀av免费| 麻豆一二三区av精品| 成人特级av手机在线观看| 亚洲性久久影院| 色播亚洲综合网| 亚洲第一区二区三区不卡| 最近2019中文字幕mv第一页| 国产三级在线视频| 人妻久久中文字幕网| 高清日韩中文字幕在线| 亚洲人成网站高清观看| 狂野欧美激情性xxxx在线观看| 亚洲精华国产精华液的使用体验 | 欧美人与善性xxx| 日日摸夜夜添夜夜爱| 亚洲中文字幕日韩| 一进一出抽搐动态| av国产免费在线观看| 国产又黄又爽又无遮挡在线| 国国产精品蜜臀av免费| 免费看光身美女| 午夜免费激情av| 亚洲精品自拍成人| 亚洲av不卡在线观看| 美女国产视频在线观看| 精品国内亚洲2022精品成人| 深爱激情五月婷婷| 亚洲经典国产精华液单| 99久国产av精品国产电影| 久久99精品国语久久久| 亚洲国产精品久久男人天堂| 亚洲国产欧美在线一区| 国产午夜精品论理片| 天天躁日日操中文字幕| 国产午夜福利久久久久久| 色视频www国产| 美女国产视频在线观看| 波多野结衣巨乳人妻| 免费人成视频x8x8入口观看| 麻豆久久精品国产亚洲av| 婷婷色av中文字幕| 亚洲一级一片aⅴ在线观看| 国产午夜精品一二区理论片| 欧美激情在线99| 在线a可以看的网站| 热99re8久久精品国产| 在线观看一区二区三区| 又黄又爽又刺激的免费视频.| 床上黄色一级片| 欧美+日韩+精品|