異構集群環境下逆時偏移任務調度算法

高新成，劉德聚，王莉利，李 強 ，柯 璇

(1.東北石油大學 現代教育技術中心，黑龍江 大慶 163318;2.東北石油大學 計算機與信息技術學院，黑龍江 大慶 163318;3.東北石油大學 地球科學學院，黑龍江 大慶 163318)

0 引 言

任務調度優化是集群系統研究的基本問題，可分為獨立任務調度和相關任務調度，是一種典型的NP(non-deterministic polynomial)難題[1]。任務調度直接影響集群系統的性能，經典的任務調度算法主要有Min-Min、Max-Min等；這些算法在處理簡單任務時能夠以較高的效率完成計算，但是在集群中處理大規模復雜任務時，會導致節點間負載嚴重失衡，大大降低系統的工作效率[2]。

逆時偏移成像過程中存在著數據計算量巨大的問題。集群計算是目前常被采用的高性能計算數據處理方式，由于受到資源的限制，通常采用異構集群系統完成計算任務。計算節點處理性能的各異性使得一個任務在不同節點上的計算時間各不相同[3]，導致完成時間差異很大。為了獲得更優的解決方案，文中提出了一種異構集群計算任務均衡調度算法，引入CPU/GPU協同調度機制[4]，提高計算效率，減少任務完成時間。

1 相關研究工作

1.1 逆時偏移算法處理流程

疊前逆時深度偏移是全波場的雙程波動方程偏移方法[5]，成像點位于接收點波場逆時延拓與震源波場延拓時間相一致之處。選用適當的成像條件進行成像，將單炮成像結果疊加，得到最終的偏移剖面[6]。圖1為疊前逆時偏移算法處理流程。

圖1 疊前逆時偏移算法處理流程

逆時偏移計算分為三部分：正演計算、逆時外推計算和應用成像。具體步驟如下：

Step1：波場正演計算過程。沿時間方向將震源激發的波場從零時刻進行正向傳播至最大時刻，保存每一時刻的波場信息；

Step2：波場逆推計算過程。根據地震記錄的檢波點處波場沿時間反向傳播至零時刻，保存每一時刻的波場值；

Step3：應用成像。將同一時刻的兩個波場值依次進行讀取，并利用成像條件做成像運算，完成單炮數據的逆時偏移。

1.2 傳統任務調度算法

1.2.1 Min-Min算法

優先考慮節點上完成時間最短的任務是Min-Min算法的核心思想[7]。假設任務集中待處理任務數量為n，任務集為M:{M1,M2,…,Mn}；計算節點的數量為r，節點集為D:{D1,D2,…,Dr}，待處理任務的數量遠遠大于計算節點的數量，Min-Min算法的實現步驟如下：

Step1：對任務集中的每一個任務，計算該任務被分配到節點集中每個節點上的完成時間，用矩陣Amn記錄，A(n,m)表示在第n個節點上處理第m個任務需要花費的時間；

Step2：遍歷Amn，找出每個任務在節點集中的最短完成時間，用Eiu記錄，E(i,u)表示第i個任務在第u個節點上的完成最短時間；

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

Step4：將Em(i,u)分配到節點Du上，并將任務集中的Em(i,u)刪除；

Step5：將其他任務在各節點上的完成時間以及計算節點的就緒時間進行更新；

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

Min-Min算法為性能好的計算節點分配過多的計算任務[8]，然而在異構集群環境中，任務復雜且重要程度不同，完成時間較短的任務優先分配，一些重要任務卻延遲執行，導致性能較差的節點長時間接收不到任務請求，而性能好的節點則一直處于負載過重的狀態[9]。

1.2.2 Max-Min算法

Max-Min算法在任務調度之前，首先獲取每個任務被分配到節點集中的最短完成時間，然后Max-Min算法會將節點上完成時間最短的長任務優先處理。

Max-Min算法在處理存在大量短任務的任務集時，可以實現一定的負載均衡效果[10]。然而在異構集群環境下，Max-Min 算法也具有其局限性，任務隊列中的長任務具有較高的優先級，總是優先分配長任務，計算節點必須在長任務處理完成后才能處理短任務。當集群中長任務數量居多時，同樣會導致性能好的節點負載過重，使得節點間的任務調度不均衡，降低集群系統的工作效率。

2 逆時偏移計算任務均衡調度算法

2.1 算法總體思想

為了提高集群節點資源的利用率，并考慮到集群中計算節點的差異，文中設計了一種適用于異構集群的自適應節點兩級任務調度算法。首先完成節點間計算任務的分配，然后再完成節點內計算任務的CPU/GPU二級協同調度。算法的總體框架如圖2所示。

圖2 算法總體框架

算法主要思想如下：

(1)主節點通過收集計算節點的硬件資源狀態信息，對計算節點的計算能力和集群整體處理能力進行測評，為后續任務的分配以及判斷是否需要負載均衡提供可靠的數據信息。

(2)主節點將任務進行分配，根據計算節點的性能信息將任務合理地分發到各個計算節點上。

(3)計算節點根據自身CPU和GPU的處理能力，對接收到的處理任務進行協同計算，并向主節點更新硬件狀態信息。

2.2 負載均衡機制

負載不均衡會導致固有資源利用率偏低[11]。近年來，負載均衡研究的焦點開始集中在動態負載均衡技術和策略上[12-13]，考慮用節點資源的平均利用率評估節點的負載指標，節點的資源利用率需考慮設備性能以及實時任務量，是一個動態變化的值。在作業調度時需要考慮兩個節點的性能差異，將更多的任務分配給計算能力強的節點，使得該節點的請求平均響應時間逐漸增加，另一個節點任務分配就相對較少，請求平均響應時間逐漸減少，最終達到兩者持平，從而達到負載均衡的目的[14]。

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

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

(1)

2.3 節點權值計算

節點計算能力是判斷能否為該節點分配任務的重要依據，節點各項資源的利用率[15]是評估節點計算能力的主要指標；異構集群中各節點的配置不同，同樣影響節點計算能力的差異；因此在評估計算能力時，要同時考慮各節點的性能和資源利用率。

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

(2)

2.4 算法流程設計

文中設計了異構集群環境下的逆時偏移計算任務均衡調度算法。實現節點間的一級任務分配和節點內CPU/GPU二級協同計算，如圖3所示。

圖3 逆時偏移調度算法流程

Node1-4表示各計算節點，文中算法的具體實現步驟如下：

Step1:主節點獲取Node節點的硬件狀態信息，

對Node節點的計算能力、集群處理能力進行測評；

Step2:根據Node節點以及集群的測評信息，判斷當前是否可以為該Node節點分配任務，是否需要開啟負載均衡；

Step3:主節點加載任務隊列，依據各Node節點的狀態信息，將炮集數據分塊并分配給各Node節點，等待先完成任務的Node節點再次請求；

Step4:各Node節點接收主節點發送的炮集數據，在節點內將炮集任務進行分配，CPU負責任務調度，向主節點發送數據請求等邏輯任務以及部分數據計算，將更多的炮集數據分配到運算能力強的GPU上；

Step5:當Node節點內任務完成時，Node節點向主節點發送請求數據，若主節點返回空數據集，則任務處理完成。

3 實驗結果分析

3.1 實驗環境

在異構集群環境下進行，搭建了由五個節點構成的集群環境，具體的系統配置見表1。

表1 系統配置

3.2 算法性能對比分析

通過實驗，對比文中算法與Min-Min和Max-Min算法的任務完成時間、任務處理中各節點的負載情況，評估各算法的性能。

3.2.1 任務完成時間

炮集數目是影響逆時偏移計算時間的重要指標，為保證實驗數據的準確性，設置20、30、40、50四種不同炮集數目的逆時偏移任務，如圖4所示。

圖4 任務完成時間對比

當炮集數目為20時，相比于Min-Min、Max-Min算法，文中算法的任務處理時間縮短了約12%；隨著炮集數目的增加，文中算法在處理逆時偏移任務時開始表現出更高的計算效率。當炮集數目達到50時，文中算法比Min-Min、Max-Min算法用時縮短了16%左右。

3.2.2 節點負載分析

記錄Min-Min、Max-Min算法和文中算法中各節點的CPU和GPU使用率，分析各節點的負載狀態，評估各算法在任務處理中的負載均衡效果。Node1-4的CPU、GPU使用率對比如圖5所示。

圖5 Node1-4的CPU和GPU使用率對比

(1)Min-Min算法中，Node1和Node2的CPU、GPU在整個算法執行的大部分時間內占用率很低，而Node3和Node4的CPU、GPU在算法執行過程中保持很高的使用率。這是因為Min-Min算法將節點上完成時間短的任務優先處理，為性能好的節點優先分配任務，導致集群中其他節點遲遲接收不到任務請求，而性能好的節點卻一直于負載過重狀態。

(2)Max-Min算法中，Node1-4在開始的一段時間內一直維持很高的CPU、GPU使用率，一段時間后開始進入空閑狀態。這是因為Max-Min算法會優先處理任務隊列中的長任務，使得集群中各Node節點一開始處于負載過重的狀態，長任務處理完成后，Node節點又會處于空閑狀態。

(3)文中算法中，Node1-4在算法運行的大部分時間內，保持CPU使用率在60%左右，GPU使用率在80%以上。其中Node 1、2在20 s內CPU和GPU的使用率增長較快，這是由于Node 1、2的性能比Node 3、4較差。20 s后，Node 1、2的負載值超出設定值，向主節點請求開啟負載均衡，主節點將任務優先分配給性能較好的Node3、4。此時，Node 1、2的CPU和GPU的使用率維持相對穩定狀態，而Node 3、4的CPU和GPU使用率將繼續保持增加，一段時間后，也開始維持相對穩定的狀態。

實驗結果表明，Min-Min算法和Max-Min算法在異構集群環境下對逆時偏移數據的處理效果并不理想，在處理數據量較大的任務時，各計算節點任務分配不均勻，導致節點間負載不均衡，使得集群的計算效率較低；而文中設計的自適應節點兩級任務均衡調度算法，在處理異構集群環境下的逆時偏移數據處理時，首先實現了計算節點間的一級任務分配，然后完成節點內的二級CPU/GPU協同計算任務，能夠對大批量逆時偏移計算任務進行有效分配，使得各計算節點間的負載相對合理，節點內資源得到有效利用，在一定程度上實現了負載均衡效果，較大提高了節點資源利用率以及集群計算效率。

4 結束語

針對傳統調度算法在處理復雜任務時存在資源分配不均、效率不高的問題，結合地震數據處理逆時偏移計算，提出了一種異構集群環境下自適應節點兩級任務調度算法。該算法引入了負載均衡和CPU/GPU協同調度雙重機制，使得各計算節點間和節點內的任務分配更加合理。將該算法應用于實際的逆時偏移數據處理中，與傳統的Min-Min、Max-Min算法進行對比實驗。結果表明文中算法使得計算任務更均衡，減少了整體運算時間，有效提高了系統資源利用率和異構集群的工作效率，具有一定的實用價值。