Курносов М.Г. Берлизов Д.М. Ткачёва Т.А. Токмашева Е.И.
Анализ и оптимизация конвейерных алгоритмов широковещательной передачи стандарта MPI
Докладчик: Курносов М.Г.
На протяжении последних 20 лет библиотеки стандарта MPI (message passing interface) являются основным средством создания параллельных программ для вычислительных систем с распределённой памятью. Важной составляющей стандарта являются коллективные операции информационных обменов (collective communications), в которых участвуют все или подмножество процессов MPI-программы: Allgather, Allreduce, Alltoall, Barrier, Broadcast, Gather, Exscan, Reduce, Scan, Scatter. Профилирование пакетов параллельного моделирования показывает, что эффективность алгоритмов коллективных обменов является критически важной и может быть узким местом, ограничивающим масштабируемость параллельных программ.
Важным аспектом оптимизации алгоритмов коллективных операций является анализ времени их выполнения в различных моделях параллельных вычислений: Хокни, LogP/LogGP, BSP. В настоящей статье рассмотрены масштабируемые алгоритмы, реализующие операцию MPI_Bcast трансляционной передачи сообщения (one-to-all broadcast): алгоритмы k-арного и k-номиального дерева, а также алгоритмы с конвейеризацией передачи сообщений, линейный и на основе бинарного дерева. Исследование алгоритмов выполнено с учётом деталей их реализации в библиотеке Open MPI 4.0.0.
При вызове коллективной операции библиотека MPI динамически определяет для заданного MPI-коммуникатора (числа процессов) и параметров операции (размера сообщения, типа данных, номера корневого процесса), какой из доступных алгоритмов широковещательной передачи использовать. В текущих реализациях MPICH, MVAPICH и Open MPI используются фиксированные правила выбора алгоритма, основанные на размере транслируемого сообщения и/или числе процессов. Значительная часть алгоритмов операции MPI_Bcast имеют настраиваемые параметры, влияющие на общее время выполнения операции. В данной работе был проведён теоретический и экспериментальный анализ времени выполнения алгоритмов операции MPI_Bcast и определены в модели Хокни оптимальные значения настраиваемых параметров алгоритмов – степени деревьев и размеры сегментов в конвейеризированных версиях алгоритмов. В отличие от ранее выполненных работ, в данной работе анализ времени выполнения алгоритмов не ограничен построением асимптотических оценок, уделено внимание и константам при параметрах α и β модели Хокни. Теоретические оценки подкреплены результатами экспериментов на вычислительных системах с сетями связи стандартов Gigabit Ethernet и InfiniBand.
К списку докладов