论文部分内容阅读
网格技术能够把多种异构的、分布的计算资源融合进一个统一的框架内,其目的就是为用户提供一个廉价、高效的超级计算环境。任务资源分配策略决定了是否能够高效合理的利用这些计算资源。相对于元任务,依赖任务能够更客观的体现现实任务之间的层次关系,但是依赖任务调度是个NP完全难题,如何便捷地获得近似全局最优解是网格领域的研究热点。 本文简要地介绍了网格以及任务调度的相关基础知识,针对网格环境中的依赖任务调度问题,提出了一种改进混洗蛙跳算法(Improved Shuffled Frog Leaping Algorithm,ISFLA)。首先设计了一种依赖任务编码方法和资源分配策略,然后改进了局部搜索策略。最后,进行了系统仿真实验。本文的主要贡献包括以下几个方面: 降低解的维数,缩小解空间。目前的编码方式在进行编码时,会让解空间产生无效冗余和高维度问题。本文利用调度的两个阶段来解决这些问题。首先在次序调度阶段,将依赖任务的执行序列按照层次关系划分优先级,优先级相同的节点随机排列并封闭在同一维度中,达到降低解维度的目的。然后在匹配调度阶段,把动态最早完成优先算法思想导入资源分配策略中,让一个依赖任务执行序列只对应一个最优的资源分配方案,排除非法解和无效解,进一步缩小算法的解空间,提高算法的寻优效率。 改进局部搜索策略。针对混洗蛙跳算法进化动力不足和容易陷入局部最优的问题,改进了局部搜索策略。首先,ISFLA在每个族群中新增设了一个进化点,由原来单个进化点变为两个,使得能够同时选择路径和提供动力,解决了整个族群进化动力匮乏的问题,从而加快算法收敛速度。然后,为进化点引入突变因子,并通过邻域搜索方法,使得局部搜索策略中的任务节点进化过程由线性转变成非线性,从而扩展了算法搜索空间,以避免陷入局部最优。 系统实验仿真。通过对网格任务调度模型的详细分析,设计实现了一个网格任务调度原型系统。利用该系统,对改进算法进行实验仿真,同时与标准遗传算法,标准粒子群算法和原算法进行了比较分析。实验结果表明,改进算法进行网格依赖任务调度时,在全局寻优能力上表现更好,收敛速度更快。因此,本文提出的改进策略是有效可行的,具有一定的现实和参考意义。