如何在图问题中应用并行编程？

Question

问题描述：

有 n 个任务，其中一些任务可能依赖于其他任务，也就是如果 A 依赖于 B，则必须在 B 完成后才能完成 A。

1. 找出一种尽快完成这些任务的方法？

2. 如果考虑并行处理，如何设计程序来完成这些任务？

问题：

显然，回答第一个问题的方法是，对这些任务进行拓扑排序，然后按照那个顺序完成它们。

但是，在考虑并行处理的情况下，该如何处理？

我的答案是，首先对这些任务进行拓扑排序，然后选取那些不依赖于其他任务的任务，先完成它们，然后在剩余的任务中选取和完成那些不依赖于其他任务的任务...

我正确吗？

- Alcott

---

执行依赖关系任务前，如何并行递归执行每个依赖项？您需要一些记录来确保每个任务只被执行一次，但除此之外，它似乎很简单且高效。 - Vaughn Cato

这个回答解决了你的问题吗？有向无环图任务的并行执行 - Anmol Singh Jaggi

@AnmolSinghJaggi，您建议的目标是针对不同的语言，因此我认为它不合适。 - cigien

撤销了我的重复标记。 - Anmol Singh Jaggi

Answer 1

拓扑排序算法可以给出不同的结果顺序，因此您不能只取前几个元素并假设它们是独立的。

我建议您按入侵依赖边数对任务进行排序，而不是使用拓扑排序。例如，如果您的图具有A-->B、A-->C、B-->C、D-->C，则应将其排序为A[0]、D[0]、B[1]、C[3]，其中[i]表示入边数。

使用拓扑排序，您也可能会得到A、B、D、C。在这种情况下，很难找出您可以并行执行A和D的事实。

请注意，在完全处理某个任务后，您需要更新剩余任务，特别是那些依赖于已完成任务的任务。但是，如果进入任务的依赖关系数量相对较小（例如几百个），则可以轻松依赖于类似于基数/桶排序的东西，并保持常数时间更新排序结构。

通过这种方法，一旦一个单一的并行任务完成，您还可以轻松地启动新任务。只需更新依赖计数，并启动现在具有零入侵依赖的所有任务。

请注意，此方法假定您有足够的处理能力来同时处理没有依赖关系的所有任务。如果您的资源有限且关心处理时间的最优解，那么您需要投入更多的努力，因为问题变成了NP-hard（如arne已经提到的）。

因此，回答您最初的问题：是的，您基本上是正确的，但是，您没有解释如何有效地确定这些独立任务（请参见上面的示例）。

- Frank

Answer 2

我建议使用有向森林结构按任务执行时间作为边权重对它们进行排序。将树形结构从最重到最轻排序，并从最重的开始。使用这种方法，您可以同时检查循环依赖关系。

使用并行性会得到二进制问题，这是NP难题。尝试查找该问题的近似解决方案。

- arne

---

我当然是指二进制装箱问题。如果你在喝第一杯咖啡之前发布帖子，就会出现这种情况。 - arne

Answer 3

请看来自项目管理领域的关键路径法。它基本上可以满足您的需求：给定依赖关系和持续时间的任务，它会输出需要多少时间以及何时激活每个任务。

(*)请注意，该技术假设有无限数量的资源，以获得最佳解决方案。对于有限资源，有一些贪心算法的启发式方法，例如GPRW[当前+后续任务时间]或MSLK[最小总浮动时间]。

(*)还要注意，它需要知道（或至少估计）每个任务需要多长时间。

- amit