Running Noob

Do Something Meaningful

0%

Energy-Minimized Scheduling of Real-Time Parallel Workflows on Heterogeneous Distributed Computing Systems

发表于 更新于 分类于
本文字数： 2.7k 阅读时长 ≈ 2 分钟
  • 降低能耗的方法：关掉一些能源利用率低的处理器（DPM：dynamic power management）；DVFS。
  • 实时工作流：即时性、可靠性

Energy-Minimized Scheduling of Real-Time Parallel Workflows on Heterogeneous Distributed Computing Systems

  • 降低能耗的方法：关掉一些能源利用率低的处理器（DPM：dynamic power management）；DVFS。
  • 实时工作流：即时性、可靠性

System model

  • M个处理器，，，，
  • 工作流，，
    • 任务集合，，，
    • 任务之间的依赖关系： E = N x N 的矩阵
    • 计算开销：W = N x M 的矩阵，表示任务在处理器上执行，且处理器处于频率最大时的执行时间

Power Model

    • 是静态能耗，由电流泄露引起
    • 是动态能耗，取决于处理器的频率

  • 若任务在处理频率为的处理器上执行，则其能耗为：

  • 工作流 G 的总能耗

    和分别表示分配给任务的处理器和处理器的处理频率

Reliability Model

  • 对于任务，被调度在频率为的处理器上时，其可靠性为（假设遵循泊松分布）

    • 工作流的可靠性为（当处理器都处于最大频率时）

  • 更一般的，对于被调度在频率为的处理器上的任务，

    因此，任务的可靠性就为：

Problem Formulation

  • 调度过程分为三部分：

    • a task placement plan：确定将任务调度给哪个虚拟机
    • a start time plan：任务开始执行的时间的确定
    • a frequency assignment plan：确定虚拟机的运行频率

    用元组

reliability transfer scheme

  • 找到一个任务应该满足的最低的可靠性，以最终满足

    如上图所示，将任务根据其优先级进行调度，从 To(1) 到 To(N) 连续调度，{To(1)，…，To(i-1)} 是已经调度的任务，To(i) 是正在调度的任务，{To(i+1)，…，To(N)} 是还未调度的任务。

    {To(1)，…，To(i-1)} 的可靠性是已知的，为了得到 To(i) 应该满足的最低的可靠性，假设未调度的任务 {To(i+1)，…，To(N)} 的可靠性都是最大的，则，这就是 To(i) 应该满足的最低的可靠性。

MSL algorithm
  • 由 “reliability transfer scheme，我们已经得到了每个任务应该满足的最低的可靠性，由此我们找出那些可以满足该任务可靠性需求的处理器，然后选择完成时间最短的那个处理器。

processor-merging algorithm

  • 用来降低静态能耗
  • 首先打开所有处理器，并应用 MSL 算法，判断 Rreq 和 Dreq 是否满足，若满足则进一步，否则 break：
    • 对所有开着的处理器，应用 MSL 算法，判断 Rreq 和 Dreq 是否满足，若满足则计算总能耗；
    • 然后关闭其中开着的处理器，继续前面的步骤，直到没有处理器能被关闭为止。

DVFS on task level

  • 用来降低动态能耗
  • 在满足可靠性和即时性的前提下，调低处理器的频率，以降低动态能耗。
response time requirement

  • 基于 MSL 算法生成的调度结果，依次地从 To(N) 到 To(1) 进行任务执行频率的调整

  • 是任务 Tj 在处理器 pk 上执行时的响应时间需求。

    任务在调度执行时，应该满足这个要求。

  • 最终，对于在处理器 pk 上执行的任务 Tj 来说，其可行执行时间区间为

reliability requirement

  • 定义可靠性比，R(G) 是基于 MSL 调度结果计算的工作流的可靠性，由 MSL 算法可知，若能生成调度解，则 R(G) >= Rreq ，所以 βr <= 1

    当任务 To(i) 的执行频率重新调整时，其所要求的可靠性为：

scaling down processor frequency

  • 由调整的可靠性需求式子，可以得到任务的最大可执行时间：

    $w^{‘}{o(i),k} = w{o(i),k}/f_{o(i)}$

    再根据任务的可执行区间 Δj,k ，可以得到调整任务频率的方法：

    fo(i) 就是降低后的频率。

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