本发明涉及异构环境高性能计算机技术领域，特别是一种多相同gpu异构系统环境下的任务调度节能方法。
背景技术：
ict(informationandcommunicationtechnology)行业已成为21世纪社会发展和世界经济增长的重要动力。但其消耗的能量却已占全球耗电量的10％；其碳排放总量则达到了全球碳排放总量的2％～2.5％，在发达国家尤甚，达到10％。而随着全球对ict行业的持续投入，其规模和能耗也将保持增长的趋势。为推动ict产业的绿色低碳环保可持续发展，绿色计算已成为众多国内外研究者的共识。目前，以大数据技术、人工智能技术为代表的ict产业正在不断改变我们的生活、交通、学习以及对世界的认知，使得支撑这些技术发展的gpu(graphicsprocessingunit)异构系统(heterogeneouscomputingsystem，hcs)成为计算机系统的主流。gpu异构系统具有高加速性、易学易懂、系统便于扩展等特点使其发展迅猛，目前被广泛应用于大数据处理、深度学习、云计算、人工智能、无人车驾驶、分子模拟计算等领域，巨大的应用市场也反过来极大地推动了gpu异构系统的发展。典型的gpu异构系统通常由cpu将计算任务分配到gpu进行计算；在由多个gpu组成的计算机系统中，对各个gpu分配的计算任务会极大地影响整个系统的功耗。虽然gpu异构系统的性能功耗比相对于传统的计算机系统有了较大的提升，但在整个计算机系统中其功耗仍占有较大的比例。为顺应ict产业的发展，对gpu异构系统的功耗优化以达到减少hcs功耗的目的，许多学者提出了各种方法和模型。但目前的研究工作仍存在如需要手动改写目标任务代码、异构系统的能耗受任务执行的顺序影响、假设gpu在运行任务是功耗的恒定的及在任务调度前需要对任务进行预先运行以获得参数等问题。
而在任务调度研究方面，可以分为两类：基于任务特征的调度节能技术及对任务调度的节能技术，具体描述如下：
首先，是基于任务特征的调度节能技术。在gpu支持concurrentkernelexecution特征后，其节能技术得到了一种解决思路。lieta首先通过预先运行cudaprofiler工具获得参数ri以判定kernel类别，并以任务类别互补特性为启发实施concurrentkernelexecution节能。qingetal通过建立concurrentkernel之间block个数的比率与能耗间的关系指导gpu节能；通过利用预测block个数比率的方法以及提出的静态估计功耗性能模型以达到节能的目的，但该方法需要转换任务代码。lietal受到任务类别互补特性实施节能的启发，在对任务进行分类后利用建立的能耗节约量回归预测模型以及调度方法达到节能的目的。dongetal通过比较concurrentkernel和顺序kernel的耗能，选择能耗较少的方式执行任务；对于能耗的获取，采用了能耗估计模型和性能估计模型的方法。xieetal和huetal都关注数据中心的节能。xieetal提出递归及分层的互联结构用于平衡吞吐量和功耗。huetal通过峰值负荷调度以达到和促进高能效的数据中心的qos服务。
其次，是任务调度的节能技术。liuandluk通过任务预先运行的方式获得任务和处理器资源参数，利用线性规划方法达到对linpack程序在各个处理器中的节能调度，但该方法需要手动改写目标处理器的代码。bariketal依据kaleemetal提出的分析方法得到任务的特征及执行时间等参数调节负载率达到减少处理器能耗的目的。此后，maetal提出具有动态分配层以及频率调节层的两层能耗管理框架，对比了四种动态分配方案并分析了它们的优劣。wangandren通过线性预测的方法得到任务在各个处理器执行的时间参数，在给定的时间约束下协调处理器之间的负载分配，最后对每个处理器进行频率调整以减少能耗。choietal根据任务的剩余执行时间提出预测程序剩余执行时间的调度方式，并指出greggetal的交替分配调度(alternate-assignmentscheduling，aa)、空闲优先调度(first-freescheduling，ff)以及性能历史调度(performance-historyscheduling，ph)方法的不足，即异构系统的功耗受任务执行的顺序的影响。hamanoetal提出一种动态调度的节能方法，选择能耗延迟积(energydelayproduct，edp)最小的任务分配到对应的处理器上，但方法认为所调度的任务功耗是恒定的。valeryetal的研究表明在移动设备中利用共享内存架构能提高处理器间的协作，进而加速对pca(principalcomponentsanalysis)的计算，从而有效地降低了移动设备的能耗。silbersteinandmaruyama考虑了任务在各个处理器上的能耗，根据有向无环图构造了一个在多个相互依赖任务下的最小能耗调度方法，并在在处理器没有开销时验证了方法的可行性。khalidetal在处理器计算能力非均衡的情况下提出osched调度方法，综合考虑设备的计算能力以及任务的计算需求以实现任务在各个处理器中的负载均衡。jangetal研究了单任务在多处理器环境下的能耗优化以及多任务自适应任务功率感知分配方案，提出单任务下最优任务分配算法以及多任务下最优电压/频率调整方案，文中虽然研究了多任务下的节约能耗方法，但更专注于电压/频率的调整。
综上所述，对于异构系统的节能研究虽然有较大进展，但依然存在着不足。
假设系统中待执行的任务序列为taski(0≤i≤n)，系统中当前可用的处理器资源为gpui(0≤i≤n)，那么系统能耗的可以用式(1)表示：
由式(1)可知，系统能耗可表示为系统中的所有的gpu，cpu和主板消耗的能耗之和，进一步可表示为各自的功率与时间的乘积。对于一组待调度的任务及数量一定的相同gpu而言，待调度任务在不改变任务结构的情况下根据调度算法的不同会产生不同的序列，但不会改变单个任务执行时的功率，即待调度任务序列的平均功耗保持不变。因此，系统能耗可进一步表示为平均功耗
在解决执行时间t最小的问题中，异构系统通常采用aa，ff以及ph等调度方法来解决。aa方法采用循环的方式将任务分配到各个处理器中。ff采用将任务分配到空闲处理器中的动态调度方法。如系统中所有处理器的状态都为空闲，则分配到用户指定的第一个逻辑处理器中；如系统中所有处理器的状态都为忙碌，则任务会等待直到有空闲的处理器可用，然后再进行分配。由于ff考虑了处理器的状态，因此在绝大多数情况下能够得到比aa更好的效果。然而，由于系统当前可用的处理器以及任务执行的顺序不同，因此ff方法和aa方法一样不能保证任务执行顺序的一致性。为了让系统更快地执行任务，ph方法采用了类似更快的处理器获得更多任务的思想，让处理速度慢的处理器获得少量任务而处理速度快的处理器获得大量任务。它依据处理器间执行时间的ratio比值进行调度判断：如果ratio值比预先定义的上限小，则将其放在该处理器上执行；如果ratio值比预先定义的上限大，则用ff的方法分配任务。由于考虑了任务的执行时间，ph方法在执行效果上比aa以及ff更好。但由于ph方法只针对处理器执行速度进行调度，会导致处理器的过度利用和空闲等待。例如，如果所有待执行的任务依据上述计算得到的ratio值全部分配给第一个处理器，那么第一个处理器将会过利用而剩余的处理器将会变得欠利用。choietal指出这种方法存在这样的问题，但是并未提出特定的解决方案。
技术实现要素：
本发明的目的在于，提供一种多相同gpu异构系统环境下的任务调度节能方法。本发明具有降低平均能耗和调度方法更有效的特点。
本发明的技术方案：一种多相同gpu异构系统环境下的任务调度节能方法，包括下述步骤：
a.获取任务执行时间、任务数量及可用gpu数量的信息；
b.利用步骤a获取的信息以均分思想和折半方法对任务按执行时间进行分配。
前述的多相同gpu异构系统环境下的任务调度节能方法所述的步骤a中，获取信息前，先对任务进行分组得到任务组，再获取任务组内的任务执行时间、任务数量及可用gpu数量的信息。
前述的多相同gpu异构系统环境下的任务调度节能方法所述的步骤b具体按下述方法进行：
b1.根据步骤a获取的信息，建立存储任务时间、任务编号、每个处理器对应的处理任务编号及每个处理器累计的执行时间的数组；
b2.求出任务组内任务执行时间的平均值，首先分配单个任务执行时间大于平均值的任务，剩余任务转至步骤b3进行分配；
b3.求出剩余任务的平均时间，再分配单个任务执行时间大于该平均时间的任务；小于该平均时间的任务继续执行步骤b3，直至待分配的任务队列分配完毕。
前述的多相同gpu异构系统环境下的任务调度节能方法中，待步骤b3执行结束，任务被分配到对应的gpu后，将每个gpu的任务队列记录的任务编号分配给对应的gpu。
前述的多相同gpu异构系统环境下的任务调度节能方法中，所述方法接受任务数量的取值范围为：
其中，ntask表示任务数量；
ssystem_memeory表示系统内存总容量,
sgpu_memeory表示系统显存总容量,
n(twait)表示在等待任务到达时间内可接受的任务量；
n(tprocess)表示在处理任务的时间内可处理的任务量。
有益效果
与现有技术相比，本发明为了缓解目前存在的“需要手动改写目标任务代码、异构系统的能耗受任务执行的顺序影响、假设gpu在运行任务是功耗的恒定的、在任务调度前需要对任务进行预先运行以获得参数”的技术问题，以及使hcs能更广泛地应用以适应任务的多样性，采用多相同gpu异构系统进行节能研究，提出任务组内均衡时间的任务节能调度，通过合理分配各个gpu上的任务来减少系统能耗消耗。本发明通过获取程序在各个gpu上的功耗及时间，然后将能耗优化问题转化为调度问题。具体地，首先获取任务执行时间、任务数量以及系统中可用的gpu数量；其次，利用上述信息以均分思想和折半方法对任务按执行时间进行分配。
本发明分析了多相同gpu异构系统环境下节能问题的本质，并将其转化为调度问题。为解决该调度问题引入均分的思想，提出以时间均衡的方式分配组内任务的调度方法。该方法根据任务执行的功耗及时间首先计算选定任务组内所有待执行任务时间的平均值，然后对显著高于阈值的任务优先分配；其次，将剩余的任务分配到累计时间最小的gpu队列并记录对应累计的任务编号；最后，将获得的结果分配到系统中执行。
本发明通过合理划分任务量、考虑任务的执行时间及处理器数量信息以减少系统处理任务的整体执行时间，进而达到式(1)中能耗最小化的目的；此外，本发明将任务根据执行时间平均分配给系统中的各个处理器能够有效地解决系统中的一个或一些处理器的过利用或欠利用的问题，进而使得本发明的调度方法更有效。实验结果表明，与现有方法相比，本发明平均节省8.6％的能量，证明本发明是有效的、合理的、可行的。
为了能够充分说明本发明的性能，发明人将本发明与aa，ff及ph调度方法进行了实验对比分析，在假设输入规模为n、处理器个数为定值的情况下，对aa，ff及ph调度方法的分析可知，它们的时间复杂度都为o(n)；而本发明方法则类似于折半查找所消耗的时间，即本发明方法的时间复杂度为o(nlog2n)，所以本发明方法耗时较多。但执行任务的总时间包含任务调度时间及任务执行时间，通常任务执行时间远远大于任务调度时间，因此在任务执行时间能够显著减少的情况下，可以忽略任务调度时间的增加。实验过程如下：
实验的硬件和软件环境如表1所示：
表1实验的硬件和软件环境
异构系统的硬件环境采用cpu(i5-7500)和gpu(四块nvidiageforcegtx1060显卡)模式；系统内存8gb；gtx1060的架构是pascal，显存6gb，拥有10个streamingmultiprocessors(sm)；每个sm包含128个cuda核，共计1280个cuda核；单卡提供4.4tflops浮点运算能力。软件实验环境为windows10，vs2015以及cuda9.2。
为了更好地进行验证，选取四个典型的cudabenchmark程序进行实验，分别为matrixmultiplication，vectoradd，scalarproducts以及matrixtranspose，它们的具体参数如表2所示。使用hioki3334ac/dc功率计作为系统能耗测量工具，测量的能耗为异构系统的能耗。
表2实验采用的基准程序
选择典型的调度方法进行比较，分别是aa，ff和ph。由于aa和ff调度方式的性能及待执行任务的顺序影响系统能耗，因此采用多次执行求平均值的方法获取比较数据。本文实验环境中的gpu都是相同的，任务执行的顺序会同样地影响ph方法，因此采用同样的方式获取ph方法的能耗数据。bats的实现方法如下，首先在vs2015中进行实现；在得到bats的输出结果后，对程序序列重新编程运行以获取功耗数据，将运行bats的能耗记为jbats，任务运行的能耗记为jtasks，最终将系统能耗记为jbats和jtasks之和。
用式(2)确定任务数量，为了验证方法的有效性，系统等待时间内所接受的任务量不是关注重点，因此取n(twait)为∞。而对于n(tprocess)，综合处理时间及任务量的关系以获得合适的值。为此采用实验对比的方法获得，如图1所示。由图可见，任务数0～20时调度方法消耗的时间最少；任务数20～80时消耗的时间相对稳定；任务数为100时，消耗的时间有一个明显的拐点。为了获得最佳的性能，调度任务的时间应该足够短，并且调度更多的任务。结合式(2)、表1及表2的参数，其中
表3展示了任务在不同调度策略以及不同输入情况下的平均能耗，对比的方法是当前典型的调度策略。调度策略所使用的输入情况考虑了典型的任务数以及每个任务的典型输入情况。
表3不同调度方法在不同输入情况下的能耗消耗情况
在表3中，casea的输入规模为80个任务数，其中mm，va，sp和mt的数量分别为20个；mm的输入范围为100×5120～400×10240；va的输入范围为20～50m；sp的输入范围为16～32m；mt的输入范围为64～144m。由casea的输入规模可以直观地看出，aa的能耗最高，其次是ff和ph，能耗最小的为本发明方法。aa方法能耗较高是由于仅仅考虑了以循环的方式分配任务，缺乏对处理器信息的考虑。对于ph方法，由于所依赖的ratio值在实验环境中是相同的，因此ph方法在多个相同gpu的情况下退化为ff方法，所以ff和ph方法的能耗几乎相同。由于考虑了处理器的信息，因此ff和ph方法的实验效果优于aa方法。和aa，ff和ph方法相比，本发明方法以均分执行时间的方式将任务分配给处理器且在调度的结果上是确定的，所测得的能耗是一次性测量，由于综合考虑了任务及处理器信息，因而能耗最低。在80个输入任务数及对应输入范围下，本发明方法比aa方法平均节约11.17％的能耗，比ff和ph方法平均节约5.70％的能耗。
caseb的输入规模为80个任务数，其中mm，va，sp和mt都为20个；mm的输入范围为100×5120～8100×32400；va的输入范围为20～200m；sp的输入范围为16～128m；mt的输入范围为64～484m。可以看出，在不改变输入任务数量以及改变输入规模的情况下，aa方法依然能耗最高，ff和ph次之，本发明方法与其它方法相比依然能耗最低。这种现象产生的原因和casea相同，不再赘述。在相同任务数量以及改变输入规模的情况下，本发明方法比aa方法平均节约12.41％的能耗，比ff和ph方法平均节约5.86％的能耗。
casec的输入规模的任务数为72个，其中mm，va，sp和mt都为18；mm的输入范围为100×5120～8100×68400；va的输入范围为20～400m；sp的输入范围为16～384m；mt的输入范围为64～625m。可以看到，改变任务数量及输入范围后，各种方法所呈现的能耗趋势与casea和caseb的类似，产生的原因同前，不再赘述。在改变输入任务数及对应输入范围下，本发明方法比aa方法平均节约11.05％的能耗，比ff和ph方法平均节约5.39％的能耗。
图2展示了本发明方法在casea输入规模情况下对单个gpu的内存变化情况，共经历四次循环分配：第一次循环分配序号1～7的任务；第二次循环分配序号8～11的任务；第三次循环分配序号12～16的任务；第四次循环分配序号17～18的任务。总体上看，随着分配任务越多，内存占用量就越大。在序号1～7的任务分配中，内存分配量有突然增加的趋势，而后面的内存分配量的增加相对平缓，原因在于本发明方法的分配以时间为主而非以内存占用量为主。
图3至图5展示了四个任务在不同的调度策略以及不同输入情况下各个处理器平均执行时间的比率。图3展示了对应于表3中casea输入规模在任务数量为80个情况下各个处理器执行时间的比率。可以看出，aa方法的处理器有34.50％执行时间的差距，最大的执行时间比率为46.38％，最小的执行时间比率为11.88％。ff和ph方法中存在17.47％的时间差距，最大的执行时间比率为35.92％，最小的执行时间比率为18.45％。本发明方法中有0.02％的时间差距，最大的执行时间比率为25.01％，最小的执行时间比率为24.99％。由执行时间的差别可以看出，本发明方法给四个gpu分配的任务是较均匀的，使得执行整体任务所消耗的时间较少，从侧面验证了表3中本发明方法在casea输入规模下功耗较小的原因。
图4展示了对应于表3中caseb输入规模的各个处理器执行时间的比率。可以看出，aa方法中的最大的执行时间和最小的执行时间相差31.68％，ff和ph方法中的最大的执行时间和最小的执行时间相差17.53％，而本发明方法中的最大比率和最小比率两者只相差0.12％。由执行时间的差别可以看出，本发明方法给四个gpu分配的任务是比较均匀的，使得执行整体任务所消耗的时间较少，从侧面验证了表3中本发明方法在caseb输入规模下功耗较小的原因。
图5展示了对应于表3中casec输入规模下的各个处理器执行时间的比率。可以看出，aa方法中的最大的执行时间比率为46.04％，最小的执行时间比率为13.24％，两者相差32.80％。ff和ph方法中最大的执行时间比率为35.20％，最小的执行时间比率为19.41％，两者相差15.79％。而本发明方法中最大的执行时间比率与最小的执行时间比率相同。从相差时间的比率上来看，bats较aa，ff和ph方法对任务的分配更加均匀合理，因此从侧面验证了表3中本发明方法在casec输入规模下功耗较小的原因。
综上所述，在改变输入规模以及输入范围的情况下，本发明方法较aa，ff和ph能够均匀分配任务且较aa方法平均节能11.55％，较ff和ph方法平均节能5.656％，总体平均节能8.6％。证明本发明方法是有效的、合理的，也是可行的。
附图说明
图1是任务量与执行时间的关系；
图2是本发明方法使用内存变化情况；
图3是表3中casea输入规模的各个处理器执行时间的比率；
图4是表3中caseb输入规模的各个处理器执行时间的比率；
图5是表3中casec输入规模的各个处理器执行时间的比率。
具体实施方式
下面结合附图和实施例对本发明作进一步的说明，但并不作为对本发明限制的依据。
实施例。一种多相同gpu异构系统环境下的任务调度节能方法，包括下述步骤：
a.获取任务执行时间、任务数量及可用gpu数量的信息；
b.利用步骤a获取的信息以均分思想和折半方法对任务按执行时间进行分配。
前述的步骤a中，获取信息前，先对任务进行分组得到任务组，再获取任务组内的任务执行时间、任务数量及可用gpu数量的信息。
前述的步骤b具体按下述方法进行：
b1.根据步骤a获取的信息，建立存储任务时间、任务编号、每个处理器对应的处理任务编号及每个处理器累计的执行时间的数组；
b2.求出任务组内任务执行时间的平均值，首先分配单个任务执行时间大于平均值(该处的平均值，也可以是根据经验设定的阈值，本发明实验中，就使用了经验设定)的任务，剩余任务转至步骤b3进行分配；
b3.求出剩余任务的平均时间，再分配单个任务执行时间大于该平均时间的任务；小于该平均时间的任务继续执行步骤b3，直至待分配的任务队列分配完毕。
待步骤b3执行结束，任务被分配到对应的gpu后，将每个gpu的任务队列记录的任务编号分配给对应的gpu。
所述方法接受任务数量的取值范围为：
其中，ntask表示任务数量；
ssystem_memeory表示系统内存总容量,
sgpu_memeory表示系统显存总容量,
n(twait)表示在等待任务到达时间内可接受的任务量；
n(tprocess)表示在处理任务的时间内可处理的任务量。
任务数量的多少影响bats方法的性能。对于任务数量，bats的最小接受量为1，最大接受量受系统内存容量大小、单个gpu显存的容量大小、等待任务到达时间以及处理任务的时间等因素的影响。系统内存容量过小将限制系统接受任务的能力，可以用系统内存总容量除以任务平均内存消耗来表示，即：
由于本发明采用了均分思想及折半查找的方法，依据任务时间大小分配任务，因此对系统能耗的影响也就最小。具体地，任务调度节能方法伪代码描述如表4所示：
表4
表4中，调度方法的输入为任务列表和gpu的数量，输出为各个gpu的处理任务量。第1～3行为完成本发明方法所定义的一些变量，其中k表示当前迭代中的总任务量；kn表示gpu序号；cuindex表示算法迭代中的gpu序号；gettasktime(p[i])为获取任务的执行时间；存储任务序列时间的采用二维数组tgpu[i][1]进行存储；任务编号采用tgpu[i][0]进行存储。gpu任务累计时间accmpcu[numpu]用于判断任务应放到那个gpu中去执行。存储每个gpu应处理的任务编号用pgpu[numpu][k]表示。第4行和第5行分别为获取任务的执行时间、任务编号及计算平均时间。第6～14行筛选单个任务执行时间大于阈值的任务以防止某个gpu出现过利用的情况。第16～29行依照待执行程序时间的平均值以及折半调度的思想对任务进行循环分配；其中第18-26行分配大于平均时间的任务，存储小于平均时间的任务为下次的循环分配作准备。
对于第8行以及第21行中分配任务的函数assigntasks()，其伪代码描述如表5所示。其输入为gpu编号、任务编号以及任务的执行时间；输出为当前任务所在的处理器序列pgpu[][]以及各个处理器要执行的任务的累计时间accmpcu[]。第1～8行寻找对应的gpu编号为存储gpu的编号作准备。第9行为对应的gpu存储对应任务编号。第10行将任务时间累加到对应gpu的时间累加器中。
表5
1.一种多相同gpu异构系统环境下的任务调度节能方法，其特征在于：包括下述步骤：
a.获取任务执行时间、任务数量及可用gpu数量的信息；
b.利用步骤a获取的信息以均分思想和折半方法对任务按执行时间进行分配。
2.根据权利要求1所述的多相同gpu异构系统环境下的任务调度节能方法，其特征在于：步骤a中，获取信息前，先对任务进行分组得到任务组，再获取任务组内的任务执行时间、任务数量及可用gpu数量的信息。
3.根据权利要求2所述的多相同gpu异构系统环境下的任务调度节能方法，其特征在于：所述的步骤b具体按下述方法进行：
b1.根据步骤a获取的信息，建立存储任务时间、任务编号、每个处理器对应的处理任务编号及每个处理器累计的执行时间的数组；
b2.求出任务组内任务执行时间的平均值，首先分配单个任务执行时间大于平均值的任务，剩余任务转至步骤b3进行分配；
b3.求出剩余任务的平均时间，再分配单个任务执行时间大于该平均时间的任务；小于该平均时间的任务继续执行步骤b3，直至待分配的任务队列分配完毕。
4.根据权利要求3所述的多相同gpu异构系统环境下的任务调度节能方法，其特征在于：待步骤b3执行结束，任务被分配到对应的gpu后，将每个gpu的任务队列记录的任务编号分配给对应的gpu。
5.根据权利要求4所述的多相同gpu异构系统环境下的任务调度节能方法，其特征在于：所述方法接受任务数量的取值范围为：
其中，ntask表示任务数量；
ssystem_memeory表示系统内存总容量,
sgpu_memeory表示系统显存总容量,
n(twait)表示在等待任务到达时间内可接受的任务量；
n(tprocess)表示在处理任务的时间内可处理的任务量。
技术总结