Сначала я хотел бы заявить, что понятия не имею, верны ли мои предположения или понимание буферов MPI.Если это не правильно, этот вопрос, скорее всего, недействителен.Я исследовал столько, сколько мне показалось необходимым, и я чувствую, что мои предположения логичны.
Обратите внимание: ниже TL; DR.
Допущения: это мое понимание MPI Isends:
Определение: начинается неблокирующая отправка
int MPI_Isend(const void *buf, int count, MPI_Datatype datatype, int dest, int tag, MPI_Comm comm, MPI_Request *request)
- Буфер - это просто ссылка на некоторую выделенную память.
- При использовании Isend буфер нельзя безопасно использовать повторно, если не подтверждено, что получение прошло успешно.
- Создавая новый, выделенный для памяти буфер для каждого экземпляра Isend, у нас не будет проблем с буфером.
- Процесс может распределить буфер по буферам, Isend, продолжить работу икогда он должен отправить снова, он может просто создать другой буфер, используя другой malloc.
- Эти буферы (ссылки) могут быть сохранены в связанном списке, который может использоваться для освобождения всех буферов после обнаружения завершенияпришел к выводу, что все соответствующие отправка и получение были успешными.
Справочная информация:
Я программирую игровой AI для игры под названием Othello.Я использую разные методы, но здесь я сосредоточусь на использовании техники, называемой NegaScout (разновидность AlphaBeta / Minimax).
Я специально пытаюсь повысить эффективность по мере увеличения числа процессов.Таким образом, я хочу, чтобы моя программа была очень масштабируемой и не заботилась о производительности программы, скажем, с менее чем 8 ядрами.
Мне нужен способ эффективного балансирования нагрузок этих процессов.Первый этап балансировки нагрузки относительно прост.Просто работайте на глубине, где есть достаточно деревьев для изучения каждого процесса.Проблема существует, когда процесс выполнил поиск своего дерева перед другим - балансировка нагрузки должна продолжаться.Это подразумевает, что мы должны реализовать балансировку нагрузки в алгоритме NegaScout.
Я использую метод master / slave (или, скорее, клиент / сервер) для обработки динамической балансировки нагрузки вначале.Но когда процессы должны получать работу друг от друга, все становится немного сложнее.Я не могу просто работать со стеком доступной работы, потому что значения альфа-бета зависят от значений внутри каждого рекурсивного вызова, или, скорее, от их состояния (состояния платы) в дереве.
Моя теория таковачто существует возможность чрезмерных издержек связи, если используются блокирующие посылки.Например, если я являюсь процессом, который должен отправлять работу запрашивающему процессу, было бы неэффективно использовать обычную блокирующую отправку, которая должна ожидать другой процесс, который теперь может проверять другие теги связи;например, TERMINATE_TAG.
Я думаю, что наиболее существенная ситуация с коммуникационными накладными расходами могла бы быть здесь:
- Я - процесс, P0, которому нужна работа.
- Я получаю работу отprocess, P1.
- Я делаю свою работу и получаю ответ.
- Я инициирую блокирующую или неблокирующую отправку:
- 4.1.Блокировка отправки позволяет мне отправить
MPI_DOUBLE с буфером, который был выделен только один раз.Но теперь я жду, пока процесс P1 получит его, прежде чем я смогу продолжить поиск работы.Процесс P1 теперь может находиться на другой глубине своего дерева.Это будет означать, что он не может получить ответ от P0, потому что мы не можем использовать его на такой глубине.Теперь P0 блокируется, пока P1 не вернется на эту глубину.Кроме того, это может происходить несколько раз на разных глубинах, вызывая блокировку многих процессов. - 4,2.С другой стороны, если я неправильно выделю буфер ответов и укажу, на какой глубине следует использовать ответ в теге, я могу инициировать
MPI_Isend с буфером.Адрес этого буфера затем добавляется в мой связанный список буферов для освобождения по окончании.Теперь, когда ответ был отправлен с использованием неблокирующей отправки, я могу сразу же отправиться на поиски дополнительной работы, а не ждать приема в P1.
Вот точка зренияиз процесса, который имеет избыточную работу:
- Я, процесс P1, постоянно проверяю входящие сообщения, используя
MPI_Iprobe. - Когда я получаю запрос на работу, я решаю, является ли онцелесообразно отправить это или нет.
- 2.1.Если у меня нет работы, я делаю malloc целочисленный буфер (который не будет использоваться ни одной из сторон), добавляю его в свой связанный список буферов, чтобы позже освободить, и отправляю неблокирующую посылку с тегом
I_MAY_HAVE_WORK_LATER или I_DONT_HAVE_WORK - в зависимости от ситуации.Неблокирующая отправка позволяет мне продолжить мою другую работу и обрабатывать другие входящие сообщения, не вызывая узких мест. - 2.2.Если у меня есть работа, я кодирую данные (структуру платы, текущую глубину и значения альфа-бета) и размещаю их в новом буфере.Затем я инициирую еще одну неблокирующую отправку с этим буфером, который был добавлен в мой связанный список.Я могу немедленно продолжить свою работу и обрабатывать другие сообщения.
- Если я достигну конца списка работ на этой конкретной глубине, мне теперь нужно собрать все ответы из процессовна которую я отправил работу.Предположим, у меня есть счетчик, который показывает количество процессов, на которые я отправил работу.Ниже следует некоторый псевдокод:
while (counterOfProcessesIveSentWorkTo > 0) {
flag = 0;
while (!flag) {
MPI_Iprobe(... MPI_ANY_SOURCE, MPI_ANY TAG ...);
}
/* get tag and source */
if ( tag == ...) { //handle requests for work, termination, etc
} else if (tag == HERES_YOUR_SCORE) { // This tag also checks for depth
MPI_Recv(...)
counterOfProcessesIveSentWorkTo--;
/* Handle score processing */
}
}
Теперь, когда у нас есть некоторый опыт, я наконец могу задать свой вопрос:
Предполагая, что предложенная мной стратегия динамического буфера работает, она эффективна?Будет ли компромисс в постоянно неправильных буферах стоить уменьшения накладных расходов на связь?
У этого метода есть одно очевидное ограничение.Массивные связанные списки буферов, давайте предположим, что у нас достаточно памяти, чтобы справиться с этим.
Извините за длинный вопрос.Мне просто интересно найти эффективный способ балансировки нагрузок во всех процессах.
TL; DR:
- Действительно ли это вообще возможно для создания и выделения памяти для используемых буферовв MPI_Isend, а затем только освобождая эти буферы во время завершения?
- Как постоянное malloc'ирование буферов повлияет на эффективность обработки моей программы?
- Будет ли значительное влияние на снижение уровня постоянного обмена данными?производительность моей программы?
Я все еще пытаюсь исправить свой код, поэтому я пока не могу сам ответить на эти вопросы.Я надеялся, что кто-то с большим опытом мог бы сэкономить мне время, указав, является ли этот метод жизнеспособным или нет.
Большое спасибо за чтение этого довольно длинного вопроса!Любой совет будет оценен.