允许并发遍历图的算法

Question

在描述一组任务的有向无环图中，我需要找到所有可以并行处理的任务。该图没有循环且规模较小（约1000个节点，2000条边），性能不是主要问题。

带有所需结果的示例：

- [] 是一个组。必须在继续之前处理组中的所有任务。 - [x & y] 表示 x 和 y 可以并行处理（x 和 y 并行）。 - x -> y 表示 x 和 y 必须按顺序处理（x 在 y 之前）。

1

a -> [b & c] -> c

2

[a & e] -> b -> c -> [d & f]

3

[ [a -> b] & [e -> f] ] -> [ [c -> d] & g ]

我不想实际执行图形，而是构建一个尽可能并行的数据结构，同时保持顺序。算法的术语和名称对我来说不是很熟悉，所以我很难在网上找到类似的问题/解决方案。

- Antti

---

如果您想要最短的执行时间计划，那么这很容易。否则，在图形上可能会很困难，但如果您的输入确实是那些表达式而不是一般的DAG，则可能很容易。 - Matt Timmermans

你的例子很基础。对于更复杂的图表，例如这个，你会期望什么输出？ - trincot

@trincot 与上面相同格式的图片。按照我上面指定的格式： a -> [ [b -> c -> e] & [d -> f] ] -> g -> h 或者 a -> [ b & [d -> f] ] -> [ [c -> e] & g ] -> h 这个想法是一个任务必须在所有依赖项都准备就绪后才能运行。任何时候，如果有多个任务可以运行，则它们会并发运行。由于有多种解决方案，因此这似乎更像是一个优化问题，而不是我之前意识到的那样。在这里，第一个解决方案略微更好，因为它允许 c 在等待 f 之前开始处理。 - Antti

@Antti 问题在于，通常情况下，当您将DAG推入顺序格式时，您将丢失一些信息（DAG的信息），因此您很可能也会始终拥有非最优调度。在上面的示例中，g 在第一个解决方案中等待 c->e，而 c 在第二个解决方案中等待 d->f。因此，如果您绝对需要这种格式，则需要定义某些指标，使得一种解决方案比另一种更好。例如，违规数量或序列长度。或者您可以为问题提供更多约束条件，例如任务具有单位长度。 - rex123

你的图表中没有我图表中的链接d->e，这会使它更加复杂（你能提出建议吗？）。但是，是的：通过将其压缩到所需的输出，您将不得不添加比原始图表中更多的限制。在您提供的第一种解决方案中，您让g等待e，这与它无关。而在第二个解决方案中，您让c等待f...那么，在您认为不可接受之前，可以添加多少此类额外依赖项到问题中？ - trincot

Answer 1

从数学角度来看，我会将这个问题构建成找到一个最小定义的串并联偏序，扩展给定的偏序。

我会首先转化为传递闭包，然后重复应用两个启发式算法。

1. 如果x有一个依赖项y，而y只依赖于x，则将它们合并成一个新的节点z=[x → y]。
2. 如果x和y有相同的依赖项和依赖关系，则将它们合并成一个新的节点z=[x & y]。

现在，如果输入已经是串并联的，则结果将是一个节点。但通常情况下，这将留下一个嵌入了类似于问题中最后一个例子中的b → c，b → g，f → g的N形结构的图形。必须通过添加一个或多个b → f，c → f，c → g，f → b，f → c，g → c来解决这个结构。但在另一个实例中，此操作又会创建新的N形结构。没有明显的闭包概念，这就是为什么这个问题对我来说很难的原因。

其中一些选择似乎比其他选择更糟糕。例如，c → f强制执行b→c→f→g的顺序，而f→c是唯一不会增加关键路径长度的选择。

我想我会尝试：

3. 如果启发式算法1和2没有目标，则形成一个图，边为x--y，当且仅当x和y具有公共依赖项或公共依赖性时，计算此图的连通分量，并合并最小的非单例组件，然后进行另一次传递闭包缩减。

- David Eisenstat

Answer 2

这是我想到的解决方案（伪代码）：

sequence = []
for each (node, depth) in depthFirstSearch(graph)
  sequence[depth].push(node)
return sequence

< p > sequence 定义了处理图形的顺序。如果其中的一个项目包含多个节点，则可以同时处理它们。

虽然这样可以实现一些并发，但它不会像它本应该那样快速地前进。例如，在问题中的第 3 个示例中，f 需要先完成 a（因为当 a 和 e 在深度0时，它将在深度1），理想情况下，当 e 完成时，可以开始处理 f 的工作。

- Antti

---

depthFirstSearch似乎无法解决第三个例子，长进程a可能与e和f同时运行。 - raxetul