algorithm - 如何通过合并任务来 reduce task 数量？

Question

我有一大组任务对象。大多数任务都有 parent 任务 -- 之前需要执行。大多数任务都有子任务 -- 只能在之后执行。关键是这样一组任务对象，一旦创建就经常执行并且应该通过并行执行任务来利用所有可用的 CPU。我遇到的问题是，与任务对象相关的工作量往往太小——调度代码只处理自身——真正要做的工作不会显示在分析结果中(咧嘴一笑)。任务对象确实提供了成本函数!我正在考虑创建另一组任务对象，每个新任务对象都包含旧任务对象的集合。这些新任务对象引用的父子对象当然也应该是新任务对象。这将通过降低并行度来减少必要的通信。

显然，将旧任务合并到新任务中有更好和更坏的方法......

有人能想出一个算法来做这件事吗？我是在重新发明轮子吗？

Answer 1

您似乎拥有一组要执行的任务的部分顺序，其中前置任务必须在后续任务运行之前完成。

如果你对任务T2的执行成本有一个度量，并且小于调度开销，那么你可以考虑优化掉它。

如果它只有一个前驱 T1(只需将其代码插入到前驱 T1 的末尾，并将前驱 T1 链接到 T2 的后继)或只有一个后继 T3(只需将其代码插入到继任者 T3 的开始，并将 T2 的前任链接到 T3)。

假设你有

     (;|  1 (<< 2 4)  a
          2 b
          3 (<< 4) c
          4 d )

(一个部分顺序 PARLANSE 程序，任务 1 2 3 4 分别由工作 a b c d 组成，任务 1 在任务 2 和 4 之前发生，任务 3 在 4 之前发生。有趣的运算符“;|”是由部分顺序混合驱动的串行“;”和并行“|”计算。有趣的运算符 (<< n m) 表示“运行时间早于 n 和 m”。 请注意，任务 1 和 3 可以并行运行； 2 和 3 以及 2 和 4 也可以。[这是可以表达的非完全平行的最小偏序]。

如果 b 太小，您可以将其优化为:

     (;|  1 (<< 4)  (;; a  b)
          3 (<< 4) c
          4 d )

其中 a 和 b 是串行执行的。

如果它有多个前任和后继者，那就没那么容易了。您可以利用的事实是，任何偏序计算都有许多完全合法的线性化。在这种情况下，您基本上想要收集一组在其中一个序列中线性化的成本太低的任务，并用它们的线性化替换它们。

假设任务 4 太小了。因为 a b c d 是偏序的有效线性化，您可以组合任务 c 和 d:

     (;|  1 (<< 2 3)  a
          2 b
          3 (;; c d) )

在极端情况下，这个过程会序列化所有计算，如果它们的成本很小，而这正是您在这种情况下想要的。