一種自適應資源精細匹配的DAG調(diào)度方法

胡鵬輝　鄧曉華　魏靜波　陳臘嬌

摘 要： 針對目前計算密集或數(shù)據(jù)密集特征的任務依賴和并行處理的耦合度過高，采用將關聯(lián)任務的執(zhí)行順序控制與并行算法的處理邏輯相分離。該方法通過任務分解的方式和自適應的多資源精細匹配，利用DEM數(shù)據(jù)建立起十萬量級柵格的大流域生態(tài)水文過程DAG任務調(diào)度模擬。在實驗部分，用多重對比的方法評估在分辨率、數(shù)據(jù)規(guī)模、進程數(shù)量以及本地資源管理器（LRM）不同條件情況下該方法的性能。實驗結果表明，任務分解的自適應多資源精細匹配DAG調(diào)度方法大幅度提高了并行性能和效率，具有較好的魯棒性和擴展性。

關鍵詞： DAG調(diào)度； 并行算法； 數(shù)據(jù)密集； 計算密集； 多資源匹配

中圖分類號： TN911.1?34 文獻標識碼： A 文章編號： 1004?373X（2017）21?0117?04

A DAG scheduling method for adaptive resources subtle matching

HU Penghui1， 2， DENG Xiaohua1， 2， WEI Jingbo1， 2， CHEN Lajiao3

（1. School of Information Engineering， Nanchang University， Nanchang 330031， China；

2. Institute of Space Science and Technology， Nanchang University， Nanchang 330031， China；

3. Institute for Remote Sensing & Digital Earth， Chinese Academy of Sciences， Beijing 100094， China）

Abstract： For the task dependence of computing intensive or data intensive characteristics and the high coupling degree of parallel processing， a method of separating the execution sequence control of correlation task and processing logic of parallel algorithm is adopted. By means of the task decomposition approach and adaptive multi?resource subtle matching， the DEM data is used to establish the DAG task scheduling simulation of the large watershed eco?hydrology process with hundred?thousand magnitude grids. The method performances of resolution， data scale， progress quantity and local resource manager （LRM） are evalua?ted under the condition of different resolutions by means of the multi?comparison method. The experimental results show that the DAG scheduling method of adaptive multi?resource subtle matching for task decomposition can improve the parallel performance and efficiency greatly， and has strong robustness and perfect scalability.

Keywords： DAG scheduling； parallel algorithm； intensive data； intensive computing； multi?resource matching

0 引 言

水文模型是指水文數(shù)學模型，而分布式水文模型是指分布式流域水文數(shù)學模型[1]。分布式水文模型與DEM結合，用偏微分方程控制基于物理過程的水文循環(huán)時空變化，它是探索和認識復雜水文循環(huán)過程和機理的有效手段，可用于解決許多水文實際問題。廣泛應用于流域水文的模型主要包含SWAT，SHE，DHSVM，HMS，SVAT，TOPMODEL等。上述流域生態(tài)水文過程模型由于缺乏對生態(tài)水文耦合機制的描述，以及難以獲得植被參數(shù)等問題造成了無法滿足流域水資源管理的需求。因此，本文采用基于生態(tài)最優(yōu)性原理建立起分布式流域生態(tài)水文模型[2?4]。同時，全流域的地學分析和模擬對計算性能提出了更高的要求。特別是處理規(guī)模擴大至大區(qū)域流域模擬時，數(shù)據(jù)密集計算問題凸顯[5]，這對面向計算密集的集群并行處理極具挑戰(zhàn)性。

針對大規(guī)模高分辨率、長歷時流域的分布式水文模擬計算的情況，若能從任務分解的角度將執(zhí)行控制和處理邏輯進行解耦則能更準確地模擬計算水文過程[6]。該過程將流域劃分為大量的模擬計算柵格任務，依據(jù)模擬任務計算間的依賴關系，基于DAG[7?9]調(diào)度的并行處理方法將這些計算任務分配到多個計算節(jié)點上。由于在DAG調(diào)度中，缺乏對任務密集特性及任務規(guī)模的考慮，任務調(diào)度和資源分配存在一定的盲目性。鑒于此，本文提出一種基于數(shù)據(jù)密集計算DAG調(diào)度及自適應資源協(xié)同分配的方法。

1 生態(tài)水文模擬計算并行化策略endprint

1.1 柵格任務的劃分與匯流網(wǎng)絡的構建

采用高分辨率的DEM地形分析提取流域數(shù)據(jù)，以確定的柵格任務計算單元離散化流域，同時，以確定的柵格任務計算單元間流向關系，在流域流向的基礎上，建立匯流網(wǎng)絡，如圖1所示。以此劃分出的柵格任務計算單元是后續(xù)計算過程的基本單元，充分考慮了空間的交互作用。

1.2 確定及求解側向水文模擬、匯流計算的方法

考慮側向水文過程主要為流域坡面匯流過程。在GIS支持下，采用逐柵格任務計算單元匯流的計算方法。為準確地描述徑流運動規(guī)律，本文采用改進的生態(tài)最優(yōu)性的定量刻畫時，采用水流物理運動為基礎的逐柵格匯流方法。由于每個柵格任務計算單元上游的來水和本柵格任務計算單元產(chǎn)水均對該柵格單元土壤水的影響變化起關鍵作用，因此給出每一個時間步長內(nèi)柵格單元的水量變化則更為合理。

在逐柵格涉及的坡面水流和河道水流的匯流計算中，采用運動波方程簡化圣維南方程組：

[?qs?x+?y?t=P-Qinf] （1）

[qs=αym] （2）

式中：[qs]為地表單寬流量（單位：[m3s-1]）；[P]為降雨量（單位：mm）；[Qinf]為下滲量（單位：mm）。于是可得：

[?y?t+α?ym?x=P-Qinf] （3）

對于運動波的數(shù)值解法采用主流的四點隱式有限差分方法來求解式（3），則：

[qj+1i+1-qj+1iΔt+qj+1i+1-qji+1Δt=（P-Qinf）ji] （4）

因此，不難看出柵格單元[t+1]時刻的水位取決于[t+1]時刻上游柵格來水和[t]時刻本柵格單元水位。對于一個柵格單元，只需知道其上游的入流，利用牛頓迭代法便可完成匯流計算，如此模擬整條流域。

1.3 構建流域柵格任務計算單元DAG

針對每條子流域，分別構建柵格任務計算單元依賴關系的DAG。具體實施如下：從流域出口的柵格任務計算單元開始，其次是追蹤上游匯入柵格任務計算單元，出口柵格任務計算單元作為父節(jié)點。直接上游柵格任務計算單元作為其子節(jié)點，以此類推，直到最上游沒有流向向內(nèi)的柵格任務計算單元為止，從而建立一個柵格任務計算單元相關的DAG，如圖2，表1所示。父節(jié)點任務計算單元的執(zhí)行依賴子節(jié)點的計算完成，追蹤樹的任何路徑需要按照從上游到下游的順序執(zhí)行。每一個柵格任務計算單元即將參與計算時，它的直接上流域柵格流量均是已知的。相比傳統(tǒng)的生態(tài)水文模擬，不同之處在于每一個柵格都將完成整個模擬時段內(nèi)生態(tài)水文過程計算，而且同層柵格任務計算單元是相互獨立的，只有存在依賴關系的柵格任務計算之間才進行隱式有限差分法的匯流計算。

2 生態(tài)水文模擬計算的DAG調(diào)度和自適應資

源協(xié)同分配

2.1 流域柵格任務DAG調(diào)度

如圖3所示，構建起的流域柵格任務DAG調(diào)度模型基本思想為：

（1） 利用高分辨率基于DEM地形分析方法提取流域數(shù)據(jù)，離散化流域柵格任務計算單元根據(jù)柵格流向數(shù)據(jù)文件建立柵格任務計算單元DAG。

（2） 考慮到大量任務間數(shù)據(jù)依賴關系，利用關鍵路徑確定DAG調(diào)度策略來明確任務執(zhí)行優(yōu)先級。

（3） 在柵格任務與資源映射中，考慮到資源性能與任務的數(shù)據(jù)密集程度，利用不平衡搜索算法評估負載狀況，結合模擬退火算法進行資源的自適應匹配。

2.2 任務優(yōu)先級的確定和資源分配策略

初始化柵格任務計算單元一致的優(yōu)先級，掃描柵格任務DAG以調(diào)整任務優(yōu)先級：葉節(jié)點具有最高執(zhí)行優(yōu)先級，同為葉節(jié)點時，結合任務高度、動態(tài)調(diào)整的關鍵路徑[10]來區(qū)分；任務高度的確定則以已完成任務的所有后續(xù)任務的實際執(zhí)行時間來重新計算，因此關鍵路徑也是在不斷調(diào)整當中。確定任務優(yōu)先級是為了確立任務狀態(tài)隊列，任務狀態(tài)隊列在這里分為運行、就緒和失敗三類。為了提升系統(tǒng)調(diào)度的有效性，對于失敗的任務，設置有限次數(shù)的任務重提。

目前DAG調(diào)度算法缺乏針對不同規(guī)模和數(shù)據(jù)密集程度的處理任務的多資源協(xié)同分配機制，且算法選擇上需權衡其復雜度與調(diào)度效果，而用粒子群或是遺傳算法優(yōu)化的DAG調(diào)度算法[11]效果較好，但調(diào)度復雜、控制繁瑣、開銷過大。鑒于此，在任務調(diào)度上采用基于關鍵路徑動態(tài)調(diào)整任務優(yōu)先級的MPI編程規(guī)范算法加以實現(xiàn)，通過使用異步不平衡搜索算法實現(xiàn)節(jié)點負載均衡，模擬退火算法用于任務和資源的協(xié)同匹配，最終使任務完成時間最少[12?13]。在資源管理器上，選用適合大量任務并發(fā)的PBS進行資源的分配，同時，實驗部分對比本地fork方法管理資源的性能。

3 實驗結果與分析

3.1 實驗硬件環(huán)境

選擇江西省鄱陽湖支流域作為實驗區(qū)，鄱陽湖位于江西省北部，北緯28°22′～29°45′，東經(jīng)115°47′～116°45′。流域面積為162 225平方千米。鄱陽湖屬北亞熱帶季風氣候，年均氣溫為16.5～17.8 ℃，年平均降水量為1 570 mm。每年4—9月為汛期，10月至次年3月為枯水期。選取支流域內(nèi)土地利用和植被、土壤類型單一的為實驗區(qū)，匯流參數(shù)主要是曼寧系數(shù)，采用默認值。實驗區(qū)包含該流域30 m，90 m和270 m分辨率下對應柵格的任務計算單元分別為289 756，51 653和7 156。實驗硬件環(huán)境如表2所示。實驗算法的評價標準有并行程序的加速比和效率，加速比是指串行運行時間和并行運行時間的比值，并行效率是指加速比和運行核數(shù)的比值。實驗結果均選取三次實驗取平均值的方式，對比不同分辨率下不同柵格任務計算單元間并行方法的性能。在資源調(diào)度上，對比PBS資源管理器和本地資源fork方法管理性能。

3.2 結果分析

不同分辨率的DEM地形分析提取流域數(shù)據(jù)時，分辨率越高數(shù)據(jù)越密集，劃分的柵格任務計算單元越多。在30 m，90 m和270 m分辨率下，實驗結果如表3所示，評價效果如圖4，圖5所示。在同一分辨率下，一定的柵格任務計算單元，隨著進程數(shù)不斷增加，并行效率逐漸減小。endprint

例如，在270 m分辨率下，本地資源管理器采用fork的自管理方法時，并行效率下降明顯；在進程量為4的情況下并行加速比為3.72；當進程量為64，128時，對應加速比只有26.3，47.1。這表明一方面并行算法能夠利用到多核的并行計算環(huán)境，另一方面，并行效率提升微弱。這主要是因為，對于低分辨率采集的流域數(shù)據(jù)任務量較少，并行程度低，用在調(diào)度上的開銷（進程的上下文切換）、進程間的通信以及其他的系統(tǒng)開銷占總的運行時間的比重大。

在不同的分辨率下，將流域劃分成不同數(shù)據(jù)密集程度計算任務時，越密集的計算任務具有更高的加速比。這極大的體現(xiàn)了基于任務分解的DAG調(diào)度方法的優(yōu)勢。此時，用于任務的調(diào)度開銷、進程間的通信和系統(tǒng)開銷相對于計算密集和數(shù)據(jù)密集的并行任務耗費時間比重下降明顯。因此，該方法具有更好的并行性能。

隨著任務規(guī)模的提升，數(shù)據(jù)密集、計算密集程度加劇，進程量成倍增加時，并行效率平穩(wěn)下降。這證明了并行程序具有高度的可擴展性。同規(guī)模的計算任務，并行效率的提升受進程的數(shù)量影響巨大。在大規(guī)模的并行任務中，可并行的任務線程量達到一定程度，消耗最多的資源是內(nèi)存，一旦內(nèi)存達到瓶頸，整個系統(tǒng)將面臨崩潰。對此，提供的自適應資源的分配策略就是限定資源池的最大量，進而約束最大并行線程量，同時根據(jù)內(nèi)存的耗費情況反饋給資源調(diào)度器以達到資源分配的自適應性，最終保證了系統(tǒng)的魯棒性。實驗對比了并行算法在PBS和本地自管理fork（）資源兩種情況下，采用PBS多任務并行調(diào)度，能將數(shù)以十萬級柵格任務并行效率提升18.8%～23.6%，特別是任務規(guī)模較小、并行進程量為128時，效率提升更加明顯。

4 結 論

本文針對計算密集和數(shù)據(jù)密集特征的任務依賴與并行處理的耦合度過高的情況，提出將關聯(lián)任務的執(zhí)行順序控制與并行算法的處理邏輯相分離。實驗中采用了多重對比的方法，在數(shù)據(jù)規(guī)模、進程數(shù)量以及本地資源管理器三個方面評估了該方法的性能，本文的并行算法在大規(guī)模并行任務計算當中表現(xiàn)出良好的魯棒性和擴展性。在并行效率方面，數(shù)以十萬級的并行任務，進程數(shù)量高達128時，并行效率在75%以上，較高限度地利用了多核計算環(huán)境，大幅度降低任務執(zhí)行時間。同時，配合多任務并行的資源管理器（PBS），實際并行效率能提高18.8%～23.6%。

參考文獻

[1] 徐宗學，程磊.分布式水文模型研究與應用進展[J].水利學報， 2010，41（9）：1009?1017.

[2] CHEN L J， ZHU A X， QIN C Z， et al. Review of eco?hydrological models of watershed scale [J]. Progress in geography， 2011， 30（5）： 535?544.

[3] CHEN L J. An optimality?based fully distributed watershed ecohydrological model [D]. Beijing： University of Chinese Academy of Sciences， 2012.

[4] 陳臘嬌.基于生態(tài)最優(yōu)性原理的全分布式流域生態(tài)水文模型[D].北京：中國科學院研究生院，2012.

[5] FURHT B， ESCALANTE A. Handbook of data intensive computing [M]. New York： Springer， 2011.

[6] 劉軍志，朱阿興，秦承志，等.分布式水文模型的并行計算研究進展[J].地理科學進展，2013，32（4）：538?547.

[7] LIU Fang， WANG Zhiyong. DAG?extended deletion algorithm in graphical abstract grid workflow model for remote sensing quantitative retrieval [C]// Proceedings of 2010 the 2nd International Conference on Education Technology and Computer. [S.l.]： IEEE， 2010： 369?373.

[8] CANON L C， JEANNOT E. Evaluation and optimization of the robustness of DAG schedules in heterogeneous environments [J]. IEEE transactions on parallel and distributed systems， 2010， 21（4）： 532?546.

[9] CHEN Jinlin. An updown directed acyclic graph approach for sequential pattern mining [J]. IEEE transactions on knowledge and data engineering， 2010， 22（7）： 913?928.

[10] 陳養(yǎng)平，王來熊，黃士坦.DAG任務模型的粒子群優(yōu)化調(diào)度算法[J].武漢大學學報，2007，40（2）：130?138.

[11] 張聰，沈惠璋.基于量子粒子群優(yōu)化的DAG并行任務調(diào)度研究[J].計算機應用研究，2010，27（7）：2459?2461.

[12] LUSK E L， PIEPER S C， BUTLER R M. More scalability， less pain： a simple programming model and its implementation for extreme computing [J]. SciDAC review， 2010， 17： 30?37.

[13] KIRKPATRICK S， GELATT C D， VECCHI M P. Optimization by simulated annealing [J]. Science， 1983， 220（4598）： 671?680.endprint