Балансировка нагрузки в приложении параллельной обработки

Question

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

Приложение должно выполнять очень дорогостоящие операции с очень большим набором данных в течение тысяч итераций:

for step = 0 to requested_iterations
  for i = 0 to width
    for j = 0 to height
      for k = 0 to depth
        matrix[i,j,k] = G*f(matrix[i,j,k])

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

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

Некоторые особенности:

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

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

3. Выделенные серверы также могут присоединяться и выходить из сетки, но это предсказуемо.

Пока что лучшая идея, которую я смог придумать:

1. Пусть каждый узел отслеживает само время, необходимое для обработки группы n ячеек в матрице (ячеек, обработанных за единицу времени) и сообщает об этом в центральное хранилище.
2. Соотнесите это время с общим временем для кадра (по всей сетке) моделирования и общим размером проблемной области. Таким образом, каждый узел получал бы оценку, выраженную в рабочих единицах (ячейках матрицы) за раз, и скалярную оценку, выражающую его производительность по сравнению с остальной сеткой.
3. На каждом кадре распределите рабочую нагрузку на основе этих показателей так, чтобы каждая машина заканчивала работу как можно ближе к одинаковому времени. Если машина A в 100 раз быстрее, чем машина B, она получит в 100 раз больше ячеек матрицы для обработки в данном кадре (при условии, что размер матрицы достаточно велик, чтобы в нее можно было включить дополнительные машины).
4. Узлы, покидающие сетку (рабочие столы, на которые выполнен вход и т. Д.), Перераспределяют рабочую нагрузку между оставшимися узлами.

Или

Расположите узлы в древовидной структуре, где каждому узлу назначен «вес». Узлы, расположенные выше в дереве, имеют вес, основанный на их способностях в сочетании с их способностями их детей. Этот вес корректируется на кадр. Когда узел теряет связь со своим дочерним узлом, он использует кешированный граф дерева для связи с потерянными потомками и перебалансировки своей ветви.

Если это имеет значение, приложение представляет собой комбинацию C # и OpenCL.

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

Редактировать

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

Спасибо за отличные, подробные ответы.

Answer 1

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

• Разбейте работу на мельчайшие компоненты (мы знаем, что сейчас есть 1000 задач)
• Запустить сетевой сервер (желательно UDP с тайм-аутами, чтобы избежать перегрузки сети), который имеет значение вверх
• Запустите процессы кластера.
• Каждый процесс спрашивает: «Какой номер работы я должен выполнить?» и сервер отвечает с номером
• По окончании процесса запрашивается следующий номер задания. Когда все задачи выполнены, сервер возвращает -1 процессам, поэтому они выключаются.

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

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

Answer 2

Я бы не стал отслеживать эту статистику слишком сильно на уровне сервера. Вы собираетесь ввести изрядную сумму накладных расходов.

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

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

Примеры основаны на матрице, содержащей 10 рабочих единиц и 5 серверов.

одинаково быстро, все доступно:

Сервер 1 регистрируется и захватывает блок 1. Это продолжается для следующих 4 машин (то есть: Сервер 2 получает блок 2 ...) Когда блок 1 завершен, сервер 1 затем захватывает блок 6. Остальные захватывают остальное. Как только последний сервер регистрируется, матрица готова.

Низкая Раздельная производительность, все доступно:
Вы снова запускаете круговой прием, и первые 5 юнитов приобретаются серверами. Однако сервер 1 занимает на 30% больше времени, чем остальные. Это означает, что сервер 2 захватит блок 6. и т. Д. В какой-то момент сервер 1 проверит блок 1, в то время как блоки 2–5 будут завершены, и 6–10 будут назначены. Серверу 1 назначен блок 6, поскольку это еще не сделано. Однако Сервер 2 проверит свою завершенную работу до того, как Сервер 1 завершит свою работу. Ничего страшного, просто выбросьте этот последний результат.

Огромное отдельное исполнение, все в наличии
Вы снова запускаете круговой прием, и первые 5 юнитов приобретаются серверами. Допустим, сервер 1 занимает на 400% больше времени, чем остальные. Это означает, что сервер 2 захватит блок 6 и т. Д. После того, как сервер 2 проверит блок 6, он увидит, что блок № 1 все еще работает. Идем дальше и назначаем его на сервер 2; который завершит его до того, как сервер 1 вернется.

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

Машина исчезает
Это имеет тот же план, что и «Огромное отдельное представление», указанное выше. Единственное отличие состоит в том, что машина либо никогда не сообщит, либо сделает это через некоторое неизвестное время.

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

---

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

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

Answer 3

Я бы пошел на децентрализованное решение.

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

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

Перед каждым запуском процесса каждый узел должен подавать широковещательный сигнал о: «Я начинаю делать X». Один раз закончил, всегда транслировали: «Я закончил Х».

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

Плохо: первое время настройки может занять не безразличное количество времени.

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

Много лет назад я сделал что-то подобное и с довольно хорошими результатами. Но это определенно не было в таком большом масштабе, как описано вами. И масштаб, на самом деле, имеет значение.

Так что выбор за вами.

Надеюсь, это поможет.