«Воровство работы» против «пожимания плечами работы»? - PullRequest
14 голосов
/ 31 марта 2010

Почему я могу найти много информации о «краже труда» и ничего о «пожимании плечами» в качестве стратегии динамического распределения нагрузки?

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

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

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

Разъяснение

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

Я не думаю, что логика принятия решения потребует гораздо большего, чем атомарное чтениерасчетная длина q ближайших (обычно от 2 до 4) соседей здесь.Я не думаю, что это больше связывает, чем подразумевают воры, опрашивающие и крадущие у своих соседей.(Я предполагаю, что очереди «без блокировки, без ожидания» в обеих стратегиях).

Разрешение

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

Я нахожу множество ссылок, ищущих по этим терминам инекоторые из них выглядят довольно солидно.Я опубликую ссылку, когда найду такую, которая лучше всего соответствует (или разрушает!) Логике, которую я имел в виду, с моим определением «Трудового пожимания плечами».

Ответы [ 6 ]

18 голосов
/ 31 марта 2010

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

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

Пример

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

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

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

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

Work-Stealing

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

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

Work-Пожав

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

5 голосов
/ 31 марта 2010

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

3 голосов
/ 31 марта 2010

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

2 голосов
/ 01 апреля 2010

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

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

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

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

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

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

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

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

2 голосов
/ 31 марта 2010

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

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

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

0 голосов
/ 01 апреля 2010

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

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

...