Как вычислительные затраты на операцию mpi_allgather сравниваются с операцией сбора / разброса?

11

Я работаю над проблемой, которую можно распараллелить, используя одну операцию mpi_allgather или одну операцию mpi_scatter и одну операцию mpi_gather. Эти операции вызываются в цикле while, поэтому их можно вызывать много раз.

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

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

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

Пол
источник
Пожалуйста, опишите структуру коммуникации и размеры. А MPI_Scatterсопровождаемый MPI_Gatherне обеспечивает такую ​​же семантику связи, как MPI_Allgather. Возможно, существует избыточность, когда вы выражаете операцию любым способом?
Джед Браун
Пол, Джед прав, ты имеешь ввиду " MPI_Gatherа" MPI_Bcast?
Арон Ахмадиа
@JedBrown: я добавил немного больше информации.
Павел
@AronAhmadia: я не думаю, что я должен использовать MPI_Bcast, потому что я посылаю часть вектора для каждого процесса, а не весь вектор. Мое обоснование заключается в том, что более короткое сообщение будет отправляться быстрее, чем сообщение большего размера. Имеет ли это смысл?
Павел
Матрица уже распределена избыточно? Это уже учтено? Разделяют ли несколько процессов одни и те же кэши и шину памяти? (Это повлияет на скорость решения избыточных систем.) Насколько большими / дорогими являются системы? Зачем решать серийно?
Джед Браун

Ответы:

9

Во-первых, точный ответ зависит от: (1) использования, то есть входных аргументов функций, (2) качества и подробностей реализации MPI и (3) используемого вами оборудования. Часто (2) и (3) связаны, например, когда поставщик оборудования оптимизирует MPI для своей сети.

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

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

С другой стороны, если один находится на Blue Gene, делая при MPI_Reduce_scatter_blockпомощи MPI_Allreduce, которая делает больше общения , чем MPI_Reduceи в MPI_Scatterсочетании, на самом деле совсем немного быстрее. Это то, что я недавно обнаружил, и является интересным нарушением принципа самосогласованности производительности в MPI (этот принцип более подробно описан в «Принципах самосогласованной производительности MPI» ).

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

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

#ifdef TWO_MPI_CALLS_ARE_BETTER_THAN_ONE
  MPI_Scatter(..)
  MPI_Gather(..)
#else
  MPI_Allgather(..)
#endif

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

const int use_allgather = 1;
const int use_scatter_then_gather = 2;

int algorithm = 0;
double t0 = 0.0, t1 = 0.0, dt1 = 0.0, dt2 = 0.0;

while (..)
{
    if ( (iteration==0 && algorithm==0) || algorithm==use_scatter_then_gather )
    {
        t0 = MPI_Wtime();
        MPI_Scatter(..);
        MPI_Gather(..);
        t1 = MPI_Wtime();
        dt1 = t1-t0;
    } 
    else if ( (iteration==1 && algorithm==0) || algorithm==use_allgather)
    {
        t0 = MPI_Wtime();
        MPI_Allgather(..);
        t1 = MPI_Wtime();
        dt2 = t1-t0;
    }

    if (iteration==1)
    {
       dt2<dt1 ? algorithm=use_allgather : algorithm=use_scatter_then_gather;
    }
}
Джефф
источник
Это неплохая идея ... время их обоих и определить, какой из них быстрее.
Павел
Большинство современных аппаратных сред HPC оптимизируют многие вызовы MPI. Иногда это приводит к невероятному ускорению, а иногда к крайне непрозрачному поведению. Быть осторожен!
Meawoppl
@Jeff: Я только что понял, что пропустил одну важную деталь ... Я работаю с кластером в Texas Advanced Computing Center, где они используют топологию сети с толстым деревом. Повлияет ли это на разницу в производительности между подходами, основанными на общем сборе и общем сборе?
Павел
Топология @Paul здесь не является доминирующим фактором, но у толстого дерева есть существенная пропускная способность, которая должна сделать дешевую сборку. Однако собирать всегда нужно дешевле, чем собирать. Для больших сообщений это может быть меньше, чем в 2 раза.
Джефф
5

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

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

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

  • Теперь код более четко отражает то, что вы пытаетесь сделать, делая его более понятным для следующего человека, который придет к вашему коду в следующем году, не имея представления о том, что должен делать код (этот человек вполне может быть вами);
  • Для этого более конкретного случая доступны оптимизации на уровне MPI, которых нет в более общем случае, поэтому ваша библиотека MPI может вам помочь; и
  • Попытка свернуть свою собственную, скорее всего, будет иметь неприятные последствия; даже если он работает лучше на компьютере X с реализацией MPI Y.ZZ, он может работать намного хуже, когда вы переходите на другую машину или обновляете реализацию MPI.

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

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

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


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