云環(huán)境下的一種并行任務(wù)劃分方法研究

牛偉偉 張千

摘 要： 并行任務(wù)劃分一直是高性能計(jì)算的研究重點(diǎn)。結(jié)合地震資料數(shù)據(jù)處理的應(yīng)用云環(huán)境，以任務(wù)運(yùn)行時(shí)間估計(jì)模型作為優(yōu)化目標(biāo)函數(shù)，提出了一種改進(jìn)的粒子群優(yōu)化算法，用以解決地震資料任務(wù)劃分問(wèn)題。仿真實(shí)驗(yàn)證明，改進(jìn)后的算法增強(qiáng)了全局搜索能力，提高了收斂速度和收斂精度，有效提高了云環(huán)境下任務(wù)的執(zhí)行效率。

關(guān)鍵詞： 云計(jì)算； 地震資料數(shù)據(jù)處理； 任務(wù)劃分； 粒子群優(yōu)化算法； 全局最優(yōu)

中圖分類(lèi)號(hào)：TP393 文獻(xiàn)標(biāo)志碼：A 文章編號(hào)：1006-8228（2014）06-15-04

0 引言

任務(wù)劃分是實(shí)現(xiàn)程序并行化的基礎(chǔ)，任務(wù)劃分策略的好壞直接影響到負(fù)載平衡性、通信復(fù)雜度、任務(wù)間的依賴(lài)性以及任務(wù)間的同步方式等。在并行計(jì)算中常用的任務(wù)劃分方法是基于任務(wù)圖劃分的方法[1]，但這種方式也存在不足之處，例如對(duì)語(yǔ)句的并行性分析過(guò)細(xì)，導(dǎo)致對(duì)任務(wù)劃分過(guò)于復(fù)雜。因此，本文結(jié)合地震資料處理云處理平臺(tái)，以任務(wù)運(yùn)行時(shí)間估計(jì)模型作為優(yōu)化目標(biāo)函數(shù)，提出了一種改進(jìn)的粒子群優(yōu)化算法來(lái)解決地震資料數(shù)據(jù)劃分問(wèn)題。

1 任務(wù)劃分條件

地震資料數(shù)據(jù)要充分利用云節(jié)點(diǎn)進(jìn)行處理就必須對(duì)其進(jìn)行劃分。地震道是地震數(shù)據(jù)的基本單位[2]，本文采用的并行方式是把地震資料數(shù)據(jù)按炮點(diǎn)進(jìn)行并行化[3-4] ，基于炮點(diǎn)劃分的數(shù)據(jù)任務(wù)之間基本不需要通信，其先天的獨(dú)立性使其能夠更好地進(jìn)行并行計(jì)算。綜合上述地震數(shù)據(jù)資料的分析，考慮所搭建的云計(jì)算平臺(tái)的處理性能，將地震資料數(shù)據(jù)進(jìn)行作業(yè)劃分有幾個(gè)條件。

⑴ 基于共炮集并行劃分作業(yè)的處理方式具有一定的優(yōu)點(diǎn)，如在具體劃分過(guò)程中，可以將一炮數(shù)據(jù)劃分為一個(gè)子任務(wù)，數(shù)據(jù)量較大時(shí)也可以將幾炮數(shù)據(jù)劃為一個(gè)子任務(wù)，同時(shí)這樣劃分后各個(gè)子任務(wù)之間的耦合程度非常低，所以這種方式的作業(yè)劃分類(lèi)似于批作業(yè)松耦合并行調(diào)度。

⑵ 云計(jì)算節(jié)點(diǎn)劃分時(shí)，結(jié)合模糊聚類(lèi)中“物以類(lèi)聚”的思想，將計(jì)算存儲(chǔ)等性能相差不大的節(jié)點(diǎn)歸為一類(lèi)，讓每個(gè)作業(yè)隊(duì)列面對(duì)一個(gè)自治的節(jié)點(diǎn)區(qū)域，該種處理方式能夠結(jié)合作業(yè)大小的劃分，體現(xiàn)出高性能節(jié)點(diǎn)處理復(fù)雜任務(wù)，低性能節(jié)點(diǎn)處理簡(jiǎn)單任務(wù)的優(yōu)勢(shì)。

⑶ 劃分完地震資料數(shù)據(jù)后，可采用基于HDFS的共享分布式存儲(chǔ)方式，通過(guò)這種方式，所有子任務(wù)的數(shù)據(jù)都通過(guò)NameNode集中式管理，在具體的任務(wù)執(zhí)行開(kāi)始，作業(yè)服務(wù)器會(huì)初始的數(shù)據(jù)進(jìn)行按隊(duì)列與資源節(jié)點(diǎn)匹配程度分發(fā)，將要處理的任務(wù)分配到數(shù)據(jù)存在的節(jié)點(diǎn)執(zhí)行，這樣在任務(wù)執(zhí)行過(guò)程可以減少網(wǎng)絡(luò)通信要求，任務(wù)結(jié)束后再?gòu)母魈幚斫Y(jié)點(diǎn)返回處理結(jié)果到共享存儲(chǔ)結(jié)點(diǎn)，進(jìn)行結(jié)果的合并處理。這種存儲(chǔ)方式能夠顯著提高處理海量數(shù)據(jù)時(shí)系統(tǒng)的整體效率。

2 任務(wù)劃分策略

由于地震數(shù)據(jù)資料具有粗粒度、松耦合的并行化特點(diǎn)，數(shù)據(jù)之間聯(lián)系較少，因此不適合用基于圖劃分工具的任務(wù)劃分方法[9]，并且云計(jì)算環(huán)境的廣域性和動(dòng)態(tài)性決定了任務(wù)劃分要受到諸多因素的影響，對(duì)于可分任務(wù)，對(duì)其分解策略要視環(huán)境而定。根據(jù)資源的負(fù)載能力進(jìn)行合理的劃分，如果粒度劃分太細(xì)，網(wǎng)速傳輸及任務(wù)啟動(dòng)等消耗太大，而如果粒度太大就不能充分利用現(xiàn)有的計(jì)算資源。因此，云環(huán)境下的任務(wù)劃分可以歸結(jié)為優(yōu)化問(wèn)題，本文以任務(wù)運(yùn)行時(shí)間估計(jì)模型作為優(yōu)化目標(biāo)函數(shù)，采用了一種改進(jìn)的粒子群優(yōu)化算法對(duì)任務(wù)進(jìn)行優(yōu)化劃分。

2.1 任務(wù)運(yùn)行時(shí)間模型

如圖1所示，根據(jù)云資源節(jié)點(diǎn)信息對(duì)數(shù)據(jù)塊進(jìn)行預(yù)處理，將處理后的任務(wù)裝載到活動(dòng)池，活動(dòng)與服務(wù)映射程序從活動(dòng)池取活動(dòng)執(zhí)行映射，在活動(dòng)執(zhí)行過(guò)程中對(duì)主數(shù)據(jù)塊進(jìn)行處理。在預(yù)處理階段對(duì)前驅(qū)數(shù)據(jù)PWD進(jìn)行劃分，然后將數(shù)據(jù)進(jìn)行分解加入到活動(dòng)池中，分解過(guò)程可能要附加額外數(shù)據(jù)，所以，在分解過(guò)程中引入膨脹因子inf，并且inf≥1。

預(yù)處理過(guò)程中用到的資源屬性參數(shù)定義如下。

2.2 改進(jìn)的粒子群優(yōu)化算法

粒子在二維空間迭代過(guò)程如圖2所示，展示了該粒子從位置zk迭代到位置zk+1的過(guò)程，并反映了式⑸的迭代過(guò)程，圖2中v1是局部最優(yōu)值pbest導(dǎo)致的改變速度，vk是這一時(shí)刻此粒子所具有的速度，v3是改進(jìn)算法后加入的改變量，它使粒子更趨向于全局最優(yōu)解，v2是全局最優(yōu)值gbest引起的該粒子向gbest方向的改變速度，而速度v是使用經(jīng)典粒子群公式⑵所產(chǎn)生的改變后的速度，速度v是受vk，v1，v2共同影響下所產(chǎn)生的速度矢量，由此位置矢量改為zk+1，速度vk+1是采用公式⑷所改變的速度矢量，速度vk+1是受vk，v1，v2，v3的共同影響下所產(chǎn)生的速度矢量，由此產(chǎn)生的位置迭代為為zk+1。下一時(shí)刻，該粒子會(huì)從位置zk迭代到位置zk+1，經(jīng)歷如此迭代過(guò)程后，所有粒子將向全局最優(yōu)點(diǎn)靠近，最終達(dá)到精度要求的較優(yōu)解。

綜上所述，云環(huán)境下使用改進(jìn)的粒子群算法，進(jìn)行地震數(shù)據(jù)資料任務(wù)劃分的步驟如下：

① 對(duì)總數(shù)據(jù)快進(jìn)行預(yù)處理，劃分PWD數(shù)據(jù)塊；

② 對(duì)PWD數(shù)據(jù)劃分，把劃分后的活動(dòng)壓入到活動(dòng)池中等待處理；

③ 對(duì)主數(shù)據(jù)MainD進(jìn)行劃分。

選擇最大迭代次數(shù)Nmax和閾值ξ；

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

3.1 實(shí)驗(yàn)設(shè)計(jì)

采用標(biāo)準(zhǔn)測(cè)試函數(shù)Schaffers F6函數(shù)[11]來(lái)分析和測(cè)試該改進(jìn)算法的性能，如下所示：

此函數(shù)只有一個(gè)全局最大值點(diǎn)f（0，0）=1，在全局最大值周?chē)幸蝗O值點(diǎn)，均值為0.990283。為了和原粒子群算法公平比較，兩種算法在同樣的實(shí)驗(yàn)環(huán)境下運(yùn)行，采用下面三種測(cè)試方法。

TEST 1：測(cè)試算法在達(dá)到預(yù)設(shè)的最大迭代次數(shù)時(shí)的最優(yōu)值。針對(duì)基準(zhǔn)函數(shù)測(cè)試10次，然后取最優(yōu)解的平均，目的是比較改進(jìn)的算法與原算法的尋優(yōu)結(jié)果。

TEST 2：測(cè)試算法在達(dá)到預(yù)設(shè)的運(yùn)算精度的耗時(shí)。目的是比較兩個(gè)算法的收斂速度。針對(duì)函數(shù)每次測(cè)試10次，然后取平均。

TEST 3：測(cè)試改進(jìn)后算法對(duì)任務(wù)調(diào)度性能的影響。測(cè)試用例采用了100×1000和1000×1000的矩陣相乘，采用改進(jìn)后算法將任務(wù)進(jìn)行分解，然后采用FCFS算法進(jìn)行任務(wù)的調(diào)度，測(cè)試運(yùn)行的時(shí)間。

3.2 實(shí)驗(yàn)結(jié)果及分析

TEST 1和TEST 2的測(cè)試結(jié)果如表1和表2所示，由于篇幅原因只列出5次測(cè)試的結(jié)果。通過(guò)分析表1和表2中的數(shù)據(jù)，我們歸納為以下兩點(diǎn)。

⑴ 當(dāng)?shù)螖?shù)固定為2000次時(shí)，表1中經(jīng)典粒子群算法所得到的解的平均值為0.9909125，表2中改進(jìn)的粒子群算法的解的平均值為0.9937346。由此可知，在相同迭代次數(shù)的情況下，改進(jìn)的粒子群算法比經(jīng)典粒子群算法尋優(yōu)能力更強(qiáng)，求出的最優(yōu)解更精確。

4 結(jié)束語(yǔ)

本文結(jié)合地震資料數(shù)據(jù)處理，研究了云環(huán)境下的任務(wù)劃分問(wèn)題，對(duì)于可分任務(wù)，對(duì)其分解策略要視環(huán)境而定。根據(jù)資源的負(fù)載能力進(jìn)行合理的劃分，如果粒度的太細(xì)，網(wǎng)速傳輸、任務(wù)啟動(dòng)等消耗太大；而如果粒度太大，又不能充分地利用現(xiàn)有的計(jì)算資源。因此結(jié)合地震資料任務(wù)粗粒度、松耦合的并行化特點(diǎn)，提出了一種改進(jìn)的粒子群優(yōu)化算法進(jìn)行任務(wù)優(yōu)化劃分。

實(shí)驗(yàn)結(jié)果表明，改進(jìn)后的算法收斂速度更快，達(dá)到了提高整體任務(wù)執(zhí)行效率的目的。下一步的研究是如何實(shí)現(xiàn)更為復(fù)雜的數(shù)據(jù)處理與調(diào)度工作。

參考文獻(xiàn)：

[1] 郝水俠，曾國(guó)蓀，譚一鳴等.一種基于DAG圖的異構(gòu)可重構(gòu)任務(wù)劃分方法[J].同濟(jì)大學(xué)學(xué)報(bào)（自然科學(xué)版），2011.39（11）：1693-1698

[2] 趙長(zhǎng)海，晏海華，王宏琳，史曉華，王雷.面向地震數(shù)據(jù)處理的并行與分布式編程框架[J].石油地球物理勘探，2010.12（1）：146-155

[3] 李建江，舒繼武，王有新，王鼎興，鄭緯民.一種基于共享存儲(chǔ)的疊前深度偏移并行算法[J].軟件學(xué)報(bào)，2002.13（12）：2231-2236

[4] 王宏琳.基于網(wǎng)絡(luò)的地震數(shù)據(jù)處理—從集群計(jì)算系統(tǒng)到云計(jì)算系統(tǒng)[J].石油地球物理勘探，2003.38（4）：381-386

[5] Saaty T. Decision making with the analytic hierarchy process.International Journal of Services Sciences，2008.1：83-98

[6] 張偉哲，田志宏，張宏莉，何慧，劉文懋.虛擬計(jì)算環(huán)境中的多機(jī)群協(xié)同調(diào)度算法[J].Journal of Software，2007.18（8）：2027-2037

[7] Lech Kurowski， David Sussman， Investment Project Design： AGuide to Financial and Economic Analysis with Constraints[M]，2011：354

[8] Shufen Zhang， Shuai Zhang， Xuebin Chen， Shangzhuo Wu.Analysis and Research of Cloud Computing System Instance[J].2010 Second International Conference on Future Networks，2010.60：88-92

[9] 蔣廷耀，李慶華.DAG任務(wù)圖的一種調(diào)度算法[J].小型微型計(jì)算機(jī)系統(tǒng)，2003.24（10）：1796-1799

[10] 李民，蔣慕蓉，肖清，高毅.云計(jì)算中的簡(jiǎn)單任務(wù)劃分方法[J].云南大學(xué)學(xué)報(bào)（自然科學(xué)版），2007.29（S1）：59-63

[11] Jun Sun， Bin Feng， Wenbo XU. Particle Swarm Optimizationwith Particles Having Quantum Behavior[A].Proc 2004 Congress on Evolutionary Computation[C]，2004：325-331