TL; DR:
Существует ли эффективный способ разделения целочисленных переменных по всем процессам в стандартной реализации MPI (то есть без библиотек или прикольных вещей ).
Я работаю над простым игровым ИИ, в котором мы используем MPI. AI использует стандартный метод поиска по альфа-бета-дереву, чтобы найти лучший ход, зависящий от функции оценки. Основа программы работает следующим образом:
- доска представлена в виде битборда.
- процесс 0 инициализирует все, разветвляя первую доску в зависимости от количества доступных ходов
- процесс 0 распределяет работу по всем другим процессам (например, одному или нескольким поддеревам) с помощью MPI_Scatter
- все процессы вызывают поиск альфа-бета по своему поддереву, которое затем создает большее дерево для этого процесса
- каждый процесс вычисляет статическую оценку своего дерева
- используйте MPI_Gather, чтобы найти лучший ход
- верните лучший ход.
У меня две проблемы:
- Динамическое распределение нагрузки / балансировка:
У некоторых процессов больше работы, чем у других. Например, если в одном наборе деревьев будет меньше ходов, оно будет выполняться быстрее. Но что, если процесс может определить, что он находится под большой нагрузкой и может получить выгоду от некоторого распределения нагрузки с другим пустым процессом? Простая идея заключается в том, чтобы реализовать какую-то очередь, в которой процессы могут запрашивать работу? Возможно ли это без общей очереди между процессами? Проблема с оценкой самой глубокой платы каждого процесса состоит в том, что общее время выполнения - это, по сути, самый медленный процесс. Таким образом, если P1 требуется 0,1 с для расчета оценки, а P2 - 10 с, чтобы вычислить оценку, и, скажем, оценка P1 лучше, то вычисления и время тратятся впустую.
- Общие значения альфа-бета:
Значения альфа-бета определяют глубину среза дерева. Это означает, что даже если другой процесс нашел лучшие значения альфа-бета, чем другой процесс, этот другой процесс с устаревшими значениями альфа-бета выиграет от использования взамен значений альфа-бета другого процесса. Есть ли способ поделиться этими двумя значениями без чрезмерных накладных расходов на связь?
Я читал это в другом посте:
Каждый поток получает стек, хотя обычно для приложения имеется только одна куча (хотя нередко иметь несколько куч для разных типов размещения).
Применимо ли это к MPI? Есть ли какая-то куча, к которой могут обращаться все процессы? Я путаю термины нить и процессы?
Некоторые другие решения, о которых я думал:
- Процесс 0 действует ТОЛЬКО как коммуникатор между процессами и управляет очередью. Процессы должны оценивать меньшие значения глубины, посылать свое лучшее дерево в P0 и запрашивать работу. Это также решило бы проблему обмена альфа-бета-версиями. К сожалению, я думаю, что это все равно приведет к длительному времени ожидания, так как P0 придется ждать, пока каждый процесс вернет свое лучшее дерево, чтобы переоценить очередь. Кроме того, мы теряем весь процесс (P0), действуя только как коммуникатор и, следовательно, не выполняем много работы.
Любые мнения будут с благодарностью.
Спасибо!