小编Ari*_*iel的帖子

给定一个 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 找到具有最大节点数的级别，并将该最大值设置为最大并行度，这也是不正确的，因为它没有考虑来自不同级别的节点可能同时运行的情况。看这个反例：