论文部分内容阅读
异构多处理器系统由一组具有不同处理能力的处理器构成，任务调度成为改进系统性能的关键因素。如何合理地将任务分配给不同处理器，使整个系统性能达到最佳，是任务调度需要解决的问题。由于异构多处理器系统的异构性、灵活性和复杂性等特点，使得传统的调度算法面临新的挑战。因此，在分析现有调度算法的基础上提出一个好的调度算法，充分利用各种计算资源，尽可能提高异构多处理系统资源利用率和吞吐量，是一个重要而现实的问题。
粒子群优化算法是近年兴起的一种用于解决优化问题的启发式算法，具有自组织、自学习、自适应、多点并行及有指导的搜索等特点，被广泛用于解决各类NP问题和任务调度问题。已有仿真实验证明：在处理任务调度问题时，粒子群优化算法与传统调度算法相比更具优越性。
本文对异构多处理器系统的任务调度策略与调度算法进行了较为深入的研究，并在已有工作的基础上进行了探索和创新，取得了一定的成果。具体内容体现在如下几个方面：
(1)针对异构多处理器系统独立任务调度问题，本论文提出改进的粒子群优化算法。通过分析每个处理器的计算能力，建立异构多处理器系统独立任务的调度模型。在计算适应值函数时，本文对粒子的位置值进行取整运算，使粒子群优化算法更好的应用于离散空间。同时利用调整惯性权重的策略来提高全局收敛速度，克服粒子在迭代后期搜索性能下降的缺点。和局部粒子群优化算法、全局粒子群优化算法相比，仿真结果证明了本文提出的改进算法能在极短的时间内，获得较好的调度结果。
(2)针对异构多处理器系统DAG任务调度问题，本论文提出一种基于混合粒子群优化的任务调度算法。通过分析DAG任务模型特点建立异构多处理器任务调度的数学模型。为了使粒子群算法能更好的应用到离散领域，引入交换运算的概念，构造一种特殊的粒子群优化算法。同时加入爬山算法能够克服粒子群算法早熟收敛和局部搜索能力不足的缺陷，达到加速算法收敛，提高运行质量的效果。和遗传算法、基本粒子群算法相比，本文所提出的混合粒子群优化算法能够在更短的时间内得到较好的调度结果，特别适合应用较大规模的异构多处理器任务调度。
任务调度是NP完全问题，将粒子群优化算法应用于任务调度中，利用粒子群优化算法所具有的并行性和全局解空间搜索的特点，可以有效地缩短任务的完成时间，提高异构多处理器系统资源的使用效率。因此本论文的研究成果，对于推广粒子群优化算法的应用范围有一定的理论参考价值和实际应用价值。