云中面向圖像并行計算的數據分布策略

祝家鈺，肖 丹，鄒 洋

（重慶郵電大學 計算機科學與技術學院，重慶400065）

0 引 言

云計算是一種典型的分布式、并行計算模式［1］，這種模式大大減少了計算任務的執行時間。與依賴一些大型中央處理設備的系統不同，云計算系統由大量在不同地域上分布的計算機構成一個計算池，以較低的代價在動態、不可靠的網絡環境中提供大容量和高性能的計算服務。

云計算系統中，通常把一項任務需要被計算的數據分成多塊，分發到多個計算機節點上進行并行計算，從而獲得較高的執行速度。然而云中節點都是異構的，具有不同的CPU速率、存儲能力和傳輸能力等。對同一個計算任務，不同的節點耗時是不同的。因此，云計算中的數據分發布局策略是相當關鍵重要的，不合理的數據分布會影響系統整體的任務響應時間。如何設計計算任務的數據分布算法，以提高數據處理效率，并使云中各節點負載均衡，是一個挑戰性的研究課題［2］。

隨著科學技術的高速發展，許多大規模工程和科學計算問題都對計算速度提出了越來越高的要求。例如圖像并行處理［3］。它是一種綜合的數字信息處理技術，是大數據量數字圖像在計算機計算領域中的一項需長遠發展的技術，其主要目的是實現圖像處理的實時性和快速性。隨著圖像分辨率的提高，每一景圖像的數據量增加，計算量也相應增加。圖像數據的存儲具有相關性和規律性，其算法也具有鄰域性、一致性的特點，適合分布式并行計算。因此圖像處理越來越多地在云計算平臺上進行，數據處理速度需要不斷地提高。但專門針對面向云的分布式集群環境圖像并行計算的數據分布研究相對較少。

針對以上問題，提出一種基于云計算系統的、適用于圖像并行計算的按節點性能比率進行數據分布的策略。該策略通過建立性能函數，將節點CPU速率、存儲能力和傳輸能力等參數進行歸一后，再計算節點間的性能比率，根據性能比率進行任務數據量的分布；并依據鏈路帶寬制定數據發送的順序。

1 系統模型及分析

本系統采用主從 （Master／Slave）類型的云計算系統結構［4］。目前的云存儲系統基本都采用該結構，包括Google的 GFS［5］、Amazon的s3［6］和 Yahooy采用的 HDFS［7］等。主控數據服務器節點 （以下簡稱主節點）負責從節點性能測試與整個系統數據及任務消息的發送與處理結果的回收。

本系統建立的模型包括一個主節點和多個從節點。用星狀圖表示，如圖1所示。G＝ ｛N0，N1，…，Nn｝，其中N0是負責數據分布的主節點，N1，…，Nn是從節點。此外，主節點和從節點Ni.間存在虛擬的傳輸鏈接Li。

圖1 系統模型

在云中執行一項計算任務順序如下：

（1）主節點通過網絡接收到用戶請求。

（2）主節點根據數據分布策略將計算數據分布到從節點上。

（3）各從節點接收命令及數據，在本地執行計算。

（4）主節點收集各從節點的計算結果綜合后并返回給用戶。

以上過程均要消耗時間，表示如下，TTUS：用戶請求傳輸到主節點的時間。TTSNi：主節點傳輸數據到節點Ni的時間。CTNi：節點i執行數據處理的時間TTNi.S：節點i傳輸結果到主節點的時間。TTSU：主節點向用戶遞交結果的時間。

那么，從用戶發出請求到得到處理結果，總需花費的時間是

式中：TTUS和TTSU是由網絡速度決定的，很難改變。節點i上傳結果的TTNi.S基本不可控。但TTSNi.與主節點為該從節點分配的數據量有很大關系；而CTNi由從節點計算能力決定。因此我們主要關注這兩方面，通過建立函數模型估算節點性能，并計算節點間的性能比，為性能好的節點分布較多計算數據來最終減少任務響應時間。

2 按性能比率進行數據分布的策略 （PDDS）

根據每個從節點的性能和傳輸鏈路狀態，提出一種云平臺上針對圖像并行計算的數據分布策略。本節首先闡述性能比率的概念，然后基于性能比率引出該策略。并用一個實例來說明。

2.1 性能比率

根據所有從節點的性能比率來劃分負載。因此本策略的有效性依賴于對性能比率估算的準確性。在引入性能比之前，先探討云系統中的節點計算力［8］，用節點i完成特定數據量處理的耗時來衡量。與該節點的CPU頻率，總線速度，I／O速度及內存容量，CPU核的個數相關?？捎玫仁奖硎緸?/p>

式中：Data——待處理的數據量，fi——節點i的CPU頻率，vbi——總線速度，mi、vioi、Numi——內存容量，IO速度和CPU核的個數。節點i對應的Ti值越小，表示該節點的計算能力越大。

在分布式系統中，網絡帶寬也是評價節點性能

的一個重要標準，數據傳輸花費直接影響系統對任務的響應時間。因此，對節點i定義性能函數

這里Pi，1＝＜i＝＜M，是性能函數中的一個參數。代表節點的CPU速度，網絡帶寬，內存容量等。在本文中，PFi定義為

式中：SN——所有從節點集合。Ti——節點i執行某個計算任務的時間。Bi——從節點i和主節點間的鏈路帶寬。W1——第一項的權重，W2是第二項的權重。

性能比PR定義為每個從節點性能函數值的比率。例如，設有3個從節點N1，N2和N3，其PR即PF1：PF2：PF3是1／3∶1／2∶1／6，即3個節點的性能比是2∶3∶1。換句話說，如果計算任務的數據量是6個單位，那么其中2個會分布給N1，3個分布給N2，1個分布給N3。

2.2 數據分發的順序

主節點向從節點分布工作量需要兩個步驟：

（1）總工作數據量根據n個從節點的PR 性能進行劃分。

（2）檢測各鏈路帶寬值，按照鏈路帶寬從大到小的順序依次占用相應鏈路傳輸數據。

假設三條鏈路，L1，L2和L3，分別對應從節點N1，N2和N3到主節點的鏈路。其中L2帶寬最寬，L1次之，L3帶寬最小。那么主節點首先占用L2向N2發送數據，其次是N1，最后是向N3。

在實際運用中，Bj的估算可以利用NWS（network weather service）系統，即網絡氣象服務［9］。NWS利用一套高性能的分布式傳感器 （網絡監視器，CPU監視器等）收集系統狀態信息，可以反饋節點負載，網絡帶寬等信息。被廣泛使用在分布式系統，以實現動態的資源性能檢測。

2.3 PDDS算法

本算法應用在主從節點類型的云計算平臺中，分為兩個模塊。在主節點模塊，待處理的數據被分割成多個子集，根據從節點間的性能比率，分布到各從節點上。性能最好的節點獲得的數據量最多，反之亦然。從節點模塊負責數據的計算。該算法描述如下：

主節點模塊：

（1）初始化。

（2）計算所有從節點的性能比。

（3）根據性能比將計算任務總數據量劃分成多份。

（4）獲得主節點到從節點i的鏈路帶寬Bi。

（5）根據各鏈路帶寬，主節點以Bi非遞增順序依次占用各鏈路發送數據到相應從節點，各從節點獲得的數據量由性能比決定。

（6）主節點搜集所有從節點的計算結果。

（7）將結果返回給客戶。

（8）完成。

從節點模塊：

（1）接收來自主節點的數據。

（2）在本地進行數據計算。

（3）發送結果給主節點。

不失一般性的，在該算法中，假定主節點不參與數據的處理。

2.4 實 例

利用圖2進一步說明主模塊算法。

（1）主節點N0進行初始化工作。

（2）通過等式 （4）得到3個從節點的PR值，假設為2∶3∶1。

（3）待處理的總數據量以2∶3∶1的比例被劃分為6份。其中，兩份數據分發給N1；3份分發給N2；1份分發給N3。

（4）利用NWS服務，獲得L1～L3鏈路的帶寬比B1∶B2∶B3，設為3∶1∶2。

（5）主節點首先向N1發送數據，因為N1到主節點的鏈路L1帶寬最寬，其次是N3，最后N2。

（6）主節點收集來自從節點的計算結果。（7）主節點輸出結果。

（8）主節點完成收尾工作。

3 仿真實驗

3.1 系統建立和實驗方法

從以上分析可以得知，本數據分布策略與節點性能和鏈路狀況密切相關。本文實驗對云計算仿真平臺Cloud－Sim［10－11］進行了擴展，模擬實驗環境包括9臺PC機，1臺作為主節點，對數據進行分布控制，其余8臺作為從節點。

圖2 系統實例

在實驗中，數據被預先存放在主服務器節點上。依照主模塊中的算法向各從節點分布數據。節點計算力和性能比的計算均和第2節中描述的一致。此外，w1設為1.5，w2設為0.8。由于是實驗模擬，因此節點i的Ti和節點i到主節點鏈路的Bi的值均事先設定好。得到從節點性能比率見圖3。圖3中橫坐標表示節點編號，縱坐標是其對應的性能函數值PFi。

圖3 節點性能比率

3.2 實驗結果及分析

為了驗證本文數據分布策略的性能在同類算法中的優劣，設計了兩種數據分布算法對比試驗：“Eq＿ds”算法和“cpu＿ds”算法?！癊q＿ds”表示平均地分布數據量到從節點的算法；“cpu＿ds”表示以CPU速率比來分布數據量；PDDS是本文策略。在主節點模塊，對從節點性能比和鏈路帶寬計算完成后，即分別按照這3種策略進行數據分布。本實驗中的圖像并行計算是把數字圖像數據量按系統中從節點的數目和性能比率進行劃分 （任務粒度），主節點采用鏈路帶寬遞減的順序將數據分發給各個從節點，由每個從節點按要求完成規定的圖像計算任務，各從節點把處理后的結果數據送回主節點進行組合，然后提取這整個過程的處理時間，以此模擬圖像并行處理。

設置總數據量以分解后的計算任務總數來衡量［12］。這里每個子任務對應的計算數據量都是相同的。分別為20，60和100個，分別應用這3種算法進行數據分布后，獲取圖像并行計算任務響應時間。實驗結果如圖4所示。結果表明，PDDS數據分布算法能夠使任務響應時間最短。從該實驗可以看出，鏈路帶寬是衡量一個從節點計算性能的重要因素，“Eq＿ds”算法和 “cpu＿ds”算法是兩種靜態的數據分布算法，沒有考慮鏈路帶寬因素，因此不能適應實際網絡狀況。本文中的PDDS算法因為結合了網絡帶寬，減少了數據傳輸時間花費，所以能較好地適應網絡環境。而 “cpu＿ds”算法性能表現最差，是因為它只考慮了節點CPU速率這一個參數，而CPU速度并不是衡量節點計算機性能［13］的唯一因素。

圖4 算法執行時間比較

從圖5可以看出，各種分布策略在不同從節點數量下的反應時間差別較明顯，隨著從節點數目的增加，采用PDDS數據分布策略，得到的圖像并行計算響應時間線性下降，明顯優于其他分布策略。原因在于該算法充分考慮了節點性能差異，使處理能力強的節點能者多勞，且分布數據時利用了鏈路帶寬因素，從而提高了系統響應效率。

圖5 不同節點數目下的系統響應時間

圖6是數據發送順序影響系統響應時間的測試結果。分別測試數據計算任務總數為20，60和1003種情況下的系統對任務的完成時間。本文提出的PDDS算法采用2.2節所敘述的按照鏈路帶寬遞減的順序依次占用相應鏈路進行數據分發。并與其他兩種數據分發順序進行對比：一種名為 “INC＿DS”，與PDDS數據分發順序相反，按照鏈路帶寬遞增的順序依次占用相應鏈路進行數據分發；另一種名為 “RAND＿DS”，采用任意順序分發數據。結果如圖所示，PDDS算法使系統對計算任務的響應時間縮短，要優于其他兩種算法。這是因為減少了所有從節點等待計算任務的時間。

4 結束語

圖6 數據分發順序對系統響應時間的影響

根據圖像數據存儲的規律性和相關性，以及云計算中數據分布存儲的特點，本文提出了一種面向圖像并行處理的數據分布策略。該策略為了均衡系統中各計算節點的負載，依據節點的處理能力和鏈路帶寬狀況進行不同數據量的分布；并結合網絡帶寬來決定數據傳送的順序，最終達到降低系統響應時間、提高系統性能的目的。經過實驗表明，本文的策略能明顯減少圖像并行計算時間，實施簡單并有效。

以后的工作是進行圖像并行計算以外的其他類型的應用，比如數據挖掘等來進一步測試本策略，并改進該策略。

［1］Hayes.Cloud－computing ［J］.Communications of the ACM，2008，51 （7）：9－11.

［2］CHEN Quan，DENG Qianni.Cloud computing and its key techniques ［J］.Journal of Computer Applications，2009，29（9）：2563－2566 （in Chinese）.［陳全，鄧倩妮.云計算及其關鍵技術 ［J］.計算機應用，2009，29 （9）：2563－2566.］

［3］ZHANG Xuqing，CHEN Shengbo，FAN Jizhang，et al.Remote sensing image parallel processing based on grid environment［J］.Microcomputer Information，2010，25 （5）：5－6（in Chinese）.［張旭晴，陳圣波，范繼璋，等.基于網格環境的遙感圖像并行處理 ［J］.微計算機信息，2010，25 （5）：5－6.］

［4］CHEN Kang，ZHENG Weimin.Cloud computing：System instances and current research ［J］.Journal of Software，2009，20 （5）：1337－1348 （in Chinese）. ［陳康，鄭緯民.云計算：系統 實 例 與 研 究 現 狀 ［J］.軟 件 學 報，2009，20 （5）：1337－1348.］

［5］CAI Jian，WANG Shumei.Cloud computing system instances based on Google ［J］.Computer Knowledge and Technology，2009，5 （25）：7093－7095 （in Chinese）. ［蔡鍵，王樹梅.基于Google的云計算實例分析 ［J］.電腦知識與技術，2009，5（25）：7093－7095.］

［6］Amazon.Amazon elastic compute cloud amazon EC2 ［EB／OL］.［2012－04－20］.http：／／aws.amazon.com／ec2／，2009／.

［7］Yahoo.Hadoop tutorial［EB／OL］.［2012－04－20］.http：／／publicyahoo.com／gogate／hadoop－tutorial／start－tutorial.html，2009／.

［8］ZENG Zhi，LIU Renyi，ZHANG Feng，et al.A policy of task allocation base on distributed cluster computing towards cloud ［J］.Science of Telecommunications，2010，24 （10）：30－33（in Chinese）.［曾志，劉仁義，張豐，等.面向云的分布式集群四叉樹任務分布策略 ［J］.電信科學，2010，24（10）：30－33.］

［9］Michiorri，Andrea.Forecasting real－time ratings for electricity distribution networks using weather forecast data ［C］／／20th International Conference and Exhibition，CI－RED，2009：1－4.

［10］Belalem G，Tayeb F Z，Zaoui W.Approachesto improve the resources management in the simulator CloudSim ［C］／／Proc of the First International Conference of Information Computing and Applications. Heidelberg：Springger Verlag Press，2010：189－196.

［11］Calheiros R N，Ranjan R，Beloglazov A，et al.CloudSim：A toolkit for modeling and simulation of cloud computing environments and evaluation of resource provisioning algorithms［J］.Software Practice ＆Experience，2011，41 （1）：23－50.

［12］Beloglazov，Anton Buyya，Rajkumar.Energy efficient resource management in virtualized cloud data centers ［C］／／10th IEEE／ACM International Conference，2010：826－828.

［13］ZHAO Bo.PageRank－based computer performance evaluation method ［J］.Computer Engineering，2010，36 （17）：286－288（in Chinese）.［趙波.基于PageRank的計算機性能評價方法 ［J］.計算機工程，2010，36 （17）：286－288.］