Анализ и оптимизация алгоритма параллельных цепочек для реализации корневой редукции на распределенных вычислительных системах
Курносов М.Г.

В модели параллельных вычислений LogP построено аналитическое выражение времени выполнения алгоритма k параллельных цепочек для реализации корневой редукции на распределенных вычислительных системах (ВС). По построенной функциональной зависимости найдено оптимальное значение числа k параллельных цепочек, при котором алгоритм характеризуется минимальным в модели LogP временем выполнения. На основе этого создан алгоритм с оптимальным числом параллельных цепочек. Для сокращения времени ожидания корневым процессом результатов частичных редукций разработан алгоритм с адаптивным числом параллельных цепочек. Зависимость времени выполнения созданных алгоритмов от числа процессов имеет порядок роста Ο(sqrt{P}), что эффективнее по сравнению с линейным Ω(P) временем выполнения исходного алгоритма. Алгоритмы реализованы в стандарте MPI и исследованы на вычислительных кластерах с сетями связи стандарта InfiniBand QDR.

Ключевые слова: корневая редукция, модель передачи сообщений, MPI, параллельное программирование, распределенные вычислительные системы.

Название статьи, аннотация и ключевые слова на английском языке

  • Курносов М.Г. – Сибирский государственный университет телекоммуникаций и информатики, Центр параллельных вычислительных технологий, ул. Кирова, 86, 630102, Новосибирск; директор, e-mail: mkurnosov@gmail.com