基于移动代理的异构计算中的负载平衡研究

摘要

课题基于移动代理对异构计算的负载平衡问题做了一些研究.首先对移动代理的特点、优势及形式化作了阐述,与其它模型作了比较,并对其性能进行了分析.随后的研究内容包括:利用移动代理对机器的负载状态进行动态监控、基于移动代理改进MPI并行程序的负载平衡、基于移动代理的并行计算框架、移动代理的负载平衡过程的数学分析、负载平衡的算法和策略、动态期望调度算法以及利用遗传算法增强移动代理的调度能力等.负载监控是负载平衡模型中的一个重要组成部分,为负载平衡决策提供基础.多数负载监控是为同构的计算环境设计的,不能满足异构计算的需要.或者是针对特定的异构环境,开发难度大,扩展性和移植性差.为了基于移动代理研究异构计算环境的负载平衡的目的,我们提出了基于移动代理进行负载监控.该方法能够简化程序的开发难度,降低网络的开销,动态检测异构计算环境中各节点的负载状况,为负载平衡提供了基础.在异构计算环境下编程通常利用像PVM、MPI这样的消息传递库.基于这些库的并行程序由一组互相通信的进程或线程组成.要想有效使用异构计算系统,需要程序员在各计算机间均匀分配并行任务,而且,他还要考虑背景负载这样的动态因素.由于在MPI环境中缺少负载平衡机制,很可能会使某些已经很忙的机器超载,导致性能恶化.如果MPI并行任务能有选择地在轻载机器上运行,排除重载机器,将会提高系统的性能.我们提出了一个基于移动代理的方法改进MPI并行程序的负载平衡.在基于移动代理负载监控的基础上,获得系统中各个机器的负载信息,将其中负载较轻的节点找出来构成一个子集群,这样就可把MPI并行任务调度到该子集群中的机器上执行,从而加快并行程序的运行.由于用PVM和MPI开发的并行程序在异构计算系统中不能无缝移植,如要在各计算机上进行显式编译,以便在其上运行;在某计算机系统上编译时,源程序可能需要修改;缺乏任务调度和负载平衡机制等,使得人们试图寻求新的方法解决这些问题.由于移动代理能够沿异构网络移动,在到达的节点上执行任务,它们自主决定所采取的行动,因此能够根据负载的变化选择适当的机器以完成其操作,从而在必要的移动后可以使整个系统达到一个平衡状态.我们设计了基于移动代理模型的并行计算框架,以简化并行程序的开发,对移动代理的负载平衡过程进行了数学分析,提出了一些负载平衡策略,使移动代理能够适应异构集群系统中负载的变化,提高资源利用率,改善应用程序的性能.提出了一个网络计算系统的动态期望调度算法,该算法可以加快作业的执行,提高系统的吞吐量.并给出了该算法在移动代理系统中的实现,用实验验证了算法的性能.