我有 [;N;] 工作单元 [;w_n;]，它们实际上是可并行化的，令人尴尬。每个都需要大约给定的时间长度，[;t_n;]，这是我们事先知道的。
鉴于我可能需要处理工作单元的某些子集，以及我可能使用最多 [;P;] 进程的约束，每个进程都在单独的 CPU 上，我如何提前有效地分配工作单元，以使所有进程尽可能（及时）彼此接近地完成？
问问题
69 次
1 回答
2
A）如果它们在统计上都是相同的持续时间，并且你无法控制它们中的任何一个运行多长时间，我猜平均而言，你不能做得比“一个处理器完成一个工作单元，需要任何未完成的工作单元并执行直到完成”。您的平均运行时间将为 Sum(1..N,t_n)/P。
B）如果他们有一些可预测的时间，我很想要求每个进程选择估计时间最长的剩余工作单元，然后运行它。这首先运行所有昂贵的工作，留下大量的小工作来回填剩余的时间。
C) 如果您坚持预先选择的静态计划，请离线运行算法 B) 并为流程预先分配工作单元。与动态计划相比，这可能会为您提供更长的总运行时间，动态计划可以在一定程度上考虑实际变化。
于 2013-03-01T20:39:45.143 回答