運(yùn)用蒙特卡洛模擬法的數(shù)據(jù)流調(diào)度優(yōu)化模型研究?

施 健 孟慶強(qiáng) 呂順利

（南瑞集團(tuán)公司（國網(wǎng)電力科學(xué)研究院） 南京 210024）

1 引言

隨著信息通信技術(shù)的高速發(fā)展，特別是泛在物聯(lián)網(wǎng)技術(shù)的普及應(yīng)用，時(shí)時(shí)刻刻產(chǎn)生著海量、實(shí)時(shí)的數(shù)據(jù)流，面對這些“無限”運(yùn)動著的數(shù)據(jù)，需要進(jìn)行在線且精確的計(jì)算和分類，從而能夠及時(shí)挖掘出其中隱含的有價(jià)值信息［1～3］。在云計(jì)算為代表的分布式流計(jì)算系統(tǒng)中，不僅包含了海量的靜態(tài)、離線、結(jié)構(gòu)化的數(shù)據(jù)，還有實(shí)時(shí)傳輸、持續(xù)生成的非結(jié)構(gòu)化數(shù)據(jù)。為滿足多任務(wù)并行處理的復(fù)雜計(jì)算需要，在分布式流計(jì)算系統(tǒng)中，將進(jìn)行計(jì)算的海量數(shù)據(jù)切分成若干個(gè)小塊數(shù)據(jù)流后交由多臺計(jì)算機(jī)并行處理，并將局部計(jì)算結(jié)果整合得出最終結(jié)果。針對輸入的同組數(shù)據(jù)流，其采用的調(diào)度算法不同，最終的計(jì)算效率差異非常大。

在傳統(tǒng)的分布式處理模式中，輸入的大多是靜態(tài)數(shù)據(jù)，在利用有向無環(huán)圖DAG（Directed Acyclic Graph）表示并行數(shù)據(jù)流在多處理機(jī)上進(jìn)行任務(wù)調(diào)度時(shí)，其任務(wù)的執(zhí)行時(shí)間是可預(yù)知的。由于分布式流計(jì)算系統(tǒng)中輸入的是“無限"運(yùn)動著的數(shù)據(jù)，而且這些數(shù)據(jù)的大小也是不確定的。這種不確定性的存在，使得傳統(tǒng)的經(jīng)典靜態(tài)流據(jù)流調(diào)度方法將不再完全適用［4～5］。

本文提出一種運(yùn)用蒙特卡洛模擬法的數(shù)據(jù)流任務(wù)調(diào)度方法，該方法利用隨機(jī)數(shù)生成算法，在一定約束條件下大量模擬生成任務(wù)執(zhí)行時(shí)間，通過經(jīng)典的靜態(tài)調(diào)度算法（HEFT）產(chǎn)生相應(yīng)的預(yù)調(diào)度方案，經(jīng)過綜合比較最終得到一種最優(yōu)的預(yù)調(diào)度方案。實(shí)驗(yàn)結(jié)果表明：本文提出的方法不僅大大縮短了任務(wù)的調(diào)度時(shí)間，而且具有非常強(qiáng)的通用性。

2 靜態(tài)調(diào)度算法HEFT基本原理

異構(gòu)計(jì)算最早完成時(shí)間（Heterogeneous Earli?est Finish Time，HEFT）算法［6］作為一種經(jīng)典的針對異構(gòu)計(jì)算資源的列表啟發(fā)式靜態(tài)數(shù)據(jù)流調(diào)度算法，目前已經(jīng)得到廣泛認(rèn)可。

其主要思想分為兩個(gè)階段，第一階段是任務(wù)優(yōu)先級別的確定，根據(jù)任務(wù)的執(zhí)行時(shí)間以及與后繼任務(wù)的數(shù)據(jù)傳輸時(shí)間計(jì)算得到這個(gè)任務(wù)優(yōu)先級別，并根據(jù)優(yōu)先級別排序。第二個(gè)階段是處理器的選擇，根據(jù)第一個(gè)階段得到的任務(wù)排序，選取未被調(diào)度的任務(wù)中優(yōu)先級最高的任務(wù)，然后遍歷所有可用資源，查找到能夠最早完成處理該任務(wù)的計(jì)算資源，并將該任務(wù)分配到資源上相應(yīng)的空閑時(shí)隙中。

HEFT算法在每一階段都會選擇向上權(quán)值rank最大的任務(wù)，并把選擇出的任務(wù)分配給處理機(jī)，采用把任務(wù)插入到處理機(jī)空閑處的方法盡量減小最早完成時(shí)間。HEFT算法流程步驟見圖1。

圖1 HEFT算法流程圖

但在分布式流計(jì)算系統(tǒng)中，輸入源為實(shí)時(shí)動態(tài)的數(shù)據(jù)流，且數(shù)據(jù)量大小也是隨機(jī)的，因此，HEFT算法在實(shí)際應(yīng)用環(huán)境中，實(shí)驗(yàn)結(jié)果與預(yù)期結(jié)果差距較大。

3 基于蒙特卡洛模擬的改進(jìn)算法

蒙特卡洛模擬MCS（Monte Carlo Simulation）方法［7～10］的核心思想是利用隨機(jī)數(shù)，通過大量的隨機(jī)取樣實(shí)驗(yàn)來趨近數(shù)據(jù)的真實(shí)值，它已成為當(dāng)前解決統(tǒng)計(jì)推斷中模型擬合及優(yōu)化問題的一種有效可行方法。本文提出利用蒙特卡洛模擬法，常采用反復(fù)的隨機(jī)抽樣來獲得大量的隨機(jī)樣本，并通過計(jì)算所獲得樣本的結(jié)果來預(yù)測最優(yōu)的預(yù)調(diào)度方案。

3.1 改進(jìn)算法模型

設(shè)G=(N ，E ) 表示一組由節(jié)點(diǎn)N和一組邊E組成的DAG有向無環(huán)圖，形式都為(i →j) ，其中i，j∈N。節(jié)點(diǎn)i表示對應(yīng)的任務(wù)，邊i→j表示任務(wù)i和j之間任務(wù)間的依賴關(guān)系。G在處理機(jī)集合R上被調(diào)度，相應(yīng)的改進(jìn)算法流程如下：

1）定義輸入空間：MCS的輸入空間l是一組隨機(jī)生成各任務(wù)在各處理機(jī)上執(zhí)行時(shí)間的集合。定義如下：

其中，ETi，p表示任務(wù)i在處理機(jī) p上的確切執(zhí)行時(shí)間。

2）隨機(jī)抽樣：針對輸入空間lg中每個(gè)隨機(jī)生成的任務(wù)執(zhí)行時(shí)間進(jìn)行抽樣，得到樣本函數(shù)，表示為fsmp(lg)：

其中，ti，p是從 ETi，p中抽取的一個(gè)隨機(jī)樣本。

3）隨機(jī)任務(wù)執(zhí)行時(shí)間的均值：lg中每個(gè)具體任務(wù)在相應(yīng)處理機(jī)上執(zhí)行時(shí)間的平均值，其定義如下：

其中，μi，p為 ETi，p的期望值。

4）生成預(yù)調(diào)度方案：采用HEFT啟發(fā)式靜態(tài)調(diào)度算法對樣本進(jìn)行處理，得到一種靜態(tài)預(yù)調(diào)度方案Ωg，定義如下：

選擇預(yù)調(diào)度方案：每次從輸入空間lg中隨機(jī)抽取一樣本，依次計(jì)算每種靜態(tài)預(yù)調(diào)度方案Ωg的完工時(shí)間。

最后計(jì)算每種預(yù)調(diào)度方案的多個(gè)完工時(shí)間平均值，選出平均值最小的預(yù)調(diào)度方案。

改進(jìn)算法實(shí)現(xiàn)

基于蒙特卡洛模擬的改進(jìn)算法框架如下：

輸入：帶有隨機(jī)生成任務(wù)執(zhí)行時(shí)間lg集合的DAG應(yīng)用g。

輸出：最優(yōu)預(yù)調(diào)度方案Ωg。

1）創(chuàng)建一個(gè)空的預(yù)調(diào)度方案列表L；

2）應(yīng)用HEFT調(diào)度算法進(jìn)行處理，得出平均預(yù)調(diào)度方案，并存入到L；

3）生成階段：While不滿足生成階段的終止條件（重復(fù)m次），repeat；

4）在lg中取一個(gè)隨機(jī)生成的任務(wù)執(zhí)行時(shí)間樣本 pg，其中包含g中各任務(wù)在不同處理機(jī)上執(zhí)行時(shí)間的一組隨機(jī)值；

5）應(yīng)用啟發(fā)式靜態(tài)調(diào)度算法HEFT對任務(wù)執(zhí)行時(shí)間樣本 pg進(jìn)行處理，最終生成相應(yīng)的一種預(yù)調(diào)度方案Ωg；

6）把預(yù)調(diào)度方案Ωg存入L中，為后續(xù)計(jì)算最優(yōu)平均完工時(shí)間做準(zhǔn)備；

7）End While（每循環(huán)一次，就在lg中隨機(jī)抽取一個(gè)新的樣本 pg）；

8）選擇階段：for每一次循環(huán)（重復(fù)執(zhí)行n次），do；

9）在lg中取一個(gè)隨機(jī)生成的任務(wù)執(zhí)行時(shí)間樣本，其中包含lg中各任務(wù)在不同處理機(jī)上執(zhí)行時(shí)間的一組隨機(jī)值；

10）for針對L中存入的每一種預(yù)調(diào)度方案Ωg，do；

12）End for（L中每一種預(yù)調(diào)度方案采用的任務(wù)執(zhí)行時(shí)間都是一樣的，即都為）；

13）End fo（rL中每一種預(yù)調(diào)度方案都得到了n個(gè)不同的完工時(shí)間）；

14）經(jīng)過選擇階段的循環(huán)計(jì)算后，對L中每一種預(yù)調(diào)度方案Ωg的 n個(gè)不同完工時(shí)間值求平均

MCS算法的復(fù)雜性完全依賴于生成階段的啟發(fā)式調(diào)度算法復(fù)雜度和選擇階段計(jì)算完工時(shí)間的算法復(fù)雜度。設(shè)帶權(quán)任務(wù)有向無環(huán)圖DAG，有節(jié)點(diǎn)v和邊e，其在處理機(jī)P上被調(diào)度，則生成階段和選擇階段重復(fù)的次度分別假定為常數(shù)m和n。生成階段由于采用了HEFT算法，因此此階段的算法復(fù)雜度為O(e p m )；選擇階段的算法復(fù)雜度為O(e n)。改進(jìn)后的算法復(fù)雜度為O(e pm+en)。值，并把這個(gè)平均值作為平均完工時(shí)間；

15）Return取出擁有最小平均完工時(shí)間的預(yù)調(diào)度方案Ωg，作為最終要輸甩出的調(diào)度方案；

16）end。

3.2 算法復(fù)雜度分析

4 算法驗(yàn)證與比較

為驗(yàn)證改進(jìn)后算法的可行性，對HEFT算法和MCS算法進(jìn)行了DAG調(diào)度的仿真。本文采用一個(gè)帶有12個(gè)任務(wù)的典型DAG進(jìn)行測試。圖2展示出了DAG的結(jié)構(gòu)和在兩個(gè)相互依賴的任務(wù)之間進(jìn)行傳輸?shù)臄?shù)據(jù)的大小。

圖2 DAG拓?fù)鋱D

實(shí)驗(yàn)采用3臺異構(gòu)處理機(jī)，利用高斯分布（Gaussian distribution）分布建模隨機(jī)生成任務(wù)執(zhí)行時(shí)間，表1給出了每個(gè)隨機(jī)任務(wù)執(zhí)行時(shí)間的平均值μ，且隨機(jī)變量設(shè)定在[ ]0.5μ，1.5μ 內(nèi)，其標(biāo)準(zhǔn)偏差為0.167μ。

表2給出3臺異構(gòu)處理機(jī)之間的數(shù)據(jù)傳輸速率。

為驗(yàn)證改進(jìn)后算法的性能，在生成階段循環(huán)的重復(fù)次數(shù)為1000次，在選擇階段循環(huán)的重復(fù)次數(shù)為30次，且DAG啟發(fā)式調(diào)度算法采用HEFT算法。

表1 三個(gè)異構(gòu)處理機(jī)上各任務(wù)執(zhí)行時(shí)間

表2 處理機(jī)間的傳輸率

圖3為采用改進(jìn)后算法得到的最優(yōu)調(diào)度方案和采用傳統(tǒng)HEFT算法得到調(diào)度方案?？梢姡诖说湫偷腄AG圖中，改進(jìn)后算法的完工時(shí)間遠(yuǎn)小于傳統(tǒng)HEFT算法的完工時(shí)間，性能提升在10%左右（改進(jìn)后算法的調(diào)度完工時(shí)間約為163.5s，HEFT算法的調(diào)度完工時(shí)間約為181.5s）。

圖3 兩種算法得到的調(diào)度方案

實(shí)驗(yàn)結(jié)果表明此仿真的DAG圖中，在靜態(tài)啟發(fā)式調(diào)度HEFT算法的基礎(chǔ)上運(yùn)用蒙特卡洛模擬改進(jìn)算法，其結(jié)果優(yōu)于只使用HEFT算法得到的靜態(tài)調(diào)度方案。

5 結(jié)語

本文對傳統(tǒng)的啟發(fā)式靜態(tài)調(diào)度HEFT算法進(jìn)行了分析與研究，針對HEFT算法中存在的任務(wù)執(zhí)行時(shí)間不確定性的問題，借鑒了Monte Carlo方法，改進(jìn)后的算法在任務(wù)執(zhí)行時(shí)間隨機(jī)變化的情況下，獲得一種性能較為優(yōu)秀的平均完工時(shí)間調(diào)度方案。雖然改進(jìn)后的算法其任務(wù)調(diào)度過程相對復(fù)雜，但相對那些在每個(gè)處理機(jī)上的每個(gè)任務(wù)執(zhí)行時(shí)間預(yù)測值確定后才能進(jìn)行啟發(fā)式靜態(tài)調(diào)度的算法而言，其具有較大的性能提升。

通過仿真環(huán)境對傳統(tǒng)的HEFT算法和改進(jìn)后的算法進(jìn)行驗(yàn)證，實(shí)驗(yàn)結(jié)果表明改進(jìn)后的算法能夠獲得一個(gè)較優(yōu)的靜態(tài)預(yù)調(diào)度方案，并且在任務(wù)執(zhí)行時(shí)間預(yù)測值不準(zhǔn)確的情況下運(yùn)用改進(jìn)后的算法，并沒有產(chǎn)生過多的時(shí)間成本。在生成階段沒有太多隨機(jī)抽樣的情況下，也能找到一個(gè)好的調(diào)度方案，并且在選擇階段只需要進(jìn)行很少數(shù)的隨機(jī)抽樣就能選出最佳的調(diào)度方案。

為使得調(diào)度算法能夠具有較好地適用性，后續(xù)研究工作中應(yīng)采用更多種不同類型的DAG進(jìn)行進(jìn)一步的優(yōu)化甚至改進(jìn)，同時(shí)，對蒙特卡洛模擬生成的隨機(jī)數(shù)也可嘗試采用更多種的概率分布為任務(wù)執(zhí)行時(shí)間建模。

［1］Babeoek B，Babu S，Datar M．Models and Issues in Data Stream Systems［M］.In：Proc ofthe 21stACM SIGACT-SIGMOD-SIGART.New York： ACM Press，2002：1-16.

［2］WILHELM K，Evangelia K.Balancing load in stream pro?cessing with the cloud［C］//International Conference on Data Engineering，2011：16-21.

［3］ALFRED J，et al.A stream processing system simulator［C］//Workshop on Principles of Advanced and Distribut?ed Simulation，2010：97-105.

［4］HIROAKI S，et al.An adaptive high-availability scheme for distributed stream processing systems［C］//IEEE Inter?national Conference on Mobile Data Management，2010：413-418.

［5］NAZARIO C.Exploiting constraints to build a flexible and extensible data stream processing middleware［C］//Pro?ceedings of the 2010 IEEE International Symposium on Parallel and Distributed Processing，2010：356-359.

［6］H.Topcuoglu，S.Hariri，M.Wu，Performance-effective and low-complexity task scheduling for heterogeneous computing［J］.IEEE Trans.Parallel Distrib.Syst，2002，13（3）：260-274.

［7］丁明，李生虎，黃凱.基于蒙特卡羅模擬的概率潮流計(jì)算［J］.電網(wǎng)技術(shù)，2001（11）：10-14.DING Ming，LI Shenghu，HUANG Kai.Probabilistic load flow analysis based on Monte-Carlo simulation［J］.Power System Technology，2001，25（11）：10-14.

［8］劉煒，李群湛，唐兵，等.基于蒙特卡洛模擬的城市軌道概率潮流分析［J］.西南交通大學(xué)學(xué)報(bào)，2010，45（4）：561-567.LIU Wei，LI Qunzhan，TANG Bing，et al.Probabilistic Load Flow for Urban Rail Traction Power Supply Based on Monte Carlo Simulation［J］.Journal of Southwest Jiaotong University，2010，45（4）：561-567.

［9］Zhongming Y，Edward L，Yuen K H，et al.Probabilistic characterization of current harmonics of electrical traction power supply system by analytic method［J］.Iecon Pro?ceedings，1999，1：360-366.

［10］Rodrigues A B，Silva M G D.Probabilistic Assessment of Available Transfer Capability Based on Monte Carlo Method With Sequential Simulation［J］.Power Systems IEEE Transactions on，2007，22（1）：484-492.