異構(gòu)集群環(huán)境下逆時(shí)偏移任務(wù)調(diào)度算法

高新成，劉德聚，王莉利，李 強(qiáng) ，柯 璇

(1.東北石油大學(xué) 現(xiàn)代教育技術(shù)中心，黑龍江 大慶 163318;2.東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318;3.東北石油大學(xué) 地球科學(xué)學(xué)院，黑龍江 大慶 163318)

0 引 言

任務(wù)調(diào)度優(yōu)化是集群系統(tǒng)研究的基本問(wèn)題，可分為獨(dú)立任務(wù)調(diào)度和相關(guān)任務(wù)調(diào)度，是一種典型的NP(non-deterministic polynomial)難題[1]。任務(wù)調(diào)度直接影響集群系統(tǒng)的性能，經(jīng)典的任務(wù)調(diào)度算法主要有Min-Min、Max-Min等；這些算法在處理簡(jiǎn)單任務(wù)時(shí)能夠以較高的效率完成計(jì)算，但是在集群中處理大規(guī)模復(fù)雜任務(wù)時(shí)，會(huì)導(dǎo)致節(jié)點(diǎn)間負(fù)載嚴(yán)重失衡，大大降低系統(tǒng)的工作效率[2]。

逆時(shí)偏移成像過(guò)程中存在著數(shù)據(jù)計(jì)算量巨大的問(wèn)題。集群計(jì)算是目前常被采用的高性能計(jì)算數(shù)據(jù)處理方式，由于受到資源的限制，通常采用異構(gòu)集群系統(tǒng)完成計(jì)算任務(wù)。計(jì)算節(jié)點(diǎn)處理性能的各異性使得一個(gè)任務(wù)在不同節(jié)點(diǎn)上的計(jì)算時(shí)間各不相同[3]，導(dǎo)致完成時(shí)間差異很大。為了獲得更優(yōu)的解決方案，文中提出了一種異構(gòu)集群計(jì)算任務(wù)均衡調(diào)度算法，引入CPU/GPU協(xié)同調(diào)度機(jī)制[4]，提高計(jì)算效率，減少任務(wù)完成時(shí)間。

1 相關(guān)研究工作

1.1 逆時(shí)偏移算法處理流程

疊前逆時(shí)深度偏移是全波場(chǎng)的雙程波動(dòng)方程偏移方法[5]，成像點(diǎn)位于接收點(diǎn)波場(chǎng)逆時(shí)延拓與震源波場(chǎng)延拓時(shí)間相一致之處。選用適當(dāng)?shù)某上駰l件進(jìn)行成像，將單炮成像結(jié)果疊加，得到最終的偏移剖面[6]。圖1為疊前逆時(shí)偏移算法處理流程。

圖1 疊前逆時(shí)偏移算法處理流程

逆時(shí)偏移計(jì)算分為三部分：正演計(jì)算、逆時(shí)外推計(jì)算和應(yīng)用成像。具體步驟如下：

Step1：波場(chǎng)正演計(jì)算過(guò)程。沿時(shí)間方向?qū)⒄鹪醇ぐl(fā)的波場(chǎng)從零時(shí)刻進(jìn)行正向傳播至最大時(shí)刻，保存每一時(shí)刻的波場(chǎng)信息；

Step2：波場(chǎng)逆推計(jì)算過(guò)程。根據(jù)地震記錄的檢波點(diǎn)處波場(chǎng)沿時(shí)間反向傳播至零時(shí)刻，保存每一時(shí)刻的波場(chǎng)值；

Step3：應(yīng)用成像。將同一時(shí)刻的兩個(gè)波場(chǎng)值依次進(jìn)行讀取，并利用成像條件做成像運(yùn)算，完成單炮數(shù)據(jù)的逆時(shí)偏移。

1.2 傳統(tǒng)任務(wù)調(diào)度算法

1.2.1 Min-Min算法

優(yōu)先考慮節(jié)點(diǎn)上完成時(shí)間最短的任務(wù)是Min-Min算法的核心思想[7]。假設(shè)任務(wù)集中待處理任務(wù)數(shù)量為n，任務(wù)集為M:{M1,M2,…,Mn}；計(jì)算節(jié)點(diǎn)的數(shù)量為r，節(jié)點(diǎn)集為D:{D1,D2,…,Dr}，待處理任務(wù)的數(shù)量遠(yuǎn)遠(yuǎn)大于計(jì)算節(jié)點(diǎn)的數(shù)量，Min-Min算法的實(shí)現(xiàn)步驟如下：

Step1：對(duì)任務(wù)集中的每一個(gè)任務(wù)，計(jì)算該任務(wù)被分配到節(jié)點(diǎn)集中每個(gè)節(jié)點(diǎn)上的完成時(shí)間，用矩陣Amn記錄，A(n,m)表示在第n個(gè)節(jié)點(diǎn)上處理第m個(gè)任務(wù)需要花費(fèi)的時(shí)間；

Step2：遍歷Amn，找出每個(gè)任務(wù)在節(jié)點(diǎn)集中的最短完成時(shí)間，用Eiu記錄，E(i,u)表示第i個(gè)任務(wù)在第u個(gè)節(jié)點(diǎn)上的完成最短時(shí)間；

Step3：在E(i,u)中找出最小值，記為Em(i,u)；

Step4：將Em(i,u)分配到節(jié)點(diǎn)Du上，并將任務(wù)集中的Em(i,u)刪除；

Step5：將其他任務(wù)在各節(jié)點(diǎn)上的完成時(shí)間以及計(jì)算節(jié)點(diǎn)的就緒時(shí)間進(jìn)行更新；

Step6：任務(wù)集是否為空，若不為空則返回至Step1；若為空，則任務(wù)分配完成。

Min-Min算法為性能好的計(jì)算節(jié)點(diǎn)分配過(guò)多的計(jì)算任務(wù)[8]，然而在異構(gòu)集群環(huán)境中，任務(wù)復(fù)雜且重要程度不同，完成時(shí)間較短的任務(wù)優(yōu)先分配，一些重要任務(wù)卻延遲執(zhí)行，導(dǎo)致性能較差的節(jié)點(diǎn)長(zhǎng)時(shí)間接收不到任務(wù)請(qǐng)求，而性能好的節(jié)點(diǎn)則一直處于負(fù)載過(guò)重的狀態(tài)[9]。

1.2.2 Max-Min算法

Max-Min算法在任務(wù)調(diào)度之前，首先獲取每個(gè)任務(wù)被分配到節(jié)點(diǎn)集中的最短完成時(shí)間，然后Max-Min算法會(huì)將節(jié)點(diǎn)上完成時(shí)間最短的長(zhǎng)任務(wù)優(yōu)先處理。

Max-Min算法在處理存在大量短任務(wù)的任務(wù)集時(shí)，可以實(shí)現(xiàn)一定的負(fù)載均衡效果[10]。然而在異構(gòu)集群環(huán)境下，Max-Min 算法也具有其局限性，任務(wù)隊(duì)列中的長(zhǎng)任務(wù)具有較高的優(yōu)先級(jí)，總是優(yōu)先分配長(zhǎng)任務(wù)，計(jì)算節(jié)點(diǎn)必須在長(zhǎng)任務(wù)處理完成后才能處理短任務(wù)。當(dāng)集群中長(zhǎng)任務(wù)數(shù)量居多時(shí)，同樣會(huì)導(dǎo)致性能好的節(jié)點(diǎn)負(fù)載過(guò)重，使得節(jié)點(diǎn)間的任務(wù)調(diào)度不均衡，降低集群系統(tǒng)的工作效率。

2 逆時(shí)偏移計(jì)算任務(wù)均衡調(diào)度算法

2.1 算法總體思想

為了提高集群節(jié)點(diǎn)資源的利用率，并考慮到集群中計(jì)算節(jié)點(diǎn)的差異，文中設(shè)計(jì)了一種適用于異構(gòu)集群的自適應(yīng)節(jié)點(diǎn)兩級(jí)任務(wù)調(diào)度算法。首先完成節(jié)點(diǎn)間計(jì)算任務(wù)的分配，然后再完成節(jié)點(diǎn)內(nèi)計(jì)算任務(wù)的CPU/GPU二級(jí)協(xié)同調(diào)度。算法的總體框架如圖2所示。

圖2 算法總體框架

算法主要思想如下：

(1)主節(jié)點(diǎn)通過(guò)收集計(jì)算節(jié)點(diǎn)的硬件資源狀態(tài)信息，對(duì)計(jì)算節(jié)點(diǎn)的計(jì)算能力和集群整體處理能力進(jìn)行測(cè)評(píng)，為后續(xù)任務(wù)的分配以及判斷是否需要負(fù)載均衡提供可靠的數(shù)據(jù)信息。

(2)主節(jié)點(diǎn)將任務(wù)進(jìn)行分配，根據(jù)計(jì)算節(jié)點(diǎn)的性能信息將任務(wù)合理地分發(fā)到各個(gè)計(jì)算節(jié)點(diǎn)上。

(3)計(jì)算節(jié)點(diǎn)根據(jù)自身CPU和GPU的處理能力，對(duì)接收到的處理任務(wù)進(jìn)行協(xié)同計(jì)算，并向主節(jié)點(diǎn)更新硬件狀態(tài)信息。

2.2 負(fù)載均衡機(jī)制

負(fù)載不均衡會(huì)導(dǎo)致固有資源利用率偏低[11]。近年來(lái)，負(fù)載均衡研究的焦點(diǎn)開(kāi)始集中在動(dòng)態(tài)負(fù)載均衡技術(shù)和策略上[12-13]，考慮用節(jié)點(diǎn)資源的平均利用率評(píng)估節(jié)點(diǎn)的負(fù)載指標(biāo)，節(jié)點(diǎn)的資源利用率需考慮設(shè)備性能以及實(shí)時(shí)任務(wù)量，是一個(gè)動(dòng)態(tài)變化的值。在作業(yè)調(diào)度時(shí)需要考慮兩個(gè)節(jié)點(diǎn)的性能差異，將更多的任務(wù)分配給計(jì)算能力強(qiáng)的節(jié)點(diǎn)，使得該節(jié)點(diǎn)的請(qǐng)求平均響應(yīng)時(shí)間逐漸增加，另一個(gè)節(jié)點(diǎn)任務(wù)分配就相對(duì)較少，請(qǐng)求平均響應(yīng)時(shí)間逐漸減少，最終達(dá)到兩者持平，從而達(dá)到負(fù)載均衡的目的[14]。

集群中節(jié)點(diǎn)的資源一般分為靜態(tài)資源和動(dòng)態(tài)資源，其中靜態(tài)資源是指各節(jié)點(diǎn)CPU、GPU的數(shù)量及配置等固定不變的性能指標(biāo)，而動(dòng)態(tài)資源是指CPU利用率、GPU利用率、網(wǎng)絡(luò)吞吐率、磁盤I/O讀寫速率等可變動(dòng)的因素，這些資源的變化狀態(tài)影響著節(jié)點(diǎn)的負(fù)載狀態(tài)。定義CPU利用率、GPU利用率、網(wǎng)絡(luò)吞吐率、CPU內(nèi)存使用率、GPU顯存使用率、磁盤I/O讀寫速率分別為cpu_u、gpu_u、net_u、Cmem_u、Gmem_u、disk_u。定義節(jié)點(diǎn)負(fù)載參數(shù)Li，如公式(1)所示：k1,k2,…,k6用于控制各指標(biāo)在節(jié)點(diǎn)負(fù)載中的占比大小，通過(guò)對(duì)節(jié)點(diǎn)的負(fù)載情況的計(jì)算，為負(fù)載低的節(jié)點(diǎn)優(yōu)先分配新任務(wù)，對(duì)于負(fù)載過(guò)高的節(jié)點(diǎn)，暫時(shí)不分配任務(wù)，從而減少負(fù)載均衡的發(fā)生。

Li=k1*cpu_u+k2*gpu_u+k3*net_u+k4*Cmem_u+k5*Gmem_u+k6*disk_u

(1)

2.3 節(jié)點(diǎn)權(quán)值計(jì)算

節(jié)點(diǎn)計(jì)算能力是判斷能否為該節(jié)點(diǎn)分配任務(wù)的重要依據(jù)，節(jié)點(diǎn)各項(xiàng)資源的利用率[15]是評(píng)估節(jié)點(diǎn)計(jì)算能力的主要指標(biāo)；異構(gòu)集群中各節(jié)點(diǎn)的配置不同，同樣影響節(jié)點(diǎn)計(jì)算能力的差異；因此在評(píng)估計(jì)算能力時(shí)，要同時(shí)考慮各節(jié)點(diǎn)的性能和資源利用率。

文中考慮了CPU頻率、CPU數(shù)量、CPU內(nèi)存、GPU頻率、GPU顯存、GPU數(shù)量、節(jié)點(diǎn)負(fù)載等多項(xiàng)指標(biāo)，分別表示為cpu_rate、cpu_num、cpu_mem、gpu_rate、gpu_mem、gpu_num、Li等。節(jié)點(diǎn)計(jì)算能力Vi如公式(2)所示：k1,k2用于控制公式中每一項(xiàng)的重要程度，Δcpu_rate、Δgpu_rate分別表示CPU和GPU實(shí)時(shí)的變化頻率，完成所有節(jié)點(diǎn)的權(quán)值計(jì)算之后，根據(jù)作業(yè)請(qǐng)求的資源信息，自動(dòng)選取符合要求且節(jié)點(diǎn)權(quán)值較大的作為運(yùn)行節(jié)點(diǎn)，這樣就會(huì)使得集群慢慢趨于負(fù)載均衡態(tài)。

(2)

2.4 算法流程設(shè)計(jì)

文中設(shè)計(jì)了異構(gòu)集群環(huán)境下的逆時(shí)偏移計(jì)算任務(wù)均衡調(diào)度算法。實(shí)現(xiàn)節(jié)點(diǎn)間的一級(jí)任務(wù)分配和節(jié)點(diǎn)內(nèi)CPU/GPU二級(jí)協(xié)同計(jì)算，如圖3所示。

圖3 逆時(shí)偏移調(diào)度算法流程

Node1-4表示各計(jì)算節(jié)點(diǎn)，文中算法的具體實(shí)現(xiàn)步驟如下：

Step1:主節(jié)點(diǎn)獲取Node節(jié)點(diǎn)的硬件狀態(tài)信息，

對(duì)Node節(jié)點(diǎn)的計(jì)算能力、集群處理能力進(jìn)行測(cè)評(píng)；

Step2:根據(jù)Node節(jié)點(diǎn)以及集群的測(cè)評(píng)信息，判斷當(dāng)前是否可以為該Node節(jié)點(diǎn)分配任務(wù)，是否需要開(kāi)啟負(fù)載均衡；

Step3:主節(jié)點(diǎn)加載任務(wù)隊(duì)列，依據(jù)各Node節(jié)點(diǎn)的狀態(tài)信息，將炮集數(shù)據(jù)分塊并分配給各Node節(jié)點(diǎn)，等待先完成任務(wù)的Node節(jié)點(diǎn)再次請(qǐng)求；

Step4:各Node節(jié)點(diǎn)接收主節(jié)點(diǎn)發(fā)送的炮集數(shù)據(jù)，在節(jié)點(diǎn)內(nèi)將炮集任務(wù)進(jìn)行分配，CPU負(fù)責(zé)任務(wù)調(diào)度，向主節(jié)點(diǎn)發(fā)送數(shù)據(jù)請(qǐng)求等邏輯任務(wù)以及部分?jǐn)?shù)據(jù)計(jì)算，將更多的炮集數(shù)據(jù)分配到運(yùn)算能力強(qiáng)的GPU上；

Step5:當(dāng)Node節(jié)點(diǎn)內(nèi)任務(wù)完成時(shí)，Node節(jié)點(diǎn)向主節(jié)點(diǎn)發(fā)送請(qǐng)求數(shù)據(jù)，若主節(jié)點(diǎn)返回空數(shù)據(jù)集，則任務(wù)處理完成。

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

3.1 實(shí)驗(yàn)環(huán)境

在異構(gòu)集群環(huán)境下進(jìn)行，搭建了由五個(gè)節(jié)點(diǎn)構(gòu)成的集群環(huán)境，具體的系統(tǒng)配置見(jiàn)表1。

表1 系統(tǒng)配置

3.2 算法性能對(duì)比分析

通過(guò)實(shí)驗(yàn)，對(duì)比文中算法與Min-Min和Max-Min算法的任務(wù)完成時(shí)間、任務(wù)處理中各節(jié)點(diǎn)的負(fù)載情況，評(píng)估各算法的性能。

3.2.1 任務(wù)完成時(shí)間

炮集數(shù)目是影響逆時(shí)偏移計(jì)算時(shí)間的重要指標(biāo)，為保證實(shí)驗(yàn)數(shù)據(jù)的準(zhǔn)確性，設(shè)置20、30、40、50四種不同炮集數(shù)目的逆時(shí)偏移任務(wù)，如圖4所示。

圖4 任務(wù)完成時(shí)間對(duì)比

當(dāng)炮集數(shù)目為20時(shí)，相比于Min-Min、Max-Min算法，文中算法的任務(wù)處理時(shí)間縮短了約12%；隨著炮集數(shù)目的增加，文中算法在處理逆時(shí)偏移任務(wù)時(shí)開(kāi)始表現(xiàn)出更高的計(jì)算效率。當(dāng)炮集數(shù)目達(dá)到50時(shí)，文中算法比Min-Min、Max-Min算法用時(shí)縮短了16%左右。

3.2.2 節(jié)點(diǎn)負(fù)載分析

記錄Min-Min、Max-Min算法和文中算法中各節(jié)點(diǎn)的CPU和GPU使用率，分析各節(jié)點(diǎn)的負(fù)載狀態(tài)，評(píng)估各算法在任務(wù)處理中的負(fù)載均衡效果。Node1-4的CPU、GPU使用率對(duì)比如圖5所示。

圖5 Node1-4的CPU和GPU使用率對(duì)比

(1)Min-Min算法中，Node1和Node2的CPU、GPU在整個(gè)算法執(zhí)行的大部分時(shí)間內(nèi)占用率很低，而Node3和Node4的CPU、GPU在算法執(zhí)行過(guò)程中保持很高的使用率。這是因?yàn)镸in-Min算法將節(jié)點(diǎn)上完成時(shí)間短的任務(wù)優(yōu)先處理，為性能好的節(jié)點(diǎn)優(yōu)先分配任務(wù)，導(dǎo)致集群中其他節(jié)點(diǎn)遲遲接收不到任務(wù)請(qǐng)求，而性能好的節(jié)點(diǎn)卻一直于負(fù)載過(guò)重狀態(tài)。

(2)Max-Min算法中，Node1-4在開(kāi)始的一段時(shí)間內(nèi)一直維持很高的CPU、GPU使用率，一段時(shí)間后開(kāi)始進(jìn)入空閑狀態(tài)。這是因?yàn)镸ax-Min算法會(huì)優(yōu)先處理任務(wù)隊(duì)列中的長(zhǎng)任務(wù)，使得集群中各Node節(jié)點(diǎn)一開(kāi)始處于負(fù)載過(guò)重的狀態(tài)，長(zhǎng)任務(wù)處理完成后，Node節(jié)點(diǎn)又會(huì)處于空閑狀態(tài)。

(3)文中算法中，Node1-4在算法運(yùn)行的大部分時(shí)間內(nèi)，保持CPU使用率在60%左右，GPU使用率在80%以上。其中Node 1、2在20 s內(nèi)CPU和GPU的使用率增長(zhǎng)較快，這是由于Node 1、2的性能比Node 3、4較差。20 s后，Node 1、2的負(fù)載值超出設(shè)定值，向主節(jié)點(diǎn)請(qǐng)求開(kāi)啟負(fù)載均衡，主節(jié)點(diǎn)將任務(wù)優(yōu)先分配給性能較好的Node3、4。此時(shí)，Node 1、2的CPU和GPU的使用率維持相對(duì)穩(wěn)定狀態(tài)，而Node 3、4的CPU和GPU使用率將繼續(xù)保持增加，一段時(shí)間后，也開(kāi)始維持相對(duì)穩(wěn)定的狀態(tài)。

實(shí)驗(yàn)結(jié)果表明，Min-Min算法和Max-Min算法在異構(gòu)集群環(huán)境下對(duì)逆時(shí)偏移數(shù)據(jù)的處理效果并不理想，在處理數(shù)據(jù)量較大的任務(wù)時(shí)，各計(jì)算節(jié)點(diǎn)任務(wù)分配不均勻，導(dǎo)致節(jié)點(diǎn)間負(fù)載不均衡，使得集群的計(jì)算效率較低；而文中設(shè)計(jì)的自適應(yīng)節(jié)點(diǎn)兩級(jí)任務(wù)均衡調(diào)度算法，在處理異構(gòu)集群環(huán)境下的逆時(shí)偏移數(shù)據(jù)處理時(shí)，首先實(shí)現(xiàn)了計(jì)算節(jié)點(diǎn)間的一級(jí)任務(wù)分配，然后完成節(jié)點(diǎn)內(nèi)的二級(jí)CPU/GPU協(xié)同計(jì)算任務(wù)，能夠?qū)Υ笈磕鏁r(shí)偏移計(jì)算任務(wù)進(jìn)行有效分配，使得各計(jì)算節(jié)點(diǎn)間的負(fù)載相對(duì)合理，節(jié)點(diǎn)內(nèi)資源得到有效利用，在一定程度上實(shí)現(xiàn)了負(fù)載均衡效果，較大提高了節(jié)點(diǎn)資源利用率以及集群計(jì)算效率。

4 結(jié)束語(yǔ)

針對(duì)傳統(tǒng)調(diào)度算法在處理復(fù)雜任務(wù)時(shí)存在資源分配不均、效率不高的問(wèn)題，結(jié)合地震數(shù)據(jù)處理逆時(shí)偏移計(jì)算，提出了一種異構(gòu)集群環(huán)境下自適應(yīng)節(jié)點(diǎn)兩級(jí)任務(wù)調(diào)度算法。該算法引入了負(fù)載均衡和CPU/GPU協(xié)同調(diào)度雙重機(jī)制，使得各計(jì)算節(jié)點(diǎn)間和節(jié)點(diǎn)內(nèi)的任務(wù)分配更加合理。將該算法應(yīng)用于實(shí)際的逆時(shí)偏移數(shù)據(jù)處理中，與傳統(tǒng)的Min-Min、Max-Min算法進(jìn)行對(duì)比實(shí)驗(yàn)。結(jié)果表明文中算法使得計(jì)算任務(wù)更均衡，減少了整體運(yùn)算時(shí)間，有效提高了系統(tǒng)資源利用率和異構(gòu)集群的工作效率，具有一定的實(shí)用價(jià)值。