论文部分内容阅读
异构计算作为高性能计算领域的研究热点之一，近年来受到了广泛的关注。异构计算是指利用一组异构的计算资源共同协作完成某一项任务，这不但满足了不同类型的应用，也开发利用了系统中各种资源的计算能力，从而使系统整体上具有较高的性能。异构计算对现在的高性能计算领域的诸多方面提出了挑战，其中的任务调度问题，对发挥系统的并行性能和保持负载平衡具有非常重要的意义。该问题已被证明是一个NP问题，无法在多项式时间内找到最优解，所以促使人们不懈地研究如何设计调度算法，在有限的时间里获得更好的解。许多启发式的算法被用来解决此类调度问题，例如遗传算法，模拟退火算法，禁忌算法等等。
遗传算法是一种全局概率搜索算法，其基本思想是模拟生物进化过程。由于遗传算法具有不受搜索空间的限制性假设的约束，不要求解空间有连续性、可导等性质，具有较好的全局寻优能力，且固有并行性。目前，遗传算法已经被广泛地应用于组合优化、机器学习、信号处理、自适应控制和人工生命等领域，它是现代有关智能计算中的关键技术之一。许多学者在将其应用到调度问题的优化上时发现，在处理调度优化问题上，遗传算法与其他的启发式算法相比，具有较大的优越性。
本文首先对异构计算环境中独立任务的调度问题进行了研究，独立任务调度问题是异构计算环境中一类特殊的问题，其特殊性主要体现在任务之间无直接的依赖关系，但仍需要合理的分配计算资源。本文以遗传算法为基础，针对独立任务调度问题的特殊性，提出了一种新的分段编码策略，在编码时将计算资源作为遗传操作的基本单元，以此为基础提出了新的区域杂交算子，以及段内和段间两种变异算子，同时将一种新的选择算子应用到独立任务调度问题当中去。模拟实验结果表明本文提出的杂交算子和变异算子能够使种群具有更好的多样性，算法具有较好的搜索能力。
随后，为解决异构计算环境下DAG任务调度问题，本文提出了一个基于遗传算法的混合调度算法。标准的遗传算法存在着搜索空间过大，收敛速度过慢，以及易陷入局部最优等缺点。为了弥补以上的缺点，文中引入了个体适应度使个体的杂交和变异概率自动的调整，引入种群适应度使参加变异和杂交的个体数量随着整体的平均适应度和最大适应度的比值自动的调整，这样可以避免早熟收敛和较低的收敛速度。同时，为改进整个算法的局部搜索能力，提出了一种基于模拟退火语义的接受准则，与传统的局部搜索相比，新接受准则引入了随机因素，较差的解也可以被接受。实验结果显示，本文提出的混合遗传算法不易于陷入局部最优，收敛速度较快。