论文部分内容阅读
解决并行算法中的数据分配问题，目前采用的主要方法是在各个计算结点上平均分配数据。如果并行系统是同构的，采用这种方法设计的算法具有很高的运行效率。但是在异构系统下，由于各个计算结点的性能不同，平均分配数据集的方法就有可能导致系统的负载失衡。 本文提出了在并行算法中使用的基于移动agent的数据集负载均衡策略：基于移动Agent综合处理速度的数据集均衡策略DBSMAV(DataSet Balancing Strategy Based on Mobile Agent Velocity)和基于移动Agent调度的数据集均衡策略DBSMAS(DataSet Balancing Strategy Based on Mobile Agent Scheduling)。目前对如此细粒度的负载均衡问题所作的研究工作还很少，本文的工作借鉴了NASA所建立的IPG(Information Power Grid)网格上面的粗粒度负载均衡算法PLUM(Parallel Load balancing for Unstructured Meshes)、SBN(Symmetric Broadcast Network)、MinEX(Minimal Extra overhead)，也参考了接收者发起的分布式启发性算法，并结合了移动Agent的思想。 理论和实验证明，移动Agent综合处理速度MAV(Mobile Agent Velocity)在计算结点的内存足够大时能够比较准确地反映计算结点的计算能力。DBSMAV策略按照各个计算结点的MAV分配数据集，较好地克服了异构系统中平均分配数据集造成的失衡。为了解决由于内存的影响而导致的负载失衡现象，我们提出了DBSMAS策略。DBSMAS策略按照重负载优先调度和整体上减少系统执行时间的原则，命令一部分移动Agent携带数据集进行迁移，使系统重新达到了平衡状态。 实验证明，我们所研究的均衡策略，利用移动Agent的移动性，很好地解决了负载失衡问题，提高了程序的执行效率。较之于传统的算法，我们策略的特点是优先保证提高程序的执行速度(平衡负载的目的是为了提高并行算法的速度)，而不是优先保证系统的平衡。