РАСПАРАЛЛЕЛИВАНИЕ ВЫЧИСЛЕНИЙ ПОИСКА КРАТЧАЙШЕГО ПУТИ НА ОСНОВЕ ТЕХНОЛОГИИ OPENMP
Работая с нашим сайтом, вы даете свое согласие на использование файлов cookie. Это необходимо для нормального функционирования сайта, показа целевой рекламы и анализа трафика. Статистика использования сайта отправляется в «Яндекс» и «Google»
Научный журнал Моделирование, оптимизация и информационные технологииThe scientific journal Modeling, Optimization and Information Technology
cетевое издание
issn 2310-6018

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

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

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

  • Аннотация
  • Список литературы
  • Об авторах

Актуальность исследования обусловлена необходимостью решения задач распараллеливания вычислений для класса 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.

Лавлинская Оксана Юрьевна
кандидат технических наук доцент
Email: lavlin2010@yandex.ru

Воронежский институт высоких технологий

Воронеж, Российская Федерация

Берников Владислав Валерьевич

Email: vladislavbernikov@gmail.com

Воронежский институт высоких технологий

Воронеж, Российская Федерация

Григорова Ольга Николаевна
кандидат экономических наук доцент
Email: grigorova@mail.ru

Воронежский институт высоких технологий

Воронеж, Российская Федерация

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

Для цитирования: Лавлинская О.Ю. Берников В.В. Григорова О.Н. РАСПАРАЛЛЕЛИВАНИЕ ВЫЧИСЛЕНИЙ ПОИСКА КРАТЧАЙШЕГО ПУТИ НА ОСНОВЕ ТЕХНОЛОГИИ OPENMP. Моделирование, оптимизация и информационные технологии. 2019;7(2). Доступно по: https://moit.vivt.ru/wp-content/uploads/2019/05/LavlinskayaSoavtori_2_19_1.pdf DOI: 10.26102/2310-6018/2019.25.2.004

565

Полный текст статьи в PDF