基于粒子群算法的分布式计算系统能效优化方法

池来新 谢 宁 张学杰 张骥先

(云南大学信息学院 云南 昆明 650500)

0 引 言

分布式计算系统的资源分配问题一直是许多研究的焦点，其目标是减少处理任务所需的时间，提升处理效率，并尽可能减少处理这些任务所需的功耗，以降低处理成本。一般来说，当高性能计算系统的处理器性能提高时，其功耗也会增加，运营的电力成本也会随之增加。对于大型分布式计算系统来说，机器运营的电力成本显得尤为重要[1]，如何对资源进行分配以调和任务处理时间和处理功耗以达到利润的最大化则成为了关键。

分布式计算系统往往包含多种类型的机器，其处理速度各不相同，而用户有大量的待处理任务，同时这些任务可分为不同类型，不同类型的任务在不同的机器上进行处理所需时间和功耗可能都不相同，以上情形都造成了问题的复杂性。一般来说，对此建立的模型都是非线性的，而且存在诸多复杂的约束条件，无法在多项式的时间内进行求解。

这种将所有任务分配给在分布式计算系统中所有机器的调度模型已经在多篇文献中提出，起初更多的研究主要针对完工时间或是系统性能进行优化。Braun等[2]比较了11种静态启发式算法，用于将一类独立的任务分配到一个分布式计算系统，目标是最小化完工时间。Diaz等[3]评估了3种用于高度异构计算系统的启发式算法，其目标是最小化完工时间和流动时间。虽然上述研究中的算法能优化完工时间，但未考虑功耗情况，因而在综合考虑完工时间和能量消耗的能效优化问题上难以发挥作用。

随着分布式计算系统不断发展，集群规模不断增大，电力成本不断提高，能耗问题已是资源分配所要考虑的重要因素，因此如何平衡计算效率和能量消耗达到能效的最优化成为研究的热点。Friese等[4]创建了一个工具，允许系统管理员研究权衡系统的性能和系统能量消耗。Oxley等[5]开发并分析了能量感知资源分配的几种启发式算法，用于能量约束和期限约束问题，同时确定每种类型的任务数量并将任务分配给每种类型的机器的调度模型。这些研究在优化系统性能的同时也考虑了功耗，以便权衡完工时间和任务处理成本。

文献[6]提出了一种基于线性规划的资源分配算法，有效计算出最小化完工时间的高质量解决方案。文献[7]设计了一种基于线性规划的舍入方法，以生成一组高质量的解决方案，可以对完工时间和能量消耗之间进行权衡以使目标值最大化。文献[8]提出了一种新的调度模型，最大化每单位时间的利润，并且将任务调度的过程分为两个阶段：先通过求取线性规划模型并对分数解进行舍入以获得整数解；再使用LPT算法将任务分配到具体机器上。Li等[9]优化了上述研究中的线性规划模型，可以得出质量更高的近似解。这类研究中均使用线性规划的方法来综合考虑完工时间和能量消耗，通过优化得出近似易于求解的线性整数规划模型进行求解，但由于对模型进行近似而产生误差，因此对算法结果的质量无法给予保障。

同时，对于资源分配问题，文献[10-12]使用拍卖的思想来解决，但拍卖思想一般用于解决多个用户的资源需求，类似背包问题，并不适用针对单一用户而必须满足所有资源需求的能效优化问题。

可见，对于分布式计算系统中能效问题的研究已较为深入，但限于问题模型过于复杂难解，其主流思想是对原本复杂的问题模型进行优化以得出相对易于求解的近似模型，因此设计出一种能直接求解该问题的非线性整数规划的算法才能从根本上解决问题并获取或趋近最优解。粒子群算法(PSO)在复杂问题模型的求解方面可以发挥较大作用，其思想简单、计算效果好，且相比其他启发式算法收敛速度快，比较适用于此类问题的求解。

PSO是一种现在流行的群优化算法，因其所要调整的参数很少，相比其他启发式算法的收敛速度更快，能在更短时间内取得比较满意的结果。PSO是用于优化连续非线性函数的最新进化优化技术之一，其源于对鸟群和鱼群的捕食行为的研究，群体之间共享最优信息，通过协作使群体达到最优的目的，群体中的各成员追随着当前搜索到的最优值的方向进行寻优。PSO还可以同其他启发式算法结合以解决不同特性的问题[13]，同时可以改善收敛性。因此，使用PSO有助于解决上述最优化问题。本文使用PSO在文献[8]基础上对原有非线性规划上进行全局搜索，求解真实目标值而非近似目标值作为适应度，以获取问题更准确的可行解，并迭代计算使其趋向于最优解。

1 问题描述

对于分布式计算系统的资源分配问题，服务提供商需要合理地将客户提交的任务集合分配到分布式计算系统的服务器上。任务包括不同种类型，每个任务都只能在一台机器上进行处理，且不可分割，并独立于其他任务，不存在执行优先级关系。客户为处理任务集合而支付的价格为p。分布式计算系统的服务提供商为客户处理任务的成本是电费，假设单位电能成本是c，为便于讨论，本文忽略其他成本。组织方的利润则是用户支付的价格减去服务方的电能成本。容易得出，当试图使用功耗较低的机器去降低电力成本提高利润时，而由于功耗较低的机器性能不够高，因此可能会增加任务集合的处理时间，故而解决问题的目标应该是最大化单位时间的利润。单位时间利润可表示如下：

(1)

式中：E(x)表示处理任务集合的总功耗；MS(x)为完工时间，两者都与资源分配的决策x相关。同文献[1]一样，将完工时间定义为所有机器的最大处理完任务的时间。

对上述设定进行举例说明：

t=2T1={1,2,…,n1}T2={1,2,…,n2}

m=2M1={1,2,…,k1}M2={1,2,…,k2}

对于一台特定的机器jk，处理完分配到该机器上的任务的时间为Fjk，显然有式(2)成立，即特定一台机器处理任务的总时间为分配到该机器上的所有任务执时间的总和。

(2)

不同的决策变量xijk有着不同的完工时间，根据完工时间的定义，可以得到完工时间的计算公式如式(3)所示，即完工时间等于在处理该任务集合中所耗时最长的机器的处理时间。

MS(x)=maxjmaxk:jk∈MjFjk

(3)

对于集合消耗的总能量E(x)，为了便于讨论，本文忽略机器的空闲功耗，即机器没有任务执行时不会产生功耗，在有任务执行时机器不会产生额外功耗，所以总能量E(x)计算如下：

(4)

因此，分布式计算系统的单位利润最大化问题可以表示为以下非线性整数规划问题：

(5)

该非线性整数规划问题的目标是最大化单位时间的利润Obj。第一个约束确保第i类型的任务全部分配完；第二个约束确保所有机器处理任务的时间小于或等于完工时间MS(x)；第三个约束确保决策变量的值为0及其以上的整数，因为任务不可分，所以要保证xijk为整数。

2 算法设计

本文称文献[8]中的算法为EAPM算法(Energy-Aware Profit Maximizing Scheduling Algorithm)，该算法所代表的近似线性规划算法为目前在分布式能效优化中的主流算法。式(5)中目标函数分子和分母的取值都与决策变量x相关，目标函数是一个非线性函数，无法在多项式的时间内求得最优解。一般的解决办法是将非线性问题转化为等效的线性问题，再将求得的最优解转换为原非线性问题的可行解。EAPM算法用完工时间的下界MS，LB来近似代替完工时间MS(x)，MS，LB被定义为不考虑功耗情况而在所有机器分配任务而获得的完工时间，计算方式如式(6)所示，然后用式(7)和式(8)做变量替换得到一个近似的线性目标函数。

(6)

(7)

(8)

近似之后的线性整数规划决策变量变为了r和z，目标函数可写为如下形式：

Obj=p·r-c·E(z)

(9)

式(9)为线性函数，可以使用传统的线性规划求解方法(如单纯形法)进行求解，再通过式(7)和式(8)将r和z转换为原问题可行解。该方法由于采用近似模型，因此存在一定误差，即在该模型下求得的最优解并非是原模型下的最优解。不过在机器类型为1的特殊情况下实际上两者的最优解一致，因为在只有一种机器类型的情况下最优的分配方案即在该类型所有机器上平分任务数。由式(6)知MS，LB基于各类型机器的平均完成时间进行计算，所以此时有MS(x)=MS，LB，则两者结果必然一致，但在更一般的情况(机器类型数大于1)下，两者存在误差，且当任务数量较小时MS，LB和最优解的完工时间MS(x)相对偏差会比较大，导致求出的解与原非线性问题的最优解仍有较大差距。

使用PSO可以克服上述问题，因为PSO可以直接对非线性问题进行全局搜索，无须事先将其转换为线性问题，可以直接通过MS(x)来计算当前调度策略的真正单位时间利润，从而能够以较准确的方向逼近最优解，该方法已广泛应用于各个领域中[14-15]，尤其在资源分配与任务调度问题上最为适用[16]。

粒子群优化算法如图1所示。PSO使用粒子作为在目标函数自变量取值空间的搜索个体，粒子的位置取值即为该粒子所对应的一个解，所有粒子都在一个D维空间(即自变量为D维向量)中进行搜索，且可以通过一个适应度函数来判断当前位置的好坏，适应度函数一般直接使用数学规划的目标函数。粒子被赋予记忆，能记住当前所搜寻到的最佳位置，每个粒子都有一个速度来决定该粒子的移动速度和方向，这个速度可以由粒子本身的历史经验(历史最佳位置)和其他粒子的历史经验(全局最佳位置)进行动态调整。

图1 粒子群优化算法简单示意图

假设在D维空间中，有n个粒子，粒子k的位置向量Xk=[Xk1,Xk2,…,XkD],1≤k≤n，粒子k的速度向量Vk=[Vk1,Vk2,…,VkD],1≤k≤n，粒子k经历过的历史最好位置Pk=[Pk1,Pk2,…,PkD],1≤k≤n，群体内(或领域内)所有粒子所经历过的最好位置Pk=[Pg1,Pg2,…,PgD]。通过若干次迭代动态调整上述变量，依次迭代即依次搜索的过程，每次迭代过程中粒子k的第d维速度更新公式如下：

(10)

式中：第一部分表示粒子的运动惯性，w被称为惯性权重，表示粒子先前速度对当前速度的影响，用于调节空间中粒子的搜索范围；第二部分表示粒子的自我认知，c1为学习因子，表示粒子最佳位置和当前位置的差对粒子速度的影响程度；第三部分代表粒子间的信息共享，c2作为学习因子，表示群体最佳位置和粒子当前位置的差对速度的影响程度[17]；r1和r2是两个随机数，用于增加搜索的随机性。为了提升粒子群算法的收敛性能，避免陷入局部最优，可以对上述参数进行动态调整[18]。每次迭代过程中粒子k的第d维位置更新公式如下：

(11)

本文算法总体流程如图2所示。

图2 算法总体流程

算法每进行一次迭代，都要计算各粒子新位置的适应度值，更新各粒子的最佳位置和群体的最佳位置，通过迭代，各粒子都将趋近于全局的最优位置。一般来说，粒子的位置和速度的取值范围是连续的实数空间，但本文问题同文献[19]和文献[20]一样，解都具有离散性。由于任务不可分，故而应将粒子的位置和速度限制为0以上的整数，对其进行离散化。

根据式(1)的目标函数，目标函数的取值代表着决策x的好坏，而x是一个二维矩阵，表示i类型任务分配到j类型机器的任务数目，为了使用粒子群优化算法，需要将决策变量x转换为一个D=t×m维的向量X，它代表了一个粒子的位置，而在计算粒子在某位置适应度时又需将向量X转换回二维矩阵的形式才能求出真实的MS(x)值。本文使用算法1和算法2实现上述两种情形的转换。

算法1将二维决策变量x转换为粒子位置向量P

输入：二维决策变量x。

输出：粒子位置向量P。

1.ProceduretransferToP(x)

2.fori=1:tdo

3.forj=1:mdo

4.Pd←xij

5.d←d+1

6.endfor

7.endfor

8.returnP

算法2将粒子位置向量P转换为二维决策变量x

输入：粒子位置向量P。

输出：二维决策变量x。

1.ProceduretransferToX(P)

3.i←(d-1)/m

4.j←(d-1)%m

5.xij←Pd

6.endfor

7.returnx

算法1通过第2行至第7行的两层for循环对二维矩阵x进行遍历，将值依次存入一维向量X中,便可生成二维决策变量对应的粒子向量。算法2通过依次遍历粒子位置向量，通过算法第3行和第4行获取对应的决策变量的下标(即任务类型和机器类型)，从而实现粒子向量到二维决策变量的转换。

PSO首先要对所有粒子进行随机的初始化，根据式(5)中的规划问题，必须考虑约束问题，为了在能够保持约束的情形下可以随机生成粒子位置P数据，最后的数据只能根据约束条件计算得出。生成粒子位置P数据的同时，要对所有粒子的最优位置Pk(k=1,2,…,D)和群体最优位置Xk进行初始化。在每一轮迭代中，通过公式计算每个粒子的新速度和新位置，速度和位置都是D维向量。之后可以根据粒子的个体适应度更新粒子个体的最佳位置和粒子群体的最佳位置。迭代完成后得到的是一个D维的粒子位置向量，必须转换为目标的t×m的决策矩阵x，才能再根据x对任务进行最终的分配。上述过程可以由算法3来实现。

算法3粒子群算法的初始化和最优化搜索

1.ProcedurePSO()

2.fork=1:Psizedo

7.endif

8.endfor

9.fort=1:step

10.fork=1:Psizedo

11.ford=1:t×mdo

13.endfor

17.endif

20.endif

21.endfor

22.endfor

24.assignMachines(x)

算法3中Psize为粒子数目，step为算法的迭代次数，t用来来指示当前的迭代次数。基本的粒子群算法是在连续空间中进行搜索，而本文的目标值都是离散值，所以计算出新的位置之后要进行离散化，一般可以直接取近似值，同时还要保证每种类型任务数目守恒的约束，以上可以通过算法4中的getBoundP()函数实现。算法中对粒子位置适应度的计算通过算法5中的getFitness()函数来完成。迭代完成后调用算法2中的transferToX()函数将粒子群体最佳位置向量转换为决策矩阵x，然后调用算法6中的assignMachines()函数对任务进行最终的分配。

算法4离散化位置向量并且在保持约束的前提下求解新一轮迭代的粒子位置

输入：粒子速度V和粒子位置X。

输出：粒子新的位置X。

1.ProceduregetBoundP(V,X)

2.ford=1:t×mdo

3. temp←Xd+Vd

4.i←(d-1)/m+1

5.i←(d-1)%m+1

9.else

10.Xd←temp

11.endif

13.endfor

14.returnX

算法5计算粒子位置的适应度

输入：粒子位置向量P。

输出：单位利润Obj。

1.ProceduregetFitness(P)

2.x=chanceferToX(P)

3.forj=1:mdo

4.fori=1:tdo

5.E←E+xijAPCijETCij

6.endfor

7.endfor

8.MS←assignMachines(x)

9.returnp/MS-cE/MS

算法6对各类型机器进行任务分配

输入：二维决策变量x。

输出：完工时间MS。

1.ProcedureassignMachines(x)

2.forj=1:mdo

3. z←φ

4.fori=1:tdo

5.z←z∪{分配在j类型机器的xij个i类型任务}

6.endfor

7.y←{对z中的任务按ETC降序排列}

9.r←arcminMachineTimej

10.分配y中第k个任务到j类型的第r台机器

11.Timejr←Timejr+ETCij

12.ifTimejr>Timestart+MSthen

13.MS←Timejr=Timestart

14.endif

15.endfor

16.endfor

17.returnMS

算法4中传入的是粒子速度和粒子上一次迭代的位置，算法第3行保证粒子位置均为整数。为了保持式(5)的约束，不能直接使用式(11)来计算粒子在新一轮迭代的位置的第d维数值，需要先用一个临时变量temp保存计算的值。第4行和第5行可以得出粒子位置向量的第d维所对应的决策矩阵x的行号和列号，xij代表第i类型任务分配在j类型机器的任务数，通过计算该类型任务分配在前面j-1个类型机器的任务数目之和s，根据式(5)中的第一个约束条件可知该类型任务在j类型机器上还能分配多少，进而可以分辨通过式(11)计算的数值能否满足约束条件。注意在j=t×m时，不能再使用式(11)，而须通过任务数目减去前面j-1个机器类型分配的任务数目的和，以使其满足约束条件，该方法同样适用于算法3中的第3行。

算法5中的粒子适应度实际上就是式(5)中的目标函数，即单位利润的取值，其中P为传入的粒子位置向量，需要通过算法2中的chanceferToX()函数转换为决策矩阵x，然后通过遍历矩阵x计算出此决策下需要消耗的功耗总和E，第8行调用算法5中的assignMachines()函数，注意这只是对此决策进行模拟的任务分配，用来计算出此决策的真正的完工时间MS，因此算法5可以计算出准确的单位利润。

算法6基于传统的LPT多处理器调度算法，独立处理各类型机器的任务分配，z用来存储分配在j类型机器上的所有任务，并且以贪婪策略将ETC更大的任务分配给有最早就绪时间的机器，此机器可以通过算法第9行获得，算法中Timejr表示第j类型机器的第r台机器的就绪时间。为了在计算粒子位置适应度的时候得出完工时间，我们用Timestart存储任务集合的开始时间，分配任务的同时要据此更新完工时间。

3 实 验

3.1 实验设置

进行模拟实验比较粒子群算法和EAPM算法的性能，主要根据用两种方法所获取的单位利润和处理完用户所有任务的完工时间及总的能量消耗来评估。不失一般性，假设所有实验中的单位电能成本c=1，客户支付价格为：

p=γEmin

(12)

式中:Emin是忽略完工时间时消耗的能量的下限。

(13)

γ=p/Emin是一个无量纲参数，用来影响价格，根据式(1)，为了盈利(即使目标值大于0)，需保证分子大于0，则需保证γEmin-cE(x)>0，根据Emin的定义必有γEmin≤E(x)，因此一般要设定γ>1，同时要考虑市场因素，不能过高。本实验分别针对γ=1.2、γ=1.3和γ=1.5进行测试。

本文模拟实验共设有5种机器类型，即m=5，每种类型机器各20台，共计100台机器，任务类型共有5种，即t=5。测试的主要变量是客户的任务数目，EAPM算法中的线性规划可以使用文献[22]中的单纯形法进行求解，测试共分为四组，前两组分别针对较小任务数量和较大任务数量时的单位利润进行测试和对比，后两组分别对完工时间和总的能量消耗进行测试和对比。

3.2 实验数据集

由前面的论述可知实验的测试数据是矩阵ETC和矩阵APC的具体数值，本次实验的数据集来源于实际的处理器基准测试[23]，该基准测试主要对不同处理器执行若干项任务，得出相对应的任务执行时间和所需能耗，从中可以整理出矩阵ETC和矩阵APC的相应数值，以便在本文实验中进行测试。

3.3 实验结果及分析

图3和图4分别显示了对较小数量任务(200～1 000个任务)和较大数量任务(2 000～10 000个任务)进行测试得出的两种算法单位利润对比结果。由图3和图4均可以看出，γ取值越高，单位利润也越高，因为价格变高了。无论任务数量取多大，PSO求解结果的单位利润都要高于EAPM算法。同时，对比图3和图4两种情况可以发现在任务数量较大的时候PSO的结果虽优于EAPM算法，但产生的差距并不是特别大，而在任务数量较小的时候，EAPM算法对于PSO结果差距明显。换言之，EAPM算法在任务量较少的情况下离最优解存在较大误差，这同2.1节中对EAPM算法的分析一致。

(a) γ=1.2

(b) γ=1.3 (c) γ=1.5图3 较小任务数量时单位利润对比

(a) γ=1.2

(b) γ=1.3 (c) γ=1.5图4 较大任务数量时单位利润对比

表1和表2分别显示了在不同任务数量(2 000～6 000个任务)下两种算法处理任务的能量消耗和完工时间对比结果。可以看出，在任务数量相对较小的情况下，PSO的完工时间要短于EAPM算法，虽然个别情形完工时间长于EAPM算法，比如在γ=1.2、任务数量为4 000的情况，但从该情况所对应的能量消耗情况来看，PSO的结果明显优于EAPM算法的结果，表明PSO在提升单位利润的同时，也在大多数情况下减少了用户的等待时间，并降低了分布式服务提供商的能量消耗，这些均对于现实情况有较大意义。从表1中同时还可以发现在任务数量相对较大的情况下，两种算法的结果一致，表明EAPM算法的误差的影响在任务数量较大的情况下被削弱，这与图3和图4所表现出来的特点一致。所以PSO在任务数量相对较小的情况下具有明显优势。

表1 较大任务数量时能量消耗对比

表2 较大任务数量时完工时间对比

产生上述差距的原因在于EAPM在建立模型的时候对如式(1)所示的目标函数进行了近似，用完工时间的下界MS，LB代替真正的完工时间MS，以便于后面进行变量替换使原非线性整数规划转换为等效的线性整数规划。但这造成了模型的不准确，而且造成的误差会在任务数目过少的时候显得特别突出，使得线性整数规划的最优解并不是原问题的最优解。而本文算法通过模拟任务分配计算出真实MS，使算法可以直接基于式(5)中准确的非线性整数规划模型进行启发式搜索，从而能够找到更优的解。

3.4 任务类型数目和机器类型数目对实验结果的影响

上述实验中任务类型数目和机器类型数目被恒定设置为5，事实上机器类型数目和任务类型数目的不同对实验结果均会产生影响。本次实验固定任务数目为1 000，γ设置为1.2，对任务类型数目和机器类型数目分别进行调试以对两种算法的单位利润、能量消耗、完工时间进行测试，结果如图5、图6所示。

(a) 单位利润对比 (b) 完工时间对比图5 任务类型数目不同时单位利润和能量消耗情况的对比结果

(a) 单位利润对比 (b) 完工时间对比图6 机器类型数目不同时单位利润和能量消耗的对比结果

图5和表3显示了在机器类型数目设置为5，任务数目设置为1 000、γ设置为1.2时两种算法在不同任务数目下的单位利润、能量消耗和完工时间况的对比结果。可以看出在不同任务数目的情况下，PSO在单位利润方面均优于EAPM算法，虽然在部分情况下PSO比EAPM算法消耗了更多能量，但通过表2可以看出，在这些情况下PSO处理任务的完工时间明显小于EAPM算法的结果，由于PSO以单位利润作为目标进行优化，故而这些情况会正常存在。

表3 任务类型数目不同时能量消耗的对比结果

图6和表4显示了在任务类型数目设置为5，任务数目设置为1 000、γ设置为1.2时两种算法在不同机器数目下的单位利润、能量消耗和完工时间情况的对比结果。可以发现PSO得出的单位利润要优于EAPM算法的结果，但由于PSO是基于单位利润进行优化的原因，存在一些能量消耗或完工时间情况下PSO不如EAPM算法的结果。同时可以发现在机器数目为1的情况下PSO和EAPM算法的单位利润、能量消耗和完工时间均取得一致的结果，这同本文的分析一致。

表4 机器类型数目不同时完工时间的对比结果

PSO在任务类型和机器类型不同的情况下均能取得不错的结果，且在大多数时候均优于EAPM算法。其原因仍在于EAPM算法使用了近似的线性模型进行求解造成和结果的不精确，即线性模型的最优解实际上离原始模型的最优解存在差距，而PSO由于直接基于原始的模型进行求解，故而具备更高的求解精度。

对于机器类型数目为1的特殊情况，可以发现两种算法的完工时间相同，这与本文的分析一致，由于EAPM算法使用各类型机器处理任务时间平均值的最大值作为完工时间的一个近似，当机器类型数目为1时，最优的结果是将所有任务分摊至所有机器，在能完全平分的情况下该近似值等于式(3)计算出来的完工时间。故而EAPM算法在任务类型数目为1的情况下能得到最优结果，同时也反映了本文算法也具备搜索到最优解的能力，而且在更为普遍的情况下可以相比传统基于线性规划的算法得出更优的结果，这对于现实中分布式计算系统的能效优化具有较大意义。

4 结 语

在分布式计算系统中，为了平衡客户的任务处理效率和功耗，进行资源调度决策以达到单位利润的最大化。本文对问题建立了准确的数学模型，指出了EAPM算法不能取得最优解的原因，详细阐述了本文所用的粒子群算法，并用该算法在保持约束的情形下离散化变量进行启发式搜索取得了比EAPM算法更优的实验结果，表明了该算法可以在分布式计算系统中得到应用。

为了讨论方便，本文对问题做了一定简化，忽略了机器待机(无任务运行)时的功耗及其他成本，且未考虑机器的功耗上限，未来可以在更复杂的情形下建立准确模型，适当调整算法使其更具可用性。