云中面向圖像并行計算的數(shù)據(jù)分布策略

祝家鈺，肖 丹，鄒 洋

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

0 引 言

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

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

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

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

1 系統(tǒng)模型及分析

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

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

圖1 系統(tǒng)模型

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

（1）主節(jié)點通過網(wǎng)絡接收到用戶請求。

（2）主節(jié)點根據(jù)數(shù)據(jù)分布策略將計算數(shù)據(jù)分布到從節(jié)點上。

（3）各從節(jié)點接收命令及數(shù)據(jù)，在本地執(zhí)行計算。

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

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

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

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

2 按性能比率進行數(shù)據(jù)分布的策略 （PDDS）

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

2.1 性能比率

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

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

在分布式系統(tǒng)中，網(wǎng)絡帶寬也是評價節(jié)點性能

的一個重要標準，數(shù)據(jù)傳輸花費直接影響系統(tǒng)對任務的響應時間。因此，對節(jié)點i定義性能函數(shù)

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

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

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

2.2 數(shù)據(jù)分發(fā)的順序

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

（1）總工作數(shù)據(jù)量根據(jù)n個從節(jié)點的PR 性能進行劃分。

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

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

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

2.3 PDDS算法

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

主節(jié)點模塊：

（1）初始化。

（2）計算所有從節(jié)點的性能比。

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

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

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

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

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

（8）完成。

從節(jié)點模塊：

（1）接收來自主節(jié)點的數(shù)據(jù)。

（2）在本地進行數(shù)據(jù)計算。

（3）發(fā)送結果給主節(jié)點。

不失一般性的，在該算法中，假定主節(jié)點不參與數(shù)據(jù)的處理。

2.4 實 例

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

（1）主節(jié)點N0進行初始化工作。

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

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

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

（5）主節(jié)點首先向N1發(fā)送數(shù)據(jù)，因為N1到主節(jié)點的鏈路L1帶寬最寬，其次是N3，最后N2。

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

（8）主節(jié)點完成收尾工作。

3 仿真實驗

3.1 系統(tǒng)建立和實驗方法

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

圖2 系統(tǒng)實例

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

圖3 節(jié)點性能比率

3.2 實驗結果及分析

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

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

圖4 算法執(zhí)行時間比較

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

圖5 不同節(jié)點數(shù)目下的系統(tǒng)響應時間

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

4 結束語

圖6 數(shù)據(jù)分發(fā)順序對系統(tǒng)響應時間的影響

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

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

［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，F(xiàn)AN Jizhang，et al.Remote sensing image parallel processing based on grid environment［J］.Microcomputer Information，2010，25 （5）：5－6（in Chinese）.［張旭晴，陳圣波，范繼璋，等.基于網(wǎng)格環(huán)境的遙感圖像并行處理 ［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）. ［陳康，鄭緯民.云計算：系統(tǒng) 實 例 與 研 究 現(xiàn) 狀 ［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.］