如何计算 DAG 中的最大并行度？

Question

给定一个 DAG（有向无环图），如何计算最大并行度？

瞬时并行度是在算法执行的每个点上可以保持忙碌的最大处理器数；的最大并行最高瞬时并行。

换句话说，给定一个表示任务依赖关系图的 DAG，最少有多少处理器/线程才能保证没有任务被阻塞？

我在这里找到的最接近的方法是：

• 在 DAG 上应用拓扑排序
• 按拓扑顺序遍历节点，计算最小层级：
  • 没有父母：0
  • 否则：最低父级 + 1
• 返回最大级别宽度（分配相同级别的最大节点数）

这个算法在几个样本上对我有用，但是在树上不起作用。例如：

  o 0
 / \
o 1 o 1
   / \
  o 2 o 2
     / \
    o 3 o 3

根据上面的算法，最大宽度为 2，但树中的最大并行度显然是叶子的数量，在上面的示例中为 4。

此处部分描述了一种类似的方法（请参阅标题为 的幻灯片Computing critical path etc.，其中描述了如何计算节点的最早开始时间以及“可以很容易地从中计算出最大...并行度”）。

---

编辑1：

@AliSoltani 使用 BFS 找到关键路径的长度即最大并行度的解决方案是不正确的，因为它仅适用于示例的子集，主要是叶子数等于最长路径的树。这是一个不起作用的情况的说明：

---

编辑2：

@AliSultani 的第二个解决方案使用 BFS 找到具有最大节点数的级别，并将该最大值设置为最大并行度，这也是不正确的，因为它没有考虑来自不同级别的节点可能同时运行的情况。看这个反例：

Answer 1

你应该critical path length在 DAG 中找到。关键路径是DAG中所有其他路径中执行要求最高的有向路径。critical path length在有 n 个节点的 DAG 中，有 n 个节点。亦是如此。maximal parallelism​n

关键路径是longest path从根到叶（在 DAG 中），要找到它，您可以使用BFS算法（呼吸优先搜索）。

实施例1

BFS order在这棵树上是O(|V|+|E|)。这是该问题的最佳解决方案。

编辑：通过 BFS 查找最大并发度

您也可以通过运行广度优先搜索算法来确定最大并发度：

• 该算法从根节点开始，逐级向叶节点进行。
• 在检查位于下一个级别的节点之前，它会探索属于同一级别的所有节点。
• 计算每个级别上的节点数并更新保存每个级别的最大节点数的变量。

示例 2（逐步）

所以在这个例子中最大并发度是4。

最终编辑

根据您给出的最后解释，您正在寻找最大的独立任务集。要解决这个问题请看这篇文章。