ДОСЛІДЖЕННЯ ТА РЕАЛІЗАЦІЯ ПАРАЛЕЛЬНОГО АЛГОРИТМУ ПОШУКУ BREADTH-FIRST SEARCH ЗА ДОПОМОГОЮ OPENMP
Валерій Олександрович Денисюк, Назар Русланович Білоус
Остання редакція: 2026-01-30
Анотація
У роботі розглянуто розробку та програмну реалізацію паралельного алгоритму пошуку в ширину Breadth- First Search (BFS), орієнтованого на обробку великих графових структур у середовищі спільної пам’яті. Актуальність теми зумовлена широким застосуванням обходу графів у задачах аналізу соціальних мереж, пошуку найкоротших шляхів у незважених графах, маршрутизації, побудови дерев досяжності, а також у багатьох прикладних напрямах обробки великих даних. BFS є базовим алгоритмом, який формує рівневу структуру обходу, що створює природні передумови до паралельного виконання: вершини одного рівня можуть опрацьовуватися незалежно з подальшим переходом до наступного рівня. У межах дослідження проаналізовано принципи рівневого (frontier-based) виконання BFS, визначено основні проблеми паралелізації, зокрема конфлікти доступу до спільних структур даних (позначення відвіданих вершин, масиви рівнів та предків), а також накладні витрати синхронізації між потоками. Для реалізації паралельного алгоритму використано технологію OpenMP, що забезпечує зручні засоби організації багатопотокових обчислень на багатоядерних процесорах. Програмний модуль реалізовано мовою C++ із представленням графа у вигляді списків суміжності, що є ефективним для розріджених графів та знижує витрати пам’яті порівняно з матрицею суміжності. Проведено експериментальне тестування послідовної та паралельної реалізацій BFS при різній кількості потоків. Визначено показники часу виконання, прискорення та ефективності, а також досліджено вплив збільшення кількості потоків на масштабованість. Отримані результати демонструють, що паралельна реалізація здатна зменшувати час обробки, проте при надмірному збільшенні кількості потоків можливе зниження ефективності через конкуренцію за ресурси пам’яті та витрати на синхронізацію. Практичне значення роботи полягає у можливості використання отриманих підходів для прискорення графових алгоритмів у задачах, де критичним є час обробки великих обсягів даних.
Ключові слова
Breadth-First Search, паралельний алгоритм, OpenMP, обхід графа, фронт обходу, продуктивність, прискорення, ефективність.
Посилання
1.Ахо А., Хопкрофт Д., Ульман Дж. Структури даних та алгоритми. Київ: Видавнича група BHV, 2002. 536 с.
2.Кормен Т., Лейзерсон Ч., Рівест Р., Штайн К. Алгоритми. Побудова та аналіз. 3-є видання. Київ: Видавнича група BHV, 2013. 1296 с.
3.C++ Довідкова документація. URL: https :// w 3 schoolsua . github . io / cpp / cpp _ ref _ reference . html # gsc.tab =0 .
4.Grama A., Gupta A., Karypis G., Kumar V. Introduction to Parallel Computing. 2nd ed. Addison-Wesley, 2003. 856 p.
5.Voss M. Parallel Graph Algorithms with OpenMP. In: OpenMP Shared Memory Parallel Programming. Springer, 2008. pp. 129–140.
6.Quinn M. J. Parallel Programming in C with MPI and OpenMP. McGraw Hill, 2003. 529 p.
7.Chapman B., Jost G., van der Pas R. Using OpenMP: Portable Shared Memory Parallel Programming. MIT Press, 2007. 400 p.
8.Методичні вказівки до лабораторних робіт з навчальної дисципліни «Паралельні та розподілені обчислення» (частина 1) для здобувачів вищої освіти першого (бакалаврського) рівня за освітньопрофесійною програмою «Комп’ютерна інженерія» спеціальності 123 «Комп’ютерна інженерія» денної і заочної форм навчання [Електронне видання] / Бойчура М. В., Шатний С. В., Шатна А. В. Рівне : НУВГП, 2023. 49 с.
9.Проектування та аналіз обчислювальних алгоритмів: Вступ до алгоритмів [Електронний ресурс]: навчальний посібник для студ. спеціальності 122 «Комп’ютерні науки»/ І. В. Федорін; КПІ ім. Ігоря Сікорського. Електронні текстові дані (1 файл: 1,97 Мбайт). Київ: КПІ ім. Ігоря Сікорського, 2022. 115 с.
10.Skiena S. The Algorithm Design Manual. Springer, 2020. 758 p.