РАСПАРАЛЛЕЛИВАНИЕ ВЫЧИСЛЕНИЙ ПОИСКА КРАТЧАЙШЕГО ПУТИ НА ОСНОВЕ ТЕХНОЛОГИИ OPENMP


УДК 681.3
DOI: 10.26102/2310-6018/2019.25.2.004

О.Ю. Лавлинская, В.В. Берников, О.Н. Григорова


Актуальность исследования обусловлена необходимостью решения задач распараллеливания вычислений для класса NP-полных задач, поскольку вычислительные мощности позволяют использовать параллельные потоки и снижать время вычислений и энергозатраты на получение сложного вычислительного результата с помощью программных технологий распараллеливания вычислений. В связи с этим, данная статья направлена на опубликование результатов исследования, основанных на анализе эмпирических данных, доказывающем эффективность параллельных вычислений для класса NP-полных задач. В статье проводится сравнение работы однопоточного приложения и многопоточного приложений, использующего технологию OpenMP, на примере алгоритма Флойда-Уоршалла поиска кратчайшего пути. В ходе эксперимента получены данные о скорости выполнения последовательного и параллельного алгоритмов. Сделаны выводы о том, что параллельный алгоритм эффективнее последовательного. При росте вычислительной мощности алгоритма эффективность параллельных вычислений возрастает. Эксперимент проводился для вычислений при разной мощности набора исходных данных, данные представлены в виде таблиц и графиков. Дана оценка эффективности применения стандарта распараллеливания OpenMP. Материалы статьи представляют практическую значимость для студентов магистратуры, изучающих курс «Вычислительные системы», могут быть использованы для решения прикладных задач оптимизации.

Ключевые слова: OpenMP, распараллеливание, поиск путей, алгоритм Флойд-Уоршалла.

Полный текст статьи:
LavlinskayaSoavtori_2_19_1.pdf