云環境下的一種并行任務劃分方法研究

牛偉偉 張千

摘 要： 并行任務劃分一直是高性能計算的研究重點。結合地震資料數據處理的應用云環境，以任務運行時間估計模型作為優化目標函數，提出了一種改進的粒子群優化算法，用以解決地震資料任務劃分問題。仿真實驗證明，改進后的算法增強了全局搜索能力，提高了收斂速度和收斂精度，有效提高了云環境下任務的執行效率。

關鍵詞： 云計算； 地震資料數據處理； 任務劃分； 粒子群優化算法； 全局最優

中圖分類號：TP393 文獻標志碼：A 文章編號：1006-8228（2014）06-15-04

0 引言

任務劃分是實現程序并行化的基礎，任務劃分策略的好壞直接影響到負載平衡性、通信復雜度、任務間的依賴性以及任務間的同步方式等。在并行計算中常用的任務劃分方法是基于任務圖劃分的方法[1]，但這種方式也存在不足之處，例如對語句的并行性分析過細，導致對任務劃分過于復雜。因此，本文結合地震資料處理云處理平臺，以任務運行時間估計模型作為優化目標函數，提出了一種改進的粒子群優化算法來解決地震資料數據劃分問題。

1 任務劃分條件

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

⑴ 基于共炮集并行劃分作業的處理方式具有一定的優點，如在具體劃分過程中，可以將一炮數據劃分為一個子任務，數據量較大時也可以將幾炮數據劃為一個子任務，同時這樣劃分后各個子任務之間的耦合程度非常低，所以這種方式的作業劃分類似于批作業松耦合并行調度。

⑵ 云計算節點劃分時，結合模糊聚類中“物以類聚”的思想，將計算存儲等性能相差不大的節點歸為一類，讓每個作業隊列面對一個自治的節點區域，該種處理方式能夠結合作業大小的劃分，體現出高性能節點處理復雜任務，低性能節點處理簡單任務的優勢。

⑶ 劃分完地震資料數據后，可采用基于HDFS的共享分布式存儲方式，通過這種方式，所有子任務的數據都通過NameNode集中式管理，在具體的任務執行開始，作業服務器會初始的數據進行按隊列與資源節點匹配程度分發，將要處理的任務分配到數據存在的節點執行，這樣在任務執行過程可以減少網絡通信要求，任務結束后再從各處理結點返回處理結果到共享存儲結點，進行結果的合并處理。這種存儲方式能夠顯著提高處理海量數據時系統的整體效率。

2 任務劃分策略

由于地震數據資料具有粗粒度、松耦合的并行化特點，數據之間聯系較少，因此不適合用基于圖劃分工具的任務劃分方法[9]，并且云計算環境的廣域性和動態性決定了任務劃分要受到諸多因素的影響，對于可分任務，對其分解策略要視環境而定。根據資源的負載能力進行合理的劃分，如果粒度劃分太細，網速傳輸及任務啟動等消耗太大，而如果粒度太大就不能充分利用現有的計算資源。因此，云環境下的任務劃分可以歸結為優化問題，本文以任務運行時間估計模型作為優化目標函數，采用了一種改進的粒子群優化算法對任務進行優化劃分。

2.1 任務運行時間模型

如圖1所示，根據云資源節點信息對數據塊進行預處理，將處理后的任務裝載到活動池，活動與服務映射程序從活動池取活動執行映射，在活動執行過程中對主數據塊進行處理。在預處理階段對前驅數據PWD進行劃分，然后將數據進行分解加入到活動池中，分解過程可能要附加額外數據，所以，在分解過程中引入膨脹因子inf，并且inf≥1。

預處理過程中用到的資源屬性參數定義如下。

2.2 改進的粒子群優化算法

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

綜上所述，云環境下使用改進的粒子群算法，進行地震數據資料任務劃分的步驟如下：

① 對總數據快進行預處理，劃分PWD數據塊；

② 對PWD數據劃分，把劃分后的活動壓入到活動池中等待處理；

③ 對主數據MainD進行劃分。

選擇最大迭代次數Nmax和閾值ξ；

3 實驗結果與性能分析

3.1 實驗設計

采用標準測試函數Schaffers F6函數[11]來分析和測試該改進算法的性能，如下所示：

此函數只有一個全局最大值點f（0，0）=1，在全局最大值周圍有一圈極值點，均值為0.990283。為了和原粒子群算法公平比較，兩種算法在同樣的實驗環境下運行，采用下面三種測試方法。

TEST 1：測試算法在達到預設的最大迭代次數時的最優值。針對基準函數測試10次，然后取最優解的平均，目的是比較改進的算法與原算法的尋優結果。

TEST 2：測試算法在達到預設的運算精度的耗時。目的是比較兩個算法的收斂速度。針對函數每次測試10次，然后取平均。

TEST 3：測試改進后算法對任務調度性能的影響。測試用例采用了100×1000和1000×1000的矩陣相乘，采用改進后算法將任務進行分解，然后采用FCFS算法進行任務的調度，測試運行的時間。

3.2 實驗結果及分析

TEST 1和TEST 2的測試結果如表1和表2所示，由于篇幅原因只列出5次測試的結果。通過分析表1和表2中的數據，我們歸納為以下兩點。

⑴ 當迭代次數固定為2000次時，表1中經典粒子群算法所得到的解的平均值為0.9909125，表2中改進的粒子群算法的解的平均值為0.9937346。由此可知，在相同迭代次數的情況下，改進的粒子群算法比經典粒子群算法尋優能力更強，求出的最優解更精確。

4 結束語

本文結合地震資料數據處理，研究了云環境下的任務劃分問題，對于可分任務，對其分解策略要視環境而定。根據資源的負載能力進行合理的劃分，如果粒度的太細，網速傳輸、任務啟動等消耗太大；而如果粒度太大，又不能充分地利用現有的計算資源。因此結合地震資料任務粗粒度、松耦合的并行化特點，提出了一種改進的粒子群優化算法進行任務優化劃分。

實驗結果表明，改進后的算法收斂速度更快，達到了提高整體任務執行效率的目的。下一步的研究是如何實現更為復雜的數據處理與調度工作。

參考文獻：

[1] 郝水俠，曾國蓀，譚一鳴等.一種基于DAG圖的異構可重構任務劃分方法[J].同濟大學學報（自然科學版），2011.39（11）：1693-1698

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

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

[4] 王宏琳.基于網絡的地震數據處理—從集群計算系統到云計算系統[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].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任務圖的一種調度算法[J].小型微型計算機系統，2003.24（10）：1796-1799

[10] 李民，蔣慕蓉，肖清，高毅.云計算中的簡單任務劃分方法[J].云南大學學報（自然科學版），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