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

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

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