Алгоритмы коллективных операций MPI

После инициализации библиотеки при помощи операций MPI_Init, MPI_Init_thread или механизма сессией MPI_Session_init каждому процессу известен коммуникатор (communicator) из \(p\) процессов. Каждый процесс имеет уникальный номер, ранк (rank), из множества \(\{0, 1, \ldots, p-1\}\). Стандарт предоставляет функции порождения новых коммуникаторов, включая группировку процессов в соответствии с иерархией памяти вычислительных узлов (например, MPI_Comm_split_type). На протяжении всей книги мы будем рассматривать только интра-коммуникаторы, так как интер-коммуникаторы редко применяются на практике.

Рассмотрим две базовые операции Send и Recv. Операция Send выполняет передачу процессу \(dest\) сообщения с тегом \(tag\). Сообщение для отправки располагается в памяти начиная с адреса \(sbuf\) и состоит из последовательно расположенных \(scount\) элементов типа \(sdtype\).

Выполнение процесса-отправителя блокируется в Send до тех пор, пока \(sbuf\) нельзя будет использовать повторно – пока сообщение из \(sbuf\) не будет скопировано библиотекой в служебный буфер или не будет отправлено получателю. Прием сообщений выполняется операцией Recv, которая требует указания адреса \(rbuf\) буфера-приема и способа размещения полученных данных в памяти, который задается параметрами \(rcount\) и \(rdtype\). Типы \(sdtype\) и \(rdtype\) могут не совпадать на стороне отправителя и получателя. Стандарт требует равенства размеров сообщений:

Если процесс передает сообщение производного типа данных с не непрерывно размещенными в памяти элементами базовых типов (non-continuous datatype), то библиотека может выполнять предварительную упаковку сообщения в непрерывный буфер. Аналогично, при получении сообщения имеется непрерывная последовательность, которая разворачивается в \(rbuf\) в соответствии с описанием типа \(rdtype\). В параметре \(status\) сохраняется ранк отправителя, тег и реальный размер принятого сообщения.

Любой производный тип данных MPI рекурсивно строится на основе предопределенных базовых типов (MPI_DOUBLE, MPI_INT и др.). Формально производный тип данных задается картой типа (type map) – последовательностью пар \((type_0, disp_0), (type_1, disp_1), \ldots, (type_{n-1}, disp_{n-1})\), где \(type_i\) – базовый тип, \(disp_i\) – смещение в байтах относительно начала буфера в памяти. Например, мы можем отправить строку матрицы как непрерывную последовательность из 100 элементов MPI_DOUBLE, а на стороне получателя построить производный тип данных и принять операцией Recv 100 элементов в виде столбца матрицы с хранением по строкам (row-major).

Упаковка сообщения для типа с несмежными элементами в памяти (например, столбец матрицы) требует выполнения копирования отдельных блоков в непрерывный буфер. Это является причиной накладных расходов при использовании производных типов. За упаковку в непрерывный буфер отвечает библиотека, но это можно реализовать и на стороне приложения, например циклом копирования элементов или операцией MPI_Pack [10],[11].

Неблокирующие операции Isend/Irecv позволяют инициировать запрос (request) на выполнение коммуникационной операции. Проверка состояния операции, завершена или выполняется, реализуется операцией Test. Дождаться завершения ассоциированной с запросом операции можно блокирующим вызовом Wait.

Неблокирующие операции позволяют реализовать в программе совмещение (перекрытие, overlap) коммуникационной операции и вычислений, которые следуют после неблокирующего вызова и не используют буфер операции. Эффективность совмещения зависит от аппаратной конфигурации целевой системы, в какой степени нижележащий коммуникационный слой и/или сетевой адаптер поддерживает аппаратную реализацию коммуникационных операций.

В большинстве реализаций библиотек MPI блокирующие операции двусторонних обменов реализуются на базе неблокирующих. Операция Send реализуется вызовов Isend, за которым сразу следует Wait. За выполнение коммуникационных операций, связанных с запросами, отвечает подсистема продвижения (MPI progress engine)  [12] . Библиотека поддерживает в каждом процессе несколько типов очередей запросов  [13],[14] . При вызове Isend создается запрос на выполнение неблокирующей коммуникационной операции, он помещается в очередь Send-Request-Queue (SRQ). Аналогично, при вызове Irecv запрос помещается в очередь Recv-Request-Queue (RRQ). Если сообщение достаточно большое и нижележащий коммуникационный уровень (TCP/IP, RoCE, InfiniBand) требует нескольких обращений к своим коммуникационным примитивам, то библиотеке MPI необходимо каким-то образом выполнять эти действия между вызовами Isend/Irecv и Wait. Для этого пользователю предоставляются функции проверки состояния запросов Test, которые запускают часть еще невыполненных коммуникационных шагов, связанных с запросом и возвращает его состояние пользователю. Операция Wait блокируется до тех пор, пока цикл обращений к подсистеме продвижения, не закончит выполнение операции, а запрос не перейдет в состояние завершенный (complete). Описанная схема – это синхронное продвижение коммуникационных операций путем явного вызова пользователем Test. Альтернативный вариант – библиотека для каждого процесса запускает поток, который асинхронного продвигает запросы. В этом случае пользователю не требуется явно вызывать Test для продвижения операций, но за это приходится платить накладными расходами на поддержание дополнительного потока, который будет делить процессорное ядро с потоком пользователя. Библиотеки Open MPI и MPICH по умолчанию собираются в режиме синхронного продвижения запросов, без выделенного потока.

При вызове операции Recv/Irecv библиотека запускает процедуру поиска поступивших сообщений (tag matching). Рассмотрим ситуацию, которая объясняет наличие в библиотеках MPI двух типов протоколов для реализации двусторонних обменов, eager и rendezvous  [15] . Процесс 0 выполняет передачу сообщения процессу 1. Процесс 1 по какой-то причине выполняет вызов операции Recv намного позже, чем по каналу связи поступило сообщение от процесса 0. Возникает вопрос – в какой буфер библиотека MPI должна сохранить поступившее сообщение процесса 0? Адрес буфера приема \(rbuf\) пользователь сообщить не успел. Очевидное решение – библиотека создает в каждом процессе очередь непредвиденных сообщений Unexpected-Message-Queue (UMQ) из \(n\) буферов фиксированного размера по \(s\) байт. Параметры \(n, s\) являются настраиваемыми, их значение известно в каждом процессе. Логика работы библиотеки для операций Send/Recv разделяется на два случая – сообщения не превышающие \(s\) байт передаются протоколом \(eager\), а сообщения больше \(s\) протоколом \(randezvous\) c предварительным установлением соединения для выделения буфер необходимого размера. Рассмотрим отдельные шаги этих протоколов.

Библиотеки MPI имеют многоуровневую организацию для абстрагирования от архитектуры целевой системы. Как правило, на нижнем уровне присутствует слой поддержки базовых коммуникационных операций конкретной сетевой технологии или транспортного механизма. Например, реализация коммуникационных примитивов Send/Recv средствами протоколов TCP/IP, InfiniBand, через общую память или через сторонние библиотеки (OpenUCX, libfabric). Подсистемы уровня выше используют эти примитивы для реализации коммуникационных операций уже с учётом семантикой стандарта MPI. Например, Open MPI имеет модульную компонентную архитектуру  [17],[18] . Она включает несколько отдельных подсистем (проектов):

Среди основных подсистемы Open MPI (frameworks) можно выделить следующие:

Каждая подсистема Open MPI может иметь несколько различных реализаций специфичных для конкретных видов коммуникационных сетей и процессорных архитектур. Например, PML включает альтернативные компоненты ucx и ob1 для операций Send/Recv. Выбор компонента можно осуществить при запуске приложения:

Аналогичная ситуация с подсистемой ompi/coll, которая включает различные компоненты реализации коллективных операций  [20],[21],[22] :

При создании нового коммуникатора библиотека опрашивает все компоненты подсистемы coll на предмет способности их функционирования на этом коммуникаторе, заданном числе процессов. Для коммуникатора формируется таблица указателей на коллективные операции. Операции могут быть из разных компонентов, так не все из них реализуют полный набор функций. Таблица заполняется в порядке невозрастания приоритетов компонентов. При запуске приложения можно явным образом задать больший приоритет нужного компонента. Например, следующим образом можно задать приоритет 100 компоненту coll/tuned:

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

Принудительный выбор алгоритма коллективной операции выполняется установкой соответствующего параметра. Выберем алгоритм бинарного дерева для операции Bcast компонента tuned:

По умолчанию коллективная операция самостоятельно принимает решение о выборе алгоритма ей реализации из доступных в компоненте. Выбор осуществляется на основе переданных параметров: размере сообщения, типе данных элементов, числа процессов. Эта процедура известна как задача выбора алгоритма коллективной операции (collective algorithm selection)  [24],[25] . Например, компонент tuned по умолчанию выбирает алгоритм исходя из предварительных измерений на вычислительном кластере его разработчиков. Очевидно, что такой выбор не для всех вычислительных систем будет оптимальным. Об этом надо помнить при использовании библиотек MPI и оценки эффективности алгоритмов коллективных операций, например тестами OSU MPI Benchmarks, Intel MPI Benchamarks. При вызове коллективной операции для различных размеров сообщений могут вызываться разные алгоритмы и на графиках времени выполнения могут появиться резкие скачки, причиной которых могут быть переключения на другой алгоритм.

Переключения на другой алгоритм могут происходить даже если пользователь задал через runtime-параметры конкретный алгоритм коллективной операции. Например, пользователем выбран алгоритм 6 для операции Allreduce и запущен на 10 процессах, но алгоритм 6 может не поддерживать некоммутативные бинарные операции или число процессов не равное степени двойки, в таком случае он передает управлению алгоритму по умолчанию или компоненту с предшествующим приоритетом. Обнаружить подобные переключения можно включив отладочный вывод:

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

Разработка и анализ параллельных алгоритмов основываются на использовании моделей параллельных вычислений (model of parallel computation) – математических моделей, описывающих:

1) архитектуру вычислительной системы;

2) набор базовых операций управления параллельными процессами;

3) методы оценки издержек на организацию параллельных вычислений.

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

Можно выделить две основные цели создания и применения моделей параллельных вычислений.

1. Теоретическая оценка эффективности параллельных алгоритмов. В обозначениях модели строятся аналитические оценки потребления параллельными алгоритмами ресурсов системы, например, издержек на обмены сообщениями, выполнения вычислительных операций, потребления памяти, электроэнергии и пр. Это обеспечивает возможность сравнивать эффективность алгоритмов по некоторым показателям в отрыве от реальных входных данных алгоритма и конфигурации системы [43],[44],[45],[46],[47] .

2. Предсказательное моделирование. Некоторые модели позволяют достаточно точно в аналитическом виде выразить потребление параллельным алгоритмом определенного вида ресурсов системы и использовать полученные оценки для предсказания количественных издержек для конкретной системы, включая перспективные системы [48],[49],[50],[51],[52],[53],[54],[55] . Здесь возникает сопутствующая задача – корректного и эффективного измерения, оценивания значений параметров моделей для конкретных аппаратных реализаций [56],[47] .

Среди известных распространение получили следующие модели параллельных вычислений: PRAM – Parallel Random Access Memory, BSP – Bulk-Synchronous Parallel, модель Р. Хокни и семейство моделей LogP (LogGP, PLogP, LogGPS, LogPC, LogfP).

Модель PRAM (Parallel Random Access Memory) – это абстракция многопроцессорной системы с общей памятью. Издержки на синхронизацию процессоров не учитываются, они взаимодействуют через разделяемую память. В зависимости от допустимых комбинаций одновременного выполнения операций чтения и записи одной ячейки памяти, выделяют следующие варианты модели:

Эта модель нашла применение при анализе параллельных алгоритмов, в частности многопоточных программ (например, разработанных с использованием языков Cilk/Cilk++ и стандарта OpenMP).

Модель BSP (Bulk-Synchronous Parallel) – модель вычислительной системы с распределенной памятью. Каждый из \(p\) процессоров имеет локальную память [44] . Процессоры реализуют взаимодействия по средствам односторонних обменов сообщениями (put, get). Параллельный алгоритм представляется как последовательность супершагов (superstep), на каждом из которых процессоры выполняют локальные вычисления, обмены сообщениями и барьерную синхронизацию (рис. 1.1).

Модель позволяет выразить суммарное время выполнения всех обменов процессорами на фиксированном супершаге. Параметры модели: \(p\) – число процессоров (процессов), \(g\) – время передачи по сети одного байта, \(l\) – время выполнения барьерной синхронизации. Время выполнения супершага выражается как:

где \(w_i\) – время локальных вычислений процессора \(i \in \{1,2,\ldots,p\}\), \(h_i\) – суммарный размер сообщений передаваемых или принимаемых процессором \(i\) на супершаге. Заметим, что в рамках модели BSP передача одного сообщения размером 100 байт занимает столько же времени, сколько и передача 100 сообщений размером один байт.

Основной механизм взаимодействия параллельных процессов в системах с распределенной памятью – двусторонние обмены сообщениями по каналам связи (point-to-point communications). Для оценки времени выполнения таких операций разработано значительное количество аналитических коммуникационных моделей. Среди них наибольшее распространение получили модели Р. Хокни (R. Hockney) и семейство моделей LogP (LogGP, PLogP, LogGPS, LogPC, LogfP).

В операции Bcast корневой процесс \(root\) передает \(count\) элементов типа \(datatype\) всем процессам коммуникатора \(comm\).

В корневом процессе \(buf\) выступает в качестве буфера отправки, а в некорневых процессах – буфером для приема сообщения. Всем процессам рассылается одинаковое сообщение, поэтом данную операцию также называют неперсонифицированной широковещательной передачей (non-personalized broadcast). В отечественной литературе закрепилось альтернативное название – трансляционный обмен  [58],[2],[3],[4] .

Для алгоритмов операции Bcast известна нижняя граница времени выполнения  [28],[59] :

где \(m = count \cdot \mathrm{sizeof}(datatype).\)

Рассмотрим основные алгоритмы реализации операции Bcast. Мы будем двигаться от простейших к более сложным и эффективным. Нас будут интересовать только алгоритмы, которые в явном виде используют операции Send/Recv для выполнения отдельных шагов коллективной операции. Мы осознано не будем рассматривать аппаратно реализованные алгоритмы (например, NVIDIA SHARP, Cray Aries Collective Engine), так как они эксплуатируют аналогичные идеи. Также мы не будем рассматривать алгоритмы для фиксированных сетевых топологий (\(k\)D-торов, многомерных кубов, многокаскадных сетей) и иерархические методы, которые в пределах многопроцессорного узла локализуют обмены между процессами через его общую память. Все перечисленные специальные методы в своей основе опираются на базовые алгоритмы, которые и являются предметом нашего рассмотрения.

Значительная часть известных алгоритмов основана на логической организации процессов в деревья различных видов. Зная свой номер \(rank\) каждый процесс определяет номера процессов с которыми он выполняет коммуникации. В подавляющем большинстве случаев такие вычисления выполняется за константное время относительно \(p\). Мы будем отдельно обсуждать ситуации когда время вычисления положения процесса в дереве функционально зависит от \(p\). При анализе времени выполнения алгоритмов будем подсчитывать затраты на выполнение операций Send и Recv.

Классическими представителями алгоритмов с линейной зависимостью времени выполнения от числа процессов являются линейный алгоритм (linear broadcast, flat tree broadcast), конвейерный алгоритм (pipeline, chain) и их комбинация – алгоритм параллельных цепочек (\(k\)-chain broadcast).

В линейном алгоритме корневой процесс \(root\) последовательно передает сообщение \(p - 1\) процессам. Ниже приведен его псевдокод. Считаем, что операции Send и Recv блокируют выполнение алгоритма до завершения передачи и приема сообщения.

На рис. 3.1 показана временная диаграмма выполнения алгоритма для четырёх процессов.

Корневой процесс 0 выполняет последовательную передачу трех сообщений. Каждая передача длится \(\alpha + m\beta\) единиц времени. Прямоугольники с операциями отражают время на коммуникации, в них не включено время ожидания поступления сообщения. Например, процесс 2 ожидает в операции Recv начала приема \(\alpha + m\beta\) единиц времени, пока корень не завершит передачу сообщения процессу 1. Аналогично, в процессе 3 время ожидания составляет \(2(\alpha + m\beta)\). Время выполнения алгоритма определяется наибольшим из времен выполнения процессов, которое приходится на корневой процесс и процесс с номером \(p - 1\). В общем случае время выполнения линейного алгоритма

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

На рис. 3.2 приведен пример для четырёх процессов. Первым выполнение завершает корневой процесс, а последним – процесс \((root - 1 + p) \mathbin{\%} p\) в конце цепочки, время которого и определяет итоговое время алгоритма

Зададимся вопросом – как можно сократить время выполнения линейных алгоритмов, как построить более быстрый алгоритм Bcast? Очевидная идея – реализовать одновременную передачу сообщений в нескольких цепочках процессов.

Алгоритм параллельных цепочек (\(k\)-chain) организует \(p\) процессов в \(k\) цепочек, где \(k\) – это входной параметр алгоритма. На первом шаге корень передает сообщение лидеру первой цепочки, на втором шаге корень передает сообщение лидеру второй цепочки и одновременно с этим лидер первой цепочки передает сообщение своему следующем процессу.

После шага \(k\) лидеры всех цепочек получили сообщение от корня и по всем цепочкам выполняется параллельная передача сообщений – это ключевая идея алгоритма. В каждую цепочку входит по \((p-1)/k\) процессов. Если \(p-1\) не делится без остатка на \(k\), то остаток отделения, \((p-1) \mathbin{\%} k\) процессов, распределяются по первым \((p-1) \mathbin{\%} k\) цепочкам – в каждую добавляется по одному процессу. Отметим, что добавлять процессы из остатка целесообразно в первые цепочки, так как это приводит к меньшему увеличению времени выполнения алгоритма по сравнению с добавлением в последние цепочки. Предлагаем читателю самостоятельно проверить это утверждение.

На рис. 3.3 приведен пример для \(p=20\) процессов, которые организованы в \(k=3\) параллельные цепочки по 6 процессов. В первую цепочку включен дополнительный процесс из остатка от деления 19 на 3. Числа над дугами – это номер шага, на котором выполняется передача. Например, процесс 7 получит сообщение в момент времени \(7(\alpha+m\beta)\), а процесс 19 в \(8(\alpha+m\beta)\). Время выполнения алгоритма определяется временем завершения \((p-1)/k - 1\) передач в последней цепочке:

Нетрудно заметить, что время выполнения алгоритма параллельных цепочек линейно зависит от числа процессов, как и в предыдущих алгоритмах. Открытым остается вопрос о выборе значения \(k\). На практике для заданной вычислительной системы можно экспериментально определить оптимальные значения \(k\) для различных \(p\) и \(m\). Рассмотрим альтернативный подход, который лежит в основе следующего алгоритма, – это теоретическое нахождение оптимального числа цепочек (в рамках нашей модели \(m\), \(p\), \(\alpha\), \(\beta\)).

Для построения алгоритма с оптимальным числом параллельных цепочек (\(k\)-opt-chain) из полученного выражения \(t_{{k-chain}}\) найдем число \(k\) цепочек, при котором он работает за минимальное время. Для этого найдем производную функции по \(k\) и приравняем её к нулю

Отсюда оптимальное число цепочек \(k^{*} = \sqrt{p-1}\). Подставим полученное значение \(k^{*}\) в выражение для времени \(t_{{k-chain}}\) и получим время работы алгоритма с оптимальным числом цепочек:

Этот алгоритм имеет степенную зависимость времени работы от числа процессов (показатель степенной функции \(\frac{1}{2}\)). Время выполнения с увеличением \(p\) растет медленнее чем у алгоритмов с линейным числом шагов. На рис. 3.4 показана зависимость количества шагов алгоритма (операций передачи), от числа \(k\) цепочек для 64, 128 и 256 процессов. На кривых показаны значения \(k_{64}\), \(k_{128}\) и \(k_{256}\), при которых достигается минимум времени выполнения алгоритма для соответствующего числа процессов.

Разовьем идею алгоритма параллельных цепочек – построим алгоритм с цепочками уменьшающейся длины.

На рис. 3.5 показан пример 11 процессов и трёх цепочек, это оптимальное количество цепочек для такого числа процессов.

Алгоритм завершается за 5 шагов. Нетрудно заметить, что передача сообщения в следующей цепочке завершается на один шаг позже текущей или за такое же время. Это связано с тем, что на доставку сообщения в очередную цепочку корневому процессу требуется отдельный шаг. Чтобы время завершения операций в цепочках не превышало времени первой, каждая следующая цепочка должна быть на один процесс короче предыдущей. Эта базовая идея алгоритма параллельных цепочек переменной длины. Длины цепочек образуют убывающую арифметическую прогрессию. В первой цепочке \(k\) процессов. На рис. 3.6 приведен пример для 11 процессов с \(k=4\) цепочками длин 4, 3, 2, 1. Итоговое время выполнения алгоритма – 4 шага, что быстрее алгоритма с тремя параллельными цепочками (рис. 3.5).

Найдем для заданного числа \(p\) процессов число \(k\) цепочек переменной длины. По цепочкам распределены \(p-1\) процессов: \(k\) процессов в первой цепочке, \(k-2\) – во второй, \(\ldots\), в последней – один процесс. Из выражения для суммы \(n\) элементов арифметической прогрессии получаем равенство:

Откуда находим значение \(k\):

Если \(p-1\) не делится без остатка на \(k\), то остаток отделения, \((p-1) \mathbin{\%} k\) процессов, распределяются по первым \((p-1) \mathbin{\%} k\) цепочкам – в каждую добавляется по одному процессу. Время выполнения алгоритма определяется временем цепочки \(k\):

Этот алгоритм имеет степенную зависимость времени работы от числа процессов, как и алгоритм с оптимальным числом параллельных цепочек. На рис. 3.7 показана зависимость времени выполнения алгоритмов от числа процессов, а также нижняя граница \(\log_2p\) числа шагов операции Bcast.

Перейдем к рассмотрению алгоритмов, которые выполняют операцию Bcast за логарифмическое число шагов от числа процессов.

Алгоритм выстраивает процессы в бинарное дерево (binary tree), по которому от корня к листам передается сообщение. Ключевая идея алгоритма – параллельная передача данных в левом и правом поддеревьях корня. Каждый процесс вычисляет свое положение в дереве, номер \(parent\) родительского процесса и номера дочерних \(left\), \(right\), только на основе своего номера \(rank\) и общего числа \(p\) процессов. Конкретный алгоритм вычисления \(parent\), \(left\), \(right\) определяется формой бинарного дерева и способом нумерации узлов – распределением \(p\) процессов по дереву. На практике распространение получили две формы деревьев для операции Bcast: завершенное бинарное дерево (complete binary tree) и бинарное дерево сбалансированное по число узлов в поддеревьях. Ниже мы рассмотрим их по отдельности.

Нумерацию узлов дерева можно задать разными способами. Эта процедура должна быть нетрудоёмкой и позволять каждому процессу вычислять свое положение за разумное для практики время – желательно за константное время, которое не зависит от числа процессов. Можно выделить следующие способы нумерации узлов:

Завершенное бинарное дерево (complete binary tree) – бинарное дерево, в котором все уровни заполнены, возможно за исключением последнего, который заполняется слева направо. Зная свой номер \(rank\) каждый процесс за константное время вычисляет номера родительского узла \(parent\), левого \(left\) и правого \(right\) дочерних процессов, если они присутствуют:

На рис. 3.8.а приведен пример завершенного бинарного дерева для \(p=13\) процессов. Последним сообщение получает самый правый листовой процесс 12 на шаге 5. В этом примере самый левый лист имеет высоту больше чем самый правый, поэтому такое дерево будем называть левосторонним деревом.

Для операции Bcast используют левосторонние деревья. Потому, что корневому процессу целесообразно на первом шаге передавать сообщение в поддерево с большим числом узлов. Это обеспечит завершение операции Bcast во втором поддереве за время не превосходящее время в поддереве c большим числом узлов. Например, на рис. 3.8.б показано правостороннее дерево для 13 процессов. Операция Bcast в нем завершается за 6 шагов, что на 1 шаг больше чем в левостороннем дереве.

Как было показано выше, алгоритм заканчивает работу, когда самый правый листовой процесс получает сообщение. Для простоты анализа оценим время выполнения алгоритма завершенного бинарного дерева, для случая когда все листовые узлы находятся на одной высоте, а все не листовые процессы имеют два дочерних узла – форма совершенного бинарного дерева (perfect binary tree). В этом случае время выполнения операции Bcast определяется временем правого листа:

где \(h\) – высота самого правого дочернего листа. Если завершенное дерево имеет форму отличную от совершенной, время выполнения операции Bcast не превосходит \(t_{{BinTree}}\).

Из выражения \(t_{{BinTree}}\) видно, что время выполнения алгоритма бинарного дерева логарифмически зависит от числа процессов. В то же время, оно в два раза больше нижней границы времени Bcast по латентности (константа перед \(\alpha\)) и в \(2\log_2 p\) раз больше нижней границы по пропускной способности (константа перед \(\beta\)).

Нетрудно обобщить алгоритм путем перехода к алгоритму \(k\)-ичного завершенного дерева (\(k\)-ary complete tree), в котором каждый узел имеет не более \(k\) дочерних процессов. Время выполнения такого алгоритма будет определяться временем самого правого листа (рис. 1.9):

Ниже приведен псевдокод обобщенного алгоритма. Обратим внимание на то, что корнем \(root\) операции может быть выбран любой процесс. В приведенных ранее формулах для вычисления положения процесса в завершенном бинарном дереве предполагается что \(root = 0\). Мы можем ввести новую нумерацию процессов (смещенную, shifted), в которой корень будет иметь номер 0, вычислить положения каждого узла с использованием ранее рассмотренных формул, а при выполнении операции осуществить обратный переход к исходной нумерации. Процесс получает новый номер \(srank = (rank - root + p) \mathbin{\%} p\) циклическим сдвигом. Обратный переход \(rank = (srank + root) \mathbin{\%} p\).

Время выполнения алгоритма \(k\)-ичного дерева в \(k\) раз больше нижней границы по латентности и в \(k\log_k p\) раз больше нижней границы по пропускной способности.

Для реализации Bcast можно использовать \(k\)-ичные деревья и других видов. Например, дерево сбалансированное по числу узлов (рис. 1.10). В левом и правом поддеревьях число процессов отличается не более чем на единицу. Время выполнения Bcast завершается за 5 шагов, как и в случае завершенного бинарного дерева. В таком дереве процесс \(rank\) находится на уровне \(l = \lfloor \log_k (rank + 1) \rfloor\), а его дочерние узлы имеют номера:

Вычисление позиции процесса в сбалансированном по числу узлов дереве связно с вычислением логарифмов и возведением в степень, на это может потребоваться порядка \(O(\log p)\) единиц времени. Этот алгоритм реализован в библиотеке Open MPI (компонент coll/base).

Заметим, что два дерева Bcast с одной формой и разной нумерацией узлов могут приводить как разному времени на целевой системе. Это связано с тем, как процессы распределены по процессорам вычислительной системы (process mapping, task affinity). Например, возможна ситуация, при которой родитель и дочерний узел в дереве размещены на значительном расстоянии в топологии системы, например, на процессорах разных вычислительных узлов. Учет распределения процессов по процессорам системы и топологии сети – это задача архитектурно-ориентированных алгоритмов, рассмотрение которые выходят за тематические рамки этой книги.

Вернемся к вопросу о выборе оптимального значения \(k\) для завершенного бинарного дерева операции Bcast.

Из выражения для \(t_{{KTree}}\) найдем оптимальную \(k^*\) степень дерева, при которой время выполнения операции Bcast минимально.

Таким образом тернарное дерево (\(k = 3\)) является оптимальным в рассматриваемой \(\alpha\)-\(\beta\) модели. На рис. 3.11 показана зависимость количества шагов алгоритма от степени \(k\) дерева для различного числа процессов.

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

В данном алгоритме процессы выстраиваются в биномиальное дерево. Каждое биномиальное дерево \(B_k\) (binomial tree) порядка \(k\) – это рекурсивно определенное корневое упорядоченное дерево состоящее из двух деревьев \(B_{k-1}\), связанных вместе, так что корень одного является крайним слева дочерним узлом другого. На рис. 3.12 приведены примеры четырех биномиальных деревьев B0, B1, B2 и B3. Количество дочерних узлов вершины логарифмически зависит от числа её потомков. Это принципиально отличает биномиальные деревья от \(k\)-ичных, в которых степень узла фиксирована.

Биномиальное дерево Bcast для \(p\) процессов – это совокупность биномиальных деревьев, степени которых определяются номерами значащих битов в двоичном представлении числа \(p\) процессов, участвующих в операции. Степени всех биномиальных деревьев различны. Например, при числе процессов \(p=8=1000_2\) имеем одно биномиальное дерево \(B_3\) (рис. 3.13).

Обозначим через \(i_1, i_2, \ldots, i_n\) номера значащих битов в двоичном представлении числа \(p\)

Все биномиальные деревья объединены в единое дерево обменов, корнем которого является корень биномиального дерева \(B_{i_n}\) – дерево наибольшей степени:

На рис. 3.13 показано дерево обменов для \(p = 13=1101_2\) процессов. Корнем всего дерева является дерево \(B_3\), его самым левым дочерним узлом является корень дерева \(B_2\). В свою очередь, самым левым дочерним узлом дерева \(B_2\) является корень дерева \(B_0\) (корни деревьев обозначены двойной линией).

Биномиальное дерево обменов, в котором дочерние узлы с большими степенями находятся левее своих сестринских узлов, будем называть левосторонним. Заметим, что для операций корневой редукции (reduce, reduction) и сборки (gather) применяют правосторонние биномиальные деревья.

Корневой процесс выполняет \(\lceil \log_2 p \rceil\) операций передачи сообщений. Каждый некорневой процесс \(r\) выполняет один прием сообщения и не более \(\lfloor \log_2 r\rfloor\) операций передачи. Процесс определяет свое положение в дереве (номера родительского процесса и дочерних) основываясь только на своем номере \(rank\). Номер \(parent\) родительского процесса вычисляется путем сброса в значении \(rank\) первого установленного бита (find first set – FFS). Наборы команд многих процессоров включают соответствующую инструкцию FFS или инструкцию CTZ (count trailing zeros) подсчета числа завершающих нулевых битов. В приложении приведен универсальный алгоритм CTZ. Тогда номер родительского процесса может быть вычислен следующим образом:

или

Например, для вычисления родителя процесса \(10 = 1010_2\) сбрасываем второй бит и получаем номер родительского процесса \(parent = 8 = 1000_2\). Если реализация операций FFS и CTZ отсутствует, то поиск и установку необходимого бита можно реализовать последовательной проверкой в цикле разрядов числа \(rank\).

Дочерние узлы каждого процесса имеют номера больше \(rank\) и меньше \(p\). Они образуют следующую последовательность:

Количество дочерних узлов процесса \(rank\) не превышает \({CTZ}(rank)\). Справедливы следующие неравенства:

Исключение составляет корневой процесс. Номера его дочерних узлов образуют убывающую последовательность степеней двойки от наибольшей степень числа два, которая меньше \(p\), до единицы. Число дочерних узлов равно \(\lceil \log_2 p \rceil\). Для вычисления номера левого дочернего узла необходимо выполнить округление значения \(p - 1\) до ближайшей снизу степени числа два. Последнее может быть реализована тривиальным циклическим алгоритмом или поразрядной операцией FLP2 (rounding down to next power of 2) [60] . Например, для \(p = 16\) процессов первый дочерний узел корня имеет номер \({FLP2}(15) = 8\), а при \(p = 9\) дочерним узлом корня является \({FLP2}(8) = 4\). Таким образом, номера дочерних узлов корня образуют убывающую последовательность степеней двойки \({FLP2}(p - 1), \ldots, 2, 1\). Например, на рис. 3.14 корень имеет четыре дочерних узла \(8, 4, 2, 1\).

Выше мы рассмотрели основные шаги алгоритма для случая когда корнем операции является процесс 0. В приведенном ниже псевдокоде корнем операции может быть люой процесс. Это реализуется путем введения новой нумерации процессов, в которой корневой процесс всегда имеет виртуальный номер 0. Каждый процесс вычисляет свой относительный номер \(srank\) – номер процесса относительно корневого (relative rank, shifted rank):

Корневой процесс всегда имеет \(srank\) равный нулю.

Перед выполнением обменов происходит обратный переход от относительных номеров процессов к исходным:

Время работы алгоритма биномиального дерева определяется временем работы корневого процесса, которое складывается из времени передачи сообщений \(\left\lceil\log_2 p\right\rceil\) дочерним узлам:

Время выполнения алгоритма совпадает с нижней границей Bcast по латентности – алгоритм биномиального дерева для сообщений небольших размеров является оптимальным (при небольших сообщениях вклад \(\alpha\) в итоговое время доминирующий). Однако время его выполнения в \(\log_2 p\) раз больше нижней границы Bcast по пропускной способности.

В алгоритме биномиального дерева номер процесса \(rank\) трактуется как число в двоичной системе исчисления, обобщим алгоритм для случая системы исчисления с произвольным основанием \(k \in \{2, 3, \ldots, p - 1\}\).

Процессы логически выстраиваются в дерево обменов, представляющее собой совокупность \(k\)-номиальных деревьев (\(k\)-nomial tree). При \(k = 2\) дерево называется биномиальным (binomial tree), а при \(k = 3\) – триномиальным (trinomial tree). В англоязычной литературе можно встретить названия quadnomial tree для \(k = 4\) и octanomial tree для \(k = 8\). В русскоязычной литературе эти термины не получили широкого распространения. На рис. 3.15.а и рис. 3.15.б показаны примеры организации 14 процессов в триномиальное и 4-номиальное деревья. При \(k=3\) операция Bcast завершается за 5 шагов, а при \(k=4\) за 6.

Номера процессов трактуются как числа, записанные в системе счисления с основанием \(k\) (radix, base). В каждом разряде номера процесса может стоять цифра из множества \(\{0, 1, \ldots, k - 1\}\). Например, номер процесса 12 в системах счисления с основаниями \(k \in \{3, 4\}\) имеет следующие представления:

Номер родительского процесса вычисляется путем сброса в номере \(rank\) текущего процесса самого младшего разряда с положительным весом (least significant digit). Например, в биномиальном дереве номер родителя для процесса \(rank=12=1100_2\) равен \(8 = 1000_2\), который получен путем сброса в числе 12 третьего бита (младшего значащего разряда). Аналогично, в триномиальном дереве родительским для процесса \(12 = 110_3\) является узел \(9 = 100_3\), а в 4-номиальном дереве родительским для процесса \(12=30_4\) является процесс 0.

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

Если остаток от деления номера процесса \(rank\) на \(k^i\) больше нуля, то искомый разряд найден. Выполняется его сброс и прием сообщения от родительского процесса.

Количество дочерних узлов любого процесса не превышает значения

Пусть найденный младший значащий разряд в \(rank\) соответствует степени \(k^q\). Тогда для нумерации дочерних узлов процесса \(rank\) доступны его младшие нулевые разряды, соответствующие степеням

Номер каждого дочернего узла образуется путем установления одного из младших нулевых разрядов. Заметим, что в любом из доступных \(q\) разрядов может быть записана цифра из множества \(\{1, 2, \ldots, k-1\}\). Поэтому число дочерних процессов узла \(rank\) не превышает \((k-1)q\). Таким образом, у корневого процесса количество дочерних узлов не превышает значения \((k-1)\left\lceil\log_k p\right\rceil\).

Например, в биномиальном дереве для нумерации дочерних узлов процесса \(8=1000_2\) доступно три младших разряда, которые соответствуют степеням \(2^2, 2^1, 1\). Таким образом процесс 8 имеет дочерние узлы с номерами:

В 4-номиальном дереве в каждом разряде могут стоять цифры 0, 1, 2 и 3, потому процесс \(4=10_4\) имеет дочерние узлы:

В приведенном ниже псевдокоде номера дочерних узлов перебираются в цикле путем прохода по убыванию степеней числа \(k\).

Время работы алгоритма – это время корневого процесса на передачу сообщений \((k-1)\left\lceil\log_k p\right\rceil\) дочерним узлам:

Рекомендуем читателю самостоятельно оценить время выполнения внутреннего процесса \(rank\) и листового.

Ответим на вопрос – какое значение \(k\) следует выбирать на практике для минимизации времени операции Bcast? На рис. 3.16 приведена зависимость числа шагов алгоритма \(k\)-номиального дерева от степени \(k\). Видно, что из дискретных значений \(k \in \{2, 3, \ldots p - 1\}\) целесообразно выбирать \(k^{*}=2\), при котором алгоритм выполняет наименьшее число шагов.

Мы определили, что алгоритм биномиального дерева является оптимальным для сообщений небольших размеров. Теперь следует предложить алгоритм для сообщений больших размеров, который будет по пропускной способности близок к нижней границе \(m\beta\) операции Bcast.

В этом алгоритме процессы выстраиваются в цепочку, а исходное сообщение разбивается на \(\left\lceil\frac{m}{s}\right\rceil\) сегментов по \(s\) байт, \(s\) – это входной параметр алгоритма. Корневой процесс передает сегмент за сегментом своему соседу. Каждый внутренний процесс цепочки принимает текущий сегмент и одновременно с этим передает ранее принятый (если такой имеется). На рис. 3.17 показан пример для четырех процессов и разбиения сообщения на три сегмента. Подразумеваться, что каналы связи поддерживают дуплексный режим работы (full duplex) – каждый процесс может одновременно передавать и принимать сообщение. Это позволяет внутренним процессам цепочки выполнять операцию SendRecv за время \(\alpha + s\beta\). Если каналы связи полудуплексные (half duplex), то время каждого внутреннего процесса увеличиться в два раза – приём текущего сегмента будет выполняться только после завершения передачи предыдущего (\(2(\alpha + s\beta)\)). Следовательно и итоговое время работы алгоритма увеличиться в два раза.

Ниже приведен псевдокод, в котором \(count\) элементов типа \(type\) разбивается на \(\left\lceil\frac{m}{s}\right\rceil\) сегментов. Каждый сегмент содержит \(s / \mathrm{sizeof}(type)\) элементов типа \(type\). Все процессы в цикле выполняют прием и/или передачу сегментов. Размер сообщения может не делиться без остатка на \(s\), поэтому последний сегмент может быть неполным. Для этого алгоритм вычисляет в переменной \(cur\_seg\_count\) размер текущего сегмента.

Время выполнения алгоритма определяется временем получения заключительного сегмента последним процессом цепочки

Из полученного выражения найдем оптимальный размер сегмента, при котором время алгоритма минимально (в рамках рассматриваемой модели):

Откуда

На рис. 3.18 показано модельное время выполнения алгоритма биномиального дерева и конвейерного алгоритма с сегментом 4096 байт и сегментом оптимального размера \(s^{*}\). Нижняя кривая показывает нижнюю границу \(m\beta\) времени операции Bcast для сообщений больших размеров. Видно, что при рассылке операцией Bcast сообщения меньше 3 МБ наименьшее время требуется алгоритму биномиального дерева, а для сообщений больших размеров лучшие результаты демонстрирует конвейерный алгоритм с оптимальным размером сегмента. На практике целесообразно провести серию экспериментов и определить наилучшее значение сегмента. Найденное значение \(s^{*}\) является хорошим начальным приближением для такого поиска.

В этом алгоритме число операций Send/Recv линейно зависит от числа процессов и количества сегментов. Оценим во сколько раз алгоритм превышает нижнюю границу \(m\beta\) времени Bcast по пропускной способности. Найдем множитель при \(\beta\) в отношении \(t_{{Pipeline}}\) к нижней границе \(m\beta\):

где \(n = \frac{m}{s}\) – число сегментов. Видно, что при использовании одного сегмента \(n=1\) отклонение от нижней границы по пропускной способности будет в \(p-1\) раз. При числе сегментов \(n \geq p-1\) отклонение от нижней границы становится меньше двух и убывает с ростом \(n\).

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

Процессы выстраиваются в бинарное дерево. Исходное сообщение разбивается на \(\left\lceil\frac{m}{s}\right\rceil\) сегментов по \(s\) байт. Корень передает сегмент за сегментом своим левому и правому дочерним процессам. На рис. 3.19 показан пример для 7 процессов и трёх сегментов сообщения. На первом шаге корень передает первый сегмент процессу 1, на втором шаге этот же сегмент передается процессу 2, после чего корень начинает передачу дочерним узлам второго фрагмента.

На третьем шаге процесс 1 одновременно передает первый сегмент и принимает второй – используется полнодуплексный режим (рис. 3.20). На четвертом шаге в полнодуплексном режиме работает процесс 2. Таким образом полнодуплексный режим у процессов 1 и 2 используется не каждом шаге, а только через шаг, что не позволяет полностью использовать возможности каналов связи – достигнуть использования всей доступной пропускной способности (full bandwidth).

Время выполнения алгоритм определяется высотой дерева \(h\). Первый сегмент достигнет листа через \(h = \lceil\log_2 p \rceil\) шагов. На прием оставшихся сегментов потребуется еще \(n - 1\) шагов, где \(n = \left\lceil\frac{m}{s}\right\rceil\) – число сегментов. Время выполнения алгоритма определяется временем получения последнего сегмента самым правым листом:

Из выражения \(t_{{PipelinedBinTree}}\) найдем оптимальный размер сегмента, при котором время алгоритма минимально:

Откуда

На рис. 3.21 показано модельное время выполнения алгоритмов операции Bcast. Алгоритм биномиального дерева показывает лучшие результаты для сообщений меньше 120КБ, для сообщений в интервале [120KB, 20MB] лучшие результаты у алгоритма бинарного дерева с сегментацией сообщения. Для сообщений больше 50МБ наименьшее время у конвейерного алгоритма с оптимальным размером \(s^{*}\) сегмента. На практике можно провести измерения времени выполнения алгоритмов на целевой системе для различных \(p\), \(m\) и сформировать правило динамического выбора алгоритма с наименьшим временем для заданного числа процессов и размера сообщений.

Рассмотрим два алгоритма Bcast для сообщений больших размеров, которые не используют конвейерную передачу сегментов. Их ключевая идея – это расщепление операции Bcast на две коллективные операции – Scatterv с последующим вызовом Allgatherv  [61] . Алгоритм имеет ограничение – он применим для больших размеров сообщений \(count \ge p\).

Исходное сообщение разбивается на \(p\) блоков по \(count / p\) элементов типа \(type\), которые рассылаются операцией Scatterv всем процессам. После чего все блоки собираются в каждом процессе операцией Allgatherv. Фаза Scatterv реализуется алгоритмом биномиального дерева, а операция Allgatherv алгоритмом рекурсивного удваивания (recursive doubling) или кольцевым алгоритмом. Рассмотрим подробнее версию с Allgatherv на базе кольца. Ниже приведен псевдокод алгоритма.

На этапе Scatterv корневой процесс передает каждому дочернему узлу блоки для его поддерева. На рис. 3.22 показано биномиальное дерево, в котором процесс 4 принимает от корня блоки 4-7, процесс 2 блоки 2-3, а листовой процесс 1 только свой блок. Внутренние узлы дерева принимаю блоки и передают соответствующие части своим дочерним процессам. После окончания фазы Scatterv каждый процесс содержит в буфере \(buf\) порядка \(count / p\) элементов типа \(type\) начиная с позиции \(srank\) (новая нумерация процессов с корнем 0).

Каждый процесс поддерживает в переменной \(recv\_count\) количество элементов, которые он получил от родителя для его поддерева. Обратим внимание, что стандарт MPI позволяет указывать в операции Recv большее число принимаемых элементов, чем в действительности может содержать входящее сообщение. Поэтому при приеме блоков от родителя мы указываем оценку сверху \(recv\_max\) ожидаемого числа элементов. Это упрощает алгоритм. Реальное число принятых элементов определяется функцией GetRecvCount. На рис. 3.23 приведен пример кольцевого алгоритма Allgatherv для 8 процессов.

Читателю предлагается самостоятельно разобрать случай когда \(count\) не делится без остатка на \(p\) – выяснить как по дочерним процессам распределяются блоки.

Оценим время выполнения алгоритма. Время алгоритма биномиального дерева для Scatterv определяется временем корня, который последовательно за \(\left\lceil\log_2p\right\rceil\) итераций передает своим дочерним процессам группы со следующим количеством блоков:

Каждый блок по \(count / p\) элементов типа \(type\) и занимает \(m/p\) байт. Тогда время этапа Scatterv:

На этапе Allgatherv все процессы выполняют одинаковое число шагов. В случае использования кольцевого алгоритма каждый процесс выполняет \(p-1\) операций SendRecv блоками по \(m/p\) байт:

Здесь предполагается, что каналы связи поддерживают дуплексный режим – операции Send и Recv выполняются одновременно. Итоговое время алгоритма Bcast на основе Scatterv с биномиальным деревом и операцией Allgatherv на базе кольца:

В случае реализации Allgatherv рекурсивным удваиванием каждый процесс выполняет \(\log_2 p\) операций SendRecv группами блоков возрастающей длины:

Время выполнения Bcast в этом случае составит:

На рис. 3.24 приведено время выполнения алгоритмов операции Bcast на модельных данных. На размерах сообщений до 30КБ лучшие результаты показывает алгоритм биномиального дерева. На сообщениях [30КБ, 70МБ] наименьшее время у алгоритма ScattervAllgathervRdbl, а на сообщениях больше 70MB лучшие результаты показывает конвейерный алгоритм с оптимальным размером сегмента.

Важно отметить, что в отличие от рассмотренных ранее алгоритмов с сегментацией сообщения, в этих алгоритмах на этапах Scatterv и Allgatherv на базе рекурсивного удваивания размер сообщения непостоянный – передаются диапазоны блоков. Это может привести к использованию в конкретной реализации библиотеки MPI различных протоколов Send/Recv, например переключению с протокола \(eager\), для коротки сообщений, на протокол \(randezvous\) для сообщений больших размеров. В конечном счете это может как положительно, так и отрицательно сказаться на времени выполнения алгоритма.

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

Возможно ли построить алгоритм операции Bcast, который будет достигать нижней границы времени Bcast для больших сообщений (full bandwidth algorithm)? Ответ утвердительный. Известно несколько алгоритмов, например [28] , [62] , но они требуют предварительных вычислений позиции процессов в графах и деревьях специального вида. В [62] предлагается использовать циркулянтный граф, а главная идея [28] – построить два бинарных дерева, в которые входит каждый процесс и на каждом шаге выполняет одновременный прием и передачу сегментов.

Операция Scatter – это персонифицированная широковещательная рассылка. Все процессы получают сообщения одинакового размера, но из разных позиций буфера отправки \(sbuf\), который содержит \(p\) блоков:

Корневой процесс \(root\) передает \(scount\) элементов типа \(stype\) каждому процессу \(rank\) начиная с адреса

Процессы принимают сообщение в буфер \(rbuf\) как \(rcount\) элементов типа \(rtype\). Тип принимаемых элементов \(rtype\) может отличаться от типа отправляемых \(stype\). Например, корень может отправить каждому процессу персональную строку матрицы из 100 целых чисел, а принимающий процесс может сохранить сообщение в памяти как столбец из 100 элементов. Требования стандарта выполнены, сигнатуры типа отправки \(stype\) (MPI type signature) и приема \(rtype\) совпадают, совпадает и их размер – 100 элементов типа . Параметры \(sbuf\), \(scount\) и \(stype\) значимы только на стороне корня, остальным процессам следует их игнорировать.

Стандарт MPI определяет операцию Scatterv c нерегулярными размерами сообщений.

Корень передает процессу \(rank\) сообщение из \(scounts[rank\)] элементов типа \(stype\) начиная со смещения

Для операции Scatter мы рассмотрим два основных алгоритма её реализации – линейный и алгоритм биномиального дерева. Для нерегулярной версии Scatterv, как правило, библиотеки реализуют только линейный алгоритм. Мы не будем его рассматривать, так как он аналогичен соответствующему алгоритму для Scatter.

В алгоритме плоского дерева (linear tree, flat tree) корневой процесс последовательно принимает сообщения от всех процессов \(0, 1, \ldots, p-1\). Сообщение из своего буфера отправки \(sbuf\) он копирует в позицию \(root\) буфер приема \(rbuf\). Наибольшим временем выполнения характеризуется корневой процесс. Очевидно, что время выполнения линейно зависит от числа процессов \(p\) и размер сообщения \(m = scount \cdot sizeof(stype)\):

Как следует из названия в этом алгоритме процессы выстраиваются в биномиальное дерево (binomial tree), корнем которого является процесс \(root\). Дерево растет вправо, чтобы совместить выполнение операций Send/Recv в поддеревьях. Структура дерева аналогична биномиальному дереву для операции корневой редукции (см. раздел. link:[reduce_bmtree_commutative]). За исключением того, что в операции Gather процесс передает родителю не одно сообщение, а блок – сообщения всех потомков. Кроме этого внутренним узлам и листьям не доступна информация о типе сообщения корня, параметры \(rcount\) и \(rtype\)). Основное время выполнения алгоритма приходится на корневой процесс. Листовые узлы передают своё сообщение родителю и сразу выходят из операции. Если корнем является процесс отличный от 0, то процессы вводят новую нумерацию – циклически смещенную на значение \(root\): \(srank = (rank - root + p) \mathbin{\%} p\). Это упрощает вычисление положения процесса в биномиальном дереве.

На рис. 4.1 приведены примеры биномиальных деревьев для \(p=9\) с корнями в процессах 0 и 8. Во втором случае, \(root = 8\), корень формирует результат во временном буфере, положения блоков не соответствует исходной нумерации процессов. Поэтому на последнем шаге необходимо переставить два интервала элементов для установления канонического порядка в \(rbuf\).

Ниже приведен псевдокод алгоритма. На первом шаге выполняется создание временного буфера \(tmpbuf\). Очевидно, что для внутреннего узла достаточно выделять буфер, вмещающий количество блоков не превосходящее число потомков узла. Мы для простоты выделяем буфер для \(p\) блоков. В переменной \(count\) формируется количество элементов во временном буфере. Корень и внутренние узлы выполняют не более \(log_2p\) операций приема сообщений, после чего внутренние узлы передают результат родителю.

Оценим время выполнения алгоритма для случая числа процессов равного степени двойки. Обобщение на произвольное значение \(p\) не представляет сложности. Наибольшим временем характеризуется корневой процесс. Он выполняет \(\log_2 p\) операций Recv для сообщений с числом блоков \(1, 2, 4, \ldots, 2^{\log_2(p) - 1}\):

где \(m = scount \cdot sizeof(stype)\).

Если корнем выбран процесс \(root > 0\), то в конце алгоритмы возникают дополнительные накладные расходы на перестановку \(p\) блоков в \(rbuf\): \(mp\lambda\).