考虑延迟和效率的最佳任务分配方式

Question

我正在寻找一种算法来分配一些任务。问题如下：

假设我有一个中心任务生产者和一些客户端消费者。生产者生成任务，消费者接受任务(对于初学者，一次一个)，处理它们，当它们完成后，接受新的任务(我已经有一个任务队列)。

问题是，如果考虑到任务从生产者到消费者的延迟，将任务分组在一起可能是有意义的。例如，假设我们总共有10个任务和2个消费者。如果每个任务的处理时间为5ms，网络延迟也为5ms，则向每个消费者发送两组各5个任务将花费5ms+ 5*5ms = 30ms，而单独发送任务将花费5*5ms + 5*5ms = 50ms，因为每个任务都会出现延迟开销。

它不像分组那么简单，因为一些任务可能会花费更长的时间，并且将它们分开发送将是有意义的，因为让其他使用者并行处理耗时较短的其他任务。我计划做一些关于任务类型的统计。消费者的数量也不是恒定的。

有没有一个好的算法或好的阅读方法可以帮助我实现这一点？

Answer 1

在生产者生成任务的时候，不立即发送它只会增加该任务的延迟。因此，我假设任务分派器在当前任务队列的快照上工作:它获取队列中的所有任务，立即向所有方向发送它们，返回队列，再次获取在此期间积累的所有任务，起泡，冲洗，重复。

调度程序维护每个使用者的完成时间的估计。它根据完成时间的增加对消费者进行排序，并将一个任务添加到完成时间最早的消费者的批次中。然后，它将平均任务时间与消费者完成时间估计值相加，从而获得新的估计值，然后根据新的估计值对消费者进行重新排序(在使用堆的O(log n)中)，并转到下一个任务。在处理完当前快照的所有任务后，将批发送给消费者，然后去制作新的快照。

此策略将实现平均相等的消费者负载。它可以改进：

• ，如果每个消费者能够提供一些关于估计完成时间的反馈:它是平均任务时间乘以消费者中挂起的任务数量。它更精确，因为如果处理每个任务的时间已知或可以按任务估计，则使用者将使用完成任务的实际时间，而不是平均
• ，因此调度程序将使用每个任务的估计值，而不是平均值。

编辑：忘记提到：

完成时间估计为start-time + average-task-time * number-of-tasks-sent-to-a-consumer + latency * number-of-batches-sent-to-a-consumer。

Answer 2

为了澄清我对你的问题的评论，让我们假设你的消费者中有以下循环：

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()是并行执行的(显然，假设这两个函数不共享任何状态)。

Answer 3

啊..。细粒度并行(提供更好的负载平衡，但同步开销相对较高)和粗粒度并行(显然相反)之间的经典决策。抱歉，没有简单的答案。

一些想法：

1. 做了很多分析，这是找到合适数量的任务进行分组的好方法。很好的老方法：)
2. 考虑在每个客户端创建一个本地任务队列。这可以启用某种类型的预取，例如当任务n完成时，请求任务n+5并启动任务n+1。不确定您是否正在使用多线程，或者任务n+1是否会被中断以接受任务n+5。
3. 尝试尽可能压缩任务表示。这可能意味着使用char而不是int (这确实对数组有影响)。也许任务的某些部分可以在到达consumer.
4. Consider时重新计算，使用每个使用者上的某种计时器作为反馈，以调整下一次作为一个组的任务数量。如果你花了太多的时间，那么下次抓取更少的任务。当心一个花哨的启发式可能会有一些不平凡的开销。