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

    面向CPU+MIC混合異構(gòu)平臺(tái)的地震波疊前時(shí)間偏移算法并行與優(yōu)化策略*

    2015-03-31 02:53:18王勇獻(xiàn)
    關(guān)鍵詞:任務(wù)調(diào)度線程異構(gòu)

    熊 敏,王勇獻(xiàn)

    (國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院,湖南 長沙 410073)

    面向CPU+MIC混合異構(gòu)平臺(tái)的地震波疊前時(shí)間偏移算法并行與優(yōu)化策略*

    熊 敏,王勇獻(xiàn)

    (國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院,湖南 長沙 410073)

    地震波的疊前時(shí)間偏移算法是構(gòu)造復(fù)雜巖層成像最有效的方法之一。地震勘探進(jìn)入海量數(shù)據(jù)時(shí)代,且疊前偏移算法是數(shù)據(jù)處理中最費(fèi)時(shí)的環(huán)節(jié),對(duì)疊前偏移算法做并行計(jì)算優(yōu)化有著重要的研究意義。近年來,高性能并行計(jì)算開始進(jìn)入異構(gòu)、眾核時(shí)代,以Intel新一代至強(qiáng)融核MIC(Xeon Phi)為例,新型眾核處理器具有成本低、性能高等特點(diǎn)。從最經(jīng)典的Kirchhoff疊前時(shí)間偏移 (PKTM) 算法出發(fā),基于CPU+MIC異構(gòu)平臺(tái),采用offload編程模式實(shí)現(xiàn)對(duì)PKTM算法的并行移植與性能優(yōu)化,對(duì)于6 000萬規(guī)模(8 000×8 000)的應(yīng)用問題,總的并行模擬時(shí)間從357.52 s減少到1.66 s,性能提升了214.37倍。

    協(xié)同并行;Intel至強(qiáng)融核;異構(gòu)并行;Kirchhoff疊前時(shí)間偏移;性能優(yōu)化

    1 引言

    對(duì)地底巖層構(gòu)造進(jìn)行成像是石油、天然氣勘探開發(fā),以及地震勘探等領(lǐng)域的重要環(huán)節(jié)。地震波的疊前時(shí)間偏移算法是構(gòu)造復(fù)雜巖層成像最有效的方法之一。Kirchhoff疊前時(shí)間偏移PKTM(Prestack Kirchhoff Time Migration)算法具有成像效率高、對(duì)速度模型要求低的優(yōu)點(diǎn),能適應(yīng)縱橫向速度變化較大的情況,同時(shí)還適用于大傾角的偏移成像,因此在構(gòu)造復(fù)雜的地區(qū),其優(yōu)勢(shì)更為突出。該算法自20世紀(jì)90年代起,逐漸成為地震勘探數(shù)據(jù)處理的常用成像手段[1]。圖1顯示的是PKTM算法的反演過程,圖1a是地下模型空間,圖1b數(shù)據(jù)空間,圖1c是反演獲得的模型空間,對(duì)于如漢字這樣復(fù)雜的形狀,PKTM算法仍然具有很高的還原度。隨著地震勘探進(jìn)入海量數(shù)據(jù)時(shí)代,對(duì)計(jì)算資源的需求日益增加,疊前偏移算法是數(shù)據(jù)處理中最費(fèi)時(shí)的環(huán)節(jié),對(duì)疊前偏移算法進(jìn)行并行計(jì)算優(yōu)化有著重要的研究意義。

    Figure 1 PKTM migration process

    近年來,高性能計(jì)算開始進(jìn)入異構(gòu)、眾核時(shí)代,異構(gòu)眾核是大規(guī)模并行計(jì)算機(jī)的發(fā)展趨勢(shì),新型眾核處理器具有成本低、性能高等特點(diǎn)。以Intel新一代至強(qiáng)融核MIC(Xeon Phi)為例,單個(gè)MIC設(shè)備擁有50個(gè)以上的處理器核,并采用寬向量(512位)設(shè)計(jì),能夠提供1 TFlops雙精度浮點(diǎn)運(yùn)算的性能,同時(shí)MIC還具有通用編程環(huán)境(Fortran、C 和 C++)、低功耗性能比、支持異構(gòu)應(yīng)用等優(yōu)勢(shì)[2]。Intel針對(duì)MIC推出一系列軟件工具鏈,以支持基于MIC的軟件開發(fā),當(dāng)前CPU+MIC異構(gòu)平臺(tái)主要有四種編程模式:CPU原生模式、CPU為主MIC為輔模式(又稱offload模式)、CPU和MIC對(duì)等模式、MIC為主CPU為輔模式。最新TOP500[3]蟬聯(lián)第一的“天河二號(hào)”超級(jí)計(jì)算機(jī)即以MIC作為加速部件。針對(duì)不同領(lǐng)域應(yīng)用問題的模型和計(jì)算特點(diǎn),結(jié)合MIC的體系結(jié)構(gòu)特點(diǎn),研究在該處理器平臺(tái)上的性能優(yōu)化已經(jīng)成為當(dāng)前的研究熱點(diǎn)之一。

    受益于硬件平臺(tái)的不斷更新與發(fā)展,地震波疊前時(shí)間偏移計(jì)算方法的性能在過去一段時(shí)間也持續(xù)獲得較大的提升。Bhardwaj D等人[4]利用MPI實(shí)現(xiàn)疊前偏移算法優(yōu)化,使偏移計(jì)算效率提高了近30%。王華忠等人[5]在集群系統(tǒng)中利用OpenMP多線程并行方法,優(yōu)化了三維Kirchhoff積分法偏移實(shí)現(xiàn)方案。張清等人[6]利用CUDA編程模型在GPU平臺(tái)上設(shè)計(jì)實(shí)現(xiàn)了靜態(tài)8點(diǎn)并行插值算法,性能是CPU動(dòng)態(tài)插值算法內(nèi)核的22.76倍。隨著MIC等新型眾核系統(tǒng)的出現(xiàn),如何在CPU+MIC的異構(gòu)平臺(tái)上,充分結(jié)合硬件體系結(jié)構(gòu)特點(diǎn)與疊前時(shí)間偏移算法本身的特點(diǎn),來做并行性能優(yōu)化,仍是一個(gè)值得探索的問題。本文從最經(jīng)典的Kirchhoff疊前時(shí)間偏移 (PKTM) 算法出發(fā),基于CPU+MIC異構(gòu)平臺(tái),采用offload編程模式實(shí)現(xiàn)對(duì)PKTM算法的并行移植與性能優(yōu)化。

    2 地震波疊前時(shí)間偏移算法

    在經(jīng)典的Kirchhoff疊前時(shí)間偏移(PKTM)算法中,定義了兩個(gè)空間,一個(gè)是模型空間,簡記為x-s空間,是對(duì)地底巖層構(gòu)造的刻畫,其離散下標(biāo)記為(ix,is);另一個(gè)為數(shù)據(jù)空間,簡記為y-t空間,是對(duì)儀器成像數(shù)據(jù)的刻畫,其離散下標(biāo)記為(iy,it)。PKTM算法的實(shí)質(zhì)是根據(jù)成像數(shù)據(jù)各像素的取值來反演、“復(fù)原”原始地底巖層構(gòu)造的過程,具體來說,對(duì)于某個(gè)模型空間點(diǎn)(x,s)而言,按照成像原理與規(guī)律,若它會(huì)在數(shù)據(jù)空間內(nèi)的點(diǎn)(y,t)處成像(該點(diǎn)未必唯一),則需要滿足式(1):

    (x-y)2=v2(t2-s2)

    (1)

    其中v是與波傳播速度相關(guān)的一個(gè)常數(shù)。PKTM算法就是根據(jù)這一原理進(jìn)行實(shí)現(xiàn)的,圖2為經(jīng)典PKTM算法的核心實(shí)現(xiàn)流程[7],其優(yōu)點(diǎn)是在復(fù)雜邊界條件下仍然能保持計(jì)算穩(wěn)定[8]。

    Figure 2 Classical PKTM algorithm

    圖2 經(jīng)典Kirchhoff疊前時(shí)間偏移(PKTM)算法流程

    算法的主體部分是用一個(gè)三重循環(huán)操作data和modl兩個(gè)數(shù)組,其時(shí)間復(fù)雜度為O(nx2×nt),空間復(fù)雜度為O(nx×nt)。

    3 移植和優(yōu)化方法

    根據(jù)PKTM的實(shí)現(xiàn)過程與計(jì)算特點(diǎn),本文將從四個(gè)層次對(duì)PKTM算法進(jìn)行移植和優(yōu)化:算法層次的優(yōu)化、串行程序性能優(yōu)化、單一平臺(tái)上的多線程并行以及CPU+MIC異構(gòu)平臺(tái)上的混合并行。

    3.1 算法層次的優(yōu)化

    本文首先分析原始算法的時(shí)間復(fù)雜性,并嘗試降低一個(gè)量階時(shí)間開銷的快速算法,基于新的快速算法探索進(jìn)一步縮小迭代空間、提升加速效果的技術(shù)。

    3.1.1 快速PKTM算法

    由圖2中的經(jīng)典PKTM算法流程可知,該算法的核心是計(jì)算數(shù)組下標(biāo),其中當(dāng)給定模型空間下標(biāo)(ix,is)以及數(shù)據(jù)空間的第一維下標(biāo)iy時(shí),計(jì)算數(shù)據(jù)空間的下標(biāo)it是最費(fèi)時(shí)的部分,要用到加減乘除及乘方、開方、取整等運(yùn)算,即:

    t2=(x-y)2/v2+s2,it=[t/dt]

    (2)

    其中[ ]表示取整運(yùn)算符。注意到計(jì)算t時(shí)等號(hào)右邊第一項(xiàng)僅依賴于x與y的差值,因此若作變量替換ib=iy-ix,則可直接針對(duì)ib進(jìn)行遍歷,避免對(duì)(ix,iy)的組合進(jìn)行遍歷,從而達(dá)到降低遍歷空間開銷的目的。受此啟發(fā),Claerbout J F和Black J L在經(jīng)典算法基礎(chǔ)上進(jìn)行改進(jìn),提出快速PKTM算法實(shí)現(xiàn),流程如圖3所示[5]??焖偎惴ㄊ购诵挠?jì)算部分集中在二重循環(huán)的內(nèi)部,時(shí)間復(fù)雜度從經(jīng)典算法的(nx2×nt)降低到了O(nx×nt)。

    Figure 3 Fast PKTM algorithm

    圖3 快速Kirchhoff疊前時(shí)間偏移(PKTM)算法

    3.1.2 提前確定迭代次數(shù)

    在圖3的快速PKTM算法中,第6行有一個(gè)分支判斷,以確定是否產(chǎn)生了有效的it下標(biāo)值,且僅當(dāng)it有效時(shí)才執(zhí)行第7~9行的數(shù)據(jù)更新過程。由于第6行it有效性判定準(zhǔn)則it

    b2/v2+s2

    (3)

    注意到不等式左邊為平方和的形式,它是變量b和s的遞增函數(shù),因此在第2~11行的循環(huán)迭代中,一旦某個(gè)ib值(不妨記為ibMax)導(dǎo)致第6行的it值越界無效,則后續(xù)更大ib值的迭代也同樣產(chǎn)生無效的it取值,因此可直接跳過這些后續(xù)的ib迭代,從而避免后續(xù)迭代中冗余的it計(jì)算。事實(shí)上,也可預(yù)先計(jì)算能產(chǎn)生有效it值的ib迭代范圍[0,ibMax),達(dá)到同樣的目的。提前判斷出it的有效性也就是提前確定了迭代的次數(shù),這種方法的好處是避免了無效it的計(jì)算,減少核心計(jì)算部分的計(jì)算次數(shù)。

    為了有效量化這種技術(shù)帶來的收益,先將公式(3)寫成如下等價(jià)形式:

    (4)

    這表明在b-s平面(或者等價(jià)的整數(shù)坐標(biāo)ib-is平面)上,能產(chǎn)生有效it值的范圍是一個(gè)橢圓在第一象限和第二象限所包圍區(qū)域的內(nèi)部(圖4中I所示)。圖4中橫軸表示ib的取值,縱軸表示is的取值,橢圓內(nèi)部為滿足公式(4)的范圍,以nx和-nx為頂點(diǎn)的大矩形框內(nèi)部表示圖3第1~2行的全部迭代空間范圍,本方法將ib的取值縮小到橢圓的頂點(diǎn)ibMax和-ibMax,兩個(gè)矩形框之間的部分(圖4中II所示)即為本方法所節(jié)約的迭代范圍。以nx=8 000,nt=8 000,dt=0.004,dx=25,v=1 000為例,經(jīng)過簡單計(jì)算可知迭代空間大小從1.28×108減少為2.048×107,避免了約84%的無效迭代。

    Figure 4 Ellipse relationship between variables ib and is

    3.1.3 利用對(duì)稱性減少迭代次數(shù)

    觀察圖4,發(fā)現(xiàn)產(chǎn)生有效it的區(qū)域具有對(duì)稱性,即圖4中橢圓在第一象限和第二象限所包圍區(qū)域左右對(duì)稱,同時(shí)通過3.1.2節(jié)的方法優(yōu)化后所確定的迭代范圍也具有對(duì)稱性,即與橢圓相切的矩形區(qū)域同樣左右對(duì)稱??紤]到公式(1)中計(jì)算t的過程用到的是b-s平面中點(diǎn)的坐標(biāo)的平方值,而在對(duì)稱區(qū)域中,對(duì)稱點(diǎn)的坐標(biāo)的平方值相同,因此可以利用此特性減少迭代次數(shù)以及核心計(jì)算的次數(shù)。圖5為本方法的優(yōu)化示意圖,優(yōu)化代碼將ib=0的情況進(jìn)行特殊處理,剩下的兩個(gè)部分完全對(duì)稱,ib的迭代范圍縮小到(1,nx-1),核心計(jì)算的次數(shù)也隨之減半。

    優(yōu)化前 doib=-(nx-1),(nx-1) …if(it

    優(yōu)化后 doib=0,0 …(單獨(dú)處理ib=0情形)enddodoib=1,nx-1 …(核心計(jì)算:計(jì)算it的值) if(it

    Figure 5 Optimization method of symmetry to reduce loop cycles

    圖5 利用對(duì)稱性減少迭代次數(shù)示意圖

    3.2 串行程序的性能優(yōu)化

    在算法層次進(jìn)行優(yōu)化之后,本文對(duì)于串行程序進(jìn)行了一系列優(yōu)化,包括優(yōu)化計(jì)算和優(yōu)化訪存兩個(gè)方面。

    3.2.1 優(yōu)化計(jì)算

    (1)常量計(jì)算提前。

    圖3所示的快速Kirchhoff疊前時(shí)間偏移算法的流程中,第3~5行集中了平方、開方、除法和乘法等耗時(shí)的計(jì)算過程,是算法的核心計(jì)算部分。其中dx、dt、v、ds為常量,僅與常量相關(guān)與變量無關(guān)的計(jì)算只需要計(jì)算一次,就可以在每次迭代中使用,因此將這樣的常量計(jì)算提前到循環(huán)外部,可以有效減少計(jì)算的次數(shù)。對(duì)于公式(2)中對(duì)it的求解可以改寫成如下形式(ix-iy):

    (5)

    改進(jìn)前,除法運(yùn)算和平方運(yùn)算的運(yùn)算次數(shù)約為4×nx×nt,而將常量計(jì)算提前后,除法運(yùn)算的運(yùn)算次數(shù)為1,平方運(yùn)算的運(yùn)算次數(shù)為2×nx×nt+2×nt+1。

    (2)避免單雙精度混合運(yùn)算。

    兩種不同精度的數(shù)運(yùn)算時(shí),根據(jù)包容性,精度低的數(shù)需要先進(jìn)行精度轉(zhuǎn)換才能保證計(jì)算結(jié)果的正確性。如單雙精度浮點(diǎn)數(shù)混合運(yùn)算時(shí),單精度浮點(diǎn)數(shù)將先轉(zhuǎn)換成雙精度數(shù),然后再進(jìn)行雙精度浮點(diǎn)計(jì)算。而精度越高,運(yùn)算的開銷越大,因此如果僅使用單精度就能滿足的運(yùn)算,應(yīng)當(dāng)避免與雙精度浮點(diǎn)數(shù)混合運(yùn)算,從而減少高精度運(yùn)算的額外開銷。

    快速Kirchhoff疊前時(shí)間偏移算法中的所有計(jì)算過程,利用單精度浮點(diǎn)計(jì)算就足以保證精度。在具體代碼中,常常會(huì)用到一些浮點(diǎn)常量,如果沒有顯式標(biāo)識(shí)為單精度浮點(diǎn)數(shù),這些浮點(diǎn)常量將先被自動(dòng)處理為雙精度浮點(diǎn)數(shù),然后再與單精度的變量進(jìn)行混合運(yùn)算。為了避免單雙精度混合運(yùn)算,應(yīng)當(dāng)在使用浮點(diǎn)常量時(shí)顯式地將其標(biāo)識(shí)為單精度浮點(diǎn)數(shù)。

    (3)SIMD向量化。

    現(xiàn)代CPU處理器指令集普遍支持以單指令多數(shù)據(jù)(SIMD)方式執(zhí)行向量指令,充分利用好這些向量指令,可顯著提高應(yīng)用程序性能。例如,在IntelXeon處理器上支持256位寬的向量寄存器及相對(duì)應(yīng)的AVX或AVX2向量處理的指令,而在新一代MIC處理器上則支持512位寬的向量寄存器及相應(yīng)向量處理指令,這意味著理想情況下,MIC上的一條指令可以并發(fā)處理16個(gè)單精度浮點(diǎn)數(shù)(每個(gè)單精度浮點(diǎn)數(shù)4字節(jié)、32位)的操作,較單指令單數(shù)據(jù)的標(biāo)量處理加速16倍。

    為了在應(yīng)用程序中充分進(jìn)行SIMD向量化,可以通過編譯器自動(dòng)向量化、手工添加編譯指導(dǎo)語句、使用庫提供的向量數(shù)據(jù)類型編程、使用intrinsics編程以及內(nèi)嵌向量化匯編指令等方式加以實(shí)現(xiàn)。為了在性能與程序移植性、可讀性等方面達(dá)到平衡,本文主要采用重構(gòu)程序、使用編譯指導(dǎo)語句相結(jié)合以輔助編譯器自動(dòng)向量化的方式。主要技術(shù)包括:①對(duì)內(nèi)層對(duì)稱的ix迭代進(jìn)行循環(huán)分裂,形成兩個(gè)循環(huán)結(jié)構(gòu),為了利用編譯器自動(dòng)向量化,將其均修改為迭代變量逐次增加的形式;②在兩個(gè)最內(nèi)層循環(huán)上加上#pragmasimd以告訴編譯器無需進(jìn)行依賴性檢測,從而生成向量化指令。

    3.2.2 優(yōu)化訪存

    訪存是并行程序獲得良好并行效果的重要因素之一,并行程序的執(zhí)行過程中,由于循環(huán)變量有一定先后順序,可能出現(xiàn)訪問數(shù)據(jù)的順序與數(shù)據(jù)存放的順序不一致的情況,造成訪存局部性不好,發(fā)生訪問內(nèi)存不連續(xù)的問題,訪存的不連續(xù)必將帶來額外的訪存開銷。解決這一問題可以根據(jù)循環(huán)的特點(diǎn),對(duì)數(shù)據(jù)內(nèi)存布局進(jìn)行調(diào)整。

    本文首先進(jìn)行了循環(huán)交換優(yōu)化,但交換之后訪存的空間局部性不好,即相鄰兩次訪存的地址不連續(xù),存在較大跨度。這是因?yàn)榭焖貾KTM算法中的模型空間與數(shù)據(jù)空間均以二維數(shù)組的形式存儲(chǔ),算法進(jìn)行循環(huán)交換優(yōu)化之后,訪問二維數(shù)組的順序與數(shù)組在內(nèi)存中存放的順序不一致,導(dǎo)致訪存不連續(xù)。為解決這個(gè)問題,可以通過調(diào)整數(shù)據(jù)內(nèi)存布局,將二維數(shù)組在內(nèi)存中的存放順序調(diào)整成算法循環(huán)過程中的訪存順序,以優(yōu)化訪存性能。數(shù)據(jù)內(nèi)存布局調(diào)整前和調(diào)整后的訪存模式如圖6所示。

    Figure 6 Memory access models before and after the exchange of loop variables

    3.3 單一平臺(tái)上的多線程并行

    不論是傳統(tǒng)CPU處理器還是新興MIC平臺(tái)均為多核或眾核體系結(jié)構(gòu),充分挖掘應(yīng)用程序的并發(fā)性、提高多個(gè)處理器核心的利用率是提高應(yīng)用程序性能的關(guān)鍵要素之一。在這種具有共享存儲(chǔ)特點(diǎn)的平臺(tái)上,主要通過OpenMP多線程模型實(shí)現(xiàn)并行,為此需要對(duì)應(yīng)用程序進(jìn)行深入分析和并行性發(fā)掘。

    3.3.1 任務(wù)分解的多線程并行

    為了實(shí)現(xiàn)方便,最初采用分割最外層ib循環(huán)的方式進(jìn)行任務(wù)分解,每個(gè)任務(wù)分別處理一段互不重合的ib范圍,在整個(gè)模型空間及數(shù)據(jù)空間中進(jìn)行遍歷,發(fā)現(xiàn)滿足有效性的點(diǎn)對(duì)(ix,is)和(ix±ib,it),并完成相應(yīng)的數(shù)據(jù)更新操作;多個(gè)任務(wù)并發(fā)處理,但由于不同任務(wù)中更新模型空間的位置有可能相同,為了避免線程級(jí)數(shù)據(jù)競爭,需要對(duì)模型空間點(diǎn)更新操作進(jìn)行關(guān)鍵段保護(hù)(使用OpenMP的critical語句)或原子操作保護(hù)(使用OpenMP的atomic語句)。這種多線程并行在實(shí)現(xiàn)上只是針對(duì)循環(huán)書寫編譯指導(dǎo)語句,編程靈活、簡單,并行效率高。

    上述OpenMP多線程實(shí)現(xiàn)會(huì)出現(xiàn)數(shù)據(jù)競爭,導(dǎo)致某些線程空閑等待,造成線程資源的浪費(fèi)以及時(shí)間的消耗。避免數(shù)據(jù)競爭需要保證線程之間訪問的數(shù)據(jù)區(qū)域彼此不重合,需要對(duì)任務(wù)分解方案進(jìn)行改進(jìn)。

    注意到PKTM算法的核心處理是對(duì)模型空間的nx×nt個(gè)離散網(wǎng)格點(diǎn)進(jìn)行更新,由于各個(gè)離散網(wǎng)格點(diǎn)的更新過程相互獨(dú)立、互不影響,因此,本質(zhì)上可并發(fā)處理。因此可以針對(duì)模型空間的數(shù)據(jù)分割進(jìn)行任務(wù)分解,為了在并發(fā)性和并行粒度兩方面取得折衷,僅針對(duì)模型空間x-s平面中的s維進(jìn)行一維分割,形成多個(gè)獨(dú)立的并行任務(wù)。采用這種新的任務(wù)分解后,每個(gè)任務(wù)僅遍歷模型空間的一個(gè)局部塊,彼此之間互不重疊,不會(huì)發(fā)生同時(shí)寫同一模型數(shù)據(jù)點(diǎn)的數(shù)據(jù)競爭;另一方面,盡管各任務(wù)間可能出現(xiàn)訪問同一數(shù)據(jù)空間點(diǎn)的情況,但由于是讀操作,不影響結(jié)果正確性,因此無需特殊處理。

    在實(shí)現(xiàn)上,為了增大并行粒度,可簡單地將代碼中的ib循環(huán)與is循環(huán)進(jìn)行交換,對(duì)最外層的is循環(huán)添加OpenMP編譯指導(dǎo)語句。由于采用第3.2.2節(jié)訪存優(yōu)化技術(shù),這種循環(huán)交換后不會(huì)引發(fā)訪存性能問題。

    3.3.2 多線程并行的運(yùn)行配置與性能優(yōu)化

    為了充分提升多線程并行程序的運(yùn)行性能,還要考慮應(yīng)用程序跟操作系統(tǒng)、硬件平臺(tái)間的協(xié)同問題,特別是任務(wù)調(diào)度及線程對(duì)處理器核的親和性問題。

    由于通常線程數(shù)目受處理器資源所限,通常要遠(yuǎn)小于并行任務(wù)的數(shù)量,采用何種策略將這些任務(wù)分配、調(diào)度到所有線程上,也會(huì)對(duì)性能造成直接影響,在下面的第3.4.2節(jié)專門詳細(xì)討論這個(gè)問題。

    線程與處理器核綁定可以提高線程訪問CPU的Cache命中率,從而提高程序的并行性能。

    3.4 CPU+MIC異構(gòu)平臺(tái)上的混合并行

    本文采用CPU為主MIC為輔模式,即offload模式進(jìn)行CPU+MIC的混合并行。Offload模式適合串行計(jì)算程序中包含高并行計(jì)算部分,且并行部分并行度高的情況[9]。CPU+MIC混合并行的難點(diǎn)主要是任務(wù)分配和負(fù)載均衡的問題,混合并行的負(fù)載均衡涉及到不同計(jì)算能力的兩個(gè)平臺(tái)之間以及平臺(tái)內(nèi)部各線程之間的負(fù)載均衡。下面將分別介紹這兩個(gè)層次的任務(wù)分配和負(fù)載均衡策略。

    3.4.1CPU和MIC之間負(fù)載均衡

    由于主頻與核數(shù)的不同,CPU與MIC之間的處理能力有差異,為了達(dá)到不同平臺(tái)之間的負(fù)載均衡,需要針對(duì)MIC和CPU的任務(wù)處理能力,對(duì)MIC和CPU的任務(wù)進(jìn)行分配。本文用變量ratio表示上傳到MIC上進(jìn)行處理的任務(wù)占總?cè)蝿?wù)的比例,通過調(diào)整ratio的值,可以得到最優(yōu)的MIC與CPU任務(wù)數(shù)之比。當(dāng)墻鐘時(shí)間最短時(shí),認(rèn)為MIC與CPU的任務(wù)比達(dá)到最優(yōu),此時(shí)對(duì)應(yīng)的ratio′( 1-ratio)的值即為最優(yōu)的MIC與CPU的任務(wù)比。

    3.4.2 CPU或MIC內(nèi)部多線程之間負(fù)載均衡

    (1)采用動(dòng)態(tài)任務(wù)調(diào)度策略。

    任務(wù)調(diào)度策略包括動(dòng)態(tài)任務(wù)調(diào)度和靜態(tài)任務(wù)調(diào)度。對(duì)于本應(yīng)用,采用靜態(tài)任務(wù)調(diào)度策略會(huì)導(dǎo)致負(fù)載不均衡,采用動(dòng)態(tài)任務(wù)調(diào)度策略則可以緩解負(fù)載不均勻的情況。

    理論上,PKTM算法求得的數(shù)據(jù)空間下標(biāo)it的值與負(fù)載量之間滿足以下關(guān)系:

    (6)

    其中,it為整數(shù),且it∈[0,nt]。

    公式(6)表明:對(duì)于確定的整數(shù)it,其負(fù)載量f(it)是可估算的,且負(fù)載量關(guān)于it遞減,負(fù)載量f(it)的函數(shù)圖像如圖7所示(nx=8 000,nt=8 000,dt=0.004,dx=25,v=1 000時(shí))。不妨假設(shè)線程數(shù)為2,采用靜態(tài)任務(wù)調(diào)度策略時(shí),任務(wù)將按照it遞增的順序交替分配給線程0和線程1,即所有it為偶數(shù)的計(jì)算任務(wù)交由線程0處理,所有it為奇數(shù)的計(jì)算任務(wù)交由線程1處理。假設(shè)分配給線程0和線程1的任務(wù)數(shù)相等,設(shè)為nTask,則線程0和線程1的負(fù)載量fp0和fp1可由公式(7)表示。

    f(2)+…+f(2×nTask-2),

    f(3)+…+f(2×nTask-1),

    (7)

    由于f(it)關(guān)于it遞減,因此有f(0)>f(1),f(2)>f(3),…,f(nTask-2)>f(nTask-1),于是fp0>fp1,導(dǎo)致線程0和線程1之間的負(fù)載不均衡,且這種不均衡性會(huì)隨著任務(wù)數(shù)增加而更加明顯。

    采用動(dòng)態(tài)任務(wù)調(diào)度策略會(huì)根據(jù)線程的實(shí)際任務(wù)完成情況來分配新任務(wù),負(fù)載不均衡的現(xiàn)象可以得到一定緩解。Vtune的實(shí)測結(jié)果也反映了這一點(diǎn),詳見下一節(jié)內(nèi)容。

    Figure 7 Relationship between overload and variable it

    (2)單個(gè)任務(wù)的粒度可調(diào)整。

    為進(jìn)一步解決負(fù)載不均衡問題,本文在采用動(dòng)態(tài)任務(wù)調(diào)度的調(diào)度策略的同時(shí),考慮利用chunksize變量調(diào)節(jié)任務(wù)的粒度。進(jìn)行任務(wù)分配時(shí)的變量chunksize,其大小代表分配給線程的任務(wù)個(gè)數(shù),chunksize的值越大,任務(wù)的粒度越大。本文將chunksize作為影響負(fù)載均衡問題的一個(gè)因素進(jìn)行了一系列測試,通過調(diào)整chunksize值,測得一系列程序運(yùn)行的墻鐘時(shí)間,其中,最短的墻鐘時(shí)間對(duì)應(yīng)的chunksize值即為負(fù)載最均衡的chunksize值。

    4 測試結(jié)果與分析

    4.1 測試平臺(tái)與環(huán)境

    為考察第3節(jié)各類優(yōu)化與效果,我們使用一個(gè)單結(jié)點(diǎn)的CPU+MIC異構(gòu)計(jì)算機(jī)系統(tǒng)進(jìn)行了測試。測試平臺(tái)的環(huán)境與參數(shù)如表1所示。

    Table 1 Test platform and circumstance

    4.2 典型優(yōu)化方法的效果

    第3節(jié)提到的各種優(yōu)化方法相互之間有一定影響,所以單獨(dú)表示各個(gè)方法的性能比較困難。本文主要將之前提到的典型優(yōu)化方法融入到了3個(gè)主要版本中,測得問題規(guī)模為nt=8 000,nx=8 000時(shí),幾個(gè)典型優(yōu)化方法的性能提升如圖8所示。

    Figure 8 Performance improvement of classical optimization methods

    圖8中,橫坐標(biāo)為版本號(hào),版本1(包括v1.0,v1.1和v1.2)均為基于經(jīng)典PKTM算法的優(yōu)化版本,版本2(包括v2.0和v2.1)基于快速PKTM算法,版本3(包括v3.0和v3.1)為CPU+MIC協(xié)同異構(gòu)平臺(tái)下的優(yōu)化版本。版本1主要進(jìn)行的優(yōu)化包括編譯器優(yōu)化,Pthread改為OpenMP和提前確定迭代次數(shù);版本2主要進(jìn)行的優(yōu)化包括常量計(jì)算提前、循環(huán)交換、調(diào)整數(shù)組順序,利用對(duì)稱性減少迭代次數(shù),線程動(dòng)態(tài)任務(wù)分配;版本3主要是在版本2的基礎(chǔ)上進(jìn)行MIC移植,改進(jìn)了CPU與MIC之間的負(fù)載比例。

    圖8的縱坐標(biāo)代表獲得的性能提升,CPU的最優(yōu)性能在16線程的條件下獲得,性能提升的基準(zhǔn)為經(jīng)典PKTM并行算法的CPU性能;MIC的native模式最優(yōu)性能在180線程的條件下獲得,性能提升的基準(zhǔn)為基于經(jīng)典PKTM并行算法的MIC native模式性能;CPU+MIC的offload模式最優(yōu)性能在CPU端16線程、MIC端240線程×單MIC卡的條件下獲得,性能提升的基準(zhǔn)為經(jīng)典PKTM并行算法的CPU性能。具體性能提升如表2所示,最優(yōu)時(shí)間1.66 s與最原始的經(jīng)典PKTM并行算法的357.52 s相比,性能提升了214.37倍。

    Table 2 Performance improvement

    4.3 問題規(guī)模取值對(duì)計(jì)算量的影響

    問題規(guī)模對(duì)程序的計(jì)算量有一定影響,從而影響到優(yōu)化的性能。比如在快速PKTM算法中提前確定迭代次數(shù)的優(yōu)化方法,在固定規(guī)模nx=8 000,nt=8 000的條件下,it的計(jì)算量減少了約84%,對(duì)應(yīng)不同規(guī)模的組合,減少的計(jì)算量也不同。

    本文針對(duì)基于快速PKTM算法的提前確定迭代次數(shù)的優(yōu)化,測試了幾組不同規(guī)模對(duì)算法計(jì)算量以及性能提升的影響。測試結(jié)果如圖9所示。

    Figure 9 Effect of scale combination on the amount of computation

    圖9四幅圖的橫坐標(biāo)代表ix的取值范圍,縱坐標(biāo)是最大計(jì)算量比,表示對(duì)應(yīng)一個(gè)具體ix,實(shí)際產(chǎn)生有效it時(shí)的計(jì)算量占優(yōu)化前計(jì)算it需要的計(jì)算量的比例。如圖9d中,ix=319時(shí),最大計(jì)算量比為0.13,表示優(yōu)化前求it所進(jìn)行的計(jì)算中,只有13%的計(jì)算產(chǎn)生了有效的it,而87%的計(jì)算量不滿足條件判斷。經(jīng)過提前確定迭代次數(shù)的優(yōu)化,可以有效剔除無效計(jì)算,性能優(yōu)化的效果與問題規(guī)模的組合有關(guān)。如nx=2 000,nt=1 000時(shí)(如圖9d所示),最大計(jì)算量比為0.13,在此組合下進(jìn)行提前確定迭代次數(shù)的優(yōu)化至少能減少87%的計(jì)算量;而nx=1 000,nt=4 000時(shí)(如圖9c所示),最大計(jì)算量比為0.9,優(yōu)化后能減少的計(jì)算量為10%,不如圖9d的效果好。

    4.4 典型優(yōu)化方法效果展示

    固定問題規(guī)模nx=8 000,nt=8 000之后,仍然有一些因素會(huì)對(duì)優(yōu)化性能造成一定影響,如3.4節(jié)提到的,將程序移植到MIC平臺(tái)上與CPU協(xié)同處理的過程中涉及到的負(fù)載平衡問題,任務(wù)調(diào)度策略會(huì)影響性能,同時(shí)線程任務(wù)粒度的大小對(duì)性能也有一定影響。

    4.4.1 CPU或MIC內(nèi)部多線程之間的負(fù)載均衡

    之前介紹了CPU與MIC之間的處理能力有差異,因此需要針對(duì)MIC和CPU的任務(wù)處理能力,對(duì)MIC和CPU進(jìn)行任務(wù)分配。圖10顯示了調(diào)整MIC與CPU任務(wù)分配比例對(duì)程序運(yùn)行性能的影響。其中橫坐標(biāo)為變量ratio(單位為0.1),它表示分配到MIC端的任務(wù)數(shù)占總?cè)蝿?wù)的比例,縱坐標(biāo)代表按照ratio劃分任務(wù)后程序執(zhí)行的墻鐘時(shí)間。從圖10可以看出,當(dāng)ratio約為0.5時(shí),墻鐘時(shí)間最短,此時(shí)可以認(rèn)為MIC與CPU之間的負(fù)載大致平衡,對(duì)應(yīng)的MIC與CPU之間最優(yōu)任務(wù)數(shù)之比約為1∶1。

    Figure 10 Allocation performance of load balance between MIC and CPU

    4.4.2 動(dòng)靜態(tài)任務(wù)調(diào)度策略

    3.4.2節(jié)已從理論上分析了動(dòng)態(tài)調(diào)度相較于靜態(tài)調(diào)度負(fù)載更為平衡,Vtune實(shí)測的結(jié)果也表明動(dòng)態(tài)任務(wù)調(diào)度負(fù)載的優(yōu)勢(shì)。圖11是利用Vtune實(shí)測出的程序在不同任務(wù)調(diào)度策略下的運(yùn)行情況。圖11a采用靜態(tài)任務(wù)調(diào)度策略,其中第五個(gè)線程是瓶頸,其結(jié)束時(shí)間最晚,且與其它線程的結(jié)束時(shí)間相差較大,程序?qū)嶋H運(yùn)行時(shí),其它運(yùn)行結(jié)束的線程都在等待第五個(gè)線程結(jié)束,造成嚴(yán)重的資源浪費(fèi)。圖11b采用動(dòng)態(tài)任務(wù)調(diào)度策略,所有線程的結(jié)束時(shí)間相差很小,沒有線程空等的現(xiàn)象,資源利用率高,且與靜態(tài)任務(wù)調(diào)度策略相比,動(dòng)態(tài)任務(wù)調(diào)度的墻鐘時(shí)間更短。

    Figure 11 Load balance of static and dynamic scheduling

    4.4.3 線程任務(wù)粒度大小

    本文在考慮調(diào)度策略對(duì)性能造成影響的同時(shí),也考慮了線程任務(wù)粒度(chunksize)對(duì)負(fù)載均衡造成的影響。進(jìn)行任務(wù)分配時(shí)的變量chunksize,其大小代表分配給線程的任務(wù)個(gè)數(shù),chunksize的值越大,任務(wù)的粒度越大。不同的任務(wù)粒度會(huì)影響程序的負(fù)載情況,經(jīng)過實(shí)測得到chunksize與墻鐘時(shí)間的關(guān)系如圖12所示,其中橫坐標(biāo)代表不同的chunksize的大小,縱坐標(biāo)代表對(duì)應(yīng)的程序運(yùn)行墻鐘時(shí)間。由此可知,采取靜態(tài)任務(wù)調(diào)度,chunksize=6時(shí)墻鐘時(shí)間最短,負(fù)載相對(duì)平衡;采取動(dòng)態(tài)任務(wù)調(diào)度策略,chunksize=5時(shí)墻鐘時(shí)間最短,負(fù)載相對(duì)平衡。

    Figure 12 Effect of chunk size on load balance

    5 測試結(jié)果與分析

    本文針對(duì)Kirchhoff疊前時(shí)間偏移算法處理地震勘探數(shù)據(jù)的問題,基于CPU+MIC協(xié)同異構(gòu)平臺(tái),采用提前確定迭代次數(shù)、常量計(jì)算提前、循環(huán)交換、數(shù)據(jù)內(nèi)存布局調(diào)整、利用對(duì)稱性減少迭代次數(shù)、線程動(dòng)態(tài)任務(wù)分配、改進(jìn)CPU+MIC負(fù)載比例等一系列方法對(duì)原始程序進(jìn)行移植和優(yōu)化,對(duì)于6 000萬規(guī)模(8 000×8 000)的應(yīng)用問題,總的并行模擬時(shí)間從357.52 s減少到1.66 s,性能提升了214.37倍。本文第4節(jié)的應(yīng)用問題來源于中國計(jì)算機(jī)學(xué)會(huì)高性能計(jì)算專業(yè)委員會(huì)與Intel公司聯(lián)合舉辦的2013年全國教育科研并行應(yīng)用程序優(yōu)化大賽決賽題目,作者所在團(tuán)隊(duì)以本文優(yōu)化方法及效果獲得最高異構(gòu)計(jì)算性能獎(jiǎng)。

    本文針對(duì)異構(gòu)平臺(tái)計(jì)算能力的差異,進(jìn)行了一系列的分析與測試,總結(jié)出影響異構(gòu)平臺(tái)負(fù)載平衡的幾方面因素,并通過Vtune等進(jìn)行了驗(yàn)證,最終確定負(fù)載平衡的策略。本文進(jìn)行的優(yōu)化和分析策略可以擴(kuò)展到其它相似的異構(gòu)程序移植中去。

    后續(xù)工作主要可以從兩方面入手,一是可以進(jìn)一步分析并行程序的可擴(kuò)展性,二是針對(duì)更大的問題規(guī)模,可以考慮使用MPI多進(jìn)程將程序擴(kuò)展到多個(gè)結(jié)點(diǎn)上并行。

    [1] Zhao Chang-hai, Wang Shi-hu, Luo Guo-an, et al. A highly extensible 3D prestack kirchhoff time migration parallel algorithm[C]∥National Annual Conference on High Performance Computing, 2013:49-60.(in Chinese)

    [2] Jeffers J, Reinders J. Intel? Xeon Phitmcoprocessor high-performance programming[M]. NY:Elsevier, 2013.

    [3] top500 supercomputer sites[EB/OL].[2014-10-16].http://www.top500.org.

    [4] Bhardwaj D, Yerneni S. Efficient parallel I/O for seismic imaging in a distributed computing environment[C]∥Proc of

    the 3rd Conference and Exposition on Petroleum Geophysics, 2000:105-108.

    [5] Wang Hua-zhong, Liu Shao-yong, Kong Xiang-ning, et al. 3D Kirchoff PSDM for large-scale seismic data and its parallel implementation strategy[J]. Oil Geophysical Prospecting, 2012, 47(3):404-410.(in Chinese)

    [6] Zhang Qing, Chi Xu-guang, Xie Hai-bo,et al. Parallel algorithm based on the travel time computing of pre-stack time migration using GPU[J]. Computing Systems & Applications, 2011,20(8):42-46.(in Chinese)

    [7] Claerbout J F, Green I. Basic earth imagine[M]. California:Stanford University, 2008.

    [8] Claerbout J F. Introduction to Kirchhoff migration programs[R]. California:Stanford Exploration Report, 1997:385-391.

    [9] Wang En-dong, Zhang Qing, Shen Bo, et al. MIC High performance computing programming guide[M]. Beijing:China Water & Power Press, 2012.(in Chinese)

    附中文參考文獻(xiàn):

    [1] 趙長海, 王獅虎, 羅國安,等. 一個(gè)高度可擴(kuò)展的三維疊前Kirchhoff時(shí)間偏移并行算法[C]∥全國高性能計(jì)算學(xué)術(shù)年會(huì), 2013:49-60.

    [5] 王華忠, 劉少勇, 孔祥寧, 等. 大規(guī)模三維地震數(shù)據(jù)Kirchhoff疊前深度偏移及其并行實(shí)現(xiàn)[J]. 石油地球物理勘探, 2012, 47(3):404-410.

    [6] 張清, 遲旭光, 謝海波,等. 基于GPU實(shí)現(xiàn)疊前時(shí)間偏移走時(shí)計(jì)算的并行算法[J]. 計(jì)算機(jī)系統(tǒng)應(yīng)用, 2011, 20(8):42-46.

    [9] 王恩東, 張清, 沈鉑,等. MIC高性能計(jì)算編程指南[M]. 北京:中國水利水電出版社, 2012.

    XIONG Min,born in 1990,PhD candidate,CCF member(E200036553G),her research interests include large scale engineering and science computation.

    王勇獻(xiàn)(1975-),男,河南安陽人,博士,副研究員,CCF會(huì)員(E200021304M),研究方向?yàn)楦咝阅苡?jì)算。E-mail:yxwang@nudt.edu.cn

    WANG Yong-xian,born in 1975,PhD,associate research fellow,CCF member(E200021304M),his research interest includes high performance computing.

    Parallel optimization of the seismic wave PKTM algorithm on CPU+MIC heterogeneous platform

    XIONG Min,WANG Yong-xian

    (College of Computer,National University of Defense Technology,Changsha 410073,China)

    An efficient technique which is now being implemented in photographing images of complicated rock stratum is the seismic wave PKTM algorithm. With the earthquake prediction coming into massive data generation, it is of essential importance to optimize this algorithm by parallel computation. In recent years, high performance parallel computation is characterized by heterogeneous and many cores systems.A typical example of this kind of processors, featured with low cost and high performance is Xeon Phi, being known as MIC. On the basis of the classic PKTM algorithm, we parallelize and optimize the PKTM algorithm in the offload programming model, based on CPU+MIC heterogeneous platform. For applications with the scale of 64 000 000(8 000×8 000),the total parallel simulation time is reduced from 357.52 seconds to 1.66 seconds, achieving 214.37x performance improvement.

    collaborative parallel;Intel Xeon Phi;heterogeneous parallel;Kirchhoff Time Migration;performance optimization

    1007-130X(2015)01-0014-09

    2014-09-10;

    2014-11-12基金項(xiàng)目:空氣動(dòng)力學(xué)國家重點(diǎn)實(shí)驗(yàn)室開放課題資助項(xiàng)目(SKLA201401);國家自然科學(xué)基金資助項(xiàng)目(61379056, 11272352)

    TP274

    A

    10.3969/j.issn.1007-130X.2015.01.003

    熊敏(1990-),女,湖南長沙人,博士生,CCF會(huì)員(E200036553G),研究方向?yàn)榇笠?guī)模工程與科學(xué)計(jì)算。E-mail:miyazawa21yy@aliyun.com

    通信地址:410073 湖南省長沙市國防科學(xué)技術(shù)大學(xué)計(jì)算機(jī)學(xué)院學(xué)員五隊(duì)

    Address:College of Computer,National University of Defense Technology,Changsha 410073,Hunan,P.R.China

    猜你喜歡
    任務(wù)調(diào)度線程異構(gòu)
    試論同課異構(gòu)之“同”與“異”
    基于改進(jìn)NSGA-Ⅱ算法的協(xié)同制造任務(wù)調(diào)度研究
    基于時(shí)間負(fù)載均衡蟻群算法的云任務(wù)調(diào)度優(yōu)化
    淺談linux多線程協(xié)作
    overlay SDN實(shí)現(xiàn)異構(gòu)兼容的關(guān)鍵技術(shù)
    LTE異構(gòu)網(wǎng)技術(shù)與組網(wǎng)研究
    云計(jì)算環(huán)境中任務(wù)調(diào)度策略
    云計(jì)算中基于進(jìn)化算法的任務(wù)調(diào)度策略
    在新興異構(gòu)SoCs上集成多種系統(tǒng)
    Linux線程實(shí)現(xiàn)技術(shù)研究
    婷婷色av中文字幕| av女优亚洲男人天堂| 国产精品亚洲av一区麻豆 | 一级,二级,三级黄色视频| 日韩视频在线欧美| 一二三四在线观看免费中文在| 男女边吃奶边做爰视频| av在线观看视频网站免费| 亚洲av日韩在线播放| 国产精品av久久久久免费| 免费黄网站久久成人精品| 亚洲一区中文字幕在线| 美女扒开内裤让男人捅视频| 亚洲激情五月婷婷啪啪| 男女免费视频国产| 国产深夜福利视频在线观看| 国产99久久九九免费精品| 欧美精品一区二区免费开放| 国产精品久久久人人做人人爽| 国产在视频线精品| 菩萨蛮人人尽说江南好唐韦庄| 十八禁网站网址无遮挡| 日韩 亚洲 欧美在线| 日本猛色少妇xxxxx猛交久久| 国产成人精品无人区| 秋霞伦理黄片| 国产精品久久久久久精品电影小说| 大码成人一级视频| 国产成人精品无人区| 久久国产精品男人的天堂亚洲| 国语对白做爰xxxⅹ性视频网站| 人人妻人人爽人人添夜夜欢视频| 亚洲欧美精品综合一区二区三区| 久久久久精品久久久久真实原创| 国产淫语在线视频| 国产人伦9x9x在线观看| 亚洲一码二码三码区别大吗| 亚洲国产看品久久| 老司机在亚洲福利影院| av一本久久久久| 欧美精品一区二区免费开放| 亚洲精品美女久久av网站| 国产精品国产三级国产专区5o| 国产一区二区 视频在线| 这个男人来自地球电影免费观看 | 久久久欧美国产精品| 少妇 在线观看| 久久人人爽av亚洲精品天堂| 两性夫妻黄色片| 国产成人一区二区在线| 妹子高潮喷水视频| 亚洲,一卡二卡三卡| 99热网站在线观看| av网站免费在线观看视频| 欧美老熟妇乱子伦牲交| 热re99久久精品国产66热6| 青春草亚洲视频在线观看| 成人手机av| 欧美激情极品国产一区二区三区| 国产欧美日韩一区二区三区在线| 日日爽夜夜爽网站| 少妇人妻久久综合中文| 黄频高清免费视频| 亚洲成av片中文字幕在线观看| 欧美av亚洲av综合av国产av | 你懂的网址亚洲精品在线观看| 亚洲国产精品999| 国产亚洲av片在线观看秒播厂| 国产精品一二三区在线看| 丰满少妇做爰视频| 国产成人av激情在线播放| 少妇人妻久久综合中文| 亚洲精品久久久久久婷婷小说| 免费高清在线观看日韩| 国产精品香港三级国产av潘金莲 | 又粗又硬又长又爽又黄的视频| 色精品久久人妻99蜜桃| 欧美最新免费一区二区三区| 亚洲,欧美精品.| 精品亚洲成a人片在线观看| 97人妻天天添夜夜摸| 日日摸夜夜添夜夜爱| 久久久精品94久久精品| 国产欧美日韩综合在线一区二区| 五月开心婷婷网| 欧美黑人欧美精品刺激| 日韩视频在线欧美| 久久天堂一区二区三区四区| 亚洲国产欧美日韩在线播放| 国产精品免费视频内射| 欧美日韩精品网址| 国产精品熟女久久久久浪| 天天影视国产精品| 狠狠精品人妻久久久久久综合| 亚洲五月色婷婷综合| 亚洲四区av| 亚洲自偷自拍图片 自拍| 精品少妇内射三级| 毛片一级片免费看久久久久| 亚洲欧洲精品一区二区精品久久久 | 久久婷婷青草| 极品少妇高潮喷水抽搐| 999精品在线视频| 国产亚洲av高清不卡| 超碰成人久久| 亚洲欧洲精品一区二区精品久久久 | 99精国产麻豆久久婷婷| 欧美老熟妇乱子伦牲交| 亚洲成人国产一区在线观看 | 搡老岳熟女国产| 黄色 视频免费看| 99热全是精品| 在线免费观看不下载黄p国产| 韩国高清视频一区二区三区| 无限看片的www在线观看| 国精品久久久久久国模美| 9色porny在线观看| 高清av免费在线| 国产成人91sexporn| 亚洲国产av新网站| 91国产中文字幕| 日韩av不卡免费在线播放| 日韩av在线免费看完整版不卡| 久久久久久久久久久久大奶| 久久精品国产亚洲av高清一级| 欧美激情高清一区二区三区 | 99热网站在线观看| 欧美日韩视频精品一区| 最新的欧美精品一区二区| 满18在线观看网站| 国产av码专区亚洲av| 亚洲av电影在线进入| 成人亚洲精品一区在线观看| 亚洲精品美女久久av网站| 亚洲精品一二三| 国产淫语在线视频| 精品一品国产午夜福利视频| 欧美精品高潮呻吟av久久| 亚洲av成人不卡在线观看播放网 | 成年人免费黄色播放视频| 日韩欧美一区视频在线观看| 天天影视国产精品| 日韩 欧美 亚洲 中文字幕| 精品人妻在线不人妻| 日韩视频在线欧美| 在线观看免费视频网站a站| 赤兔流量卡办理| 亚洲国产精品999| 精品人妻熟女毛片av久久网站| 91精品三级在线观看| 美女高潮到喷水免费观看| 美女高潮到喷水免费观看| 黄色一级大片看看| 国产精品二区激情视频| 亚洲国产精品999| 在线精品无人区一区二区三| 久久亚洲国产成人精品v| 1024香蕉在线观看| 欧美在线黄色| 国产淫语在线视频| 国产又爽黄色视频| 无遮挡黄片免费观看| 国产亚洲精品第一综合不卡| 高清在线视频一区二区三区| 亚洲少妇的诱惑av| av在线app专区| 精品亚洲成国产av| 波多野结衣av一区二区av| 日韩制服丝袜自拍偷拍| 丝瓜视频免费看黄片| 飞空精品影院首页| 中文字幕亚洲精品专区| 久久人人爽人人片av| 亚洲国产精品成人久久小说| 美女国产高潮福利片在线看| 欧美人与性动交α欧美软件| 在线观看www视频免费| 国产成人欧美| 国产精品免费视频内射| av女优亚洲男人天堂| a级毛片黄视频| 午夜91福利影院| 亚洲欧洲日产国产| 18在线观看网站| 免费女性裸体啪啪无遮挡网站| 狠狠婷婷综合久久久久久88av| 久久99一区二区三区| 亚洲欧美一区二区三区黑人| 精品免费久久久久久久清纯 | 成人18禁高潮啪啪吃奶动态图| 搡老乐熟女国产| 亚洲国产精品一区三区| 波多野结衣一区麻豆| 日本一区二区免费在线视频| 亚洲精品自拍成人| 国产成人精品久久二区二区91 | 99久国产av精品国产电影| 国产老妇伦熟女老妇高清| 少妇 在线观看| 欧美 日韩 精品 国产| 亚洲第一av免费看| 黄片小视频在线播放| 久久女婷五月综合色啪小说| 高清黄色对白视频在线免费看| 麻豆av在线久日| 日本wwww免费看| 多毛熟女@视频| 91精品伊人久久大香线蕉| 丝袜脚勾引网站| 飞空精品影院首页| 国产xxxxx性猛交| 国产探花极品一区二区| 一级毛片黄色毛片免费观看视频| 18在线观看网站| 精品国产一区二区久久| 亚洲国产欧美在线一区| 国产一区二区 视频在线| 午夜91福利影院| 亚洲精品第二区| 成年av动漫网址| 赤兔流量卡办理| 人人妻人人澡人人爽人人夜夜| 伊人亚洲综合成人网| 亚洲色图 男人天堂 中文字幕| 亚洲av福利一区| 老司机在亚洲福利影院| av在线app专区| 国产免费现黄频在线看| 亚洲一区二区三区欧美精品| 十分钟在线观看高清视频www| 亚洲情色 制服丝袜| 亚洲欧美清纯卡通| 亚洲精品成人av观看孕妇| 丁香六月天网| 日韩欧美一区视频在线观看| 深夜精品福利| 久久久国产精品麻豆| 免费观看人在逋| 香蕉丝袜av| 久久久久久久久久久久大奶| 性少妇av在线| 女人爽到高潮嗷嗷叫在线视频| 高清在线视频一区二区三区| 欧美日韩亚洲综合一区二区三区_| 精品国产一区二区久久| 日韩免费高清中文字幕av| 国产色婷婷99| 午夜福利免费观看在线| 国产极品天堂在线| 一区在线观看完整版| 七月丁香在线播放| 国产人伦9x9x在线观看| 少妇猛男粗大的猛烈进出视频| 老司机亚洲免费影院| 久久久久久人妻| 一区福利在线观看| 看十八女毛片水多多多| 色精品久久人妻99蜜桃| 亚洲美女视频黄频| 丰满乱子伦码专区| 毛片一级片免费看久久久久| 成年人午夜在线观看视频| 97精品久久久久久久久久精品| 熟妇人妻不卡中文字幕| 岛国毛片在线播放| 一级,二级,三级黄色视频| 免费不卡黄色视频| 激情五月婷婷亚洲| 丰满少妇做爰视频| 国产无遮挡羞羞视频在线观看| 日本91视频免费播放| 亚洲视频免费观看视频| 色网站视频免费| 亚洲精品视频女| 一级毛片电影观看| 一级毛片我不卡| 丝袜在线中文字幕| 欧美变态另类bdsm刘玥| 亚洲成色77777| 亚洲精品,欧美精品| 看免费av毛片| 女性被躁到高潮视频| 在线亚洲精品国产二区图片欧美| 久热这里只有精品99| 黑丝袜美女国产一区| 免费人妻精品一区二区三区视频| 亚洲国产欧美在线一区| 少妇人妻精品综合一区二区| 国产精品.久久久| 哪个播放器可以免费观看大片| 搡老乐熟女国产| 久久久久精品性色| 巨乳人妻的诱惑在线观看| 亚洲精品自拍成人| 日韩中文字幕视频在线看片| 久久青草综合色| www.自偷自拍.com| 高清黄色对白视频在线免费看| 成人国语在线视频| 久久99一区二区三区| 国产精品秋霞免费鲁丝片| 男女高潮啪啪啪动态图| 亚洲欧美清纯卡通| 久热爱精品视频在线9| 精品亚洲成a人片在线观看| 久久av网站| 欧美精品一区二区大全| 亚洲国产欧美在线一区| 婷婷色av中文字幕| 国产一卡二卡三卡精品 | 婷婷成人精品国产| 一区福利在线观看| 国产精品一二三区在线看| 韩国av在线不卡| 国语对白做爰xxxⅹ性视频网站| 丰满迷人的少妇在线观看| 亚洲成人av在线免费| 久久毛片免费看一区二区三区| 国产精品久久久av美女十八| 亚洲av成人不卡在线观看播放网 | 亚洲av国产av综合av卡| 1024视频免费在线观看| 精品国产乱码久久久久久小说| 日日撸夜夜添| 国产亚洲最大av| 丁香六月欧美| 人妻人人澡人人爽人人| 国产精品99久久99久久久不卡 | 最近最新中文字幕免费大全7| 黄色视频在线播放观看不卡| 国产色婷婷99| 国产又色又爽无遮挡免| 在线天堂中文资源库| 亚洲欧美精品自产自拍| 婷婷色麻豆天堂久久| 欧美日韩福利视频一区二区| 亚洲免费av在线视频| 国产精品免费大片| 亚洲色图综合在线观看| 一本久久精品| 老汉色∧v一级毛片| 国产色婷婷99| 九草在线视频观看| 久久精品91无色码中文字幕| 在线观看免费日韩欧美大片| 97超级碰碰碰精品色视频在线观看| 国产精品一区二区免费欧美| 91九色精品人成在线观看| 一区二区三区激情视频| 人人妻人人澡欧美一区二区 | 亚洲成a人片在线一区二区| 国产精品永久免费网站| 一级毛片精品| 成年版毛片免费区| 一本综合久久免费| 怎么达到女性高潮| 一区在线观看完整版| 亚洲国产精品合色在线| 国产精品久久久久久人妻精品电影| 国产亚洲av高清不卡| 国产成人一区二区三区免费视频网站| 国产熟女午夜一区二区三区| 色综合欧美亚洲国产小说| 日日爽夜夜爽网站| 9热在线视频观看99| 神马国产精品三级电影在线观看 | 亚洲人成电影免费在线| 国产精华一区二区三区| 亚洲最大成人中文| 男女午夜视频在线观看| 久久久水蜜桃国产精品网| 国产精品 国内视频| 操美女的视频在线观看| 免费观看精品视频网站| 麻豆成人av在线观看| 日本欧美视频一区| 久久精品人人爽人人爽视色| 青草久久国产| 欧美国产日韩亚洲一区| av电影中文网址| 天天躁夜夜躁狠狠躁躁| 亚洲熟妇中文字幕五十中出| 中亚洲国语对白在线视频| 精品日产1卡2卡| 国产熟女xx| 每晚都被弄得嗷嗷叫到高潮| 国产精品,欧美在线| 69av精品久久久久久| 老汉色av国产亚洲站长工具| 老鸭窝网址在线观看| e午夜精品久久久久久久| 一级毛片女人18水好多| av免费在线观看网站| 国产一区在线观看成人免费| 国产亚洲欧美在线一区二区| 国产国语露脸激情在线看| 狂野欧美激情性xxxx| 成人欧美大片| 女性被躁到高潮视频| 99久久久亚洲精品蜜臀av| 久久婷婷人人爽人人干人人爱 | 精品熟女少妇八av免费久了| 免费久久久久久久精品成人欧美视频| 看免费av毛片| 欧美日韩瑟瑟在线播放| 日本免费一区二区三区高清不卡 | 91国产中文字幕| 国产成人欧美在线观看| 黑人欧美特级aaaaaa片| 欧美乱色亚洲激情| 动漫黄色视频在线观看| 国产三级在线视频| 亚洲男人天堂网一区| 久久天躁狠狠躁夜夜2o2o| 欧美丝袜亚洲另类 | 国产国语露脸激情在线看| 多毛熟女@视频| 99久久99久久久精品蜜桃| 久久国产精品影院| 久久人人精品亚洲av| 长腿黑丝高跟| 后天国语完整版免费观看| 精品国内亚洲2022精品成人| 中文亚洲av片在线观看爽| 久久婷婷人人爽人人干人人爱 | 国内精品久久久久精免费| 日韩中文字幕欧美一区二区| 日韩欧美一区二区三区在线观看| а√天堂www在线а√下载| 老司机午夜十八禁免费视频| 亚洲精品av麻豆狂野| 亚洲中文字幕一区二区三区有码在线看 | 男女下面插进去视频免费观看| 国产欧美日韩综合在线一区二区| 高潮久久久久久久久久久不卡| 欧美精品啪啪一区二区三区| 人人妻,人人澡人人爽秒播| 女生性感内裤真人,穿戴方法视频| 精品欧美国产一区二区三| 黄片播放在线免费| 国产成人欧美| 日本精品一区二区三区蜜桃| 一级,二级,三级黄色视频| 午夜久久久在线观看| 国产伦一二天堂av在线观看| 伊人久久大香线蕉亚洲五| 亚洲人成77777在线视频| 亚洲av第一区精品v没综合| 免费搜索国产男女视频| 大香蕉久久成人网| 好男人在线观看高清免费视频 | 久久国产乱子伦精品免费另类| 女人高潮潮喷娇喘18禁视频| 夜夜躁狠狠躁天天躁| 国产极品粉嫩免费观看在线| 99在线视频只有这里精品首页| 欧美成狂野欧美在线观看| 一二三四社区在线视频社区8| 欧美人与性动交α欧美精品济南到| 夜夜躁狠狠躁天天躁| 亚洲精品在线观看二区| 久久人妻福利社区极品人妻图片| 日韩欧美在线二视频| 一进一出抽搐gif免费好疼| 90打野战视频偷拍视频| 操美女的视频在线观看| 九色亚洲精品在线播放| 长腿黑丝高跟| 色综合欧美亚洲国产小说| 欧美日韩黄片免| 国产精品爽爽va在线观看网站 | 久久香蕉国产精品| 亚洲免费av在线视频| 12—13女人毛片做爰片一| 男女之事视频高清在线观看| 国产99久久九九免费精品| 午夜福利欧美成人| 国产精品美女特级片免费视频播放器 | 日本撒尿小便嘘嘘汇集6| 亚洲欧美日韩另类电影网站| 国产一区二区在线av高清观看| 亚洲精品国产一区二区精华液| 亚洲专区中文字幕在线| av网站免费在线观看视频| 窝窝影院91人妻| 精品人妻在线不人妻| 真人一进一出gif抽搐免费| 老司机深夜福利视频在线观看| www.999成人在线观看| 欧美中文日本在线观看视频| 亚洲国产欧美日韩在线播放| 免费人成视频x8x8入口观看| 日韩大尺度精品在线看网址 | 久99久视频精品免费| 一本大道久久a久久精品| 亚洲精品美女久久av网站| 国产激情久久老熟女| ponron亚洲| 亚洲五月天丁香| 韩国av一区二区三区四区| 天堂动漫精品| 亚洲国产精品久久男人天堂| 伊人久久大香线蕉亚洲五| 日本 欧美在线| 国产精品亚洲美女久久久| 长腿黑丝高跟| 亚洲精品国产色婷婷电影| 无遮挡黄片免费观看| 两个人视频免费观看高清| 色尼玛亚洲综合影院| 夜夜看夜夜爽夜夜摸| 岛国视频午夜一区免费看| 99在线视频只有这里精品首页| 日日夜夜操网爽| 神马国产精品三级电影在线观看 | 久久久久久久久久久久大奶| 精品午夜福利视频在线观看一区| 午夜激情av网站| 免费av毛片视频| 久久午夜亚洲精品久久| 久久热在线av| 动漫黄色视频在线观看| 欧美日本中文国产一区发布| 国产熟女午夜一区二区三区| 久久 成人 亚洲| 国产av在哪里看| 欧美激情高清一区二区三区| 国产成人欧美在线观看| www日本在线高清视频| 国产不卡一卡二| 免费看十八禁软件| 久久国产精品人妻蜜桃| 在线观看www视频免费| 99国产精品免费福利视频| 麻豆国产av国片精品| 精品高清国产在线一区| 神马国产精品三级电影在线观看 | 一边摸一边抽搐一进一小说| 欧美大码av| 男人舔女人下体高潮全视频| 免费在线观看亚洲国产| 悠悠久久av| 桃红色精品国产亚洲av| 黄色成人免费大全| 少妇裸体淫交视频免费看高清 | 国产精品亚洲一级av第二区| 51午夜福利影视在线观看| 成人精品一区二区免费| 男女床上黄色一级片免费看| 久久伊人香网站| 午夜福利欧美成人| 久久久久久亚洲精品国产蜜桃av| 国产高清视频在线播放一区| 一本久久中文字幕| 亚洲专区国产一区二区| cao死你这个sao货| 老司机深夜福利视频在线观看| 亚洲人成77777在线视频| 国产精品野战在线观看| 免费高清视频大片| 精品一区二区三区av网在线观看| 免费av毛片视频| 午夜久久久在线观看| 国产又爽黄色视频| 久久久国产成人精品二区| 亚洲精品在线观看二区| a在线观看视频网站| 亚洲av五月六月丁香网| 久久精品国产亚洲av高清一级| 精品久久久精品久久久| 国产三级黄色录像| 午夜免费鲁丝| 国产成年人精品一区二区| 午夜久久久久精精品| 一区二区日韩欧美中文字幕| 校园春色视频在线观看| 欧美日本亚洲视频在线播放| 很黄的视频免费| 韩国精品一区二区三区| 黄色片一级片一级黄色片| 日本免费一区二区三区高清不卡 | 97人妻天天添夜夜摸| 亚洲欧美一区二区三区黑人| 成人欧美大片| 变态另类丝袜制服| 欧美一级a爱片免费观看看 | 女性生殖器流出的白浆| 啦啦啦观看免费观看视频高清 | √禁漫天堂资源中文www| 精品国产一区二区三区四区第35| 亚洲第一欧美日韩一区二区三区| 美女免费视频网站| 人妻久久中文字幕网| 美女免费视频网站| 精品欧美一区二区三区在线| 巨乳人妻的诱惑在线观看| 亚洲第一欧美日韩一区二区三区| 91成人精品电影| 无限看片的www在线观看| 国产精品爽爽va在线观看网站 | 后天国语完整版免费观看| 妹子高潮喷水视频| 午夜免费激情av| 国产亚洲精品久久久久久毛片| 亚洲欧美一区二区三区黑人| 无限看片的www在线观看| 91av网站免费观看| 熟妇人妻久久中文字幕3abv| 国产成人精品在线电影| 99久久99久久久精品蜜桃| 嫩草影院精品99| 美国免费a级毛片| 免费观看人在逋| 免费在线观看视频国产中文字幕亚洲| 天天添夜夜摸|