负载均衡策略研究综述

负载均衡是最大化处理器利用率和提高并行计算效率的一个关键问题,而其发展相对滞后的软件成为影响并行计算应用发展的重要因素.本文给出负载均衡问题的一般性阐述,从算法理论和并行计算应用问题角度出发综述了现有负载均衡策略及其软件的研究成果.结合当前新兴并行体系结构和应用的发展趋势,分析并指出了下一步研究的问题和方向.     

基于网格计算的混合负载均衡策略

根据分布式系统的静态和动态负载均衡策略的优缺点,提出了在网格计算环境下的混合负载均衡策略.为了让网络中节点在网格计算环境中有效地执行需要大量计算的复杂任务,提出了用来评估节点效率的函数,并结合模拟实验证实了在此函数下算法的优越性.     

基于网格计算的混合负载均衡的改进策略

近年来,随着科学研究对计算资源的要求不断增加,结合分布式计算环境和互联网的网格计算已经得到越来越多研究者的关注。网格计算就是利用网络中的空闲计算资源来协助那些要求大量计算的复杂任务的执行。根据分布式系统的静态和动态负载均衡策略的优缺点,本文提出了在网格计算环境下的混合负载均衡策略。为了让网络中的节点在网格计算环境中有效地执行需要大量计算的复杂任务,并根据大量的实验总结,提出了新的用来评估节点效率的函数,较以前的函数执行效率有了提高。     

基于网格计算的自适应负载均衡策略研究

为了融合大量网络资源并有效地计算,解决网格计算中的负载均衡问题成为关键性的技术.论文提出了一种自适应负载均衡策略,采用了以静态为辅,动态自适应负载均衡算法为主的服务,可根据具体计算任务的情况,对任务重定向分配,提高了系统的伸缩性和响应时间,并采用基于CORBA体系机构的设计,在网格中间件层服务,灵活选择负载均衡算法,达到系统透明性.通过仿真模拟,证实了此策略的实用性和有效性.     

分布式控制平面: 并行BGP路由计算自适应负载均衡算法

下一代互联网高度可扩展支持服务动态部署.越来越多延时和抖动敏感服务(如IPTV、VoIP等)的应用对BGP路由计算的性能提出了更高的需求.路由器采用分布式控制平面和实现并行BGP路由计算克服集中控制平面的性能瓶颈是解决这个问题的有效途径.但现有并行BGP路由计算方案因负载均衡性能差影响了系统的并行性能.文中基于Hashing技术提出了并行BGP路由计算自适应负载均衡模型.通过在线统计路由更新设计了自适应负载均衡算法P-AP(Prediction-based Adaptive Partition),自适应地动态调整路由更新在处理节点间的分配.最后设计和实现了原型系统,并利用Route Views 收集的BGP Update数据进行实验.实验结果表明,P-AP算法具有负载均衡性能好、负载调整频率小和路由计算加速性能好等特点,能够有效地提高并行BGP路由计算性能.     

一种动态负载均衡机制的研究与实现

高性能集群工作方式越来越受到人们的关注。通常集群是一组通过网络连接的多个异构的计算机系统。在集群工作模式下,一个非常重要的问题就是要确保负载量的均衡。由于目前的负载均衡系统大多只支持同构集群环境,且均衡粒度为作业级,过于粗糙,所以不能很好的适用于并行程序中并行任务的均衡。本文提出了一种并行程序的开发框架,使用移动Agent技术解决任务的动态迁移性,为程序员提供了一个简单的开发接口,大大地简化了他们的工作。系统采用java和Aglet平台开发而成。实验表明,该系统灵活有效。     

负载均衡技术在并行化符号执行中的应用

动态符号执行在一定的并行算法下是可以并行化的,而且研究发现并行下的路径搜索任务之间没有偏序关系。并行化下的任务调度经常采用集中式策略,但传统的集中式策略由于任务分发的问题,易产生处理单元空闲等待的情况。基于以上分析,本文先采用任务队列缓冲区解决处理单元空闲等待的问题,其次,抓住并行任务无偏序关系的特点,无需考虑任务的执行优先级,只需用负载均衡技术保证各处理单元的工作负荷大致相等即可。实验证明,集中式策略的改进和负载均衡技术的使用显著提升了并行化符号执行的效率。     

基于非关系数据库的分布式负载均衡技术

在非关系数据库下的动态负载均衡算法中引入查询成本指标,通过分析历史查询日志来估计查询代价,并应用到负载均衡中的负载决策部分,使得负载排序更准确.同时对当前任务的查询代价进行估计,以找到合适的接受此任务的节点,从而使负载均衡变被动为主动,有效地缩短平均查询响应时间,提升系统的整体性能.     

基于剩余计算能力的动态负载均衡系统

基于剩余计算能力的动态负载均衡系统是一种基于新型负载向量的动态负载均衡系统。该系统使用一种新的负载评价指标：剩余计算能力,它兼顾节点的资源使用情况及节点本身的性能特征两个方面,更好地体现了集群系统的处理能力和系统正在处理的负载情况,比常用的其它负载向量更加灵活、准确。系统还将任务调度和进程迁移结合起来,以达到更有效的系统负载均衡,同时,也减小系统负载均衡带来的额外开销。     

一种用计算域分解的等几何分析并行化方法

提出一种按照计算域分解的并行化方法来构建等几何分析的刚度矩阵和右侧向量.将计算域分解成为若干个不相交的子区域,然后为每个区域分配一个处理器,所有处理器并行进行子区域上面的计算,所有处理器完成子区域的计算以后,使用一个快速的归并算法完成线性系统的装配.实验表明,本文提出的方法在8核的机器上可以达到6.46的加速比,能够在4秒左右的时间计算680万个矩阵元素个数.使用Intel MKL稀疏求解器来求解线性系统,本文的等几何分析求解器能够在大约10秒的时间内求解52万的自由度,本文的方法比ISOGAT速度要快上万倍.     

分区计算问题的并行设计

５１．引言 在许多重要研究领域中,数值模拟相当复杂,数值模拟的结果依赖于数值方法的选取,计算网络的质量,边界处理等,其复杂性表现在物理特性、数学模型、计算区域不规则的几何形状等方面．当计算区域各部分的物理特性不同而且差异较大时,比如多种物质的流体运动流场中各个部分变化程度不均匀,有些部分变化非常平缓,有些部分变化极其剧烈;或者,当计算区域极其不规则时,比如空气动力学中的进气道系统的流场计算,绕复杂形状流场的数值分析等．若在计算区域上作整体计算,不仅难以准确地描述流场变化,而且受到计算机运算速度、…     

基于有效并行求解策略的显式有限元分析并行算法

针对大规模结构非线性动力问题的有限元分析非常耗时,基于消息传递接口（MPI）机群环境,提出多种基于并行求解策略的显式有限元并行算法。基于显式消息传递的区域分解技术,采取重叠、非重叠区域分解技术及动态任务分配方法,通过将计算与通信重叠,优化处理器间的通信,对非重叠通信区域分解并行算法、重叠通信区域分解并行算法、群动态任务分配算法、动态任务分配算法及动态负载平衡算法进行研究。为在机群环境下实现非线性动力有限元分析,开发了基于有效并行求解策略的显式有限元并行算法。编写了基于消息传递编程模式的并行有限元程序,在工作站机群上实现了数值算例,分析了算法的性能,并与传统的Newmark算法进行了比较。算例表明：群动态任务分配算法的性能优于动态任务分配算法,低于区域分解算法的性能,动态负载平衡算法最优。对相同规模的问题提出的算法比Newmark算法快,优于Newmark算法。对结构非线性动力问题的有限元分析,所提出的并行算法是可行有效的。     

PC Cluster实现三维叠前深度偏移并行计算的负载平衡策略

运用用集群式并行机结构的软硬件特点,进行波动方程三维叠前深度偏移,已成为加速其庞大计算的有效工具。而集群式并行机节点之间的负载平衡,则是制约并行计算算法加速比的关键问题。文中提出运用堆排充算法以动态分配各节点计算任务,并以频率域共炮集波动方程三维叠前深度偏移并行算法为例,展示负载平衡的实现过程,测试结果表明,文中提出的负载平衡并行算法具有良好的加速比及并行效率。     

NEPTUNE:并行三维全电磁粒子模拟软件

为求解具有复杂几何的高功率微波电磁场问题,本文研制了一个三维全电磁粒子并行软件NEPTUNE。本文介绍了该并行软件的基本结构和采用的一些并行算法。目前,该软件已经成功模拟了多种高功率源器件,并可扩展到数千台处理器核上运行。     

三维变分资料同化系统并行算法设计与实现

三维变分资料同化作为现在主流数值天气预报的同化方法,能够明显改善预报数据的质量.随着科学研究的逐渐深入以及科学探测仪器和计算机技术的不断发展,受计算量和内存需求量的限制,传统串行三维变分资料同化系统已无法满足高分辨率、高精确度数值预报的要求.所以,三维变分资料同化系统的并行设计与实现显得尤其重要.本文设计了混合二维区域剖分并行化方法及其通信算法库,并将其应用于国家气象局三维变分同化系统3DVAR.数值试验表明,系统128核的并行效率相对于2核高达72％,具有良好的加速效果;同时,内存需求也随处理器个数的增加而成倍减少,满足了高分辨率预报的要求.     

气象资料三维变分同化阶段区域分解并行实现

变分同化由于能明显改善同化质量,正在成为数值天气预报的主流同化方法．研究三维变分同化的并行计算,提出了三维变分同化的阶段区域分解、观测资料的自适应划分算法、计算与通信重叠的矩阵转置和周边区域通信以及文件I／O方法,在此基础上实现了MPI并行三维变分原型系统,在由8个双CPU节点组成的Linux机群上并行加速比达到了11．9．     

分布式并行计算在交通网络仿真中的应用*

根据交通网络仿真的并行特征采用域分解方法设计交通并行仿真系统的框架,把交通网络分为几个子网,集群系统的每个节点机分别负责其中的一个子网,提出基于车辆数负载的网络分割算法来平衡各子网的负载量,并分析子网之间的通信机理.同时,在基于MPI 的并行计算平台上实现设计的并行仿真系统.通过实例表明,提出的并行算法能大大提高交通网络仿真的速度和效率.     

基于改进图划分的异构并行计算模型设计

为了实现大规模计算机集群上的高效分布式并行计算,设计了一种基于改进图划分和量子遗传算法的异构节点并行计算模型;首先,介绍了传统图划分模型并分析了其不足,然后从图的有向性、通信开销计算和负载均衡度等方面对传统的图划分模型进行了改进,从而得到一个改进的图划分模型;最后,以最小化通信开销和优化资源负载均衡为目标,通过设计编码方案,在改进的图划分模型上提出了采用量子遗传算法获取最优任务划分方案的最优解;仿真实验表明:文中方法能有效实现任务的并行计算,与其它方法相比,具有较小的通信开销和较好的负载均衡度,具有很强的可行性。