我有一大组任务对象。 大多数任务都有 parent 任务 -- 之前需要执行。 大多数任务都有子任务 -- 只能在之后执行。 关键是这样一组任务对象,一旦创建就经常执行 并且应该通过并行执行任务来利用所有可用的 CPU。 我遇到的问题是,与任务对象相关的工作量往往太小——调度代码只处理自身——真正要做的工作不会显示在分析结果中(咧嘴一笑)。 任务对象确实提供了成本函数! 我正在考虑创建另一组任务对象, 每个新任务对象都包含旧任务对象的集合。 这些新任务对象引用的父子对象当然也应该是新任务对象。 这将通过降低并行度来减少必要的通信。
显然,将旧任务合并到新任务中有更好和更坏的方法......
有人能想出一个算法来做这件事吗? 我是在重新发明轮子吗?
最佳答案
您似乎拥有一组要执行的任务的部分顺序,其中前置任务必须在后续任务运行之前完成。
如果你对任务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) )
在极端情况下,这个过程会序列化所有计算,如果它们的成本很小,而这正是您在这种情况下想要的。
关于algorithm - 如何通过合并任务来 reduce task 数量?,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/16803226/