提问人：Luchian Grigore 提问时间：11/9/2011 更新时间：11/14/2011 访问量：325
考虑延迟和效率的最佳任务分配方式
Best way to distribute tasks considering latency and efficiency
问：
我正在寻找一种算法来分配一些任务。问题如下：
假设我有一个中心任务生产者和一些客户端消费者。生产者生成任务，消费者接受任务（对于初学者来说，一次一个），处理它们，当它们完成时，接受新任务（我已经有一个任务队列）。
问题是，如果您考虑任务从生产者到使用者的延迟，那么将任务组合在一起可能是有意义的。例如，假设我们总共有 10 个任务和 2 个消费者。如果每个任务需要 5 毫秒才能处理完毕，并且网络延迟也是 5 毫秒，则向每个消费者发送 2 组 5 个任务将花费 5 毫秒 + 5*5 毫秒 = 30 毫秒，而单独发送任务将花费 5*5 毫秒 + 5*5 毫秒 = 50 毫秒，因为每个任务都会出现延迟开销。
这并不像分组那么简单，因为某些任务可能需要更长的时间，将它们分开发送是有意义的，这样可以让其他需要较短时间的任务由其他使用者并行处理。我计划做一些关于任务类型的统计。消费者的数量也不是恒定的。
任何一个好的算法或一个好的阅读可以帮助我实现这一目标的想法吗？
答：
0赞
NPE
11/9/2011
#1
似乎简单方法的主要问题是消费者会在获取下一个任务所需的时间内停滞不前。在摊位期间没有完成任何有用的工作。
由于延迟（而不是带宽）是主要问题，因此一种解决方案是在多个任务之间摊销停顿，例如将任务分组。要做好这项工作，您需要很好地了解处理每个任务需要多长时间。
另一种方法是在处理当前任务的同时获取下一个任务。这可以通过两个线程轻松完成：线程处理当前任务和线程获取下一个任务。完成当前任务后，线程可以切换角色或将下一个任务从 传递给 。这是管道并行性的一种形式。ABABA
评论
0赞
Luchian Grigore
11/9/2011
这就是我要说的 - 将任务分批分组。但问题确实是......如何？多少任务取决于消费者的数量、延迟、平均任务处理时间......应该按批次分组吗？预取也不会有效，因为不同的使用者可能已经准备好获取任务，但它是由尚未处理它的使用者获取的。
0赞
NPE
11/9/2011
@LuchianGrigore：我认为你需要摆脱算法应该在每一个可能的（角落）情况下做最佳事情的想法。更重要的是平均性能，因为这是总体上的重要因素。
0赞
Luchian Grigore
11/9/2011
当然，但我仍然不知道如何考虑到给定类型任务的平均时间或平均延迟进行分组。我知道分组是要走的路，但我仍然需要知道如何去做。
0赞
NPE
11/9/2011
@LuchianGrigore：实际上，我的回答恰恰相反。我认为预取是要走的路，尽管您在之前的评论中概述了极端情况。
0赞
Luchian Grigore
11/9/2011
但是首选并不能解决任何问题，因为它也意味着延迟。甚至在单独的线程上运行......
-1赞
Micromega
11/9/2011
#2
如果延迟的定义可以增加到 2 维，这意味着使用者可以具有不同的延迟，那么您可以尝试空间填充曲线。SFC 细分 2d 并将复杂度降低到 1 维a。所以你从 f（x，y） 计算一个数字。然后，您可以对这个数字进行排序，并按此顺序将这个数字发送给消费者。当然，你必须先写一个SFC才能使用它，我不会为你做，但如果你有问题，我可以帮助你。
评论
0赞
Iterator
11/14/2011
我没有投反对票，但我看到了两个原因：你的回答写得很差，而且你没有解释证监会将如何帮助解决问题，只是说可以创建一个证监会。
0赞
Micromega
11/14/2011
我写道，他可以对数字进行排序，并按此顺序将数字发送给消费者。这有什么不清楚的？
1赞
chill
11/9/2011
#3
在生产者生成任务的那一刻，不立即发送只会增加该任务的延迟。因此，我将假设任务分派器在当前任务队列的快照上工作：它获取队列中的所有任务，立即向各个方向发送它们，返回队列，再次获取在此期间积累的所有任务，起泡，冲洗，重复。
调度程序维护每个使用者的完成时间的估计值。它根据增加的完成时间对消费者进行排序，并将任务添加到完成时间最早的消费者的批次中。然后，它将平均任务时间添加到消费者完成时间估计值中，从而获得新的估计值，然后根据新的估计值（使用堆）对消费者进行重新排序，然后转到下一个任务。当前快照的所有任务处理完毕后，将批次发送给消费者，然后去制作新的快照。O(log n)
该政策将平均实现相同的消费者负载。可以改进：
如果每个使用者都能够提供有关估计完成时间的一些反馈：则为平均任务时间乘以使用者中待处理的任务数。它更精确，因为消费者将使用完成任务的实际时间而不是平均值
如果处理每个任务的时间是已知的，或者可以按任务估计，则调度程序将使用每个任务的估计值而不是平均值。
编辑：忘了提：
完成时间估计为 。start-time + average-task-time * number-of-tasks-sent-to-a-consumer + latency * number-of-batches-sent-to-a-consumer
评论
0赞
Luchian Grigore
11/9/2011
这是一个很好的答案，谢谢。但我确实有一些笔记......系统确实在队列中传递了一大堆任务，因此当使用者启动时，可以安全地假设队列中有足够的任务可以绕过。其次，这与消费者的处理能力无关，因为这些处理能力或多或少是相同的，而是与任务类型有关（有不同类型的任务，有些需要更长的时间，有些则更慢）。我将尝试您的建议的改编版本。
1赞
CAFxX
11/10/2011
#4
为了澄清我对你的问题的评论，让我们假设你的消费者中有以下循环：
while (keepConsuming) {
Task t = Task::get();
t.process();
}
你可以像这样重写它（假设我们可以使用 OpenMP）：
Task cur=NULL, next;
do {
#pragma omp sections
{
#pragma omp section
if (cur != NULL) cur.process();
#pragma omp section
next = keepConsuming ? Task::get() : NULL;
}
cur = next;
} while (cur != NULL);
这样，while 中的 process（） 和 get（） 将并行执行（显然，假设这两个函数不共享任何状态）。
1赞
Jason
11/10/2011
#5
啊......细粒度并行性（提供更好的负载均衡，但同步开销相对较高）与粗粒度并行性（显然相反）之间的经典决策。对不起，但没有简单的答案......
一些想法：
进行大量分析，这是找到合适数量的任务组合在一起的好方法。只是很好的老试错:)
考虑在每个客户端上创建一个本地任务队列。这可以启用某种预取，例如，当任务 n 完成时，请求任务 n+5 并启动任务 n+1。不确定是否使用多线程，或者任务 n+1 是否会中断以接受任务 n+5。
尝试尽可能压缩任务表示形式。这可能意味着使用 char 而不是 int（这确实对数组有影响）。也许任务的某些部分可以在到达消费者手中时重新计算。
考虑对每个消费者使用某种计时器作为反馈，以调整下次要作为一个小组执行的任务数量。如果你花了太多时间，那么下次就少抓任务。请注意，花哨的启发式方法可能会有一些不平凡的开销。
上一个：模板编译错误 - 标准与否？
下一个：Java 成员初始化
评论