Programming Taskbook


E-mail:

Пароль:

Регистрация пользователя   Восстановление пароля

 

ЮФУ SMBU

Электронный задачник по программированию

©  М. Э. Абрамян (Южный федеральный университет, Университет МГУ-ППИ в Шэньчжэне), 1998–2024

 

PT for MPI | Решения | Операции редукции

PrevNext


Операции редукции и составные типы данных: MPIBegin52

В следующем задании мы познакомимся с коллективными операциями редукции и особенностями использования в MPI-программах составных типов данных.

MPIBegin52. В каждом процессе дан набор из K + 5 чисел, где K — количество процессов. Используя функцию MPI_Allreduce для операции MPI_MINLOC, найти минимальное значение среди элементов данных наборов с одним и тем же порядковым номером и ранг процесса, содержащего минимальное значение. Вывести в главном процессе минимумы, а в остальных процессах — ранги процессов, содержащих эти минимумы.

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

Среди коллективных MPI-функций выделяют группу функций, обеспечивающих выполнение коллективных операций редукции, т. е. операций, связанных с пересылкой не исходных данных, а результатов их обработки некоторой групповой операцией: нахождением суммы MPI_SUM, произведения MPI_PROD, максимального MPI_MAX или минимального MPI_MIN значения и т. д. — всего в стандарте MPI предусмотрено 12 операций редукции, кроме того, программист может определять и свои собственные операции.

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

При запуске программы-заготовки, созданной для выполнения задания MPIBegin52, мы увидим на экране окно задачника, подобное приведенному ниже:

Коллективная операция редукции может применяться одновременно к нескольким наборам данных. Если каждый процесс предоставляет массив чисел (одного и того же размера), то операция редукции применяется по отдельности к элементам предоставленных массивов с одним и тем же индексом; в результате будет получен массив того же размера, каждый элемент которого будет являться результатом применения операции редукции к элементам исходных массивов с этим же индексом. В зависимости от используемой MPI-функции полученный массив может быть переслан какому-либо конкретному процессу (функция MPI_Reduce) или всем процессам данного коммуникатора (функция MPI_Allreduce). При использовании операций MPI_MAXLOC и MPI_MINLOC исходные наборы данных должны содержать пары чисел: собственно число, которое надо обработать, и его номер. Поэтому в программе необходимо определить вспомогательный тип данных (запись в Pascal, структуру в C++) для хранения таких пар. В нашем случае должны обрабатываться вещественные числа, поэтому первый элемент пары будет вещественным, а второй — целым:

[C++]

struct MINLOC_Data
{
  double a;
  int n;
};

[Pascal]

type
  MINLOC_Data = record
    a: real;
    n: integer;
  end;

Для хранения исходных данных в каждом процессе должен быть выделен массив элементов типа MINLOC_Data, и такой же массив должен использоваться для хранения результатов выполнения операции редукции. Размер набора данных, который придется хранить в этих массивах, заранее неизвестен, так как он связан с количеством процессов параллельной программы. Поэтому можно либо выделять память для массивов динамически (после того как программе станет известно число процессов size), либо использовать статические массивы, размер которых окажется достаточным для любых наборов исходных данных. При выполнении задания MPIBegin52 мы будем использовать статические массивы (особенности, связанные с использованием динамических массивов, будут рассмотрены в следующем пункте). Запустив созданную программу-заготовку несколько раз, мы можем убедиться в том, что для данного задания количество процессов может меняться в диапазоне от 3 до 5. Таким образом, учитывая, что размер наборов исходных данных равен K + 5, где K — количество процессов, нам достаточно описать массивы размера 10:

[C++]

MINLOC_Data d[10], res[10];

[Pascal]

var
  d, res: array[0..9] of MINLOC_Data;

Для большего единообразия программ мы будем использовать для языка Pascal индексацию массивов от 0. Заметим, что именно такая индексация используется в языках Delphi Pascal и Free Pascal для динамических массивов, которые в дальнейшем мы также будем применять в наших программах.

Инициализация исходного массива d должна выполняться в каждом процессе параллельной программы (в программе на языке Pascal необходимо дополнительно описать переменную i целого типа):

[C++]

for (int i = 0; i < size + 5; ++i)
{
  pt >> d[i].a;
  d[i].n = rank;
}

[Pascal]

for i := 0 to size + 4 do
begin
  GetR(d[i].a);
  d[i].n := rank;
end;

Выполнив запуск этого варианта программы, мы получим сообщение об ошибке Выведены не все результирующие данные:

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

Перед выводом результатов необходимо выполнить соответствующую коллективную операцию редукции. Она должна быть выполнена во всех процессах, после чего в главном процессе (ранга 0) надо вывести поле a каждого элемента результирующего массива res (т. е. минимальное значение, выбранное из всех элементов исходных массивов с данным индексом), а в остальных (подчиненных) процессах — поле n (т. е. ранг процесса с этим минимальным значением):

[C++]

MPI_Allreduce(d, res, size + 5, MPI_DOUBLE_INT, MPI_MINLOC,
  MPI_COMM_WORLD);
for (int i = 0; i < size + 5; ++i)
  if (rank == 0)
    pt << res[i].a;
  else
    pt << res[i].n;

[Pascal]

MPI_Allreduce(@d[0], @res[0], size + 5, MPI_DOUBLE_INT,
  MPI_MINLOC, MPI_COMM_WORLD);
for i := 0 to size + 4 do
  if rank = 0 then
    PutR(res[i].a)
  else
    PutN(res[i].n);

Обратите внимание на два важных момента. Во-первых, массивы исходных и результирующих данных передаются в MPI-функции как указатели на их начальный элемент, поэтому в варианте для языка Pascal используется операция @ взятия адреса элемента массива с индексом 0 (заметим, что в средах Delphi и Lazarus можно использовать более простые выражения: @d и @res). Во-вторых, имя типа, указываемое в качестве четвертого параметра, должно соответствовать типу элементов обрабатываемых массивов (в данном случае надо указать имя MPI_DOUBLE_INT, соответствующее структуре из двух полей — вещественного и целого).

После требуемого количества тестовых испытаний полученной программы в среде C++ будет выведено сообщение о том, что задание выполнено

Однако при запуске варианта программы для языка Pascal в среде Lazarus будет выведено сообщение об ошибочном решении:

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

Причина ошибочного поведения связана с тем, что при стандартных настройках компилятора Free Pascal, используемого в среде Lazarus 0.9, не выполняется выравнивание составных данных, в то время как в функциях библиотеки MPI предполагается, что выравнивание производится. Чтобы убедиться в этом, достаточно вызвать функцию MPI_Type_extent, которая позволяет определить размер памяти (в байтах), используемый для любого типа библиотеки MPI. Размер возвращается во втором параметре этой функции, имеющем специальный тип библиотеки MPI — MPI_Aint. Для вывода полученного значения воспользуемся новой возможностью задачника Programming Taskbook, появившейся в его версии 4.9, — функцией Show, которая позволяет выводить информацию в раздел отладки окна задачника. Опишем в программе переменную k типа MPI_Aint и добавим в конец программы следующий фрагмент:

[Pascal]

MPI_Type_extent(MPI_DOUBLE_INT, k);
Show('k = ', k);

При запуске этого варианта программы в окне задачника появится раздел отладки, и в нем будет выведено значение переменной k с предваряющим комментарием (обратите внимание на то, что значение k выводится несколько раз, так как процедура Show выполняется в каждом процессе параллельного приложения):

Таким образом, в библиотеке MPI предполагается, что для типа MPI_DOUBLE_INT отводится 16 байт, т. е. для полей этой записи выполняется выравнивание по ширине 8 байт. Если же указанное выравнивание не проводить, то запись, состоящая из одного вещественного числа двойной точности (8 байт) и одного целого числа (4 байта), будет занимать только 12 байт, и в результате все элементы массива таких записей, начиная со второго элемента, будут располагаться в памяти не в тех позициях, которые предполагает функция MPI_Allreduce. Этим и объясняется тот факт, что первые элементы исходным массивов были обработаны правильно, а остальные нет. В случае использования среды Visual Studio для языка C++, а также среды Delphi для языка Pascal, ошибки не возникает, так как компиляторы этих сред по умолчанию выполняют выравнивание данных по ширине 8 байт.

После того как причина ошибки выяснена, исправить ее для среды Lazarus не представляет труда. Достаточно добавить в запись MINLOC_Data еще одно, «фиктивное» поле, имеющее размер 4 байта и дополняющее, таким образом, размер записи до требуемых 16 байт:

[Pascal]

type
  MINLOC_Data = record
    a: real;
    n, not_used: integer;
  end;

Заметим, что вместо добавления фиктивного поля можно было бы установить для записи MINLOC_Data режим выравнивания по ширине 8 байт, указав перед ее описанием директиву компилятора Free Pascal {$PackRecords 8}.

Примечание. В версии Lazarus 1.0 отмеченная ошибка не возникает, поскольку в этой версии по умолчанию выполняется выравнивание данных по ширине 8 байт.

В заключение приведем полный текст решения задания MPIBegin52 на языках C++ и Pascal:

[C++]

struct MINLOC_Data
{
  double a;
  int n;
};

void Solve()
{
  Task("MPIBegin52");
  int flag;
  MPI_Initialized(&flag);
  if (flag == 0)
    return;
  int rank, size;
  MPI_Comm_size(MPI_COMM_WORLD, &size);
  MPI_Comm_rank(MPI_COMM_WORLD, &rank);
  MINLOC_Data d[10], res[10];
  for (int i = 0; i < size + 5; ++i)
  {
    pt >> d[i].a;
    d[i].n = rank;
  }
  MPI_Allreduce(d, res, size + 5, MPI_DOUBLE_INT, MPI_MINLOC,
    MPI_COMM_WORLD);
  for (int i = 0; i < size + 5; ++i)
    if (rank == 0)
      pt << res[i].a;
    else
      pt << res[i].n;
}

[Pascal]

program MPIBegin52;
uses PT4, MPI;
type
  MINLOC_Data = record
    a: real;
    n, not_used: integer;
  end;
var
  flag, size, rank: integer;
  d, res: array[0..9] of MINLOC_Data;
  i: integer;
begin
  Task('MPIBegin52');
  MPI_Initialized(flag);
  if flag = 0 then exit;
  MPI_Comm_size(MPI_COMM_WORLD, size);
  MPI_Comm_rank(MPI_COMM_WORLD, rank);
  for i := 0 to size + 4 do
  begin
    GetR(d[i].a);
    d[i].n := rank;
  end;
  MPI_Allreduce(@d[0], @res[0], size + 5, MPI_DOUBLE_INT,
    MPI_MINLOC, MPI_COMM_WORLD);
  for i := 0 to size + 4 do
    if rank = 0 then
      PutR(res[i].a)
    else
      PutN(res[i].n);
end.

PrevNext

 

Рейтинг@Mail.ru

Разработка сайта:
М. Э. Абрамян, В. Н. Брагилевский

Последнее обновление:
01.01.2024