面向混合计算环境的功耗感知的并行应用调度系统及方法

摘要

本发明公开了面向混合计算环境的功耗感知的并行应用调度系统及方法，所述系统包括用户层、调度层和资源层，所述用户层将用户请求传输给调度层，所述调度层将执行任务及其所需数据传输给资源层，所述调度层包括解析模块、任务聚类模块、处理单元选择分析模块和任务分配模块，所述解析模块的解析结果传输给任务聚类模块，所述任务聚类模块的聚类结果传输给处理单元选择分析模块，所述处理单元选择分析模块包括时间计算模块和功耗计算模块，其选择分析的结果传输给任务分配模块，所述资源层包括若干个DVS处理单元和若干个non-DVS处理单元。它具有调度目标为在最小化应用执行时间的前提下，兼顾系统的DVS和non-DVS混合特性并尽可能大地降低应用的执行能耗的优点。

说明书

技术领域

本发明涉及高性能计算软件节能技术领域，尤其涉及一种面向混合计算环境的功耗感知 的并行应用调度系统及方法。

背景技术

随着计算机硬件成本大幅降低和Linux集群优势日益突出，高性能计算系统部署规模越 来越大，但其对能源的巨大消耗也远远超过了人们的想象。据统计，一个每秒运行10亿次的 超级计算中心的电费每年近400万元；一台服务器3年内所消耗掉的电量成本可能会超过服 务器当初的采购成本。耗电量的增加，不但带来运行成本的增加，而且直接因为设备温度的 增加造成器件寿命的缩短，使计算机的可靠性降低。根据保护国际（CI）的数据，400万元 的用电量相当于每年向大气排放约5500吨的二氧化碳。因此，无论从经济、技术还是环境角 度，有效的功耗管理将是高性能计算领域迫切需要解决的问题。

高性能计算领域的功耗管理主要集中在CPU，因为其承担的计算任务往往都是超出常规 的海量计算。为解决CPU的高功耗问题，动态电压调整（DVS）是有效功耗设计的主要方向。 DVS是根据处理单元工作状态调整功耗的有效方式：CMOS电路中供应电压的降低导致功耗 的平方下降。异构体系结构是万万亿次级计算硬件的基础，可最大限度发挥并行处理的优势， 但由于其资源计算能力和通信带宽的差异又增加了应用执行的复杂性。就功耗感知设计来说， 异构系统的处理单元可能支持DVS技术（记为DVS处理单元），也有部分遗留处理单元不支 持DVS技术（记为non-DVS处理单元）。本发明称这种既拥有DVS处理单元又拥有non-DVS 处理单元的异构计算环境为混合DVS/non-DVS计算环境。

并行应用是高性能计算环境下典型的应用模型，其属于任务之间存在数据依赖的优先约 束应用。以往并行应用调度方法主要集中在传统的调度指标，如最小化完成时间，最小化执 行成本，负载均衡等，近来大家开始将兴趣转向调度中的功耗管理。功耗感知的调度是指在 调度过程中考虑通过DVS和动态电源管理（DPM）等系统层节能手段降低应用执行所消耗 的能量，即将能耗作为调度的评价指标之一。动态电源管理（DPM）主要通过关闭空闲的处 理单元或者使处理单元处于休眠状态来降低由泄漏电流引起的静态能耗。

功耗感知的调度最早是无线传感器网络、嵌入式系统、移动系统需要考虑的主要问题， 因为它们靠电池供电，不是一直有充足的电源供应。不同于以往领域，高性能计算系统功耗 感知的调度不仅要节省应用消耗的电能，还要保证其调度性能的不降低或者最小降低。按照 调度应用的不同，功耗感知的调度分为面向独立任务的调度和面向优先约束应用的调度。面 向独立任务的功耗感知调度方法已被广泛提出，包括时间限制的能耗优化调度，能耗限制的 时间优化调度，兼顾时间和能耗优化的调度和考虑静态能耗的调度等。国内面向独立任务的 功耗感知调度主要针对基于DVS技术的独立周期性任务集合。优先约束应用一般抽象为依赖 任务图，细分为控制依赖任务图和数据依赖任务图。面向控制依赖任务的调度完全不涉及任 务之间的数据传输，其功耗感知调度目前已得到较完美的解决。

面向数据依赖任务的部分功耗感知调度方法在满足用户需求的同时很好地提高了系统的 能耗有效性，但是仍存在一些局限性：

（1）多数方法要么单纯考虑支持DVS的系统，要么单纯考虑不支持DVS的系统，很少 考虑混合DVS/non-DVS系统的调度。即使部分方法兼顾了系统的DVS/non-DVS混合性，但 其面向具有到达时间、时间期限和利用率限制的独立实时任务，而非存在数据依赖的并行应 用。

（2）多数方法忽略了通信能耗的优化或者通信时间段内计算能耗的进一步降低。以高性 能计算为基础的现代科学领域是一个以数据为中心、计算密集、分析密集以及可视化密集的 领域，如生物信息学、环境科学、天文学等，因此，高性能计算环境应更强调数据依赖和通 信能耗的重要性。

（3）多数方法未考虑处理单元的静态能耗优化。随着芯片微型化和多核技术的发展，泄 漏电流引起的静态能耗由于单位工艺尺寸内电子组件数的增加而呈指数增长。

发明内容

本发明的目的就是为了解决上述问题，提供一种面向混合计算环境的功耗感知的并行应 用调度系统及方法，它具有调度目标为在最小化应用执行时间的前提下，兼顾系统的DVS和 non-DVS混合特性并尽可能大地降低应用的执行能耗，不仅包括任务执行时的计算能耗、通 信能耗，还包括通信时间段和空闲时间段的静态能耗的优点。

为了实现上述目的，本发明采用如下技术方案：

面向混合计算环境的功耗感知的并行应用调度系统，包括用户层、调度层和资源层，所 述用户层将用户请求传输给调度层，所述调度层将执行任务及其所需数据传输给资源层，所 述调度层包括解析模块、任务聚类模块、处理单元选择分析模块和任务分配模块，所述解析 模块的解析结果传输给任务聚类模块，所述任务聚类模块的聚类结果传输给处理单元选择分 析模块，所述处理单元选择分析模块包括时间计算模块和功耗计算模块，其选择分析的结果 传输给任务分配模块，所述资源层包括若干个DVS处理单元和若干个non-DVS处理单元。

所述用户层负责提交用户应用。

所述调度层负责解析用户提交的应用、集成调度方法，并根据调度目标尽量为各个任务 选择最佳处理单元。

所述资源层负责具体执行任务和数据传输。

所述解析模块负责将并行应用划分为单个的任务、对象和数据依赖。

所述任务聚类模块负责将任务划分为若干个任务组、确定处理单元数目和应用整体执行 时间，并达到降低通信时间和通信能耗的目的。

所述处理单元选择分析模块负责确定聚类得到的任务组应该被放置到DVS处理单元还 是non-DVS处理单元上。本发明调度目标涉及时间和功耗指标，因此处理单元选择分析模块 包括时间计算模块和功耗计算模块。

所述时间计算模块用于计算处理单元选择过程中各个任务的执行时间，以及任务组内任 务之间的空闲时间和通信时间等。

所述功耗计算模块用于计算处理单元选择过程中各个任务的计算能耗、通信和空闲时间 段内的静态能耗，以及执行DPM技术的实施能耗等。鉴于同一个任务组无论放置到DVS处 理单元还是non-DVS处理单元上，任务之间的通信能耗相同，故本发明中的通信能耗忽略计 算。

所述任务分配模块负责将任务组分配到相应的处理单元，并执行对应的系统层节能技术。

所述DVS处理单元和non-DVS处理单元负责具体执行任务，其中DVS处理单元具有动 态调节电压的功能，non-DVS处理单元可实施有条件的关闭或休眠。

上述系统所采用的调度方法，主要包括如下步骤：

步骤（1）：用户层的用户提交并行应用；调度层的解析模块将并行应用解析为单个的任 务、对象和数据依赖；任务聚类模块进行任务聚类，将任务划分成若干个任务组，并决定处 理单元数目和应用的最小完成时间；

步骤（2）：处理单元选择分析模块对处理单元进行选择，功耗计算模块根据调度目标对 功耗进行计算，时间计算模块根据调度目标对时间指标进行计算，分析每个任务组适合分配 的处理单元类型，并考虑某类处理单元资源有限时的情形，以实现处理单元的选择；所述处 理单元类型包括DVS处理单元和non-DVS处理单元；

步骤（3）：任务分配模块执行任务分配：分配到DVS处理单元的任务组，DVS处理单 元执行DVS技术；分配到non-DVS处理单元的任务组，non-DVS处理单元实施DPM技术； 资源层的处理单元根据DVS和DPM分析结果具体执行任务，同时网络资源传输所需数据。

所述步骤（1）中的任务聚类方法包括DSC和CASS-II。

所述步骤（1）中任务聚类的输入为并行应用和混合系统，具体流程如下：

步骤（11）：从并行应用的入口开始为每个任务计算参数top值，其含义为当前任务T_i到入 口任务T_in的最大距离：

${\mathrm{top}}_i=\left(\begin{array}{cc}0& T_i=T_{\mathrm{in}}\\ \max \{{\mathrm{top}}_j+t_j+t_{\mathrm{ji}}\},e_{\mathrm{ji}}\in ϵ& \mathrm{otherwise}\end{array}\right)---\left(5\right)$

步骤（12）：从下到上逐步聚类，直至入口任务T_in：从出口任务T_out开始，依次为每个任 务计算参数bottom值，其含义为当前任务T_j到出口任务T_out的最大距离：

${\mathrm{bottom}}_j=\left(\begin{array}{cc}{t}_j& T_j=T_{\mathrm{out}}\\ \max \{{\mathrm{bottom}}_i+t_{\mathrm{ji}}+t_j\},e_{\mathrm{ji}}\in ϵ& \mathrm{otherwise}\end{array}\right)---\left(6\right)$

若某任务所有后继的bottom值计算完成，则标记该任务为当前任务，其中决定当前任务 bottom值的直接后继称为主导后继；

计算所有当前任务的优先级pr_i＝top_i+bottom_i，选择pr值最大的当前任务与其主导后继 所在的任务组进行试合并：若当前任务组中所有任务的bottom值均不增加，则实施合并；否 则，该任务单独成组。

任务聚类结束，输出值为聚类后的任务分组及最小执行时间ms。

所述步骤（2）包括以下操作内容：

步骤（21）：任务之间存在优先约束关系，则任务聚类后某些任务会存在松弛时间，某些 任务组内会存在空闲时间；根据步骤（1）的聚类结果，确定任务类型为关键任务还是非关键 任务，并找出任务组内的通信时间段和空闲时间段；所述关键任务是指决定应用最小完成时 间的任务；

步骤（22）：分析并形式化DVS和DPM技术的实施方法及条件；

步骤（23）：处理单元选择分析模块根据处理单元选择的原则对处理单元进行选择；所述 处理单元选择的原则如下：

如果任务组内为关键任务，选择non-DVS处理单元；

如果任务组内有非关键任务或者通信时间段，选择DVS处理单元；

如果任务组内不仅有非关键任务或通信时间段，还有空闲时间段，且空闲时间长度不满 足DPM执行条件，选择DVS处理单元；

如果任务组内不仅有非关键任务或通信时间段，还有空闲时间段，且空闲时间长度满足 DPM执行条件，则进入步骤（24）分情况讨论；

步骤（24）：针对步骤（23）中需要分情况讨论的任务组，通过对该调度问题形式化并分 析找到任务组分别分配到DVS处理单元和non-DVS处理单元时能耗值的大小关系，实现处 理单元的选择。

所述步骤（3）中

对分配到DVS处理单元的非关键任务按照操作频率实施电压扩展，将空闲时间段和通信 时间段的电压降为最低；

对分配到non-DVS处理单元的任务组的空闲时间段，若其满足DPM的实施条件，则在 该段时间将non-DVS处理单元关闭。

所述步骤（21）中需要的几个参数及其形式化定义：

任务最早开始时间：对给定的任务，其最早开始时间是指该任务在不延长应用整体 执行时间时最早开始执行的时间，表示如下：

$t_i^{\mathrm{est}}=\left(\begin{array}{cc}0& T_i=T_{\mathrm{in}}\\ \max \{t_j^{\mathrm{ct}}+t_{\mathrm{ji}}\},e_{\mathrm{ji}}\in ϵ& \mathrm{otherwise}\end{array}\right)---\left(7\right)$

任务最迟完成时间：对给定的任务，其最迟完成时间是指该任务在不延长应用整体 执行时间时最迟应该完成的时间，表示如下：

$t_i^{\mathrm{lct}}=\left(\begin{array}{cc}\mathrm{ms}& T_i=T_{\mathrm{out}}\\ \min \{(t_j^{\mathrm{st}}-t_{\mathrm{ij}}),t_k^{\mathrm{st}}\},e_{\mathrm{ij}}\in ϵ,P\left(T_i\right)=P\left(T_k\right)& \mathrm{otherwise}\end{array}\right)---\left(8\right)$

其中任务T_j为任务T_i的后继任务，任务T_k为任务T_i的虚后继任务。虚后继任务是指与任务T_i分配到同一处理单元且在任务T_i之后执行的并行任务。

松弛时间：对给定的任务，其只需要在某个时间段内完成而不会影响应用的整体执 行时间，则称这段时间为松弛时间，表示如下：

$t_i^{\mathrm{slack}}=t_i^{\mathrm{lct}}-t_i^{\mathrm{est}}---\left(9\right)$

关键/非关键任务：对给定的任务，若其决定应用的整体执行时间，称为关键任务； 否则，为非关键任务，表示如下：

$T_i\mathrm{is}\left(\begin{array}{cc}\mathrm{critical>}& t_i^{\mathrm{slack}}=t_i\\ \mathrm{non}-\mathrm{critical>}& \mathrm{otherwise}\end{array}\right)---\left(10\right)$

所述步骤（22）的具体步骤如下：

对非关键任务，在非关键任务的松弛时间内对频率/电压实施扩展，降低其计算能耗且不 影响应用的整体执行时间；

在空闲阶段，若关闭处理单元所节省的能耗，既能抵消关闭处理单元所需的时间，又能 弥补关闭处理单元所需的能耗，则满足DPM执行的条件；

对DVS技术，实施方法为将任务运行的频率/电压扩展，通过控制操作频率，确定实施 DVS的频率值；

对给定的非关键任务，所述操作频率是指当其既能够最小化应用的执行时间又能够 最大程度地减少应用执行能耗时的运行频率，表示如下：

$f_i^{\mathrm{slack}}=f_H{t}_i/t_i^{\mathrm{slack}}---\left(11\right)$

对DPM技术，实施方法为将空闲时间段关闭，通过使空闲时间大于空闲时间阈值的方 法满足降低执行能耗且不延长执行时间的要求，从而保证抵消实施DPM的时间和能耗成本； 所述空闲时间阈值的求解方法：

t_threshold＝max{t′，e′/p_s}    (12)

其中e′/p_s为处理单元消耗e′能量所需的最少空闲时间。

所述步骤（24）中对混合计算环境下的调度问题形式化，找到任务组分别分配到DVS处 理单元和non-DVS处理单元时能耗值的大小关系，进行处理单元选择，具体处理单元的选择 依据如下：

步骤（241）：通过步骤（21）的分析知，任务组中存在关键任务、非关键任务、通信阶 段和空闲阶段；首先计算当任务组被分别分配给non-DVS处理单元与DVS处理单元时，其 对应的非关键任务、通信阶段、空闲阶段，以及任务组除去非关键任务、关键任务、通信阶 段和空间阶段后的剩余环节所消耗的能耗差的大小，分别记为z₁，z₂，z₃，z₄；

步骤（242）：如果z₄≥0，那么任务组放到DVS处理单元；如果z₄＜0，还要考虑公式 （23）是否成立，如果公式（23）成立那么该任务组被分配给non-DVS处理单元，如果公式 （23）不成立，那么该任务组被分配给DVS处理单元；

当任务组被分别分配给non-DVS处理单元与DVS处理单元时，其非关键任务所消耗的 能耗差z₁计算方法如下：

$z_1=p_H{\Sigma }_{i=1}^I{t}_{\mathrm{nc}}^i-{\Sigma }_{i=1}^I{p}_{\mathrm{slack}}^i{t}_i^{\mathrm{slack}}>0---\left(19\right);$

当任务组被分别分配给non-DVS处理单元与DVS处理单元时，其通信阶段所消耗的能 耗差z₂的计算方法如下：

$z_2=p_s^H{\Sigma }_{j=1}^J{t}_{\mathrm{comm}}^j-p_s^1{\Sigma }_{j=1}^{J_1}{t}_{\mathrm{comm}}^j>0---\left(20\right);$

当任务组被分别分配给non-DVS处理单元与DVS处理单元时，其空闲阶段所消耗的能 耗差z₃的计算方法如下：

$z_3=p_s^H{\Sigma }_{k=1}^{K_2}{t}_{\mathrm{idle}}^k-p_s^1{\Sigma }_{k=1}^{K_2}{t}_{{\mathrm{idle}}^{\prime }}^k>0---\left(21\right)$

当任务组被分别分配给non-DVS处理单元与DVS处理单元时，任务组除去非关键任务、 关键任务、通信阶段和空间阶段后的剩余环节所消耗的能耗差z₄的计算方法如下：

$z_4=e^{\prime }{K}_1-p_s^1{\Sigma }_{k=K_2+1}^K{t}_{{\mathrm{idle}}^{\prime }}^k---\left(22\right)$

公式（23）为：

$p_s^1{\Sigma }_{k=K_2+1}^K{t}_{{\mathrm{idle}}^{\prime }}^k\ge (z_1+z_2+z_3+e^{\prime }{K}_1)---\left(23\right).$

所述步骤（24）的公式的推导过程如下：

分配变量x_i定义为：

则调度问题形式化为：

$\min {\Sigma }_{i=1}^R(E_i^{\prime }(1-x_i)+E_i{x}_i)---\left(14\right)$

其中E′_i是组C_i分配到non-DVS处理单元时的能耗值，E_i是组C_i分配到DVS处理单元时的 能耗值。一种特殊情况为：若处理单元数目有限，则优先选择优先级别高的任务组放置到其 最佳处理单元类型上。任务组的优先级定义为：

Pr_i＝|E′_i-E_i|    （15）

下面给出E′_i和E_i的计算方法。假设对某个任务组，其具有I个非关键任务，J个通信阶段， K个空闲阶段，Y个关键任务，其对应的时间长度分别表示为其中空闲阶段 按照空闲时间长度的非降序排列，即初始能耗表示为：

$E_{\mathrm{init}}=p_H({\Sigma }_{i=1}^I{t}_{\mathrm{nc}}^i+{\Sigma }_{y=1}^Y{t}_c^y)+p_s^H({\Sigma }_{j=1}^J{t}_{\mathrm{comm}}^j+{\Sigma }_{k=1}^K{t}_{\mathrm{idle}}^k)---\left(16\right)$

其中p_H和分别表示最高电压时的功耗和静态功耗值。

若将任务组放至non-DVS处理单元且满足t_idle＞t_threshold的空闲阶段数目为K₁，则处理单 元可在K₁个时间段内关闭，则能耗值变为：

$E^{\prime }=p_H({\Sigma }_{i=1}^I{t}_{\mathrm{nc}}^i+{\Sigma }_{y=1}^Y{t}_c^y)+e^{\prime }{K}_1+p_s^H({\Sigma }_{j=1}^J{t}_{\mathrm{comm}}^j+{\Sigma }_{k=1}^{K-K_1}{t}_{\mathrm{idle}}^k)---\left(17\right)$

若将任务组放至DVS处理单元，在空闲和通信时间段，降低频率/电压至最低；对非关 键任务按照公式（11）调整频率，则能耗值变为：

$E={\Sigma }_{i=1}^I\left(p_{\mathrm{slack}}^i{t}_i^{\mathrm{slack}}\right)+p_s^1({\Sigma }_{j=1}^{J_1}{t}_{\mathrm{comm}}^j+{\Sigma }_{k=1}^K{t}_{{\mathrm{idle}}^{\prime }}^k)+p_H{\Sigma }_{y=1}^Y{t}_c^y---\left(18\right)$

其中是非关键任务在操作频率时的功耗值，是最低频率/电压时的静态功耗值。当 然，松弛非关键任务会覆盖部分通信和空闲时间。由后继任务等待数据到达引起的非关键任 务会覆盖通信阶段，因此，在公式（18）中通信阶段的个数变为J₁且J₁＜J。由具有相同后继 的并行任务同步引起的非关键任务，其作为数据发送者会占据部分空闲时间，因此，公式（18） 使用表示空闲时间且$t_{{\mathrm{idle}}^{\prime }}^k\le t_{\mathrm{idle}}^k.$

至于空闲阶段的数目，执行DVS后与执行DVS前是相同的，这是因为任务执行过程中 不存在空闲阶段，空闲阶段只出现在任务组的开始或结束，这与最小化应用执行时间的原则 是一致的。由此推出，对每个任务组k≤2是成立的。

根据公式（17）和（18），寻找(E′-E)的规律。对关键任务，无论其被分配到DVS还是 non-DVS处理单元，能耗值均是相同的。从公式（11），即p＝(1＋β)cv²f和推 知，对非关键任务：

$z_1=p_H{\Sigma }_{i=1}^I{t}_{\mathrm{nc}}^i-{\Sigma }_{i=1}^I{p}_{\mathrm{slack}}^i{t}_i^{\mathrm{slack}}>0---\left(19\right)$

对通信阶段，由且J₁＜J得知：

$z_2=p_s^H{\Sigma }_{j=1}^J{t}_{\mathrm{comm}}^j-p_s^1{\Sigma }_{j=1}^{J_1}{t}_{\mathrm{comm}}^j>0---\left(20\right)$

对空闲阶段，其中K₂＝K-K₁个不满足DPM实施条件，可推出：

$z_3=p_s^H{\Sigma }_{k=1}^{K_2}{t}_{\mathrm{idle}}^k-p_s^1{\Sigma }_{k=1}^{K_2}{t}_{{\mathrm{idle}}^{\prime }}^k>0---\left(21\right)$

对(E′-E)的最后一部分，表示为：

$z_4=e^{\prime }{K}_1-p_s^1{\Sigma }_{k=K_2+1}^K{t}_{{\mathrm{idle}}^{\prime }}^k---\left(22\right)$

因此，若一个任务组被分配给non-DVS处理单元，满足DPM条件的空闲时间一定符合：

$p_s^1{\Sigma }_{k=K_2+1}^K{t}_{{\mathrm{idle}}^{\prime }}^k\ge (z_1+z_2+z_3+e^{\prime }{K}_1)---\left(23\right)$

即只要左边小于右边的任何一项，该组任务即可被分配到DVS处理单元上。

本发明的有益效果：

1本发明面向并行应用，并创新性地兼顾了系统的DVS/non-DVS混合性；

2使用DSC和CASS-II方法对并行应用实施任务聚类，保证应用执行时间的最小化和通 信成本降低；

3通过提出任务组优先级的概念，将调度方法扩展到某类处理单元资源紧张的情况，有 效证明了本方法的通用性；

4本发明在计算参数任务开始时间和最迟完成时间时，不仅如以往方法一样考虑了前驱 任务或后继任务的影响，还兼顾了与其分配到同一处理单元的并行任务的制约，使其更精确 地确定了任务组中的关键/非关键任务，以最大程度地接近最优解；

5对给定的应用，鉴于空闲阶段的数目最多为2，该调度方法可快速地判定任务组应该 被分配给哪类处理单元，尤其是对固定参数的系统，因为其关系可通过简单的实验得出；

6通过DVS和DPM技术，本发明不仅降低了任务执行的动态能耗，而且兼顾了静态能 耗，因此不论任务组分配到哪类处理单元上，均可以适时降低其整体能耗。

附图说明

图1为本发明的系统框图；

图2为本发明的流程图；

图3为一个并行应用实例的示意图；

图4为图3给定实例的任务聚类结果图；

图5为图3给定实例的调度结果图。

具体实施方式

下面结合附图与实施例对本发明作进一步说明。

首先建立混合计算环境下并行应用的功耗感知调度所需的系统模型，该模型包括：混合 DVS/non-DVS计算系统模型，并行应用模型和功耗模型。

混合DVS/non-DVS计算系统考虑与调度方法关联密切的处理单元和网络资源，模型描述 为：混合DVS/non-DVS计算系统由DVS处理单元和non-DVS处理单元组成，形式化为 ，其中P_l和P′_m分别表示DVS和non-DVS处理单元；

所有DVS处理单元同构，每个处理单元有H个离散电压，表示为{v₁...v_H}，其对应的时钟频率和执行速度表示为{f₁...f_H}和{s₁...s_H}；每个处理单元可单独调节电压，电压 /频率转换的成本不计；关闭或打开DVS处理单元则消耗巨大的时间和能耗成本，表示为 t＝∞，e＝∞；

所有non-DVS处理单元同构，每个处理单元具有固定的电压v′、频率f′和速度s′，为简化 模型，设定其值为v′＝v_H，f′＝f_H，s′＝s_H；non-DVS处理单元有三种状态：活动、空闲和关闭； 处理单元处于活动状态，消耗计算能耗，包括动态能耗和静态能耗；处理单元没有任务执行 时，处于空闲状态，消耗静态能耗；关闭状态时不消耗任何能耗，但关闭和开启处理单元需 要耗费定量的时间和能耗，记为t′和e′；

所有处理单元通过网络资源连接，其数据传输速度为b（Mb/s），单位数据通信功耗为p_c（J/Mb）；在数据传输过程中，并行应用消耗网络资源的通信能耗，同时，作为数据发送方或 接收方的空闲处理单元消耗静态能耗。

并行应用是任务之间存在数据依赖的优先约束应用，可抽象为有向无环图DAG，模型形 式化描述为：，其中为任务集合，为数据依赖集合；

若两个任务T_i，T_j之间存在数据传输(T_i，T_j)，任务T_i称为任务T_j的前驱，任务T_j称为任务T_i的 后继；没有任何前驱的节点为入口任务T_in，没有任何后继的任务为出口任务T_out；每个任务 T_i，i＝1...N由多条指令组成，任务大小表示为q_i（Million Instructions）；每条边e_ij＝(T_i，T_j)的数 据传输量记为d_ij（Mb）；模型定义几个常用的参数，包括任务执行时间、数据传输时间t_ij、 任务开始时间和任务完成时间

任务执行时间：对给定任务其执行时间为当任务T_i运行在某电压等级v_j时的计算 时间，表示如下：

$t_i^j=q_i/s_j---\left(1\right)$

在确定具体电压等级之前，任务T_i的初始执行时间设定为t_i＝q_i/s_H；

数据传输时间：对给定边e_ij＝(T_i，T_j)，其数据传输时间为当数据从处理单元P(T_i)传输到 P(T_j)的时间，其中P(T_i)和P(T_j)分别表示执行任务T_i和T_j的处理单元，表示如下：

$t_{\mathrm{ij}}=\left(\begin{array}{cc}0& P\left(T_i\right)=P\left(T_j\right)\\ d_{\mathrm{ij}}/b& \mathrm{otherwise}\end{array}\right)---\left(2\right)$

任务开始时间：对给定任务，其开始时间为任务T_i的所有前驱任务或虚前驱任务均 执行完毕且所需数据都完备的时间，表示如下：

$t_i^{\mathrm{st}}=\left(\begin{array}{cc}0& T_i=T_{\mathrm{in}}\\ \max \{(t_j^{\mathrm{ct}}+t_{\mathrm{ji}}),t_k^{\mathrm{ct}}\},e_{\mathrm{ji}}\in ϵ,P\left(T_k\right)=P\left(T_i\right)& \mathrm{otherwise}\end{array}\right)---\left(3\right)$

其中为任务T_j和T_k的完成时间，任务T_j为任务T_i的前驱任务，任务T_k为任务T_i的虚前驱任 务；虚前驱任务是指与任务T_i分配到同一处理单元且在任务T_i之前执行的并行任务；

任务完成时间：对给定任务，其完成时间为任务T_i完成的时间，表示如下：

$t_i^{\mathrm{ct}}=t_i^{\mathrm{st}}+t_i---\left(4\right)$

处理单元的功耗分为动态功耗和静态功耗，动态功耗由电容充放电引起，静态功耗主要 由泄露电流引起，模型描述为：动态功耗表示为p_d＝cv²f，其中c是开关电容，v是供应电压， f是时钟频率；静态功耗表示为p_s=L_g(vI_subn+|v_bs|I_j)，其中L_g是电路中组件的数目，I_subn是亚 阈值泄露电流，v_bs是偏置电压，I_j是PN结反向电流；静态功耗与动态功耗的关系表示为 p_s＝βp_d，其中β是比例因子且0＜β＜1；

对运行在电压等级v_j的任务，其计算能耗表示为；对 给定的数据依赖e_ij∈ε，数据从处理单元P(T_i)传输到P(T_j)，其通信能耗表示为E_ij＝p_cd_ij；当 传输数据时，若处理单元P(T_i)或P(T_j)空闲，其消耗的静态能耗表示为，其中p_s为处 理单元所在电压等级的静态功耗。

如图1所示，面向混合计算环境的功耗感知的并行应用调度系统，包括用户层、调度层 和资源层，所述用户层将用户请求传输给调度层，所述调度层将执行任务及其所需数据传输 给资源层，所述调度层包括解析模块、任务聚类模块、处理单元选择分析模块和任务分配模 块，所述解析模块的解析结果传输给任务聚类模块，所述任务聚类模块的聚类结果传输给处 理单元选择分析模块，所述处理单元选择分析模块包括时间计算模块和功耗计算模块，其选 择分析的结果传输给任务分配模块，所述资源层包括若干个DVS处理单元和若干个non-DVS 处理单元。

所述用户层负责提交用户应用。

所述调度层负责解析用户提交的应用、集成调度方法，并根据调度目标尽量为各个任务 选择最佳处理单元。

所述资源层负责具体执行任务和数据传输。

所述解析模块负责将并行应用划分为单个的任务、对象和数据依赖。

所述任务聚类模块负责将任务划分为若干个任务组、确定处理单元数目和应用整体执行 时间，并达到降低通信时间和通信能耗的目的。

所述处理单元选择分析模块负责确定聚类得到的任务组应该被放置到DVS处理单元还 是non-DVS处理单元上。本发明调度目标涉及时间和功耗指标，因此处理单元选择分析模块 包括时间计算模块和功耗计算模块。

所述时间计算模块用于计算处理单元选择过程中各个任务的执行时间，以及任务组内任 务之间的空闲时间和通信时间等。

所述功耗计算模块用于计算处理单元选择过程中各个任务的计算能耗、通信和空闲时间 段内的静态能耗，以及执行DPM技术的实施能耗等。鉴于同一个任务组无论放置到DVS处 理单元还是non-DVS处理单元上，任务之间的通信能耗相同，因此，本发明中的通信能耗忽 略计算。

所述任务分配模块负责将任务组分配到相应的处理单元，并执行对应的系统层节能技术。

所述DVS处理单元和non-DVS处理单元负责具体执行任务，其中DVS处理单元具有动 态调节电压的功能，non-DVS处理单元可实施有条件的关闭或休眠。

如图2所示，上述系统所采用的调度方法，主要包括如下步骤：

步骤（1）：用户层的用户提交并行应用；调度层的解析模块将并行应用解析为单个的任 务、对象和数据依赖；任务聚类模块进行任务聚类，将任务划分成若干个任务组，并决定处 理单元数目和应用的最小完成时间；

步骤（2）：处理单元选择分析模块对处理单元进行选择，功耗计算模块根据调度目标对 功耗进行计算，时间计算模块根据调度目标对时间指标进行计算，分析每个任务组适合分配 的处理单元类型，并考虑某类处理单元资源有限时的情形，以实现处理单元的选择；所述处 理单元类型包括DVS处理单元和non-DVS处理单元；

步骤（3）：任务分配模块执行任务分配：分配到DVS处理单元的任务组，DVS处理单 元执行DVS技术；分配到non-DVS处理单元的任务组，non-DVS处理单元实施DPM技术； 资源层的处理单元根据DVS和DPM分析结果具体执行任务，同时网络资源传输所需数据。

如图2所示，调度方法的步骤如下：

步骤（a）：用户提交并行应用，将并行应用解析为单个的任务、对象和数据依赖，任务 聚类；

步骤（b）：分析任务聚类结果，将任务划分为关键任务和非关键任务，并确定空闲时间 段和通信时间段；分析并形式化DVS和DPM技术的实施方法及条件；

步骤（c）：判断是否满足提出的处理单元选择原则的前三条，如果是就确定任务组所在 的处理单元类型；如果否就进一步对调度问题进行形式化分析与计算，再确定任务组所在的 处理单元类型；

步骤（d）：任务分配，处理单元执行任务，网络资源传输数据。

所述步骤（1）中的任务聚类是并行和分布式系统中减少通信成本的有效方法；经典的无 复制任务聚类方法有MCP，DSC和CASS-II；DSC和CASS-II方法性能较优，分别适用于不 同粒度大小的应用；本发明结合DSC和CASS-II对并行应用实施聚类。

（1）为保证应用执行时间的最小化和通信成本降低，结合使用DSC和CASS-II方法对 并行应用实施任务聚类。

所述步骤（2）为该方法的核心步骤，其进一步包括以下操作内容：

（21）根据步骤（1）的聚类结果，确定任务类型为关键任务还是非关键任务，并找出任 务组内的通信时间段和空闲时间段；关键任务是指决定应用最小完成时间的任务；

（22）分析并形式化DVS和DPM技术的实施方法及条件；

（23）判断任务组内任务类型、通信时间和空闲时间数目和长度，是否满足所提出的处 理单元选择原则的前三条（任务组内只有关键任务，优先选择non-DVS处理单元；任务组内 有非关键任务或者通信时间段，优先选择DVS处理单元；任务组内不仅有非关键任务或通信 时间段，还有空闲时间段，且空闲时间长度不满足DPM执行条件，优先选择DVS处理单元）， 若满足，则直接确定处理单元类型；

（24）若不满足，则按照形式化公式分情况讨论后确定处理单元类型；为提高本发明的 通用性，通过提出任务组优先级的概念，将调度方法扩展到某类处理单元资源紧张的情况。

所述步骤（3）中的任务分配，对分配到DVS处理单元的非关键任务按照操作频率实施 电压扩展，将空闲时间段和通信时间段的电压降为最低；对分配到non-DVS处理单元的任务 组的空闲时间段，若其满足DPM的实施条件，则在该段时间将处理单元关闭。

对调度方法中的并行应用，解析后通常采用有向无环图DAG来表示。图3是一个简单 的DAG任务图，以图3为实施例，每个节点代表一个任务，节点之间的边表示任务之间的 数据依赖，其中节点和边的权值分别表示任务在最高电压运行时的执行时间和数据传输时间。

混合计算系统由DVS和non-DVS处理单元构成。针对图3实例，假定混合系统由2个 DVS处理单元和2个non-DVS处理单元构成，其参数值参照Turion MT-34处理器的性能。

下表给出该处理单元的电压-频率值，作为调度实例的输入参数之一。

表1电压-频率值

等级 频率(GHz) 电压(V) 0 1.8 1.20 1 1.6 1.15 2 1.4 1.10 3 1.2 1.05 4 1.0 1.00 5 0.8 0.90

设定开关电容值为c＝18pF；静态功耗与动态功耗的比例因子值为β＝0.3，其增加了静态 功耗的比例。由功耗模型和上述参数值计算可知：最大功耗值其 中静态功耗值$p_s^H\cong 14w;$最小功耗值$p_1=(1+\beta ){\mathrm{cv}}_1^2{f}_1\cong 15.2w,$其中静态功耗值$p_s^1\cong 3.5w.$设 定执行DPM技术的时间和能耗成本分别为t′＝1s，e′=6J，则DPM的阈值为 t_threshold＝max{1，6/14}＝1s。设定通信资源的通信功耗为p_c＝1.5J/Mb，数据传输速度为 b＝100Mbps。上述参数通过对CPU和网络资源的简单仪器测量和软件测试获取，具有较好的 代表性。

针对该实例，调度方法的实施步骤如下：

（1）任务聚类

表2任务聚类

上表具体描述了任务聚类方法的过程，由此可知该实例形成三个任务组，分别为 C₁{n1，n2，n7}，C₂{n4，n3，n6}，C₃{n5}，且该实例的最短执行时间为ms＝8。图4给出图3实例执 行任务聚类后的结果图。任务名称标注部分表示处理单元正在执行任务；用箭头连接两个任 务部分表示处理单元正在发送或接收数据，如第二个处理单元的数据传输时间为 t_comm＝0.5+0.5+2.5＝3.5，第三个处理单元的数据传输时间为t_comm＝1；空白部分表示处理 单元处于空闲状态，如第二个和第三个处理单元的空闲时间分别为t_idle＝8-6.5＝1.5和 t_idle＝8-3＝5。

（2）处理单元选择

首先计算参数值：任务执行时间，任务最早开始时间，任务最迟完成时间和任务松弛时 间（见下表），确定任务组中的关键任务和非关键任务。

表3任务最迟完成时间和任务松弛时间

由关键任务和非关键任务的定义知，任务n1，n2，n5，n7为关键任务，任务n3，n4，n6为非关键 任务。

根据本发明提出的处理单元选择原则知，任务组C₁{n1，n2，n7}内均为关键任务，宜选择 non-DVS处理单元；任务组C₂{n4，n3，n6}兼有非关键任务、通信时间和空闲时间，且空闲时间 长度满足DPM执行条件，宜用公式求解；任务组C₃{n5}兼有关键任务、通信时间和空闲时间， 且空闲时间长度满足DPM执行条件，宜用公式求解。

对任务组C₂{n4，n3，n6}，其有三个非关键任务，三个长度分别为0.5s，0.5，2.5s的通信时间段， 一个长度为1.5s的空闲时间段。若将其放于non-DVS处理单元，空闲时间时执行DPM技术， 可节省能耗14*1.5-6＝15J。若将其放于DVS处理单元，通信时间和空闲时间内可执行DVS 技术；三个非关键任务的操作频率为$f_3^{\mathrm{slack}}=f_4^{\mathrm{slack}}=f_6^{\mathrm{slack}}=1.8*1/1.5=1.2\mathrm{GHz},$则DVS后的 三个任务的计算功耗值为p_slack＝31w。既然处理单元的电压-频率为离散值，若求得的频率值 不是给定表中的频率值，则从表中选择比求得频率稍大且最接近一个作为实际操作频率进行 电压扩展。将任务n4，n3，n6实施DVS技术后，通信时间仅剩n6→n7，将其频率将为最低，即 f＝0.8GHz；对空闲时间，也将其频率降为最低。因此，将该任务组放至DVS处理单元的能 耗节省为$60.7*3+14*5-3*1.5*p_{\mathrm{slack}}-p_s^1*(2.5+1)=100.35J.$由于100.35＞15，任务组 C₂{n4，n3，n6}宜放于DVS处理单元上。

对任务组C₃{n5}，其具有一个关键任务，一个长度为1s的通信时间，一个长度为5s的空闲 时间。若将其放于non-DVS处理单元，能耗节省为14*5-6＝64J。若将其放于DVS处理单 元上，能耗节省为由于64＞63，故该任务组宜放于non-DVS处理单 元上。

确定了三个任务组适合的处理单元类型，计算其相应的优先级分别为 Pr₁＝0，Pr₂＝100.35-15＝85.35，Pr₃＝64-63＝1；系统具有2个DVS处理单元和2个non-DVS 处理单元。因此，任务组C₂优先选择DVS处理单元，任务组C₃优先选择non-DVS处理单元， 任务组C₁选择non-DVS处理单元。

（3）任务分配

对图3实例实施调度方法后的执行结果见图5所示。任务组C₁放于non-DVS处理单元上； 任务组C₂放于DVS处理单元上，任务n4，n3，n6运行于频率1.2GHz上，通信时间n6→n7和空闲 时间运行于频率0.8GHz上；任务组C₃放于non-DVS处理单元上，在空闲阶段，该处理单元关 闭。

为直观表明各参数的含义，特给出表4以供查阅。

表4参数含义描述

为验证提出方法的有效性，本发明分别使用TGFF工具生成的合成应用和WIEN2K产生 的实际负载进行了多次试验。通过与已有方法比较，证明了该方法更适合混合计算环境和数 据依赖应用，其任务聚类、DVS和DPM技术的有效融合，极大提高了该方法的能耗节省能 力和时间优化能力，实现了发明目的。

上述虽然结合附图对本发明的具体实施方式进行了描述，但并非对本发明保护范围的限 制，所属领域技术人员应该明白，在本发明的技术方案的基础上，本领域技术人员不需要付 出创造性劳动即可做出的各种修改或变形仍在本发明的保护范围以内。