在依赖项分辨率中获取并行项目

Question

我已经根据 维基百科文章 我正在使用依赖项解决方案，但它返回线性列表。我可以使用什么样的算法来找到独立的路径？

Answer 1

我认为边缘$（u，v）$表示必须在$ v $之前执行$ u $。如果不是这种情况，请扭转所有边缘。此外，我认为您对路径（已经由DAG给出的路径）不太感兴趣，而不是对依赖性的良好执行策略。

您可以轻松地调整拓扑排序过程：而不是附加的，而是将所有相同“深度”的项目合并到一个集合中。您将获得一个集合的列表，每个集合包含可以并行执行/安装的项目。正式地，为图$ g =（v，e）$：sets $ s_i $：

美元v in V mid forall u in V.（u，v） in e to u in bigCup_ {k = 0}^i s_k }

然后，您可以这样执行您的任务（假设有$ K $集）：

for i=0 to k
  parallel foreach T in S_k
    execute T

当然，如果任务花费不同的时间：两个平行的独立线性链在每个元素之后同步，则不会产生最大的吞吐量。为了解决这个问题，我建议您直接在源头上直接在dag上工作，从源节点开始 - $ s_0 $的那些 - 并在节点中同步/分叉，并带有几个传入/传出的边缘：

parallel foreach T in S_0
  recursive_execute T

在哪里

recursive_execute T {
  atomic { if T.count++ < T.indeg then return }
  execute T
  parallel foreach T' in T.succ
    recursive_execute T'
}

和 T.count 是一个简单的计数器，持有 T 已经执行的 T.indeg 预科员的数量和 T.succ 一组继任者。