云计算_算法
云计算(Cloud Computing)是一种新近提出的计算模式。是分布式计算(Distributed Computing )、并行计算(Parallel Computing)和网格计算(Grid Computing)的发展。 目前, 亚马逊、微软、谷歌、IBM 、英特尔等公司纷纷提出了/云计划0。例如亚马逊的AWS (AmazonWeb Services)、IBM 和谷歌联合进行的/蓝云0计划等。这对云计算的商业价值给予了巨大的肯定。同时学术界也纷纷对云计算进行深层次的研究。例如谷歌同华盛顿大学以及清华大学合作, 启动云计算学术合作计划(Academic Cloud Computing
Initiative ),推动云计算的普及, 加紧对云计算的研究。卡内基梅隆大学等对数据密集型的超级计算(Data Intensive Super Computing,DISC )进行研究,本质上也是对云计算相关技术开展研究。
IDC 的调查显示, 未来五年云计算服务将急速增长, 预期2012年市场规模可达420 亿美元。目前企业导入云计算已逐渐普及, 并且有逐年成长趋势。估计在2012年,企业投入在云计算服务的支出将占整体IT 成本的25%,甚至在2013年提高至IT 总支出的三分之
一。由此可见,在各大公司以及学术界的共同推动下, 云计算技术将会持续发展。 本文简要介绍了近2年国内发表的关于云计算环境下的算法研究的论文进展:
1、《基于云计算的数据库查询调度算法》
2010年4月,左利云等人发表了论文《基于云计算的数据库查询调度算法》,该文提出了一种相对比较适合云计算数据库的查询调度算法——CCRP 算法;该算法基于云计算数据库中数据存储的特点,在查询调度时先对数据应用连续读取特性,解决了其它算法在云计算中有部分系统资源闲置的问题,提高了查询效率. 仿真实验证实CCRP 算法在系统利用率和系统性能的表现均优于其他算法。该文核心内容如下:
1.1 云计算数据库查询调度算法
根据云计算数据库特点,研究发现可以应用云计算数据库查询调度的算法有批处理调度算法和基于计划的调度算法。批处理调度考虑内存与I/O的有效运用,相关查询尽量以批次一起执行,可节约不必要的I/O。但未考虑最大平行度与平衡负载,故选取的查询可能局限于部分节点执行而闲置部分资源且节点有不平衡负载。
基于计划的调度是将现有空闲节点计划查询调度。安排到足够节点的查询即可执行。若多个查询同时拥有所需节点, 则它们可同时执行。它发展出Largest-Fit-First (简称LFF )和First-Fit-First (简称FFF )两种算法。LFF 将待执行查询按所需节点数排升序,将使用较多节点的查询优先处理。而FFF 算法将先进入系统的查询优先处理。
研究证实对于海量数据的云计算数据库有计划地安排查询调度是必要且可行的。而基于计划的调度同批处理调度都会闲置系统资源。这对于拥有海量数据的云计算数据库是很致命的,为此著作结合基于计划调度算法的优点提出一种应用连续读取特性的查询调度算法——CCRP 算法。
1.2 CCRP算法描述
设一个云计算数据库系统中有7个待执行的查询及其所需处理节点如表1所示。如查询Q1须使用处理节点PN 1、PN 2与PN 6;Q 2必须使用处理节点PN 1与PN 4。
在保持查询对节点需求下,重组表1中行与列,使重组后具连续读取特性的排列方式,并与LFF 结合提出两种重组算法:节点需求最小查询优先(CCRPSF ),及处理节点需求最大的查询优先(CCRPLF )。CCRPSF 重组后如表2。将查询按其所需第一个节点出现的列分层级:Q 4与Q 6同属第1层;Q 1与Q 7所需第一个节点均在第三列,故Q 1与Q 7同属第3层;以此类推。将查询依处理节点需求数递增排序。CCRPLF 与其相反,将属同一层级的查询按所需处理节点数目递减排序。结合以上分析,CCRP 算法执行过程如图4所示。
1.3 结论
CCRP 算法着重于如何让每一批次的调度尽量占用全部或最多的处理节点数,以发挥最高的系统利用率,解决了其他算法在调度过程中闲置资源的致命问题,经实验证实该算法在系统利用率等方面表现要优于其他算法。
2、《基于云计算环境的蚁群优化计算资源分配算法》
2010年1月,华夏渝等人发表了论文《基于云计算环境的蚁群优化计算资源分配算法》,该文提出一种基于蚁群优化(Ant Colony Optimization)的计算资源分配算法。分配计算资源时,首先预测潜在可用节点的计算质量,然后根据云计算环境的特点,通过分析诸
如带宽占用、线路质量和响应时间等因素对分配的影响,利用蚁群优化算法得到一组最优的计算资源. 通过在Gridsim 环境下的仿真分析和比较,这种算法能够在满足云计算环境要求的前提下,获得比其他一些针对网格的分配算法更短的响应时间和更好的运行质量,因而更加适合于云环境。该文核心内容如下:
2.1计算资源的分配流程
参照Map/Reduce提出的云计算框架,云环境中的每个单元由一个单独的主作业调度节点(master Job Tracker)和该单元所辖各个节点集群中的一个从任务分配节点(slave Task Tracker )共同组成。主节点负责调度构成一个作业的所有任务,这些任务的数据资源分布在不同从节点的存储资源上的用户镜像分片中,主节点监控它们的执行,重新执行已经失败的任务,或者是做错误处理。从节点仅负责执行由主节点指派的任务。在接到主节点的指派之后,从节点开始为其下属的存储节点寻找合适的计算节点. 首先,该从节点开始检测自身的计算资源余量,如果其剩余计算资源足以满足用户提交作业的用量,则优先分配自身的计算资源,如果资源已经耗尽或者已不足以满足承诺给用户的最小计算资源量,则开始搜寻云环境中其他合适的计算资源。该研究介绍的蚁群分配算法将在这一环节中实现。搜索在一定范围内进行,目的是为了减小所带来的网络开销。如果仍然没有合适资源,则从节点报请主作业调度节点移走该节点集群中的用户数据镜像分片。
2.2计算资源优劣度评判条件
将slave 节点域看作是一个无向图G (V ,E ),其中V 是区域Area 中所有slave 节点的集,E 是连接各slave 节点的网络集合。寻找合适的计算节点,也就是在E 中的路径。e ∈Area ,其度量标准可以考虑如下几个因素:①预计执行时间:time_cost(e),指路径e 尽头的计算资源处理该作业间。②网络带宽:bandwidth(e),指路径e 所提供的网络最大带宽。③网络延迟:delay(e),指路径e 产生的最大网络延迟。
设资源选择的约束函数为
选择资源和路径的过程就是寻找满足限制条件(2)的尽量小的res(e)的路径和资源的过程,其中A ,B ,C 为三个约束条件的权重;TL ,EL 和DL 为其边界限制条件。不同的云计算环境可能会有不同的取值。
2.3对各个计算资源完成本次作业执行速度的预测
在云计算中,把任务分配给效率最高,开销最少的计算资源将会极大地提高整体的性能。所以,在分配中需要对潜在的可分配节点进行执行速度预估。
针对云计算异构和变化的特点,著者设计了一个通过积累历史值来推算下一任务执行速度的预测模型。该模型对每一个节点完成下一个工作的效率时间进行单独的预测,希望无论计算资源处在怎样的负载程度,都能凭借这个模型得到相对精确的预测. 由于每个计算节点当前的负载程度已知,并且上一次完成作业时的平均负载程度也能够查阅,所以,著者用如下模型来预测执行速度;
其中是指第m 号计算资源第k 次预测执行速度,单位可以为MIPS ,a k 为第k 次预测时的系统负载程度,指第m 号计算第k 次实际的执行速度,ρ是一个调节参数,用来在不同云环境中调节经验值和预测值的比重,以使该模型的预测达到最优。在每一个计算节点上,每完成一个作业,该节点自身将会记录本次作业完成的实际速度,并结合上次的预测结果来推算下次作业可能的执行速度。同时,系统负载a 被一并记录,这是一个重要的参数,一般可以有几个量化指标,比如CPU 的实际使用率、作业数或者线程数等。
2.4 结论
针对运营成本而言,云计算对网络环境的要求低于网格环境,而其提供的诸如SaaS 、PaaS 等服务内容却比网格对基础设施的要求更高,所以一个好的资源调度算法尤为重要。前述研究的蚁群资源分配算法能够针对云环境的大规模性、共享性和动态性等特点,动态地为用户的作业分片搜寻并分配计算资源。根据仿真结果,该算法能够有效地在云计算环境中完成计算资源搜索与分配的工作。
参考文献:
[1] 基于云计算的数据库查询调度算法 左利云; 吴良海 郑州大学学报(工学版) 2010(4)
[2] 基于云计算环境的蚁群优化计算资源分配算法 华夏渝; 郑骏; 胡文心 华东师范大学学报(自然科学版) 2010(1)
[3] 云计算及其关键技术 陈全; 邓倩妮 计算机应用 2009(9)