并行与分布式系统中的并行独立任务调度：基于有向无环图（DAG）的列表调度算法（List Scheduling）

字数 4159 2025-12-18 10:06:15

并行与分布式系统中的并行独立任务调度：基于有向无环图（DAG）的列表调度算法（List Scheduling）

题目描述

在并行与分布式计算中，我们常常需要将一组具有依赖关系的计算任务映射到多个处理器（或计算节点）上执行，以最小化总的完成时间（即调度长度，Makespan）。这些任务及其依赖关系通常用一个有向无环图（DAG）来表示。DAG中的每个节点代表一个任务，节点上的权重代表该任务的计算开销（执行时间）。DAG中的每条有向边(u -> v)表示任务u必须在任务v开始之前完成，边上的权重可以表示从u到v的数据传输开销（通信时间）。

列表调度（List Scheduling）是一种经典的启发式算法，用于解决这个DAG任务调度问题。其核心思想是：将所有任务按照某种优先级规则排序形成一个列表，然后按照这个列表的顺序，每当有处理器空闲时，就从中选择当前优先级最高且所有前驱任务都已完成的“就绪”任务分配给该处理器执行。

这个问题的挑战在于：任务间存在复杂的依赖关系和可能的通信开销，而处理器的数量是固定的。目标是在多项式时间内，找到一个尽可能接近最优解的调度方案。列表调度算法以其简单、高效且具有理论上的性能保证（近似比）而闻名。

解题过程循序渐进讲解

我们假设有一个DAG，包含n个任务，m个相同的处理器，目标是生成一个调度方案（每个任务在哪个处理器上、何时开始执行）。

第一步：问题建模与输入

任务图（DAG）：G = (V, E)，其中V是任务集合，|V| = n。每个任务v有一个计算代价w(v)。
通信代价：对于每条边e = (u, v) ∈ E，有一个通信代价c(u, v)。这表示如果任务u和v被分配到不同的处理器上执行，那么在u完成后，需要等待c(u, v)的时间，数据才能传输到v所在的处理器，v才能开始。如果u和v在同一处理器上，则通信代价通常视为0。
处理器：P个相同的处理器，P1, P2, ..., Pp。
调度目标：找到一个从任务到（处理器，开始时间）的映射，满足所有依赖约束，并最小化最后一个任务完成的时间（Makespan）。

第二步：理解列表调度的核心框架

列表调度是一个贪心算法框架，它包含两个关键部分：

优先级计算：为每个任务计算一个静态或动态的优先级，并根据此优先级对所有任务进行排序，形成一个有序列表L。常见的优先级包括：
- 自上而下的层级（Top Level, t_lvl）：也称为从起始节点开始的最长路径长度。计算方式：t_lvl(v) = w(v) + max_{(u,v)∈E} (t_lvl(u) + c(u, v))。这可以理解为任务v最早可能的开始时间（如果无限多处理器）。
- 自下而上的层级（Bottom Level, b_lvl）：也称为到终止节点结束的最长路径长度。计算方式：b_lvl(v) = w(v) + max_{(v,u)∈E} (c(v, u) + b_lvl(u))。这可以理解为任务v本身及其所有后继任务至少需要的时间。
- 动态级别（Dynamic Level）：在调度过程中动态计算，考虑任务到当前空闲处理器的时间。
调度循环：维护一个当前时间t和一个“就绪任务列表”（所有前驱已完成的任务）。算法不断循环，直到所有任务被调度：
a. 在时间t，找出所有空闲的处理器。
b. 从就绪任务列表中，按照全局任务列表L的顺序（或根据动态优先级），为每个空闲处理器分配一个任务。分配时要确保该任务的所有前驱任务都已完成，并且考虑到通信时间后，该任务确实可以在此时间t开始。
c. 如果没有就绪任务可以分配给当前的空闲处理器，则将时间t推进到下一个最早的任务完成时刻，然后重复步骤a。

第三步：详细算法步骤（以静态优先级为例）

我们以静态优先级（如b_lvl自下而上层级）为例，讲解一个不考虑处理器间通信的简化版本（即c(u,v)=0），这称为同构处理器列表调度。包含通信的版本（异构通信）逻辑类似，但就绪时间计算更复杂。

算法步骤：

计算优先级：
- 对DAG进行拓扑排序，然后逆序遍历（从出度为0的叶子节点开始）。
- 对于每个任务v，计算其b_lvl(v)：
  - 如果v是出口任务（没有后继），则b_lvl(v) = w(v)。
  - 否则，b_lvl(v) = w(v) + max_{u ∈ Succ(v)} b_lvl(u)，其中Succ(v)是v的直接后继集合。
- 计算完成后，按照b_lvl值从大到小对所有任务进行排序，得到任务列表L。b_lvl值大的任务被认为更关键，优先级更高。
初始化：
- 所有处理器标记为空闲。
- 每个任务的完成时间初始化为未知，前驱完成计数初始化为其入度（即有多少个前驱任务）。
- 当前时间t = 0。
- 维护一个就绪队列，初始时包含所有入度为0的任务。
主调度循环：
- WHILE 还有任务未被调度 DO:
  a. 识别就绪任务与空闲处理器：在时间t，检查是否有任务完成，释放其占用的处理器。将新就绪的任务（前驱完成计数减为0的）加入就绪队列。同时收集当前所有空闲处理器的集合FreeProcs。
  b. 分配任务：如果就绪队列非空且FreeProcs非空，则：
  * 按照全局优先级列表L的顺序，依次检查就绪队列中的每个任务v。
  * 将v分配给当前某个空闲处理器p（例如，第一个可用的）。
  * 记录任务v的开始时间start(v) = t，结束时间finish(v) = t + w(v)。
  * 将处理器p标记为忙碌，直到finish(v)。
  * 从就绪队列和FreeProcs中移除v和p。
  * 为v的每个直接后继任务u，将其前驱完成计数减1。如果减到0，则u变为新的就绪任务（但需要等到下一次循环步骤a才会被加入就绪队列，因为当前分配循环可能在同一个t进行）。
  * 重复此过程，直到就绪队列为空或FreeProcs为空。
  c. 时间推进：如果此时仍有任务未被调度完（即就绪队列为空但还有任务在运行，或者有任务未运行但就绪队列为空且无空闲处理器），则：
  * 找到所有正在运行的任务中，最小的结束时间t_next。
  * 将当前时间t推进到t_next。在t_next时刻，一个或多个任务完成，处理器被释放，回到步骤a。
输出：当所有任务都被调度后，算法结束。整个调度方案的完成时间（Makespan）是最后一个任务完成的时间max_{v∈V} finish(v)。

第四步：关键点与示例

为何b_lvl是好的优先级：b_lvl值大的任务位于长的关键路径上。优先调度它们，有助于避免关键路径延迟，从而减少总的Makespan。
示例说明：假设有4个任务A, B, C, D，计算代价均为1。依赖为：A->C, A->D, B->D。有2个处理器P1, P2。
- 计算b_lvl: D(1), C(1), A(1+max(1,1)=2), B(1+1=2)。优先级列表L: [A, B, C, D] (b_lvl降序)。
- t=0: 就绪队列=[A, B]。P1空闲，P2空闲。按L顺序，P1执行A，P2执行B。
- t=1: A和B完成。A完成使得C和D的前驱计数减1。C就绪，D的前驱计数从2减为1（还需等B）。就绪队列=[C]。P1和P2空闲。P1执行C。
- t=2: C完成。B的完成（在t=1时）使得D的前驱计数从1减为0，D就绪。就绪队列=[D]。P2空闲，执行D。
- t=3: D完成。Makespan=3。
考虑通信代价：当考虑通信代价c(u,v)时，计算任务v的最早开始时间（EST）变得更加复杂。即使v的所有前驱都已完成，如果v被分配到处理器p上，其开始时间至少是：max(处理器p的最早空闲时间, max_{u∈Pred(v)} (finish(u) + (u和v在不同处理器上 ? c(u,v) : 0)))。列表调度算法在为任务选择处理器时，会计算它在每个可用处理器上的EST，并选择使得EST最小的处理器（这称为最早完成时间（EFT）策略）。这使算法从简单的“列表”调度扩展为列表调度与动态分配的混合。

第五步：算法特性与近似比

时间复杂度：计算优先级（如b_lvl)需要O(|V|+|E|)。调度循环中，每次任务完成或开始都可能触发检查和分配，实现得当可达O(n^2)或O(n log n)，其中n为任务数。
性能保证（近似比）：对于同构处理器（无通信成本）的DAG调度，基于b_lvl优先级的列表调度算法有一个著名的近似比上界：2 - 1/P，其中P是处理器数量。这意味着算法得到的调度长度最多是最优解Makespan的(2 - 1/P)倍。当考虑通信代价时，理论分析更复杂，但列表调度在实践中仍表现良好。
优点：简单，易于实现，适用于动态环境，并且通常能得到较好的调度结果。
缺点：是启发式算法，不保证最优解；对于静态优先级，一旦列表确定，调度顺序就固定了，可能无法充分利用运行时信息。

总结

基于DAG的列表调度算法是并行与分布式任务调度中的一个基础且重要的启发式方法。它将复杂的调度问题分解为优先级排序和贪心分配两个阶段。通过巧妙地定义优先级（如b_lvl），算法能够优先调度关键路径上的任务，从而有效缩短整体完成时间。尽管它是近似算法，但其简单性、效率及理论上的性能保证，使其成为许多实际调度系统和编译器优化中的核心组件。扩展版本（如考虑通信、异构处理器）在此基础上融合了更多的优化策略，以适应更复杂的计算环境。

并行与分布式系统中的并行独立任务调度：基于有向无环图（DAG）的列表调度算法（List Scheduling）题目描述在并行与分布式计算中，我们常常需要将一组具有依赖关系的计算任务映射到多个处理器（或计算节点）上执行，以最小化总的完成时间（即调度长度，Makespan）。这些任务及其依赖关系通常用一个有向无环图（DAG）来表示。DAG中的每个节点代表一个任务，节点上的权重代表该任务的计算开销（执行时间）。DAG中的每条有向边 (u -> v) 表示任务 u 必须在任务 v 开始之前完成，边上的权重可以表示从 u 到 v 的数据传输开销（通信时间）。列表调度（List Scheduling）是一种经典的启发式算法，用于解决这个 DAG任务调度问题。其核心思想是：将所有任务按照某种优先级规则排序形成一个列表，然后按照这个列表的顺序，每当有处理器空闲时，就从中选择当前优先级最高且所有前驱任务都已完成的“就绪”任务分配给该处理器执行。这个问题的挑战在于：任务间存在复杂的依赖关系和可能的通信开销，而处理器的数量是固定的。目标是在多项式时间内，找到一个尽可能接近最优解的调度方案。列表调度算法以其简单、高效且具有理论上的性能保证（近似比）而闻名。解题过程循序渐进讲解我们假设有一个DAG，包含 n 个任务， m 个相同的处理器，目标是生成一个调度方案（每个任务在哪个处理器上、何时开始执行）。第一步：问题建模与输入任务图（DAG）： G = (V, E) ，其中 V 是任务集合， |V| = n 。每个任务 v 有一个计算代价 w(v) 。通信代价：对于每条边 e = (u, v) ∈ E ，有一个通信代价 c(u, v) 。这表示如果任务 u 和 v 被分配到不同的处理器上执行，那么在 u 完成后，需要等待 c(u, v) 的时间，数据才能传输到 v 所在的处理器， v 才能开始。如果 u 和 v 在同一处理器上，则通信代价通常视为0。处理器： P 个相同的处理器， P1, P2, ..., Pp 。调度目标：找到一个从任务到（处理器，开始时间）的映射，满足所有依赖约束，并最小化最后一个任务完成的时间（Makespan）。第二步：理解列表调度的核心框架列表调度是一个贪心算法框架，它包含两个关键部分：优先级计算：为每个任务计算一个静态或动态的优先级，并根据此优先级对所有任务进行排序，形成一个有序列表 L 。常见的优先级包括：自上而下的层级（Top Level, t_ lvl）：也称为从起始节点开始的最长路径长度。计算方式： t_lvl(v) = w(v) + max_{(u,v)∈E} (t_lvl(u) + c(u, v)) 。这可以理解为任务 v 最早可能的开始时间（如果无限多处理器）。自下而上的层级（Bottom Level, b_ lvl）：也称为到终止节点结束的最长路径长度。计算方式： b_lvl(v) = w(v) + max_{(v,u)∈E} (c(v, u) + b_lvl(u)) 。这可以理解为任务 v 本身及其所有后继任务至少需要的时间。动态级别（Dynamic Level）：在调度过程中动态计算，考虑任务到当前空闲处理器的时间。调度循环：维护一个当前时间 t 和一个“就绪任务列表”（所有前驱已完成的任务）。算法不断循环，直到所有任务被调度： a. 在时间 t ，找出所有空闲的处理器。 b. 从就绪任务列表中，按照全局任务列表 L 的顺序（或根据动态优先级），为每个空闲处理器分配一个任务。分配时要确保该任务的所有前驱任务都已完成，并且考虑到通信时间后，该任务确实可以在此时间 t 开始。 c. 如果没有就绪任务可以分配给当前的空闲处理器，则将时间 t 推进到下一个最早的任务完成时刻，然后重复步骤a。第三步：详细算法步骤（以静态优先级为例）我们以静态优先级（如 b_lvl 自下而上层级）为例，讲解一个不考虑处理器间通信的简化版本（即 c(u,v)=0 ），这称为同构处理器列表调度。包含通信的版本（异构通信）逻辑类似，但就绪时间计算更复杂。算法步骤：计算优先级：对DAG进行拓扑排序，然后逆序遍历（从出度为0的叶子节点开始）。对于每个任务 v ，计算其 b_lvl(v) ：如果 v 是出口任务（没有后继），则 b_lvl(v) = w(v) 。否则， b_lvl(v) = w(v) + max_{u ∈ Succ(v)} b_lvl(u) ，其中 Succ(v) 是 v 的直接后继集合。计算完成后，按照 b_lvl 值从大到小对所有任务进行排序，得到任务列表 L 。 b_lvl 值大的任务被认为更关键，优先级更高。初始化：所有处理器标记为空闲。每个任务的完成时间初始化为未知，前驱完成计数初始化为其入度（即有多少个前驱任务）。当前时间 t = 0 。维护一个就绪队列，初始时包含所有入度为0的任务。主调度循环： WHILE 还有任务未被调度 DO : a. 识别就绪任务与空闲处理器：在时间 t ，检查是否有任务完成，释放其占用的处理器。将新就绪的任务（前驱完成计数减为0的）加入就绪队列。同时收集当前所有空闲处理器的集合 FreeProcs 。 b. 分配任务：如果就绪队列非空且 FreeProcs 非空，则： * 按照全局优先级列表 L 的顺序，依次检查就绪队列中的每个任务 v 。 * 将 v 分配给当前某个空闲处理器 p （例如，第一个可用的）。 * 记录任务 v 的开始时间 start(v) = t ，结束时间 finish(v) = t + w(v) 。 * 将处理器 p 标记为忙碌，直到 finish(v) 。 * 从就绪队列和 FreeProcs 中移除 v 和 p 。 * 为 v 的每个直接后继任务 u ，将其前驱完成计数减1。如果减到0，则 u 变为新的就绪任务（但需要等到下一次循环步骤a才会被加入就绪队列，因为当前分配循环可能在同一个 t 进行）。 * 重复此过程，直到就绪队列为空或 FreeProcs 为空。 c. 时间推进：如果此时仍有任务未被调度完（即就绪队列为空但还有任务在运行，或者有任务未运行但就绪队列为空且无空闲处理器），则： * 找到所有正在运行的任务中，最小的结束时间 t_next 。 * 将当前时间 t 推进到 t_next 。在 t_next 时刻，一个或多个任务完成，处理器被释放，回到步骤a。输出：当所有任务都被调度后，算法结束。整个调度方案的完成时间（Makespan）是最后一个任务完成的时间 max_{v∈V} finish(v) 。第四步：关键点与示例为何 b_lvl 是好的优先级： b_lvl 值大的任务位于长的关键路径上。优先调度它们，有助于避免关键路径延迟，从而减少总的Makespan。示例说明：假设有4个任务A, B, C, D，计算代价均为1。依赖为：A->C, A->D, B->D。有2个处理器P1, P2。计算 b_lvl : D(1), C(1), A(1+max(1,1)=2), B(1+1=2)。优先级列表L: [ A, B, C, D] (b_ lvl降序)。 t=0: 就绪队列=[ A, B ]。P1空闲，P2空闲。按L顺序，P1执行A，P2执行B。 t=1: A和B完成。A完成使得C和D的前驱计数减1。C就绪，D的前驱计数从2减为1（还需等B）。就绪队列=[ C ]。P1和P2空闲。P1执行C。 t=2: C完成。B的完成（在t=1时）使得D的前驱计数从1减为0，D就绪。就绪队列=[ D ]。P2空闲，执行D。 t=3: D完成。Makespan=3。考虑通信代价：当考虑通信代价 c(u,v) 时，计算任务 v 的最早开始时间（EST）变得更加复杂。即使 v 的所有前驱都已完成，如果 v 被分配到处理器 p 上，其开始时间至少是： max(处理器p的最早空闲时间, max_{u∈Pred(v)} (finish(u) + (u和v在不同处理器上 ? c(u,v) : 0))) 。列表调度算法在为任务选择处理器时，会计算它在每个可用处理器上的EST，并选择使得EST最小的处理器（这称为最早完成时间（EFT）策略）。这使算法从简单的“列表”调度扩展为列表调度与动态分配的混合。第五步：算法特性与近似比时间复杂度：计算优先级（如 b_lvl )需要 O(|V|+|E|) 。调度循环中，每次任务完成或开始都可能触发检查和分配，实现得当可达 O(n^2) 或 O(n log n) ，其中 n 为任务数。性能保证（近似比）：对于同构处理器（无通信成本）的DAG调度，基于 b_lvl 优先级的列表调度算法有一个著名的近似比上界： 2 - 1/P ，其中P是处理器数量。这意味着算法得到的调度长度最多是最优解Makespan的 (2 - 1/P) 倍。当考虑通信代价时，理论分析更复杂，但列表调度在实践中仍表现良好。优点：简单，易于实现，适用于动态环境，并且通常能得到较好的调度结果。缺点：是启发式算法，不保证最优解；对于静态优先级，一旦列表确定，调度顺序就固定了，可能无法充分利用运行时信息。总结基于DAG的列表调度算法是并行与分布式任务调度中的一个基础且重要的启发式方法。它将复杂的调度问题分解为优先级排序和贪心分配两个阶段。通过巧妙地定义优先级（如 b_lvl ），算法能够优先调度关键路径上的任务，从而有效缩短整体完成时间。尽管它是近似算法，但其简单性、效率及理论上的性能保证，使其成为许多实际调度系统和编译器优化中的核心组件。扩展版本（如考虑通信、异构处理器）在此基础上融合了更多的优化策略，以适应更复杂的计算环境。