异构分布式系统中的负载均衡调度算法研究

摘要

随着社会的发展，经济的突飞猛进，为了促进社会和谐，地震灾变的预测也就越来越重要了。现代计算机技术的迅猛发展，包括地震灾变预测等越来越多的工程计算问题都依靠于大型高性能超级计算机来解决。而工程计算从一定程度上又驱动了高性能计算机的发展。目前，并行系统，网格计算等分布式技术已经成为解决工程问题的重要方法，而在分布式系统中，为了提高分布式系统的性能，调度问题成为了现代分布式系统中的一个热点问题。各种调度算法被大批的研究人员所提出，它们的调度优化目标不尽相同，但是总的来说都是为了改进分布式系统的性能。为此本文以任务调度的负载均衡为目标，对任务调度问题进行了深入的研究。
　　 首先，针对现在异构分布式系统的负载均衡问题，本文设计了一个改进的动态遗传算法IDGA(Improved Dynamic Genetic Algorithm)应用于异构分布式系统的调度器中，以此来优化异构分布式系统的负载均衡性能。考虑到传统的遗传算法在任务调度的应用中存在着最大进化代数有限的缺点，本文涉及了IDGA算法，克服了最大进化代数受限的缺点，并且在找到符合负载均衡标准的解以后，IDGA算法会按照一定的策略重新设置系统的负载均衡标准来试图找到比当前最优调度更好的调度。
　　 其次，由于IDGA算法可以动态设置最大进化代数，那么有可能引起遗传算法时间复杂度的增加，为了提高IDGA算法的效率，通过引入MapReduce分布式系统模型，将IDGA算法在MapReduce模型下并行化。
　　 最后，在IDGA算法的并行化过程中，提出了一个用来表示遗传算法初始种群的数据结构--二叉选择树，在利用这个数据结构对遗传算法进行选择操作的时候，可以提高选择操作的时间效率。该二叉选择树是一个平衡的二叉树，所以搜索的平均复杂度是O(10g n)，其中n代表种群的规模。而传统的遗传算法中，只能通过线性时间复杂度O(n)才能成功选择出一个个体。该二叉树的每个节点上都记录了该节点左子树的所有节点的适应度之和与右子树的所有节点的适应度之和。所以在决定选择左子树、右子树还是当前节点时可以通过产生一个随机数，并根据各自的适应度函数值来进行选择，这样明显提高了选择操作的效率。