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

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

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

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

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

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

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

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

1.2 確定及求解側(cè)向水文模擬、匯流計(jì)算的方法

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

在逐柵格涉及的坡面水流和河道水流的匯流計(jì)算中，采用運(yùn)動(dòng)波方程簡(jiǎn)化圣維南方程組：

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

[qs=αym] （2）

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

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

對(duì)于運(yùn)動(dòng)波的數(shù)值解法采用主流的四點(diǎn)隱式有限差分方法來(lái)求解式（3），則：

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

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

1.3 構(gòu)建流域柵格任務(wù)計(jì)算單元DAG

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

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

源協(xié)同分配

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

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

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

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

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

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

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

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

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

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

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

3.2 結(jié)果分析

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

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

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

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

4 結(jié) 論

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

參考文獻(xiàn)

[1] 徐宗學(xué)，程磊.分布式水文模型研究與應(yīng)用進(jìn)展[J].水利學(xué)報(bào)， 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].北京：中國(guó)科學(xué)院研究生院，2012.

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

[6] 劉軍志，朱阿興，秦承志，等.分布式水文模型的并行計(jì)算研究進(jìn)展[J].地理科學(xué)進(jìn)展，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)平，王來(lái)熊，黃士坦.DAG任務(wù)模型的粒子群優(yōu)化調(diào)度算法[J].武漢大學(xué)學(xué)報(bào)，2007，40（2）：130?138.

[11] 張聰，沈惠璋.基于量子粒子群優(yōu)化的DAG并行任務(wù)調(diào)度研究[J].計(jì)算機(jī)應(yīng)用研究，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