摘要:文章首先介绍了一种基于代理的网格资源管理分级模型;然后提出了一种负载均衡算法的设计思想,有效地提高了网格计算能力和资源利用率。
关键词:网格,代理,网格资源管理,负载均衡
1引言
网格是把分布在不同地理位置上的计算资源通过因特网整合成一台巨大的超级计算机,实现各种资源的全面共享。网格计算是跨管理域的分布式计算,其资源的分布性、动态性、异构性等,使得资源管理面临扩展性和伸缩性两大挑战。软件代理可以看作是模型化的复杂系统的高级抽象,展示高度的动态行为,协同应用与环境交互,完成给定的目标,很好地解决上述两个问题。
本文介绍了一种基于代理的网格资源管理分级模型,并在此模型上提出了一种负载均衡算法的设计思想。
2基于代理的网格资源管理模型
在基于代理的网格资源管理模型中,用户只需要将任务提交给资源请求代理;而代理的背后有多少个资源提供方,各个资源的性能和任务被分配到哪台处理机上执行等对于用户来说都是透明的。基于代理的网格资源模型通过一个管理本地网格资源的调度算法集成了性能预测技术,为资源调度提供实时依据。
2.1代理的分级体系模型
代理和被发布的计算资源构成一个分级的网状结构,包括若干个代理以及在这些代理注册的大量计算资源。计算资源可以选择某个代理进行注册,每个代理最终管理一组资源,响应用户的任务请求。由于可用带宽、主机性能等原因,一个代理接收到一个新的计算任务以后,如果自身负载过重,或者自身的可用资源难以满足新的计算任务的要求,就会根据负载均衡算法,通过ACP(AgentCommunicationProtoco1)把计算任务交给其他代理完成。
2.2基于代理的负载均衡算法
2.2.1负载均衡算法的思想
本文设计的负载均衡算法属于动态平衡算法,决策取决于系统当前的状态。算法思想是紧邻方法(NearestNeighborApproach),它假定并行处理系统是由多个结点按照一定的结构相互连接构成的并行处理网络,每个结点只能和与其直接连接的结点通信,计算负载也只能通过这些连接移动。在负载平衡过程中,每个结点只能与其周围的结点进行负载交换,通过多次循环迭代实现系统的负载平衡。
2.2.2负载均衡算法的设计
(1)把系统中的Agent按照从上到下、从左到右的方法进行顺序编号1~P,在Ai上注册代理管理的各个计算资源的计算负载为Lij,计算速度为Sij,如果该代理上注册了n个计算资源,我们将其编号为1~n。则该代理的计算负载Li为各个计算负载(Lij)总和;计算速度(Si)为各个资源计算速度(Sij)的加权平均,其中Wj为速度权值(根据各个计算资源的性能确定),计算时间为:
Ti=Li/Si(1)
则该模型中所有代理的计算负载可以表示为一个向量:L=(L1,L2,…,LP)。
(2)在(1)中已经按顺序编号的代理可以用图G=(V,E)来表示,其中V是代理,P是代理的数量,|V|=P;E是边,代表节点之间的通信连接。结点用Ai表示。同样,将边从1到|E|编号,使每个边也有惟一的序号与之对应,用ei表示,|E|是边的数量。我们把结点Ai及与其相邻的结点构成的子图称为负载域。
则G中与每个结点相邻的所有结点的负载和将构成一个矩阵为:
lA=ALT=(LA1',LA2',…,LAP')T
其中lAi'是与结点Ai相邻的所有结点的负载和。则G中各个负载域的总负载为:
LA=ALT+LT=(LA1,LA2,…,LAP)T(2)
其中LAi是结点Ai的负载域的总负载,A是G的邻接矩阵,其维数为|V|×|V|,其元素为aij(结点i和j邻接时,aij=1;结点i和j不邻接时,aij=0);
同时,结点Ai的负载域的计算速度为:
(3)由式(2)、(3)得,结点Ai的负载域的平均计算时间为:
TAi=LAi/SAi(4)
对于结点Ai的负载平衡问题,就归结为调整计算时间Ti和负载域平均计算时间TAi的问题。若定义结点Ai迁移的负载为:
бi=(Ti-TAi)*Si
则由式(4)得G中各结点的负载域计算时间的变化向量为:
T=(T1-TA1,T2-TA2,……,TP-TAP)(5)
(4)假设在G中结点间的每一条边都有一个方向,从序号大的处理结点指向序号小的结点,沿ei边的负载迁移量为δi,则计算负载迁移向量为:
δ=(δ1,δ2,δ3,……,δ|E|)(6)
要使结点负载域达到平衡,写成矩阵的形式为:
S-1MδT=TT(7)
其中S为对角矩阵,S=diag(S1,S2,……,SP),M是G的关联矩阵,其维数为|V|×|E|,其元素为aij(结点i与ej关联,i为起点时,aij=1;结点i与ej关联,j为起点时,aij=-1;结点i与ej不关联时,aij=0);由式(7)得出G中每条边的负载迁移向量δT,使各个代理结点平均计算时间为TT,从而实现负载平衡。对于给定的系统,已知S和M,测量出T,可通过式(7)求出δ。
2.2.3基于代理的负载均衡算法的优点
(1)灵活、有效:负载平衡要考虑多种因素,可以根据用户需要来调节权值,也可以由其它因素决定;由于算法允许多结点并发负载,所以系统的负载均衡不存在瓶颈的问题。
(2)透明:负载平衡的过程是在各代理之间自适应地进行,对用户来说是透明的。