一种对集群回填作业调度改进的RB_HAR策略

李薛剑， 雷 政

(1.安徽大学 计算机科学与技术学院，合肥 230601;2.中国科学技术大学 计算机科学与技术学院，合肥 230026)

0 引 言

随着高性能计算技术的发展，集群系统在高性能计算领域占据了越来越大的比重[1]。作业调度策略作为集群作业管理系统的核心，其优劣直接影响着高性能集群的性能[2]。以提升集群计算资源利用率为目的的回填算法被证明是性能最好的调度算法之一[3]。

一些基于回填算法的改进策略对回填算法进行了完善，如LT-backfilling[4]算法能有效的保证计算节点的负载均衡；RB-FIFT[5]算法能大大减少资源碎片，提高系统的吞吐率和资源利用率；基于任务类型的集群调度策略[6]在进一步提升资源利用率的同时维护了用户共享资源的公平性等。但这些回填算法都是基于作业的预估运行时间来选取填充作业，由于作业运行时间无法精确的预估，所以一定程度上影响了调度算法的效率[7]。

之前的回填算法通常会出现以下两个问题：①回填作业的预估运行时间过长，集群会产生新的资源碎片；②回填作业的预估运行时间过短时，如果出现预约时间到达而回填作业没有完成的情况。为不影响预约作业运行，一般采取的方式是杀死回填作业，释放计算资源给预约作业使用。产生资源碎片和回填作业未完成被杀死都会导致算法的执行效率下降。

本文提出的RB_HAR策略在不影响预约作业运行和集群调度整体效率的前提下，适当延长回填作业使用资源的时间来提升回填作业的完成率。设计实验将结合了RB_HAR的改进回填策略应用于高性能集群的作业调度中，对比其他调度策略，RB_HAR不但继承了回填算法高响应比、高利用率等优点，而且相于较一般的回填算法，回填作业的完成率得到了极大的提升。

1 一般回填算法分析

HAR策略主要应用于高性能计算集群的作业调度中，用以提升一般回填作业调度算法时回填作业完成率。本节通过分析一般回填算法执行过程，指出在作业预约时间到达时，一般回填算法在传统方式处理回填作业的不足，从理论上验证了RB_HAR策略的可行性。

1.1 高性能计算集群模型

为了方便描述使用一般回填算法时的作业调度过程，这里给出了高性能计算集群。

高性能计算集群主要思想是利用高速网络将PC机、SMP服务器甚至是超级计算机连接起来，使用单一系统统一管理，以达到更高的计算性能，主要用于大规模数据计算[8]。常见的高性能计算集群节点由刀片式计算机或PC机构成，这类集群的特点是廉价易构建、便于扩充、各节点运算能力差异不明显。

在高性能计算集群系统中，用户提交的作业可以从两个方面描述：申请CPU核数和预估运行时间[9]。借鉴文献[9]中的研究方法，将提交的作业抽象成以占用CPU核数为长、运行时间为宽的矩形；将集群抽象成以集群的总CPU核数为X轴、集群开启时间为Y轴的二维集群坐标系。如图1所示是一个抽象的CPU核数为16的高性能计算集群，其中矩形①、②、③表示正在运行的作业，预估作业①将t1时刻完成计算；矩形④表示已经计算结束的作业；矩形⑤表示该作业预约了一块计算资源，将在t4时刻占用CPU核N10～N16；矩形⑥、⑦是因作业⑤预约而填充运行的作业。

图1 高性能计算集群模型图

1.2 一般回填算法流程

采用Backfilling算法进行作业调度流程如图2所示。

图2 Backfilling算法流程图

对图1所示集群的当前状态，按照 图2的流程图可知：

(1) 直接运行阶段。当前集群资源满足①、②、③号作业需求，直接投入运行。

(2) 作业预约阶段。当前5个空闲CPU核(图1中的N12～N16)不能满足作业⑤的需求，根据节点负载均衡和尽量减小作业响应比的原则，作业⑤预约了7个CPU核(图1中的N10～N16),将在作业③结束后(t4时刻)开始计算。

(3) 填充操作阶段。等待队列中选取了⑥、⑦作为回填作业投入到资源碎片中运行。

(4) 处理预约阶段。根据回填算法，在t4时刻系统会杀死未完成的作业⑦，释放节点N15、N16给作业⑤使用。

1.3 一般回填算法分析

上述执行过程的结果是作业⑤开始运行，CPU核N8、N9空闲。若此时等待队列中找不到一个作业申请的CPU核数小于等于2，节点N8、N9会一直处于空闲状态，直到t2时刻，空闲CPU核数增至5才有可能满足新作业的需求。回溯上述过程，若在t4时刻让作业⑤使用CPU核N8～N14，允许作业⑦最迟运行到t2时刻，这样既能保证集群作业调度性能不变也能避免作业⑦未完成被杀死。

2 RB_HAR策略及实现

2.1 RB_HAR策略思想

从一般回填算法分析可看出，当回填作业因为预估运行时间短于实际运行时间而在未完成时将要被系统杀死时，如果继续让预约作业运行，那么既可以不影响集群调度性能，也能保证预约作业在预约时间投入计算。因此，可以适当的延长回填作业运行时间，以提高回填作业的完成率。

由于多数改进的回填算法仅在第(3)步回填操作阶段通过使用不同的策略选取回填作业来对回填算法进行改进，而RB_HAR策略主要是在第(4)步处理预约阶段对回填算法进行改进，所以理论上RB_HAR策略也适用于多数改进的回填算法。

2.2 RB_HAR策略描述

为方便描述RB_HAR策略，表1和表2给出了集群中单个CPU核的属性和单个作业的属性及说明。

表1 CPU核心相关属性及说明

结合了RB_HAR策略的回填算法流程图如图3所示，其中回填算法部分既可以是一般的回填算法也可以是一些改进的回填算法。

作业调度和预约处理根据一般回填算法或其他改进的回填算法进行。当某一预约作业AJ的预约运行时间到达，因AJ预约而回填运行的作业FJ没有结束运行，即(1)成立时，考虑如何处理FJ：

表2 作业相关属性及说明

图3 结合了RB_HAR的回填算法流程图

FJ=AJ.FJ_V[i](AJ.FJ_V[i].jState==RUN)

(1)

当集群系统同时满足条件I和II时，允许FJ继续运行一段时间：

条件1 下式成立：

(2)

式中，FJ表示继续运行一段时间不会影响AJ在预约时间运行。其中节点N[i]如果空闲，枚举类型N[i].nState==FREE，值为1，求和运算后可表示由N个CPU核心构成的集群中空闲节点的总数。

条件2

Job[0].aNode

(3)

X.aNode

(4)

minTime>X.aNode

(5)

式(3)成立且式(4)式(5)不同时成立。式(3)表示当前空闲节点小于等待队列队首作业申请节点数。式(4)、(5)同时成立表示能在等待队列中找到一个作业X填充到因等待队列队首作业预约而形成的资源碎片中。minTime表示当前集群运行作业的最短剩余时间，可用下式说明：

minTime=MIN(N[1].ocTime,N[2].ocTime,……,

N[n].ocTime)

(6)

式中,N[n].ocTime表示集群CPU核n上有作业运行(不包括回填作业)，该作业的剩余运行时间为ocTime。

如果条件1和条件2同时满足，则应允许填充作业FJ延长运行，增加的运行时间为minTime，即允许FJ延长运行的时间等于当前集群正在运行作业的最短剩余运行时间。如果FJ继续运行minTime后仍没有完成，则杀死该作业，反馈给用户，检查作业并重新预估运行时间后再重新放入等待队列中接受调度。

3 实验设计

本文将HAR策略应用于Backfilling算法中提出一种改进的回填算法RB_HAR。为验证RB_HAR策略的有效性，本节设计了几组比较实验，根据实验数据分析RB_HAR在提升集群利用率、作业公平性及回填作业完成率上的表现。

3.1 实验环境

本实验使用8台PC机搭建了一个小型集群用于RB_HAR算法和其他调度算法的比较测试，PC机配置为双核CPU：Pentium(R)Dual-Core，主频3.20GHz；2GB内存。节点间使用千兆以太网交换机相连，装有Ubuntu15.04操作系统。管理节点和登录节点共用一台主机，使用开源TORQUE[10]作为作业调度软件，自定义调度算法，分别进行了FCFS(先来先服务算法)[11]、Backfilling(回填算法)[12]和RB_HAR调度算法的对比测试。

3.2 实验数据集

本实验选取了目前高性能集群性能测试中常用的LINPACK-Benchmark的HPL作为测试作业集[13]。因为HPL求解问题规模是可变的，通过改变求解矩阵的大小和使用的CPU核数，能获得不同规模的作业，便于比较分析调度策略性能。

结合本实验使用的集群规模以及Feitelson和Nitzberg对大量高性能计算中心作业分析得出的作业集特征[14]，构造了由26.9%的串行作业和73.1%的并行作业组成的混合作业集：并行作业中28.3%的作业申请2个CPU核数，25.1%的作业申请4个CPU核数，17.1%的作业申请6个CPU核数，15.2%申请8个CPU核数，14.3申请10～12个CPU核数。每个作业实际运行时间为50～200 s不等，申请节点数少的作业实际运行时间较短。

本次实验构造4个规模的作业集，作业个数分别为100、300、500和1 000，作业随机到达，在保证等待队列中作业数量大于5个的基础上，作业到来时间间隔为0～1 000 s的随机值。

3.3 实验比较参数

本节给出了实验涉及到的一些比较参数的定义及其作用。

参数1集群平均利用率。集群利用率是反应调度算法优劣的一个重要参数[15]，定义集群平均利用率，如下式所示：

J[i].bTime)×J[i].applyNode]

(7)

式中：M为作业总数；N为集群节点个数；totalTime是完成M个作业花费的总时间；J[i].ftime、J[i].bTime、J[i].applyNode分别表示第i个作业的完成时刻、开始时刻和占用节点数。

参数2作业平均响应比。作业响应比反映了调度算法的公平性，好的调度算法应该具有较小的响应比。定义作业平均响应比，如下式所示：

(8)

式中：J[i].ftime、J[i].aTime、J[i].bTime分别表示第i个作业的完成时刻、到达时刻和开始运行时刻。

参数3填充作业完成率。在回填算法中，由于作业运行时间的不准确预估可能导致某些填充作业一次无法完成，还需进行第2次调度。将填充作业中一次调度就完成的填充作业所占的比率称为填充作业完成率。RB_HAR策略的提出旨在使用回填算法时提高填充作业完成率。

4 实验结果及分析

每组实验使用4个规模的作业集分别对FCFS、Backfilling和RB_HAR 3种调度算法进行测试，计算的作业集规模有4种：100，300，500和1 000。收集了30组实验结果进行统计，得到了作业完成总时间、集群平均利用率、作业平均响应比、填充作业完成率的平均值。

4.1 批作业完成总时间比较

图4所示为3种调度算法完成一定数量作业时间的比较如，在各组实验中RB_HAR算法和Backfilling算法完成一定量作业的总时间都明显少于FCFS算法。相较于Backfilling算法， RB_HAR算法虽然完成总时间略长，但劣势并不明显。且该算法兼顾了回填作业的完成率。

图4 作业完成总时间比较

4.2 集群平均利用率比较

图5所示为使用3种调度算法对集群的平均利用率进行比较，RB_HAR算法很好的继承了Backfilling算法集群资源高利用率的特点，且明显优于FCFS算法。

图5 集群平均利用率比较

4.3 作业平均响应比比较

图6所示为3种作业调度算法对应的作业平均相应时间比较。由于小作业可以通过回填的方式提前得到调度，相比较于FCFS，RB_HAR和Backfilling有着更小的作业响应比，很大程度上保证了作业调度的公平性。

图6 作业平均响应比比较

4.4 填充作业完成率比较

图7所示为Backfilling算法和RB_HAR算法的回填作业完成率比较。RB_HAR算法兼顾了填充作业的完成率，相较于简单的Backfilling算法，填充作业完成率平均提升了13.29%。93%的填充作业完成率能满足大多数用户的要求，未完成的填充作业可接受2次调度。

图7 填充作业完成率比较

4.5 综合分析

RB_HAR算法继承了Backfilling的集群资源高利用率、作业低响应比等优点，从对实验数据的分析可以看出，RB_HAR算法的性能明显优于FCFS。RB_HAR与Backfilling算法回填作业完成率的比较实验，验证了RB_HAR能有效的提升回填作业的完成率。由此可见RB_HAR策略应用于回填算法时，在面向系统和面向用户[16]两方面都有着出色的表现。

5 结 语

本文将HAR策略应用于回填算法中，提出一种改进的回填算法RB_HAR。该算法不仅继承了一般预约回填算法的集群资源利用率高和作业低响应比等优点，同时还有效的提升了回填作业的完成率，减少回填作业2次运行带来的资源浪费、作业调度的不公平性，最后的实验结果也证实了RB_HAR策略的优越性。此外，研究过程中还存在某些问题：比如，RB_HAR策略不能保证回填作业百分之百完成，无限制的允许回填作业运行至结束，可能导致预约作业响应比增加；由于条件限制，RB_HAR策略未能应用于更大型的集群系统。解决存在的这些问题将是今后工作的重点。