云中面向图像并行计算的数据分布策略

祝家钰，肖 丹，邹 洋

（重庆邮电大学 计算机科学与技术学院，重庆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核的个数相关。可用等式表示为

式中：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”算法。“Eq＿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.］