Geek Answers Handbook

The best way to distribute tasks based on latency and efficiency

I am looking for an algorithm to distribute some tasks. The problem is this:

Let's say I have a major task maker and some client clients. The producer creates tasks, and consumers take tasks (for starters, one at a time), process them, and when they are completed, perform new tasks (I already have a task queue).

The fact is that if you think that a task needs to be obtained from the producer to the consumer, it may make sense to combine the tasks together. For example, let's say we have 10 tasks in total and 2 consumers. If each task requires 5 ms and the network delay is 5 ms, sending each of two groups of 5 tasks to each of them will be 5 ms + 5 * 5 ms = 30 ms; individually, 5 * 5 will be required when sending tasks ms + 5 * 5ms = 50 ms, because the delay overhead appears for each task.

This is not as simple as grouping, as some tasks are likely to take longer and it would be wise to send them separately so that other tasks that take a shorter time are handled in parallel by other consumers. I plan to make some statistics about the type of tasks. The number of consumers is also not constant.

Any idea of ​​a good algorithm or good reading that can help me achieve this?

+5
source share
5 answers

, , . , : , , , , , , .

. . , , ( O(log n) ) . , , .

. :

  • : , , . ,

  • , , .

: :

start-time + average-task-time * number-of-tasks-sent-to-a-consumer + latency * number-of-batches-sent-to-a-consumer.

+1

, , :

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);

, () get() while (, - ).

+1

Ahhh... parallelism ( , ) parallelism (, , ). , ...

:

  • , . :)

  • . , . n , n + 5 n + 1. , n + 1 , n + 5.

  • . char int ( ). , , .

  • - , , . , . , , .

+1

, , , . .

, , , , , , . , , .

. : thread A B . A , , B A. parallelism.

0

If your definition of delay can be increased to 2 measurements, this means that cosumer may have a different delay, then you can try the gap filling curve. Sfc subdivides 2d and reduces complexity to 1 dimension. So you are calculating a number from f (x, y). Then you can sort this number and send the number in this order to consumers. Of course, you must write SFC before you can use it. I will not do this, but I can help you if you have problems.

-1
source

More articles:


All Articles