International Conference
"Modern Problems of Applied Mathematics and Mechanics: Theory, Experiment and Applications", devoted to the 90th anniversary of professor Nikolai N. Yanenko

Курносов М.Г.  

Моделирование алгоритмов коллективных обменов информацией между ветвями параллельных программ

     Основу современного высокопроизводительного инструментария моделирования природных явлений и сложных технических процессов составляют распределенные вычислительные системы (ВС). Параллельные алгоритмы и программы для таких ВС преимущественно разрабатываются в модели передачи сообщений (Message Passing). В этой модели ветви параллельной программы взаимодействуют друг с другом путем обменов информационными сообщениями по каналам межмашинных связей ВС.
      Анализ использования в параллельных алгоритмах и программах схем обменов информацией показывает, что до 80% времени обменов приходится на коллективные операции, в которых одновременно участвуют несколько ветвей программы (например, в стандарте MPI передача информации из одной ветвей всем реализуется коллективной функцией MPI_Bcast).
     В коммуникационных библиотеках стандарта MPI и системах параллельного программирования (в частности в модели PGAS – Partitioned Global Address Space) для реализации коллективных обменов используются алгоритмы рассылки данных по кольцу, рекурсивного сдваивания, алгоритм Дж. Брука (J. Bruck) и алгоритмы, упорядочивающие ветви в деревья различных видов. Перечисленные алгоритмы характеризуются различным временем выполнения и опираются на предположение об однородности каналов связи между вычислительными узлами распределенных ВС. Однако современные системы являются мультиархитектурными, для них характерны иерархическая структура и зависимость времени передачи данных между узлами от их размещения в системе.
     В докладе приводятся результаты исследования времени выполнения параллельных программ, реализующих распространенные численные методы, при использовании различных алгоритмов коллективных обменов информацией. Предлагается метод оптимизации алгоритмов коллективных обменов информацией между ветвями параллельных программ в иерархических распределенных ВС. Метод поясняется на примере создания алгоритмов трансляционно-циклических обменов (ТЦО, All-to-all Broadcast), учитывающих иерархическую структуру распределенных ВС. Приводятся результаты моделирования созданных алгоритмов на вычислительных кластерах различных конфигураций.