梁宇軒,祁 鑫,韓君男

(中國(guó)石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院,山東 青島 266580)

?

虛擬計(jì)算環(huán)境的疊前深度偏移并行調(diào)度策略研究

梁宇軒,祁 鑫,韓君男

(中國(guó)石油大學(xué)(華東) 計(jì)算機(jī)與通信工程學(xué)院,山東 青島 266580)

通過對(duì)地震資料處理數(shù)據(jù)進(jìn)行分析,以模糊集合資源為依據(jù),構(gòu)建虛擬計(jì)算環(huán)境,并對(duì)并行任務(wù)進(jìn)行有效劃分,設(shè)計(jì)基于模糊聚類的并行調(diào)度算法。該算法首先對(duì)并行任務(wù)DAG圖設(shè)計(jì),然后采用模糊聚類方法將任務(wù)分配到合適的計(jì)算節(jié)點(diǎn)上,將資源在性能差異方面所產(chǎn)生的影響降到最低。研究結(jié)果證明計(jì)算節(jié)點(diǎn)分配任務(wù)的計(jì)算量越大,該節(jié)點(diǎn)的計(jì)算能力越強(qiáng),表明這種方法可以最大限度的挖掘虛擬計(jì)算環(huán)境的能力,從而使成本變得更小,而效率得到提高。

虛擬計(jì)算;并行調(diào)度;模糊聚類

虛擬計(jì)算環(huán)境一般用來處理較大規(guī)模的數(shù)據(jù)計(jì)算任務(wù),目的是利用計(jì)算環(huán)境組織異構(gòu)資源協(xié)同工作來實(shí)現(xiàn)的,具體過程如下:首先是利用網(wǎng)絡(luò)獲取數(shù)量較多的空閑的計(jì)算資源;然后對(duì)計(jì)算資源存在的不同之處進(jìn)行屏蔽;最后為各個(gè)用戶分配合適的計(jì)算資源來協(xié)同工作[1-2]。地震資料處理在石油地質(zhì)中有很重要的應(yīng)用,是典型的大規(guī)模處理的異構(gòu)環(huán)境[3],因此在對(duì)其建立的虛擬計(jì)算環(huán)境里[4],保證調(diào)度系統(tǒng)效率的關(guān)鍵所在,就是如何合理劃分任務(wù)并提交到合適的節(jié)點(diǎn)。

1 異構(gòu)環(huán)境下的并行任務(wù)劃分

資源在虛擬計(jì)算環(huán)境下的基本特征是異構(gòu)性,但是實(shí)際中計(jì)算性能的不同可能會(huì)造成調(diào)整策略的變動(dòng)。本文研究的目的就是在虛擬計(jì)算環(huán)境中,能把地震資料疊前深度偏移數(shù)據(jù)劃分到更合適虛擬計(jì)算環(huán)境,結(jié)合地震資料數(shù)據(jù)的特點(diǎn)以及地震資料處理的異構(gòu)環(huán)境,提出了如下針對(duì)并行任務(wù)的劃分算法。

(1)采用局部同構(gòu)法將所有的資源分成n個(gè)梯度,通過二元組重新整合資源集合,即:

(1)

在式(1)中,有V和C兩個(gè)集合,分別指的是資源性能和資源數(shù)量,所以Vi指在所有i(i=1,2,…,n)梯度時(shí),資源的平均性能,Ci指在所有i(i=1,2,…,n)梯度的總和。由此可以得到最后梯度i(i=1,2,…,n)的計(jì)算能力為:Pi=ViCi,通過公式可以看出,某個(gè)梯度的計(jì)算能力是與這個(gè)梯度計(jì)算資源集合的最大任務(wù)計(jì)算量成正比的。

(2)依據(jù)不同個(gè)體的計(jì)算能力,進(jìn)行任務(wù)的重新分配,用集合A={Ai|i=1,2,…,n}表示如下:

(2)

其中,Ai指的是最后要處理的炮集總數(shù),nxshoti為炮集編號(hào),梯度資源為i(i=1,2,…,n)。

(3)依據(jù)不同的梯度有著不同的任務(wù)量,計(jì)算炮數(shù)的起始和結(jié)束的數(shù)量,計(jì)算公式如下:

(a)當(dāng)i=1時(shí),

start_nxshoti=1,end_nxshoti=Pi.

(3)

(b)當(dāng)i>1時(shí),

(4)

其中,start_nxshoti和end_nxshoti分別指在整個(gè)數(shù)集里,不同梯度i(i=1,2,…,n)在所分得任務(wù)中的起始和結(jié)束的炮集編號(hào),

(4)依據(jù)(3)中得到的各炮集數(shù),獲得起始和結(jié)束時(shí)刻的道數(shù)。

(5)

(5)對(duì)各個(gè)梯度內(nèi)的任務(wù)進(jìn)行二次劃分。

如果Ci=1,則不需要此步驟,因?yàn)榇藭r(shí)資源量為1。

2 基于模糊聚類的并行調(diào)度算法

2.1 并行任務(wù)DAG圖設(shè)計(jì)

2.1.1 最短路徑

通常情況下,在表示并行任務(wù)的DAG圖里,為了能夠的得到更短的執(zhí)行總時(shí)間,所有的單獨(dú)路徑都要保證是最短的執(zhí)行時(shí)間,所有的單獨(dú)路徑有一個(gè)相差不多的執(zhí)行時(shí)間也很重要,即要保證均衡性。

依據(jù)以上兩點(diǎn),整個(gè)過程中每條執(zhí)行路徑都必須是性能最高且具有平衡性。如果整個(gè)過程中的單獨(dú)路徑數(shù)目為m,那么,其在x(x=1,2,…,m)的執(zhí)行時(shí)間中,用區(qū)間[sx,ex]來表示,sx表示的起始時(shí)間,ex表示結(jié)束時(shí)間,這時(shí)整個(gè)系統(tǒng)的最高時(shí)效性與執(zhí)行任務(wù)花費(fèi)最長(zhǎng)的時(shí)間路徑息息相關(guān),采用[smin,emax]表示最高時(shí)效性的調(diào)度目標(biāo),這其中:

(6)

由此得到了最短路徑,也就是說在處理地震資料的過程中,對(duì)疊前深度偏移進(jìn)行劃分之后所得到的并行任務(wù)DAG圖可以將復(fù)雜問題簡(jiǎn)單化,方便了整個(gè)調(diào)度策略的過程。

2.1.2 并行任務(wù)劃分與執(zhí)行時(shí)間

獨(dú)立路徑的數(shù)量是與并行劃分后的子任務(wù)的數(shù)量相統(tǒng)一的,他們的起始點(diǎn)和結(jié)束點(diǎn)是一樣的。調(diào)度過程的開始是在對(duì)DAG圖第一層次進(jìn)行任務(wù)劃分和調(diào)度,這樣保證了每條路徑的起始時(shí)間點(diǎn)是一樣的,此時(shí)刻設(shè)為0,得到如下公式:

smin=s1=s2=…=sm=0.

(7)

雖然在任務(wù)劃分與調(diào)度層和并行執(zhí)行層之間會(huì)有任務(wù)的傳輸開銷,但其對(duì)整個(gè)過程的影響不大,這里將其忽略不計(jì),這樣在第二層時(shí),同樣認(rèn)為他們的位置是起點(diǎn)時(shí)刻是同樣的,所以整個(gè)過程就簡(jiǎn)單了,各個(gè)路徑各自完成的最終執(zhí)行時(shí)間可以看成三個(gè)部分的疊加,即:

(a)子任務(wù)在這條路徑被并行執(zhí)行所需要的計(jì)算時(shí)間;

(b)從得到這個(gè)任務(wù)的執(zhí)行結(jié)果到其被送到所有結(jié)果進(jìn)行疊加的節(jié)點(diǎn)上,這一過程需要的時(shí)間;

(c)最后所有結(jié)果被疊加,所用到的時(shí)間。

由以上的分析可知,一個(gè)并行子任務(wù)的數(shù)據(jù)規(guī)模決定這個(gè)子任務(wù)的執(zhí)行時(shí)間,假設(shè)在傳輸數(shù)據(jù)量一樣的情況下,那么傳輸?shù)木W(wǎng)絡(luò)帶寬就決定了需要花費(fèi)的時(shí)間,在最后的結(jié)果疊加中,由此就得到了并行任務(wù)劃分。

2.2 基于模糊聚類的并行調(diào)度算法

根據(jù)以上描述的調(diào)度目標(biāo),對(duì)模糊聚類的并行任務(wù)調(diào)度算法的詳細(xì)表述如下:

(1)首先聚合資源節(jié)點(diǎn),利用注冊(cè)和信息服務(wù),以模糊聚類方法為基礎(chǔ),從而得出一系列具有不同梯度的集合;

(2)得到整個(gè)梯度集合的計(jì)算能力,計(jì)算能力為梯度數(shù)量、節(jié)點(diǎn)數(shù)量、梯度負(fù)載等,并對(duì)優(yōu)先級(jí)進(jìn)行排序;

(3)將原始任務(wù),根據(jù)其數(shù)據(jù)規(guī)模,設(shè)定其期望執(zhí)行時(shí)間,任務(wù)期望的計(jì)算能力。再定義兩個(gè)變量,分別為目標(biāo)起始梯度和目標(biāo)梯度范圍;

(4)根據(jù)優(yōu)先級(jí)降序,對(duì)梯度進(jìn)行循環(huán);

(5)遍歷選擇最合適的梯度,避免浪費(fèi),選擇最合適的梯度,不需要進(jìn)行跨梯度劃分時(shí),按照同構(gòu)環(huán)境下的并行任務(wù)劃分算法,將任務(wù)劃分并調(diào)度到梯度,否則按照異構(gòu)環(huán)境下的并行任務(wù)劃分算法;

(6)做好任務(wù)劃分和調(diào)度之后,還需要再找到另外一個(gè)可以成為結(jié)果疊加的匯總結(jié)點(diǎn),這個(gè)節(jié)點(diǎn)可以指定之前的一個(gè)調(diào)度節(jié)點(diǎn)。

從以上的描述中,可以看出在各個(gè)資源虛擬計(jì)算環(huán)境里存在著微小的差別,因此在同構(gòu)環(huán)境中簡(jiǎn)單化了調(diào)度算法,這樣如果并行速度足夠快,那么這個(gè)理論可以應(yīng)用于實(shí)際中。在對(duì)資源節(jié)點(diǎn)的計(jì)算能力考慮時(shí),要考慮兩方面,一是其自身的靜態(tài)物理屬性,二是其當(dāng)前的所有負(fù)載值,這樣才能保證在調(diào)度過程中不會(huì)有大的偏差。綜合來看算法的整個(gè)過程,如果不要求跨度調(diào)度,那么該算法可以達(dá)到理想情況;當(dāng)必須要進(jìn)行跨梯度劃分調(diào)度時(shí),該算法的最壞時(shí)間復(fù)雜度只有O(n2),所以可以看到這個(gè)算法與傳統(tǒng)的DAG任務(wù)調(diào)度中的更加簡(jiǎn)單。

3 實(shí)驗(yàn)測(cè)試與結(jié)果分析

以疊前深度偏移應(yīng)用實(shí)例進(jìn)行了測(cè)試,第一步的測(cè)試分析過程針對(duì)的是原始任務(wù)串行的執(zhí)行情況;第二步的測(cè)試過程針對(duì)的是按記錄道數(shù)和按偏移道數(shù)兩種不同方式任務(wù)進(jìn)行分類。

3.1 具體應(yīng)用案例

這是關(guān)于某個(gè)Fourier有限差分疊前深度偏移的應(yīng)用案例,其中最重要的計(jì)算內(nèi)容是素因子快速Fourier變換,主要輸出來自于相關(guān)的數(shù)據(jù)體記錄文件以及速度模型文件,最后的結(jié)果用偏移剖面圖表示,下面是具體的表述:

記錄數(shù)據(jù):mar_ibm_1.sgy,240炮、23040道;

執(zhí)行程序:sumigpreffd_sun.c,二維Fourier有限差分疊前深度偏移;

速度模型:mar_v_sun_sc_nh.sgy,249*750;

輸出結(jié)果:myffd.dat;

3.2 并行任務(wù)的模糊聚類的并行調(diào)度算法測(cè)試

在并行劃分和調(diào)度疊前深度偏移任務(wù)中,對(duì)處理器、內(nèi)存、硬盤和網(wǎng)絡(luò)通信四部分的按一定比例來分配,其集合為:

W={0.7,0.05,0.05,0.2}.

在整個(gè)過程中,以偏移道數(shù)模糊聚類為依據(jù),按照記錄道數(shù)和偏移道數(shù)兩種不同分類的并行調(diào)度算法,執(zhí)行疊前深度偏移測(cè)試。對(duì)試驗(yàn)結(jié)果分析后,選取合適的節(jié)點(diǎn)計(jì)算規(guī)模和合理的并行調(diào)度劃分方式,節(jié)點(diǎn)選用的是2、4、8三個(gè),對(duì)應(yīng)的劃分進(jìn)程也為2、4、8。表1為最終執(zhí)行時(shí)間的統(tǒng)計(jì)。 由上述結(jié)果可知,兩種分類下的變化規(guī)律并不相同。按記錄道數(shù)任務(wù)劃分時(shí),在節(jié)點(diǎn)數(shù)成倍上漲的情況下,其數(shù)據(jù)顯示并不會(huì)出現(xiàn)執(zhí)行時(shí)間的成倍減少,但按偏移道數(shù)任務(wù)劃分時(shí),在節(jié)點(diǎn)數(shù)成倍上漲的情況下,其數(shù)據(jù)顯示執(zhí)行時(shí)間基本也在成倍減少。這個(gè)原因是采用了按偏移道數(shù)的并行任務(wù)劃分方法,這種分類方法,可以與疊前深度偏移的特性相適應(yīng),最后的工作時(shí)間也更短。

表1 兩種分類所需時(shí)間的對(duì)比

4 結(jié) 論

(1)采用局部同構(gòu)法將所有的資源分成n個(gè)梯度,通過二元組重新整合資源,對(duì)地震資料數(shù)據(jù)按照任務(wù)梯度進(jìn)行并行任務(wù)劃分,依據(jù)梯度計(jì)算炮數(shù)的起始和結(jié)束時(shí)刻的數(shù)量,實(shí)現(xiàn)了地震資料處理在虛擬計(jì)算環(huán)境下的任務(wù)劃分。

(2)對(duì)已經(jīng)劃分好的疊前深度偏移并行任務(wù)進(jìn)行DAG分析,得到最短路徑,簡(jiǎn)化了并行任務(wù),然后以偏移道數(shù)模糊聚類為依據(jù),采用按偏移道數(shù)的并行任務(wù)劃分方法,可以與疊前深度偏移的特性相適應(yīng),縮短了工作時(shí)間,提高了執(zhí)行效率。

[1] 李偉,顧乃杰,劉振寬.三維疊前kirchhoff深度偏移軟件在并行計(jì)算機(jī)上的實(shí)現(xiàn)技術(shù)[J].計(jì)算機(jī)工程與應(yīng)用,2002(20):211-214.

[2] 張軍華,仝兆岐,何潮觀，等.基于HPF的地震資料并行處理系統(tǒng)研究與實(shí)現(xiàn)[J].計(jì)算機(jī)應(yīng)用,2002,22(9):57-59.

[3] 馬琳,陳莉.基于動(dòng)態(tài)Profiling技術(shù)的流水粒度調(diào)優(yōu)[J].計(jì)算機(jī)研究與發(fā)展,2005(6):163-170.

[4] 張辰,夏士雄,劉兵.一種改進(jìn)的可能模糊聚類算法[J].計(jì)算機(jī)應(yīng)用研究,2011,28(8):2849-2851.

[責(zé)任編輯] 董大偉

2017-03-15

國(guó)家自然科學(xué)基金項(xiàng)目(61671482)

梁宇軒(1996—)男，山東東營(yíng)人，中國(guó)石油大學(xué)(華東)計(jì)算機(jī)與通信工程學(xué)院碩士研究生，主要從事高性能計(jì)算研究。

10.3969/j.issn.1673-5935.2017.02.012

TP338

A

1673-5935(2017)02- 0042- 03