基于集群计算的任务调度算法研究

汪莹，陈新鹏

（四川大学计算机学院，成都610065）

0 引言

近年来，高速发展中的中国航天事业取得了非常优秀的成果，例如受到全世界关注的歼十战斗机、歼二十战斗机等。中国的航空工业发展起步虽晚于欧美国家，但后来居上，我国在航空工业发展中对于航空发动机的研究非常关注，发动机的研究对于航空事业极其重要，航空发动机必须在高温高压高负荷的情况下，保持稳定高效的工作性能，同时还必须考虑到自身重量、体积、成本和安全性等条件的约束，这导致航空发动机的研究进展极为缓慢且困难。实验中要做到对发动机燃烧室模拟的最大化，真实实验的成本花销极高，故众多研究人员多采取科学计算的方法来进行仿真模拟实验，可以说科学计算现在已经成为学术研究中必不可少的一门科学工具[1]。科学计算（Scientific Computing）目前被应用在多个学科领域中，它使用计算机的高级计算功能来建模解决现实生产环境下产生的复杂问题，涵盖了众多学科的科学领域。其核心是研发对应的计算模型来模拟、理解自然系统，主要针对特定的现实问题设计对应的数学简化模型，然后通过计算模拟寻求最优解来解决现实问题。在材料、物理、气象、医学、航天和军事等学科领域中对科学计算的应用非常广泛，这一类计算任务多为CPU 密集型任务（计算密集型任务），对于计算性能和计算完成时间要求很高，常采用HPC（高性能计算）集群来完成仿真实验，因为HPC 集群可以提供单计算机所不能提供的超强计算能力。极速增长的计算需求和精度需求给科学计算仿真模拟平台带来了挑战。仅提升CPU 芯片运算速度，已不能满足计算需求，若是能优化集群节点计算任务的调度策略，最大化集群资源利用率，这对我国航空工业发展有极大促进作用。

1 集群计算概念

集群和分布式计算不同，分布式计算主要研究的是分散式系统（Distributed System）的计算过程。分布式系统是一组计算机，通过互联网进行通讯和数据交互。分布式计算会把结构庞大的工程计算项目切分为许多小块计算任务（task），再分别分发给分布于世界各地的计算机进行计算，各个计算机计算完毕后上传结构，再将汇总的结果进行统一合并。通常分布式计算项目会征用世界各地志愿者提供的闲置计算资源。分布式计算的计算任务间具有独立性，不存在数据依赖，故个别计算任务的出错不会影响其余任务的计算进程和分布式计算不同，集群可被看作是一台计算机，集群中的计算机通过局域网互连，实现各个节点间的高度紧密连接。高性能计算集群会把任务分配给集群中的不同计算节点，但节点间的数据通信时延非常小，可忽略不计。

2 算法研究

2.1 Min-Min算法

Min-Min 算法作为经典的启发式的算法之一，现在依旧作为热门的基础对比算法之一，Min-Min 算法的核心思想是优先给予有最短完成时间的任务较高的优先级，总是优先执行具有最短完成时间的任务。假设有m 个待处理的任务；任务集T：{T1，T2，T3，…，Tm}，且每个任务相互独立；n 个资源节点，节点集P：{P1，P2，P3，P4，…，Pn}，n 远远小于任务的数量，即n＜＜m，现举例如下：

（1）首先对任务集T 中的每一个任务Ti，计算其被分配到每个资源节点的最早计算完成时间，用矩阵Am*n记录，当T 集不为空，则反复执行该步骤。

（2）利用得到的最小完成时间矩阵Am*n，找到每个任务的最短完成时间以及其对应的分配资源节点。在所有任务的最短完成时间中，找到最小的任务完成时间，以及其对应的任务Ti和对应的被分配主机Pj，将任务Ti分配到计算结点Pj上。并从任务集T 中删除任务Ti，并更新时间记录矩阵Am*n。

在实际的生产调度中，Min-Min 算法的调度效果并不理想，Min-Min 算法将计算任务尽可能分配给处理速度较快的计算节点[2]，这会造成处理速度较慢的计算节点处于饥饿状态。计算节点的资源利用率过低，负载不平衡，造成了资源节点的浪费。Min-Min 算法只单一的考虑了时间因素，有一定的局限性，不能满足实际生产中对各种任务不同的QoS 要求，这是它的局限性所在。

2.2 Max-Min算法

与Min-Min 算法原理类似，Max-Min 在将任务映射到计算节点前，会预先计算每个任务被分配到n 个资源节点的最早完成时间，然后会在待分配的任务集合T 中选择长任务，即选择最早完成时间数值最大的任务Ti，将其分配到对应的节点上。同理，假设有m 个待处理的任务；任务集T：{T1，T2，T3，…，Tm}，且每个任务间相互独立；n 个资源节点，计算资源节点集合P：{P1，P2，P3，P4，…，Pn}，即n＜＜m，现举例如下：

（1）先对任务集合T 判空，若不为空，对T 中所有任务，计算每个任务被分配到所有计算节点上的最早完成时间，并将结果记录到矩阵Am*n中；若T 集为空，则跳出此映射循环事件。

（2）利用矩阵Am*n，找到每个任务的最早完成时间以及其对应的资源节点。在所有的待分配任务中，找出最早完成时间数值最大的那个任务，Ti以及其对应的资源节点Pj，将Ti映射到资源节点上，并在任务池中删除此任务Ti，跳回步骤（1）更新矩阵Am*n。

与MIN-MIN 类似，传统的Max-Min 算法也具有其局限性，它会优先将长任务分配给计算节点，短任务具有较低的优先级，则会一直处于待分配状态。当用户的计算需求中短任务远远多于长任务时，会造成计算任务的调度失衡，任务的处理时延（slowdown）过长。Min-Min、Max-Min 算法单一的考虑计算任务的长短[3]，不能满足实际生产任务中多变的QoS（服务质量）需求。随着现实生活中的实际应用，需要处理的计算任务数据量愈发庞大，原有的传统调度方法能提升的效率非常有限。为了处理海量计算数据，同时最小化任务完成时间和最大化资源利用率，考虑使用启发式任务调度算法。

2.3 遗传算法

近年来群体智能优化算法，广泛的被应用于数值优化计算中，因其全局搜索能力强，不过分依赖于参数设置。遗传算法也属于启发式进化算法的一种，任务调度问题中的一个可行解对应GA 算法中的一个染色体，染色体上有基因，对应于组成可行解的多个元素。遗传算法运行时会进行N 次迭代，每次迭代过程中会生成多条染色体，即多个可行解。在这个过程中会由适应度函数来衡量每个可行解（任务调度方案）的优劣然后打分。得分较低的可行解会被淘汰，从而经过多次迭代后，可行解的质量会越来越优良[4]。

图1 为遗传算法流程图，现将算法步骤详细描述如下：

（1）初始化种群个体(染色体)，设置最大迭代次数为n，当前迭代次数count 为0。

（2）计算种群中每个个体的适应度函数值，并判断当前迭代次数count 是否小于n，符合条件则跳转到步骤3。

（3）根据步骤2 中算出的适应度函数值选择出种群中的最优个体作为步骤4 的母体，跳转到步骤4

（4）将步骤3 中挑选出的母体进行交叉操作，产生新个体，跳转步骤5

（5）将上一步骤产生的新个体，在一定概率值的指导下，进行基因突变，并把当前迭代次数加一。跳转到步骤2。

图1 GA算法流程图

3 实验

在真实的系统环境中进行任务调度成本花销过高，故而研究人员常采用模拟工具来完成仿真模拟实验，来得到逼近最优解的可行调度方案，本文选择了开源的仿真模拟平台，CloudSim 进行实验。验证遗传算法、Max-Min 算法、Min-Min 算法的调度性能。

CloudSim 是一个开源的仿真模拟框架[5]，有其自带的简单任务分配策略，若要将自己的算法引入Cloud-Sim 中进行任务分配，需要对CloudSim 中的自带的分配策略进行重写。实验开始前需要对任务参数进行初始化，例如计算结点数量以及其内存大小和CPU 计算处理速率等。本次实验设置了5 个资源结点，计算任务个数分别为25、50、100、1000，任务对于计算节点的需求，采用随机函数随机生成的模式，且任务之间相互独立。由图2 可知，遗传算法的任务完成时间远优于Min-Min、Max-Min 算法，且随着任务数量的增大，遗传算法的任务完成时间呈一个线性的缓速增长，而其余两个算法，在任务量达到1000 时，任务完成时间激增，突破了5500ms。证明启发式的遗传算法性能优于传统任务调度算法。

图2 CloudSim实验结果

4 结语

本文介绍了科学计算的研究意义，以及高性能计算集群的相关定义，根据待解决的问题，进行了问题定义。将启发式优化算法中的遗传算法和传统的Min-Min、Max-Min 算法进行对比，分别阐述了这三个算法的问题模型及算法流程，然后基于给定的任务调度算法优化目标，在CloudSim 仿真模拟平台上进行了模拟实验，由最后得出的结果可知，遗传算法相较于传统的任务调度算法Min-Min、Max-Min 有更高的性能，完成了最小化任务完成时间，最大化资源利用率的优化目标。证明遗传算法可用于解决实际生产环境中任务调度的相关问题，具有一定的研究意义。