fed_sched_int
摘录一下Marion的论文要点，方便查阅
任务模型
每个任务 \(\tau_i\) 由一组子任务 \(\tau_{i,j}\) 组成，并在其间具有优先关系 \(<\)。每个子任务 \(\tau_{i,j}\) 的特征为： - 工作量 \(c_{i,j} \in \mathbb{N}\)，表示其最坏情况下的执行时间。
子任务必须顺序执行，即它是一组必须按顺序完成的指令的集合，执行时间最长为 \(c_{i,j}\)。假设子任务执行是可重入的：执行可以被其他子任务抢占，且无需在系统中同一个核心上恢复。
优先关系限制了子任务的执行顺序，例如 \(\tau_{i,a} < \tau_{i,b}\)，则 \(\tau_{i,a}\) 必须在 \(\tau_{i,b}\) 之前完全执行。我们说，当任务 \(\tau_{i,a}\) 的所有前驱任务 \(\tau_{i,a'}\) 完成时，\(\tau_{i,a}\) 变为“可用”（available）。
根据 [26]，我们将任务分为两类： 1. 轻量任务（light tasks）：满足 \(C_i < D_i\)； 2. 重量任务（heavy tasks）：满足 \(C_i \geq D_i\)，此类任务必须利用其潜在的并行性才能满足调度要求。
本文的重点是联合调度（federated scheduling），对于每个重量任务，其被分配到一个专用核心集上并独占执行。我们仅考虑截止时间 \(D_i\) 和子任务工作量 \(c_{i,j}\) 为正整数的任务，称为整数值任务（integer-valued tasks）。
优先关系的DAG表示
子任务执行的优先关系可表示为一个有向无环图（DAG）。对于每个并行任务 \(\tau_i\)，存在一个DAG \(G_i\)，其包含的顶点集合为 \(v_{i,j}\)，对应于任务 \(\tau_i\) 的子任务 \(\tau_{i,j}\)： - 每个顶点 \(v_{i,j}\) 的属性为子任务的工作量 \(c_{i,j}\)； - 边 \(v_{i,a} \to v_{i,b}\) 存在当且仅当 \(\tau_{i,a} < \tau_{i,b}\) 且不存在 \(v_{i,c}\) 满足 \(\tau_{i,a} < \tau_{i,c} < \tau_{i,b}\)，即 \(v_{i,b}\) 直接继承 \(v_{i,a}\)。
关键路径长度的定义
对于每个图顶点 \(v_{i,j}\)，我们定义其关键路径长度或跨度 \(l_{i,j} \in \mathbb{N}\) 为从该顶点起始的最长路径的长度，该路径由沿路径每个顶点的执行时间（包括起始顶点的权重 \(c_{i,j}\)）加权。
对于相应的任务 \(\tau_i\)，跨度 \(L_i \in \mathbb{N}\) 是所有顶点的跨度中的最大值，即整个DAG的关键路径长度。跨度对应于任务在给定无限数量核心时相对于其激活时间的最早完成时间。
显然，为使任务可调度，必须满足： \[ L_i \leq D_i \]
适用于整数值任务的联合调度
对于一个重量任务 \(\tau_i\)，其特征为工作量 \(C_i\)、跨度 \(L_i\) 和截止时间 \(D_i\)，在提供足够核心的情况下，任何工作保留型（work-conserving，即贪婪型）调度器均可调度该任务。分配给任务 \(\tau_i\) 的核心数可以表示为： \[ n_i = \left\lceil \frac{C_i - L_i}{D_i - L_i} \right\rceil \tag{1} \]
我们在此证明，对于一个并行任务，如果其截止时间和所有子任务的工作量均为整数，则分配的核心数可以改进为： \[ n_i' = \left\lceil \frac{C_i - L_i + 1}{D_i - L_i + 1} \right\rceil \]
这一公式比方程 (1) 在限制重量任务的核心数方面提供了实际且直观的优势。
单工作量表调度（Unit-Workload List Scheduling）
第4节中提出的联合调度方法为高利用率的整数值任务分配了足够的处理器，以保证任何工作保留型调度器的可行性，前提是给定每个任务的工作量、关键路径长度和截止时间。然而，这种常量时间的分配方法可能会导致对重量任务的处理器过度分配，进而造成资源浪费。
在 [3] 中，Graham 的表调度方法（list scheduling）被应用于重量任务；通过使用多种启发式方法为子任务排序，可以在更少的处理器上生成可行的调度。表调度以非抢占式方式将可用子任务分配给空闲处理器；如 [14] 所述，这可能导致对重量任务的处理器分配过多。然而，允许空闲子任务进行抢占可能会引入切换问题。
方法改进
为了解决这个问题，我们提出了单工作量子任务的表调度。
- 一个整数值并行任务 \(\tau_i\)，由DAG
\(G_i\)
表示，可以被分解为一个包含单工作量顶点的DAG \(G_i^*\)。
- 在 \(G_i\) 中具有工作量 \(c\) 的顶点 \(v_{i,j}\)
被映射为一个完全有序的顶点序列，在 \(G_i^*\) 中形成从起点到终点的路径。
对于 \(G_i^*\) 中的任何边 \(v_{i,j}\)，其连接方式如下： 1. \(G_i^*\) 中进入 \(v_{i,j}\) 的任何边连接到其分解后路径中的第一个顶点； 2. 在 \(G_i\) 中离开 \(v_j\) 的任何边，现在连接到 \(v_{i,j}\) 的分解路径中的最后一个顶点。
优势
对于这样的DAG，表调度方法可以为每个单位工作量分配一个优先级；
这使得原始DAG \(G_i\)
中的相应子任务能够在单位时间步边界内被抢占。
5.1 常见的表调度启发式方法
关键路径规则（Critical Path Rule, CP）
关键路径规则用于表调度时，以最长跨度的顺序选择可用子任务进行执行。
-
子任务跨度的分配可以以深度优先搜索的方式完成；当为每个顶点分配跨度后，图的总跨度
\(L\) 会被更新。 - 该过程的时间复杂度为
\(O(|V| + |E|)\)。
DAG分解
DAG \(G\) 分解为单位工作量的 DAG \(G^*\) 的过程表示为函数 Convert_Unit_DAG： 1. 初始化 \(G^*\) 为 \(G\) 的副本。 2. 建立一个顶点集合 \(V^*\)，其由 \(G^*\) 中的顶点（实际代码中可能为指向顶点的指针）组成。 3. 对于 \(V^*\) 中的每个顶点 \(v_i\)： - 将 \(v_i\) 的工作量 \(c_i\) 转化为单位工作量顶点序列，这些顶点在 \(G^*\) 中形成路径： - 路径中的每个顶点之间用边连接，第一个顶点的跨度等于 \(v_i\) 的跨度 \(l_i\)； - 每个后续顶点的跨度比前一个顶点小1。 - 删除原始顶点 \(v_i\)。
- 处理完成后，\(G^*\)
中仅包含单位工作量的顶点：
- 通过分解，生成了 \(C - |V|\) 个额外顶点，以及 \(C - |V|\) 条额外边。
- 因此，总运行时间为 \(O(|V| + C - |V| + |E| + C - |V|)\)，简化为 \(O(C + |E|)\)。
后继数量规则（Largest Number of Successors Rule, LNS）
LNS规则以后继任务的总工作量为顺序，选择可用子任务进行执行： - 子任务 \(v_i \in G\) 的后继工作量由与 \(v_i\) 通过路径相连的所有顶点的工作量之和定义。 - 可以通过动态规划在整个图上实现这一过程，其时间复杂度为 \(O(|V| + |E|)\)。
LNS规则也可以应用于单位工作量子任务的表调度，并保持伪多项式时间复杂度。
注意
将整数值任务的 DAG \(G\) 分解为单位工作量的 DAG \(G^*\) 时，还需要为每个单位工作量顶点分配一个子图工作量。这与跨度的分配类似，不会影响算法的时间复杂度。