调度

调度的意义：

The objective of scheduling is to allocate tasks onto the processors and then order their execution so that task dependence is satisfied and the length of the schedule, known as the parallel time, is minimized。

调度算法的可行解：

Specifically, if the requests for all tasks at their critical instants are fulfilled before their respective deadlines, then the scheduling algorithm is feasible.

异构系统：

Diverse sets of resources interconnected with a high-speed network provide a new computing platform, called the heterogeneous computing system, which can support executing computationally intensive parallel and distributed applications.

与高速网络互连的各种资源集提供了一个称为异构计算系统的新计算平台，该平台可以支持执行计算密集型并行和分布式应用程序。

任务调度模型：

A scheduling system model consists of an application, a target computing environment, and a performance criteria for scheduling.

调度系统模型由应用程序、目标计算环境和调度性能标准组成。

任务调度的目标函数：

The objective function of the task-scheduling problem is to determine the assignment of tasks of a given application to processors such that its schedule length is minimized.

1 Scheduling Algorithms for Multiprogramming in a Hard-Real-Time Environment

Author: C. L. LIU and JAMES W. LAYLAND

JACM A类 1973年

题目： 硬实时环境中的多程序调度算法

优先级调度算法

静态调度算法：调度的过程中，优先级不发生改变；即优先级只被赋值一次。

动态调度算法：调度的优先级过程中会发生改变，根据不同因素情况动态的修改任务的优先级。

混合调度算法：混合静态调度算法和动态算法，即所有任务中，一部分任务的优先级是不改变的，一部分任务的优先级会发生动态改变的。

论文中的调度算法

1 A Fixed Priority Scheduling Algorithm 固定优先级调度算法，静态调度算法。

rate-monotonic priority assignment 单调速率优先级分配算法

​ 根据任务的请求周期时间T来进行对任务优先级赋值，当请求周期时间越小，则优先级越大；请求周期时间越大，则任务优先级越小。

​ 调度算法分配优先级过程中没有考虑任务的运行时间。

​ 所有能用静态优先级调度的任务集，都能使用RM算法来对该任务进行调度。

​ RM调度算法是基于优先级静态调度算法中最优的调度算法。

2 The Deadline Driven Scheduling Algorithm 截止时间驱动调度算法，动态调度算法

根据任务执行截止时间来进行对任务的动态赋值优先级；

当当前时间越接近截止时间时，任务的优先级越高；当当前时间离任务截止时间较远时，任务的优先级越低。

如果一组任务能用其他调度算法来调度的话，那么Deadline Driven Scheduling Algorithm算法也能进行调度。

Deadline Driven Scheduling Algorithm算法时最优的。

3 A Mixed Scheduling Algorithm 混合调度算法

​ 所有任务中请求周期时间比较小的K个任务，采用固定优先级调度算法中rate-monotonic priority Algorithm,RM算法；其他任务采用动态调度算法中的The Deadline Driven Scheduling Algorithm算法。

​ 优优结合。

2 DSC: Scheduling Parallel Tasks on an Unbounded Number of Processors

Author: Tao Yang, and Apostolos Gerasoulis

出处：TPDS:“PARALLEL AND DISTRIBUTED SYSTEMS.” A类 1994

categories: 聚类整合

DSC：在无数个处理器上调度并行任务

2.1 tlevel

定义：从起始结点entry node 到当前结点的最长路径。

Let $tlevel(n_i)$ be the length of the longest path from an entry (top) node to $n_x$, excluding the weight of $n_x$ in a DAG. 不包括自己的执行时间。

2.2 blevel

定义：从当前结点到exit node的最长时间。

let $blevel(n_x)$ be the length of the longest path from $n_x$, to an exit (bottom) node.

包括当前结点的执行时间。

2.3 PT

任务总的运行时间。

image-20210415152238132

2.4 DSC-Ⅰ 算法

image-20210415134255303

2.4 DSC-Ⅱ 算法

image-20210415134705950

添加 partially free list 部分自由列表

3 HEFT:Performance-effective and low-complexity task scheduling for heterogeneous computing

Author: H. Topcuoglu , S. Hariri , Min-You Wu

出处：TPDS:“PARALLEL AND DISTRIBUTED SYSTEMS.” A类 2002

categories: 列表法

用于异构计算的性能有效且低复杂度的任务调度,本文提出了两个算法，HEFT,CPOP；

有向无环图（DAG）

算法的核心步骤为两步：

第一步，如何制定任务结点（task）的优先级。

第二步，如何选取处理器的选择方式。

3.1 向上等级 upward rank

当前结点->退出结点（exit task）的需要时间。其中包含自己的平均执行时间。

$rank_{u}(n_{i}) = \overline{w_{i}} + \max_{n_{j} \in succ(n_{i})} (\overline{c_{i, j}} + rank_{u}(n_{j}))$

3.2 向下等级 downward rank

起始结点（entry task）到当前结点的 最大时间(最快时间)（the longest distance).不包含当前结点的平均执行时间。

image-20210415152351122

3.3 HEFT Algorithm ：The Heterogeneous-Earliest-Finish-Time Algorithm

任务选取阶段：任务的优先级为： $priority=rank_u$

处理器选取阶段：基于插入策略选取处理，使得选取任务在最早时间完成（EFT）。

3.3.1 算法描述

img

1：初始化任务的计算成本（平均执行时间），任务间通信成本

2：从退出结点递归调用，得出每个任务（task）的向上等级值（$rank_u$）

3：将$rank_u$按非递增排序的调度队列。

4-9: 循环等待执行队列，直到等待队列为空：

​ 选取队列中第一个任务。

​ 计算出该任务在每个处理器上的最早完成时间，选取出最早完成时间的最小值的处理器，将该任务分配给该处理器执行。

3.3.2 时间复杂度：$O(v^2 p)$

3.4 CPOP Algorithm：The Critical-Path-on-a-Processor Algorithm

任务选取阶段：任务的优先级为： $priority=rank_u + rank_d$

根据任务的优先级（|CP|=priority($n_{entry}$)）得出关键路径的结点，加入到关键结点队列

计算关键结点路径在每个处理器的执行时间总和，选择总和最小值的处理器固定为关键路径结点处理器。

处理器选取阶段：根据优先级排序顺序进行选取任务结点。

任务结点 在 关键路径队列 中：

​ 关键路径专属处理器；

不在：

​ EFT循环遍历所有处理器，选择最早时间完成的处理器。

3.4.1 算法描述

Fig. 5. - The CPOP algorithm.

1：初始化任务的计算成本（平均执行时间），任务间通信成本

2：从退出结点递归调用，得出每个任务（task）的向上等级值（$rank_u$）

3：从开始结点向下调用，得出每个任务（task）的向下等级值（$rank_d$）

4：计算每个任务的优先级：$priority=rank_u+rank_d$

5-12: 循环所有任务得出关键路径队列 $SET_{CP}$

13：选取关键路径队列结点的最佳选择处理器。

14-21：根据规则进行选取任务和任务对应处理器进行工作。

规则：

根据优先级队列（堆）进行选取任务结点。

任务结点 在 关键路径队列 中：

​ 关键路径专属处理器；

不在：

​ EFT循环遍历所有处理器，选择最早时间完成的处理器。

更新优先级队列，加入执行任务的后继结点中的ready tasks(准备任务)

3.4.2 时间复杂度：$O(e \cdot q )$

4 PEFT: List Scheduling Algorithm for Heterogeneous Systems by an Optimistic Cost Table

Author：Hamid Arabnejad and Jorge G. Barbosa

出处：TPDS:“PARALLEL AND DISTRIBUTED SYSTEMS.” A类 2014

categories: 列表法

4.1 Optimistic Cost Table 乐观成本表

主要用于考虑后继结点的预计最早完成时间。

image-20210415152303819

计算出每个任务的$rank_{ock}$

image-20210415152321632

4.2 PEFT Algorithm ：Predict Earliest Finish Time Algorithm

4.2.1 算法描述

Algorithm 1. The PEFT Algorithm.
1: Compute OCT table and $rank_{oct}$for all tasks
2: Create Empty list ready-list and put $n_{entry}$ as initial task
3: while ready-list is NOT Empty do
4: $n_i\leftarrow$ the task with highest $rank_{oct}$ from ready-list
5: for all processor $p_j$ in the processor-set P do
6: Compute $EFT(n_i,p_j)$ value using insertion-based scheduling policy
7: $O_{EFT}(n_i,P_j)=EFT(n_i,p_j)+OCT(t_i,p_k)$
8: end for
9: Assign task $n_i$ to the processor $p_j$ that minimize $O_{EFT}$ of task $n_i$
10: Update ready-list
11: end while

1：计算出每个任务的$rank_{oct}$

2：初始化就绪队列，将entry 任务加入到就绪队列

3-11：循环遍历就绪队列，直到就绪队列为空：

​ 从就绪队列中选取$rank_{oct}$最大的就绪任务

​ 计算任务在每个处理器上的EFT,进而计算$O_{EFT}(n_i,p_j)$,选取计算值最小的处理器。（注：计算EFT时，前驱结点已固定到处理器上。）

​ 更新就绪队列。

4.2.2 时间复杂度 $O(v^2 p)$