一種自適應資源精細匹配的DAG調度方法

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

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

關鍵詞： DAG調度； 并行算法； 數據密集； 計算密集； 多資源匹配

中圖分類號： 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 引 言

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

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

1 生態水文模擬計算并行化策略endprint

1.1 柵格任務的劃分與匯流網絡的構建

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

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

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

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

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

[qs=αym] （2）

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

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

對于運動波的數值解法采用主流的四點隱式有限差分方法來求解式（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。具體實施如下：從流域出口的柵格任務計算單元開始，其次是追蹤上游匯入柵格任務計算單元，出口柵格任務計算單元作為父節點。直接上游柵格任務計算單元作為其子節點，以此類推，直到最上游沒有流向向內的柵格任務計算單元為止，從而建立一個柵格任務計算單元相關的DAG，如圖2，表1所示。父節點任務計算單元的執行依賴子節點的計算完成，追蹤樹的任何路徑需要按照從上游到下游的順序執行。每一個柵格任務計算單元即將參與計算時，它的直接上流域柵格流量均是已知的。相比傳統的生態水文模擬，不同之處在于每一個柵格都將完成整個模擬時段內生態水文過程計算，而且同層柵格任務計算單元是相互獨立的，只有存在依賴關系的柵格任務計算之間才進行隱式有限差分法的匯流計算。

2 生態水文模擬計算的DAG調度和自適應資

源協同分配

2.1 流域柵格任務DAG調度

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

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

（2） 考慮到大量任務間數據依賴關系，利用關鍵路徑確定DAG調度策略來明確任務執行優先級。

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

2.2 任務優先級的確定和資源分配策略

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

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

3 實驗結果與分析

3.1 實驗硬件環境

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

3.2 結果分析

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

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

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

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

4 結 論

本文針對計算密集和數據密集特征的任務依賴與并行處理的耦合度過高的情況，提出將關聯任務的執行順序控制與并行算法的處理邏輯相分離。實驗中采用了多重對比的方法，在數據規模、進程數量以及本地資源管理器三個方面評估了該方法的性能，本文的并行算法在大規模并行任務計算當中表現出良好的魯棒性和擴展性。在并行效率方面，數以十萬級的并行任務，進程數量高達128時，并行效率在75%以上，較高限度地利用了多核計算環境，大幅度降低任務執行時間。同時，配合多任務并行的資源管理器（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] 陳臘嬌.基于生態最優性原理的全分布式流域生態水文模型[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] 陳養平，王來熊，黃士坦.DAG任務模型的粒子群優化調度算法[J].武漢大學學報，2007，40（2）：130?138.

[11] 張聰，沈惠璋.基于量子粒子群優化的DAG并行任務調度研究[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