Ответ 1

Балансировка нагрузки не является бесплатной; он имеет стоимость переключения контекста (к ядру), нахождение простаивающих процессоров и выбор работы для переназначения. Особенно в машине, где задачи переключаются все время, десятки раз в секунду, эта стоимость складывается.

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

Пример

Рассмотрим: процессор A имеет две задачи, назначенные ему. Они занимают время a1 и a2 соответственно. Процессор B, расположенный рядом (возможно, расстояние от кэш-памяти), простаивает. Процессоры идентичны во всех отношениях. Мы предполагаем код для каждой задачи, а ядро ​​находится в i-кеше обоих процессоров (без дополнительной ошибки страницы при балансировке нагрузки).

Переключатель контекста любого типа (включая балансировку нагрузки) занимает время c.

Балансировка нагрузки

Время выполнения задач будет a1 + a2 + c. Процессор A выполнит всю работу и перенесет один контекстный переключатель между двумя задачами.

Работа-Stealing

Предположим, что B крадет a2, неся время переключения контекста. Работа будет выполнена в режиме max (a1, a2 + c). Предположим, что процессор A начинает работать над a1; в то время как он делает это, процессор B будет украсть a2 и избежать любого прерывания обработки a1. Все накладные расходы на B являются свободными циклами.

Если a2 была более короткой задачей, здесь вы фактически скрыли стоимость контекстного переключателя в этом сценарии; общее время равно a1.

Работа-Пожав

Предположим, что B завершает a2, как указано выше, но A берет на себя затраты на его перемещение ( "пожав плечами" ). Работа в этом случае будет выполняться в макс (a1, a2) + c времени; контекстный переключатель теперь всегда в дополнение к общему времени, а не скрыт. Здесь простаивают холостые байты процессора B; вместо этого, занятый процессор A сжигал время, когда пожал плечами. B.

Ответ 2

Я думаю, что проблема с этой идеей заключается в том, что она заставляет потоки с фактической работой тратить свое время на постоянный поиск простаивающих процессоров. Конечно, есть способы сделать это быстрее, например, иметь очередь бездействующих процессоров, но тогда эта очередь становится узким местом concurrency. Так что лучше иметь нити, с которыми лучше не сидеть и искать работу.

Ответ 3

Основным преимуществом алгоритмов "кражи работы" является то, что накладные расходы на перемещение работы снижаются до 0, когда все заняты. Таким образом, только накладные расходы, когда какой-либо процессор в противном случае был бы бездействующим, и что накладные расходы в основном оплачиваются процессором бездействия, и только очень небольшая стоимость, связанная с синхронизацией шины, с занятым процессором.

Ответ 4

Кража работы, как я понимаю, предназначена для высокопараллельных систем, чтобы не иметь единого места (отдельный поток или единый регион памяти), ответственного за передачу работы. Чтобы избежать этого узкого места, я думаю, что он вводит неэффективность в простых случаях.

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

Понятия не имею, что вы могли бы сделать Google, боюсь.

Ответ 5

Некоторые проблемы... если занятый поток занят, разве вы не хотите, чтобы он тратил время на обработку реальной работы, вместо того, чтобы спекулятивно искать холостые потоки для разгрузки?

Как ваш поток решает, когда у него столько работы, что он должен прекратить делать эту работу, чтобы найти друга, который поможет?

Откуда вы знаете, что в других потоках не так много работы, и вы не сможете найти подходящий поток для разгрузки?

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

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

Хотя в вашем редактировании вы предполагаете, что хотите обработать процессор, а не рабочие потоки, как было предложено ранее, и в некоторых комментариях здесь. Если подающий процессор ищет минимальную длину очереди, вы потенциально добавляете латентность в submit, что не очень желательно.

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

Я думаю, что ваше отредактированное предложение с потоком подачи, выполняющим "умное" распределение работы, потенциально является преждевременной оптимизацией против кражи работы. Ваши холостые потоки так сильно врезались в автобус, что ваши бездействующие потоки не могут выполнить какую-либо работу? Затем настало время оптимизировать кражу работы.

Ответ 6

Итак, в отличие от "Work Stealing", то, что на самом деле означает "Work Shrugging", - это обычная стратегия планирования работы, которая умеет работать с процессором, кешем и памятью и масштабируется.

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