如何并行化具有依赖关系的任务节点图

我有一个任务的有向无环图(DAG),其中有向边表示依赖关系。为了使任务的执行并行化,我尝试了一些技术,但是我想知道解决这个问题的最佳方法。

A , B , C , D

         C ---.
               \
A ----------------> D
   \           /
    `--> B ---`

• A 没有依赖项;它可以立即运行
• A ,无需等待。如果它在不同的线程上 A
• C 没有依赖项,因此可以立即运行
• D A , ,和 ,它的完成标志着整个图的完成

.

到目前为止,我尝试过的最好的方法是:

1. 按拓扑结构将图形排序为列表
2. 分析节点以了解它们执行所需的时间。
3. 生成执行计划。使用N个工作线程,以相反的方式逐个任务地“填充”它们的调度(因此,从终端节点开始)。在依赖关系导致等待的情况下,这是计划中的一个缺口。

我认为我的解决方案不是最优的是因为有很多方法可以对一个图进行拓扑排序,这会产生不同的执行计划。因此,即使我的方法是最优的,我的实现可能不是因为我目前没有任何优化策略来生成列表。

我认为等待时间最少的执行计划是最好的,但我觉得我是在编这个。