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

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

1. Гергель В. П. Параллельные вычисления: технологии и численные методы: Учебное пособие в 4 томах \\ В. П. Гергель и др. Н. Новгород: Издательство Нижегородского госуниверситета, – 2013. – 239 с.

2. Левитин А. В. Глава 11. Преодоление ограничений: Метод деления пополам // Алгоритмы. Введение в разработку и анализ — М.: Вильямс, 2006. — С. 349–353. — 576 с.

3. Лавлинская О. Ю Применение теории графов в структурнотопологическом анализе информационных систем \\ О. Ю. Лавлинская, Т. В. Курченкова. – Научные ведомости Белгородского государственного университета. Серия: Экономика. Информатика. – 2017. – № 23 (272). – С. 105-112.

4. Томас Х. Кормен и др. Глава 34. NP-полнота // Алгоритмы: построение и анализ. – 2-е изд. – М.: «Вильямс», – 2006. – С. 1296.

5. Roy, Bernard (1959). “Transitivité et connexité”. C. R. Acad. Sci. Paris (англ.)русск. 249: 216 – 218.

6. Карпов А. Отладка и оптимизация многопоточных OPENMP-программ \\ RSDN Magazine. — 2008. — № 4. — С. 32-36.