异构并行系统下时间能耗权衡优化的任务调度算法

摘要

本发明提出了一种基于时间‑能耗重要性比重的并行任务调度算法，在满足时间和能耗的双重限制下，实现异构并行系统下任务所用时间和能耗的权衡优化。本发明考虑到实际情况中任务受各种因素的影响，执行时间不是固定且确定的，而是近似于正态分布，因此在确定任务调度顺序时，不采用以往技术中使用执行时间平均值的方法，而是将执行时间的平均值和方差同时考虑进来使用近似权重。在任务分配阶段，同时考虑时间和能耗这两个性能指标，并能根据时间‑能耗重要性比重将任务分配到合适的处理器，实现时间和能耗按比重的权衡优化，使系统获取更高的加权性能。本发明的算法与DVFS技术相结合，但是同样适用于同构并行系统以及无DVFS技术嵌入的计算机系统。

说明书

技术领域

本发明属于异构并行系统下任务调度领域，更具体的，涉及一种基于时间-能耗重要性比重的并行任务调度算法，在满足时间和能耗的双重限制下，实现并行任务所用时间和能耗的权衡优化。

背景技术

过去的几十年里，人们大多只关注了计算机的计算速度，为满足计算速度的需求，从增加晶体管个数、提高处理器的频率到增加处理器的并行度等方式来提高计算机性能，异构并行系统也应运而生。然而计算机速度越来越快的同时随之而来的是日益凸显的能耗问题。由于能耗问题的重要性，目前功耗和时间一样也作为衡量计算机性能的指标之一。现在有很多技术用于解决能耗问题，如动态电压频率调整技术(DVFS，Dynamic Voltageand Frequency Scaling)、资源休眠技术、内存优化技术等。其中，DVFS技术已经嵌入到大多数的处理器中。DVFS技术的本质是一种硬件技术，通过改变任务在处理器上运行时处理器的电压和频率来控制任务完成的时间和能耗。

任务调度是计算机领域的基础课题之一，其核心是调度算法，通过不同的调度算法可以有效的控制任务完成的时间和能耗。由于异构并行系统由一组异构处理器组成，不同处理器的特性不同，在处理同一任务时所用的时间和能耗也不相同，这给异构并行系统下的任务调度又带来了新的挑战。异构并行系统下的任务调度是一个NP完全问题，如何将任务分配给合适的处理器使得总的完成时间更短且能耗更少是国内外学者研究的一个热点问题。

近年来，不少与DVFS技术结合的高效的节能任务调度算法被提出来，并且取得了理想的实验结果。任务调度分为两个部分：确定任务调度顺序和任务的分配。在进行任务分配时，大部分算法的分配方案都是，在保证不超过功耗限制的前提下，最小化任务完成时间，或者是在不超过时间限制的前提下，最小化总能耗，即现有算法大部分都只满足了时间和能耗的其中一点，而不能满足二者的综合优化。另一方面，在确定任务调度顺序阶段，大多数算法在决定任务的调度顺序时，均假定任务执行时间是确定且固定的，而实际情况中，由于各种因素的影响，任务的执行时间是不确定的且近似于正态分布。另外，很多研究假定任务之间是独立的，而任务模型为依赖任务的任务调度则更为复杂，不适用于这种情况。

发明内容

根据对现有研究的不足和可拓展方向的分析，针对异构并行系统下依赖任务的能耗优化问题，本发明提供一种基于时间-能耗重要性比重的任务调度算法，在满足时间和能耗的双重限制下，实现并行任务所用时间和能耗的权衡优化。该算法结合DVFS技术，根据时间-能耗的重要性比重将任务分配给合适的处理器及相应的电压级别，做到根据比重的权衡优化，使系统的加权性能更大。

本发明只考虑时间和能耗两个性能指标，而不考虑其他的性能指标，所以我们认为时间重要性所占的比例与能耗所占重要性的比例之和为1.例如当时间特别重要时，如果其重要性所占比例为0.8，那么能耗所占重要性比例为0.2，时间能耗的重要性比重为0.8:0.2。

本发明提供一种异构并行系统下基于时间-能耗重要性比重的任务调度算法，该算法与已有算法相比具有如下优点：

1、考虑实际情况中任务受各种因素的影响，执行时间不是固定且确定的，而是类似于正态分布。符合正态分布的随机变量，实际的值不仅受平均值的影响而且受方差的影响。因此在确定任务调度顺序以及其他一些用 到任务执行时间的地方，本发明和以往算法中使用任务执行时间的平均值不同，而是将平均值和方差同时考虑进去，使用执行时间的近似权重。

2、本发明同时将时间和能耗作为性能指标，能同时满足时间和能耗的需求，并能根据时间-能耗的重要性比重进行权衡优化，使系统获得更高的加权性能。本发明同时适用于仅将时间或能耗作为唯一性能指标的任务调度系统。

附图说明

图1为基于时间-能耗重要性比重的任务调度算法的流程图。

具体实施方式

为了使本发明的目的、技术方案及优点更加清楚明白，以下结合附图对本发明进行进一步详细说明。应当理解，此处所描述的具体实施例仅仅用以解释本发明，并不用于限定本发明。

如图1所示，本发明提供了一种基于时间-能耗重要性比重的任务调度算法，包括任务顺序的确定、任务的初次分配、再次优化分配。我们将异构并行系统模拟为一个由p个异构处理器组成的集合PR＝{PR₁,PR₂,...,PR_p}，PR_j为第j个处理器，第j个处理器有m_j个电压级别；每个应用程序可以划分为n个原子的有依赖关系的并行任务，我们将这组并行任务模拟为一个任务集合V＝{v₁,v₂,...,v_n}。本发明具体包括以下几个步骤：

步骤1获取信息表，具体包括以下几个子步骤：

(1-1)获取每个处理器的活动因子α、切换电容C、处理器的静态功率P_S、每个处理器的电压级别层数m、每个处理器的每个电压级别的供电电压V和频率f。α_j，C_j，m_j分别为第j个处理器的活动因子、负载电容、处理器的静态功率和电压级别层数；v_j,k，f_j,k分别为第j个处理器第k层电压级别的供电电压和频率，第j个处理器的第k层电压级别用电压-频率对(v_j,k,f_j,k)来表示；

(1-2)获取任务的依赖关系集合E，其中e_i,j∈E代表任务v_i和v_j间有任务依赖关系，任务v_j开始执行必须先获取任务v_i计算所得的数据，即任务v_j必须在任务v_i完成之后开始；

(1-3)获取每个任务v_i在每个处理器的每个电压级别上的执行时间的随机变量w(i,j,k)代表任务v_i在第j个处理器第k层电压级别上执行时间的随机变量，该变量符合正态分布；

(1-4)根据下面的公式，计算每个任务在每个处理器的每个电压级上所用能耗：

$E(i,j,k)=({\alpha }_j{C}_j{v}_{j,k}^2{f}_{j,k}+P_S^j)*w(i,j,k),$

其中E(i,j,k)代表任务v_i在第j个处理器第k层电压级别上所用能耗的随机变量，由于w(i,j,k)符合正态分布，E(i,j,k)也符合正态分布；

(1-5)获取时间-能耗重要性比重θ:(1-θ)；

(1-6)获取给定的时间限制Mb_total和能耗限制Eb_total。

步骤2确定任务的调度顺序，具体包括以下几个子步骤：

(2-1)根据所给任务依赖关系建立有向无循环图(DAG，directed acyclicgraph)G＝{N,E}。DAG中每一个节点代表一个任务，每个有向边代表任务间的依赖关系。有向边e_i,j∈E的权重为任务的执行时间，本发明忽略任务间传输数据所用的时间；

(2-2)计算G中每个任务到结束任务的关键路径长度的平均近似权重，即在计算关键路径长度时，边的权重不再用以往技术中所使用的任务执行时间的平均值，而使用任务在所有处理器的所有电压级别上的执行时间的近似权重的平均值，任务v_i执行时间的近似权重定义如下：

其中，w(v_i)是任务v_i的执行时间的随机变量，符合正态分布，E(w(v_i))执行时间的期望值，Var(w(v_i))为执行时间的方差。我们使用Aw(v_i)的平均值而不是使用以往数据中w(v_i)的平均值；

(2-3)将任务按照递减的顺序排序，得到的顺序作为任务的调度顺序。

步骤3计算每个任务在给定时间限制Mb_total下需满足的时间限制和给定能耗限制Eb_total下需满足的能耗限制，具体包括以下几个子步骤：

(3-1)将G中有向边e_i,j的权重设置为任务v_i执行时间的近似权重的平均值

(3-2)计算此时关键路径的长度ACP_total；

(3-3)计算从起始任务到每个任务v_i的关键路径长度ACP(v_i)；

(3-4)计算每个任务在给定时间限制Mb_total下需满足的时间限制Mb(v_i)，Mb(v_i)的计算方式如下：

$Mb\left(v_i\right)=\frac{ACP\left(v_i\right)}{{\mathrm{ACP}}_{total}}*{\mathrm{Mb}}_{total};$

(3-5)用与计算任务执行时间的近似权重相同的方式，计算每个任务在每个处理器的各个电压级别上的能耗的近似权重，并计算能耗近似权重的平均值为

(3-6)计算每个任务在给定能耗限制Eb_total下需满足的能耗限制Eb(v_i)，Eb(v_i)的计算方式如下：

$Eb\left(v_i\right)=\frac{\overline{Ew\left(v_i\right)}}{\underset{i=1}{\overset{n}{\Sigma }}\overline{Ew\left(v_i\right)}}*{\mathrm{Eb}}_{total}.$

步骤4初次分配，具体包括以下几个子步骤：

(4-1)按顺序从任务调度列表中取出第一个任务v_i；

(4-2)基于已有分配，计算任务v_i在每个处理器PR_j的每个电压级别(v_j,k,f_j,k)上的执行时间满足该任务时间限制Mb(v_i)的概率P_d(i,j,k)；

(4-3)计算任务v_i在每个处理器PR_j的每个电压级别(v_j,k,f_j,k)上的所消耗能耗满足该任务能耗限制Eb(v_i)的概率Pe(i,j,k)；

(4-4)根据给定的时间-能耗重要性比重θ:(1-θ)，计算这个任务的概率加权P(v_i),P(v_i)的计算方式为：

P(v_i)＝P_d(i,j,k)*θ+P_e(i,j,k)*(1-θ)；

(4-5)将任务v_i分配给概率加权P(v_i)最大的处理器及对应的电压级别；

(4-6)重复步骤4直到任务表中的任务全部取完。

步骤5根据任务的个数选取合适的再分配次数d，如n/2次，n为任务的个数。

步骤6再次分配，具体包括以下几个子步骤：

(6-1)随机选取某个任务v_i；

(6-2)维持其他任务的分配不变，计算将该任务分配给每个处理器PR_j的每个电压级别(v_j,k,f_j,k)上的总执行时间不超过时间限制Mb_total的概率Pd_system(i,j,k)；

(6-3)计算将该任务分配给每个处理器PR_j的每个电压级别(v_j,k,f_j,k)上的总能耗不超过能耗限制Eb_total的概率Pe_system(i,j,k)；

(6-4)根据给定的时间-能耗重要性比重θ:(1-θ)，计算此时的系统概率加权P_system，P_system的计算方式如下：

P_system(v_i)＝Pd_system(i,j,k)*θ+Pe_system(i,j,k)*(1-θ)；

(6-5)将该任务分配给使得系统概率加权P_system(v_i)最大的处理器及对应的电压级别；

(6-6)重复步骤6，直到进行了d次。

步骤7完成任务分配，返回任务分配方案。

本领域的技术人员容易理解，以上所述仅为本发明的较佳实施例而已，并不用以限制本发明，凡在本发明的精神和原则之内所作的任何修改、等同替换和改进等，均应包含在本发明的保护范围之内。