分布式计算系统下可分任务的周期性多趟调度

朱海, 王晓丽, 马海明

(1.周口师范学院网络工程学院, 466001, 河南周口; 2.西安电子科技大学计算机学院, 710071, 西安)

随着物联网和互联网应用的蓬勃发展,源源不断的大数据涌入各行各业,对高性能计算的需求不断高涨。大规模计算平台如云计算、网格计算、雾计算等应运而生。然而,不管是何种分布式计算平台都离不开高效的任务调度策略[1]。

大数据任务[2],如大规模信号处理、图像处理、矩阵运算等,虽然数据规模庞大,但是任务往往具有可分性,即可以切分为任意大小的子任务且各子任务之间没有优先关系[3]。可分任务调度模型分为单趟调度和多趟调度两大类,其中单趟调度将任务划分为与服务器具有相同数目的子任务,目标是寻找最优的任务分配方案使得任务的完成时间最短。近年来,针对各类分布式计算平台,如星型网络[4]、多层树网络[5]、高斯网格[6]、云平台[7]和非线性负载的线性网络[8]等,已有文献推导得到了最优或近似最优的任务分配方案的解析解。虽然单趟调度易于实现,但是由于服务器存在较长的等待时间,降低了服务器的利用率和完成任务的效率。

针对这一问题,Bharadwaj等提出了多趟调度模型,将任务划分为数倍于服务器数的子任务并分多趟分配给各服务器[9]。通过减少服务器的等待时间提高完成任务的效率。多趟调度模型在各类计算平台得到了广泛应用,如星型网络[10]、K维网[11]、完全B-Ary树网[12]和云平台[13]等。与单趟调度模型相比,多趟调度模型求解的复杂度急剧增大。一是因为模型引入了新的变量——调度趟数,二是多趟调度的任务分配方案不再是一个向量而是一个矩阵,其中矩阵的每个元素表示各趟调度中每个服务器的任务分配量。为了得到多趟调度的最优解,Suresh等提出了一种混合实数编码进化算法[14],然而当系统规模和调度趟数很大时,算法很难在可容忍的时间范围内收敛到全局最优解。为了得到问题的近似最优解,Yang等提出了均匀多趟调度模型,将任务分配矩阵简化为向量,并推导得到了任务分配向量的解析解[15]。Shokripour等对模型进一步优化,提出了周期性多趟调度模型,将调度分为内部调度和最后一趟调度两部分[16]。最后一趟调度用来确保所有服务器同时完成计算,从而进一步降低了任务的完成时间。但是,文献[10-16]并没有找到服务器的最优调度顺序,因此不能最小化任务的完成时间。鉴于此,本文以任务的完成时间最短为目标,建立了可分任务的周期性多趟调度优化模型,并设计了全局优化进化算法对模型进行求解,得到了最优的服务器数、服务器调度顺序、最优调度趟数和最优的任务分配方案。

1 周期性多趟调度优化模型

分布式计算平台由M+1台服务器通过星型网络互连,其中p0为主服务器,{pi|i∈{1,2,…,M}}为从服务器,li是连接p0和pi的通信链路,总任务大小为W。p0负责划分和调度任务,并不参与任务计算。多趟调度过程分为内部调度和最后一趟调度。设内部调度趟数为n,则总趟数为n+1。设参与计算的从服务器数为m,且2≤m≤M。每趟调度所有服务器完成的任务量相同,记为V=W/(n+1)。

1.1 内部调度

为了获得最短的任务完成时间,内部调度中每个服务器在相邻两趟调度之间不应存在空闲时间。由图1可以看出,t1～t2时间段内,服务器pσ1先后完成了子任务ασ1V的计算(sσ1+wσ1ασ1V)和传输(oσ1+z1ασ1V),同时pσ2先后完成了子任务ασ2V的传输(oσ2+z2ασ2V)和计算(sσ2+wσ2ασ2V),因此t1～t2时段内可以建立恒等式关系。以此类推可得

ασ1V(zσ1+wσ1)+oσ1+sσ1=ασ2V(zσ2+wσ2)+

oσ2+sσ2=…=ασmV(zσm+wσm)+oσm+sσm

(1)

已知

ασ1+ασ2+…+ασm=1

(2)

利用式(1)将ασi用ασ1表示出来并代入式(2)得

图1 可分任务的周期性多趟调度

定义下面2个新的变量

则式(3)可简化为

由式(1)(5)可得内部调度的任务分配方案为

1.2 最后一趟调度

为了得到任务的最短完成时间,最后一趟调度中所有服务器必须同时完成计算,即所有服务器在T时刻同时完成计算,因此

sσi+wσiβσiV=oσi+1+zσi+1βσi+1V+sσi+1+wσi+1βσi+1V

(7)

为了简化公式,定义如下2个变量

式(8)可简化为

定义如下2个变量

由图1可得任务的总完成时间为

T=n(ασ1V(zσ1+wσ1)+oσ1+sσ1)+
βσ1V(zσ1+wσ1)+oσ1+sσ1

(13)

调度的趟数越多,每趟调度分配的任务量就越少,服务器的空闲等待时间就越短。但是,由于平台存在启动开销,调度的趟数越多,额外的开销越多,任务的总完成时间也就越大。任务的完成时间T随调度趟数n的增加先减小后增加,因此可以通过寻找函数T(n)的转折点找到调度趟数的最优解。为此,需要首先确定n的上界和下界。由前文的分析可知,对于所有参与调度的服务器有βσi>0。展开式(12)可得

将V=W/(m+1)代入式(15),化简得

引入新的符号

1.4 σ的最优解

给定服务器调度顺序σ就可以求得最优的n和m,从而可以通过式(6)(12)和(13)推导得到任务分配方案和任务的完成时间T。为了求得最优的服务器调度顺序,建立以下优化模型

βσ1V(zσ1+wσ1)+oσ1+sσ1]

2 全局优化进化算法

所提模型仅含有一组变量σ=(σ1,σ2,…,σm),即服务器的调度顺序,它是1～m的一个全排列。可见,该问题属于组合优化问题。当系统规模较大时,传统优化算法很难在可容忍的时间范围内找到问题的全局最优解或局部最优解,往往需要借助智能优化算法对问题进行求解,而进化算法作为智能优化算法类的杰出代表,非常擅长于求解组合优化问题。因此,本文设计了一个新的全局优化进化算法求解多趟调度优化模型。

2.1 编码与适应度函数

本文直接对模型的变量进行编码,即个体由I=(σ)来表示,其中σ表示服务器的调度顺序。注意,为满足模型的约束条件,个体的编码必须包含所有参与计算的服务器编号且每个服务器编号仅能包含一次。任何服务器编号的缺失或者重复都将导致产生非法个体。

随机产生N个个体作为初始种群。每产生一个个体,也就给定了一种服务器的调度顺序,进而可以求得当前处理机调度顺序下最优的n和m,然后通过式(6)和式(12)可以推导得到任务的分配方案,最后通过式(13)求得T。将T的倒数作为个体的适应度值,T越小,个体的适应度值越大,表明个体越优秀。

2.2 交叉与变异

本文采用部分匹配的交叉方法。对于任意两个父代个体I1和I2

I1=(12,10,6,9,4,1,13,0,11,5,3,7,14,2,8)

I2=(14,12,10,8,4,11,6,13,5,2,1,0,9,3,7)

交叉的具体过程如下。

步骤1随机选取两个交叉点k1和k2,要求k1

I2=(14,12,10,8,4,|11,6,13,5,2,1,0,|9,3,7)

交叉产生的后代个体以概率ps进行变异,本文采用对换变异的方法。对某一后代个体,随机选取两个变异位k1和k2,要求k1

交换这两个位置的基因可以得到变异后的个体

p′=(12,10,6,9,3,1,13,0,11,5,4,7,14,2,8)

2.3 局部搜索算子

考虑到高性能分布式平台的系统规模较为庞大,为了加快算法的收敛速度,本文为进化算法引入局部搜索算子。其基本思想是对于任意一个个体I,计算个体的适应度值f(I),搜索个体的邻域空间,即按序交换其编码相邻两位基因,更新个体I′,计算个体I′的适应度值f(I′),若新个体I′的适应度优于原来的个体I,即f(I′)>f(I),则用新个体I′替换原来的个体I,并继续在个体I′的邻域空间内执行搜索;否则,不替换。

例如,对于个体p=(12,10,6,9,4,1,13,0,11,5,3,7,14,2,8),局部搜索的步骤为:交换第1位基因12和第2位基因10,得到新的个体p′=(10,12,6,9,4,1,13,0,11,5,3,7,14,2,8)。计算个体p和p′的适应度值,如果p′的适应度值大于p的适应度值,即p′的任务完成时间小于p的任务完成时间,则交换这两个基因位,否则,不交换。然后,对个体p的第2位和第3位基因执行相同的操作,直到最后两位完成试探交换。

2.4 全局优化进化算法

本文提出多趟调度全局优化进化算法的步骤如下。

步骤1初始化。产生初始种群P(t),设置代数t=0。

步骤2交叉。对于种群P(t)中的每个个体Ij,j=1,2,…,N,计算适应度值,轮盘赌选择N个个体存入交叉池。对交叉池中的N/2对个体按照交叉概率pc进行部分匹配交叉,后代个体的集合记为O1,后代个体的数量记为R1。

步骤3变异。对于P(t)∪O1中的每个个体Ij,j=1,2,…,N+R1,随机产生实数r∈[0,1],若r

步骤4局部搜索。对P(t)∪O1∪O2中的每个个体Ij,j=1,2,…,N+R1+R2,进行局部搜索操作,更新后的个体集合记为O3。

步骤5选择。首先根据精英保留策略从P(t)∪O3中选出E个最佳个体直接保存到下一代P(t+1)中,然后通过轮盘赌方法在P(t)∪O1∪O2中选择剩下的N-E个个体放入P(t+1)中。

步骤6终止条件。若满足终止条件,终止算法并输出当前种群的最优个体。否则,跳到步骤2。

3 实验与结果分析

将本文算法与文献[10-16]采用的IZ和IW方法以及Hsu等提出的ESCR算法[17]进行了比较。平台含有15台服务器,每台服务器的相关参数见表1。本文算法的相关参数设置如下:种群大小N=100,交叉概率pc=0.6,变异概率ps=0.02,精英保留数E=5,终止条件t=200。若增加平台服务器的数量,可仅将终止条件的进化代数适量调大,其他参数保持不变。给定测试任务大小W∈{100,500,1 000,5 000,10 000},表2给出了本文、IZ、IW和ESCR等4种调度算法的对比实验结果。由表2可以看出,给定任务量,4种调度算法求得的最优调度趟数n、参与计算的处理机数m和处理机调度顺序σ各不相同,因此任务的分配方案和最终获得的任务完成时间也各不相同。对任一任务,与其他调度算法相比,本文算法都能获得最短的任务完成时间,可见模型和算法的有效性。

表1 分布式系统的参数

为了更直观地体现各算法的性能差异,图2给出了4种调度算法处理不同数量级任务的完成时间随任务量的变化曲线,其中图2a针对小规模任务W∈[100,1 000],图2b针对中规模任务W∈[1 000,10 000],图2c针对大规模任务W∈[10 000,100 000]。从图2a可以看出,当任务量相对较小时,本文算法能够获得最短的任务完成时间,IW与IZ算法并没有明显的优劣关系,而ESCR算法的任务完成时间最大。这是因为ESCR算法并没有令所有服务器同时完成任务计算,而且即便任务量较小的情况下也令所有的服务器都参与任务的计算,导致服务器的空闲等待时间较长,既降低了系统的资源利用率又没有最大化任务的执行效率。与已有算法相比,本文算法降低了至少25%的任务完成时间。从图2b可以看出,当任务量逐渐增大时,ESCR和IW算法的时间性能并没有明显的优劣之分, 而IZ和本文算法明显优于其他2种算法,本文算法时间性能最佳。从图2c可以看出,当任务量较大时,各调度算法的时间性能差异随着任务量的增大差距越来越大。ESCR算法获得的任务完成时间最大(最差),其次是IW和IZ算法,本文算法在时间性能上有明显的优势,能够最小化任务的完成时间。与已有算法相比,本文算法降低了至少43%的任务完成时间。

表2 4种算法的实验结果比较

(a)任务量从100到1 000

(b)任务量从1 000到10 000

(c)任务量从10 000到100 000图2 4种算法的时间性能对比

4 结 论

随着大数据时代的到来,对企业而言,数据即生产力,如何提高数据的处理效率受到越来越多的关注。本文以任务的完成时间最短为目标,建立了可分任务的周期性多趟调度优化模型,并设计了全局优化进化算法对模型进行求解,获得了最优的调度趟数、最优的参与计算的服务器数、最优的任务分配方案和最优的处理机调度顺序。实验结果表明,与已有调度算法相比,本文算法在任务执行效率方面提升了至少25%的性能。