Лучший способ распределить задачи с учетом задержки и эффективности

Question

Я ищу алгоритм для распределения некоторых задач.Проблема в следующем:

Скажем, у меня есть центральный производитель задач и некоторые клиенты-клиенты.Производитель генерирует задачи, а потребители берут задачи (для начала, по одной), обрабатывают их, а когда они выполнены, берут новые задачи (у меня уже есть очередь задач).

Дело в том, что если вы учитываете задержку для задачи, передаваемой от производителя к потребителю, может иметь смысл сгруппировать задачи вместе.Например, скажем, у нас всего 10 задач и 2 потребителя.Если для выполнения каждой из задач требуется 5 мс, а задержка сети также составляет 5 мс, отправка 2 групп по 5 задач в каждой для каждого потребителя займет 5 мс + 5 * 5 мс = 30 мс, а отправка задач по отдельности - 5 * 5 мс.+ 5 * 5 мс = 50 мс, поскольку задержка появляется для каждой задачи.

Это не так просто, как группировка, поскольку некоторые задачи, вероятно, займут больше времени, и имеет смысл отправлять их по отдельности, чтобы позволить другим потребителям параллельно обрабатывать другие задачи, которые занимают более короткое время.Я планирую сделать некоторую статистику относительно типа задач.Число потребителей также не является постоянным.

Любая идея о хорошем алгоритме или хорошем чтении, которая может помочь мне в достижении этого?

Answer 1

Аааа ... классическое решение между мелкозернистым параллелизмом (который дает лучшую балансировку нагрузки, но относительно более высокие накладные расходы на синхронизацию) и грубозернистым параллелизмом (который, очевидно, дает противоположное).Извините, но нет простого ответа ...

Некоторые мысли:

1. Выполните много профилирования, это хороший способ найти подходящее количество задач для группировки.Просто старый добрый метод проб и ошибок:)

2. Подумайте о создании локальной очереди задач для каждого клиента.Это может позволить некоторую предварительную выборку, например, когда задача n завершается, запросить задачу n + 5 и запустить задачу n + 1.Не уверен, что вы используете многопоточность или задача n + 1 будет прервана для принятия задачи n + 5.

3. Постарайтесь максимально сжать представление задачи.Это может означать использование char вместо int (это имеет значение для массивов).Возможно, некоторые части задачи могут быть пересчитаны, когда они доходят до потребителя.

4. Подумайте об использовании какого-либо таймера для каждого потребителя в качестве обратной связи, чтобы скорректировать количество задач, которые нужно взять в группе.в следующий раз.Если вы тратите слишком много времени, в следующий раз возьмите меньше заданий.Остерегайтесь причудливой эвристики, которая может иметь некоторые нетривиальные издержки.

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

Таким образом, process () и get () внутри while выполняются параллельно (очевидно, при условии, что эти две функции не имеют общего состояния).

Answer 3

В тот момент, когда производитель создает задачу, ее немедленная отсылка только увеличивает задержку этой задачи. Поэтому я предполагаю, что диспетчер задач работает с снимками текущей очереди задач: он принимает все задачи в очереди, отправляет их сразу во всех направлениях, возвращается в очередь, снова принимает все задачи тем временем накапливаются, вспениваются, смываются, повторяются.

Диспетчер ведет оценку времени завершения каждого потребителя. Это заказывает потребителей в соответствии с увеличивающимся временем завершения и добавляет задачу к партии потребителя с самым ранним временем завершения. Затем он добавляет среднее время задачи к этой оценке времени завершения потребителей, получая, таким образом, новую оценку, затем переупорядочивает потребителей в соответствии с новыми оценками (в O(log n) с использованием кучи) и переходит к следующей задаче. После обработки всех задач текущего снимка отправьте пакеты потребителям и создайте новый снимок.

Эта политика обеспечит равную потребительскую нагрузку в среднем . Можно улучшить:

• , если каждый потребитель может предоставить некоторую обратную связь о предполагаемом времени выполнения: это среднее время выполнения задачи, умноженное на количество задач, ожидающих в клиенте. Точнее, потому что потребитель будет использовать фактическое время выполненных задач вместо среднего

• , если время обработки каждой задачи либо известно, либо может быть оценено для каждой задачи, поэтому диспетчер будет использовать оценку для каждой задачи вместо среднего.

РЕДАКТИРОВАТЬ: Забыл упомянуть:

Время завершения оценивается как start-time + average-task-time * number-of-tasks-sent-to-a-consumer + latency * number-of-batches-sent-to-a-consumer.

Answer 4

Если ваше определение задержки можно увеличить до 2-х измерений, это означает, что у потребителя может быть другая задержка, тогда вы можете попробовать заполнить пространство кривой. SFC разделить 2d и уменьшить сложность до 1 измерения. Таким образом, вы вычисляете число из f (x, y). Затем вы можете отсортировать этот номер и отправить номер в этом порядке для потребителей. Конечно, вы должны написать SFC, прежде чем сможете его использовать. Я не сделаю этого за вас, но могу помочь вам, если у вас возникнут проблемы.

Answer 5

Кажется, что основная проблема с простым подходом заключается в том, что потребитель будет останавливаться на количество времени, необходимое для получения следующей задачи.Во время остановки полезной работы не делается.

Поскольку задержка, а не пропускная способность, является основной проблемой, одним из решений является амортизация задержки в нескольких задачах, например, путем группировки задач в пакеты.Чтобы сделать это хорошо, вам нужно иметь хорошее представление о том, сколько времени займет выполнение каждой задачи.

Альтернативой является выборка следующей задачи параллельно с обработкой текущей.Это можно легко сделать с помощью двух потоков: поток A, обрабатывающий текущую задачу, и поток B, извлекающий следующую задачу.Когда A выполнено с текущей задачей, потоки могут либо поменять роли, либо передать следующую задачу с B на A.Это форма параллелизма конвейера.