Running Noob

Do Something Meaningful

0%

Energy and Reliability-Aware Task Scheduling for Cost Optimization of DVFS-Enabled Cloud Workflows

发表于 更新于 分类于
本文字数： 7.6k 阅读时长 ≈ 7 分钟

Energy and Reliability-Aware Task Scheduling for Cost Optimization of DVFS-Enabled Cloud Workflows

  • 单云、单工作流、单目标最优化（cost）、多约束（makespan、reliability、energy consumption）
  • 怎么用 DVFS？-> 计算得到任务的 latest finish time，slot=lft-start time ，在任务的执行时间不大于 slot 的情况下，用 DVFS 尽可能地降低执行频率。
  • 输出单个最优解，不过是从多组解中选出的

System Models and Problem Description

Modeling of Virtual Machines

  • 有 m 个虚拟机集合

    每个虚拟机都可以选择其中一种配置

    • 是一个包含七个元素的元组：

      • ：虚拟机的最大计算处理能力，MIPS
      • ：带宽
      • ：内存大小，
      • ：和内存相对应的单位时间计费，
      • ：虚拟机的 CPU 频率，
      • ：虚拟机的 CPU 电压，
      • ：和 CPU 相对应的单位时间计费，

      注意，如果一个虚拟机的频率为，则它的计算处理能力应为。

Modeling of Workflows

    • ，任务的集合
    • 是有向边的集合，表示任务之间的依赖关系

  • 任务用包含三个元素的元组来表示：

    • ：任务的 id
    • ​：任务的负载（i.e.，the number of instructions）
    • ：任务所需的内存大小

  • 表示任务是任务的直接前驱任务，任务是任务的直接后继任务。

    表示任务和任务之间需要传输的数据量。

    • 如果任务和任务调度在同一台虚拟机上，则它们之间的传输时间为 0
    • 如果任务和任务分别调度在配置为和的虚拟机上，则它们之间的传输时间为

Modeling of Task Execution with Fault Tolerance

  • 假设任务被调度给配置为的虚拟机，如果虚拟机频率为，则任务的执行时间为，这是在没有考虑出错的情况下。

  • 用等距检查点技术和回滚技术来提高可靠性

  • 当没有故障发生时，任务在配置为的虚拟机上执行时的执行时间为

    • 表示频率为时检查点的个数，表示设置检查点时的时间开销
      • 检查点的时间间隔：
        • 有个检查点，就把任务执行时间分为了段。

  • 当故障一直发生时，假设是任务在执行过程中故障发生最多的次数，则此时任务的执行时间为

    • 是回滚的时间开销
    • 是从检查点得到数据和重新记录数据的时间开销

    给定，我们可以得到最佳的检查点个数（这个不知道怎么来的）

  • 用泊松分布对可靠性建模：平均故障率

    • 是配置为的虚拟机运行在最大频率时的故障率，是和系统有关的参数。

      任务在配置为的虚拟机上执行，虚拟机的频率为，则任务在执行过程中发生 t 个故障的可能性为。

    • 发生 t 个故障的任务被成功恢复的可能性为

      所以发生 t 个故障的任务成功执行的可能性为

    最终，任务调度在配置为的虚拟机上，虚拟机的频率为的情况下，任务的可靠性为。（这里我也有问题，是累加而不是累乘吗？）

Modeling of Energy Consumption

  • 对于配置为、频率为的虚拟机，

  • 对于虚拟机，

      • 是调度给的任务集
      • ：分配给任务的频率等级，最低为1，即或

      • ：虚拟机的 non-busy 时间

Problem Formulation

  • 一个工作流调度解就是、和的组合

    • 是工作流的任务和虚拟机之间的调度映射

    • 是虚拟机和虚拟机配置之间的配置映射

    • 是分配给任务 τ 的特定频率等级，在的虚拟机配置下

  • 工作流调度策略是、和的组合，任务的调度顺序受制于。

  • ：在同一个虚拟机上执行，且在任务之前执行的任务（）

  • 调度解 S 中对于一些任务的特定的虚拟机配置。

  • 假设在一个调度解中，任务被分配给虚拟机，我们用和分别表示任务的开始时间和结束时间。

    • 开始时间

    • 结束时间

    工作流调度解 S 的完工时间……

  • 这篇论文建模感觉有点过分“详细”了，反而冗长，不写了，剩下的建模自己看论文，反正也没多少了。

Proposed Approach

  • 这篇论文算法的整体框架如下：

    大致可以分为几个阶段：

    1. 初始化种群阶段。
    2. 遗传算法迭代阶段：
      • GA 阶段。
      • DVFS 阶段。
      • 选择精英 Elite 阶段。-> 选择策略

Chromosome Encoding

  • 染色体编码为“三段整数”编码，即：

    • 任务到虚拟机的映射 Task_VM，Task_VM[i]=j 表示将任务调度给虚拟机
    • 虚拟机到虚拟机配置的映射 VM_VMC ，VM_VMC[j]=k 表示虚拟机的配置为
    • 任务到 CPU 频率的映射 Task_Freq ，Task_Freq[i]=m 表示执行任务的虚拟机的频率等级为 m

    如果 Task_VM[i]=j ，VM_VMC[j]=k ，Task_Freq[i]=m ，表示将任务调度给配置为的虚拟机，且虚拟机的执行频率为。

Fitness Function（选择策略）

  • 选择策略决定了我们选择的调度解的质量（这里的适应值函数的选择作用是从整个解的角度来看的，而Reliability, Rental-Cost and Energy-Aware Multi-Workflow Scheduling on Multi-Cloud Systems的适应值函数的选择作用是从选择虚拟机及其性能状态的角度来看的）。

    ，Fitness(S) 越小，表示解越好。

    • 的意思是，如果满足 Constraint C，则值就为 x，否则为 1。
    • α、β、γ 是惩罚参数，因为完工时间对租赁开销的影响相对更大，所以设置 α=100，β=10，γ=10。

Initial Population Generation

  • 在初始化种群时，为了能高效地得到最优解，初始的种群个体之间差异应该尽可能地大。
  • 这篇论文用随机方法（random method）和 HEFT 算法（HEFT method）来初始化种群个体。
    • 随机方法（random method）：每个任务被随机地调度给虚拟机，每个虚拟机被随机地分配配置，每个任务的执行频率 level 被随机地分配。
      • 如果有多个任务被调度给同一个虚拟机，则这些任务在虚拟机上的执行顺序依据HEFT算法来确定。
      • 由于随机方法生成的调度解有可能会违反用户的 Constraint，所以对这些违反了 Constraint 的调度解，会迭代地递增任务的执行频率，直到能满足 Constraint 或者已经达到最大频率等级。
    • HEFT 算法（HEFT method）：用 HEFT 算法来生成多个调度解（这些调度解都完全一样），且任务的执行频率都处于最大频率等级。

Chromosome Modification

  • Modify 的是内存

  • 因为 Fitness Function 并没有把内存 Constraint 纳入考虑，所以根据 Fitness Function 选择的调度解是有可能违反内存 Constraint 的，所以要用这里的 Chromosome Modification 来保证不违反内存 Constraint 。

    • 个人感觉是

      1
      for k = 1 to ind.Task_VM.length() do

      而不是

      1
      for k = 1 to ind.VM_VMC.length() do

Genetic Operators

Crossover

  • 在进行交叉操作时，要考虑多种信息的交叉，包括 Task_VM、VM_VMC、Task_Freq，因此这篇论文提出了一种“三段式交叉操作”：

    • 先随机挑选两个调度解 (Chromosome，或者叫 individual ) ind1、ind2
    • 随机生成要交叉的范围下标、
    • 交叉下标范围内的任务及与之相应的虚拟机的配置。
    • 一个不知道叫什么的操作（对应例子中绿色的t5、t6）。
    • 为了解决 i) empty VMs; ii) a task whose frequency level is larger than the maximum one of its newly allocated VM 的问题，最后用 Regularize 方法。

Mutation

  • 根据虚拟机的空闲率（idle rate）来进行变异操作，空闲率越高的虚拟机越有可能被选中。

    • 变异操作具体为：将被选中的虚拟机上的任务随机分发给其他的虚拟机，避免陷入局部搜索。同时被分发的任务的执行频率也会进行随机更新。

Frequency Scaling

  • 在通过遗传算子操作后，再利用 DVFS 对调度解中的每个任务的执行频率进行调整：

    • 先得到调度解中每个任务的最晚完成时间 lft，这样就可以得到其最大完工时间
    • 然后对任务的每个可能的执行频率进行遍历， 通过一些 if 条件选择出其合适的执行频率，即使用了DVFS。

Performance Evaluation

Experimental Setup

Workflow Settings
  • Sipht、Montage、CyberShake、LIGO

Workflow Generator, Available: https://confluence.pegasus.isi.edu/display

/pegasus/WorkflowGenerator

Baseline Methods

  • baseline 有三个，都用了 DVFS：

    • EES

      • EES 算法分两步：i) 用 HEFT 算法得到调度解，且任务的执行频率都最大，相应的完工时间为；ii) 根据和，来求得任务的 earliest start time 和 latest finish time，再用 DVFS 来调节任务的频率。

      Q. Huang, S. Su, J. Li, P. Xu, K. Shuang and X. Huang, “**Enhanced Energy-Efficient Scheduling for Parallel Applications in Cloud,**” International Symposium on Cluster, Cloud and Grid Computing (CCGrid), pp.781–786, 2012.

    • DEWTS

      • DEWTS 算法分三步：i) 用 HEFT 算法得到初始解，且任务的执行频率都最大；ii) 尝试将虚拟机 merge，来减少虚拟机的总的空闲时间；iii) 根据倒推所有任务的 earliest start time 和 latest finish time，再用 DVFS 来调节任务的频率。

      Z. Tang, L. Qi, Z. Cheng, K. Li, S. U. Khan and K. Li, “**An Energy-Efficient Task Scheduling Algorithm in DVFS-Enabled Cloud Environment,**” Journal of Grid Computing, vol. 14, no. 1, pp. 55–74, 2016.

    • WUS

      • WUS 算法分三个阶段：i) 用 HEFT 初始化调度解；ii) 任务 remapping 阶段，目的是降低能耗；iii) 充分利用非关键路径上的相邻任务之间的空闲时间，即降低相应的虚拟机的频率，来进一步降低能耗。

      T. Wu, H. Gu, J. Zhou, T. Wei, X. Liu and M. Chen, “Soft Error-Aware Energy-Efficient Task Scheduling for Workflow Applications in DVFS-Enabled Cloud,” Journal of Systems Architecture - Embedded Systems Design, vol. 84, pp. 12-27, 2018.

Results and Analysis

  • 在不同的和相同的的情况下比较租赁开销。

    • 由 HEFT 算法得到工作流的完工时间 M，然后让，，来得到不同的。

  • 在不同的和相同的的情况下比较能耗。

  • 在不同的和相同的的情况下比较能耗。

  • 在不同的和相同的的情况下比较租赁开销。

  • 另外实验还设置为不同的计费模型（linear pricing model 和 super linear pricing model）

---------------The End---------------