ДОСЛІДЖЕННЯ ТА РЕАЛІЗАЦІЯ ПАРАЛЕЛЬНОГО АЛГОРИТМУ ПОШУКУ В ГЛИБИНУ ДЛЯ БАГАТОЯДЕРНИХ СИСТЕМ
Валерій Олександрович Денисюк, Михайло Васильович Білаш
Остання редакція: 2026-01-31
Анотація
У роботі розглянуто реалізацію та аналіз паралельного алгоритму пошуку в глибину (Depth-First Search, DFS) для обробки графових структур. Проаналізовано особливості класичного послідовного DFS та визначено основні труднощі його розпаралелювання в багатопотоковому середовищі. Обґрунтовано вибір списку суміжності як основної структури даних для подання графів. Розроблено програмну реалізацію паралельного алгоритму DFS мовою Python із використанням бібліотеки threading. Запропоновано модель розпаралелювання на основі розподілу піддерев графа між потоками з урахуванням синхронізації доступу до спільних даних. Проведено експериментальне дослідження ефективності алгоритму для графів різної розмірності та різної кількості потоків. Отримані результати показують, що паралельна реалізація DFS має обмежену масштабованість, зумовлену послідовною природою алгоритму та накладними витратами на синхронізацію. Разом з тим, запропонований підхід може бути використаний для аналізу ефективності паралельних алгоритмів обходу графів у багатопотокових програмних системах.
Ключові слова
паралельний алгоритм, пошук у глибину, DFS, графи, багатопотокові обчислення, паралельне програмування, Python.
Посилання
1.Bader, D. A., & Madduri, K. Designing Multithreaded Algorithms for Breadth-First Search and Depth-First Search on Multicore Systems.
2.Georgia Institute of Technology, College of Computing, Technical Report, 2006. Available at: https://www.cc.gatech.edu/~bader/papers/BFS-TR.pdf
3.Ящук С. П., Грицай Я. М. Паралельні обчислення: навчальний посібник. Львів: Вид-во Львівської політехніки, 2020.
4.Васильєв А. М. Паралельні та розподілені обчислення: підручник. Київ: КНУ, 2019.
5.Tarjan R. Depth-First Search and Linear Graph Algorithms. SIAM Journal on Computing, 1972.
6.Bondy J. A., Murty U. S. R. Graph Theory. Springer, 2008.
7.Burtscher M., Pingali K. An Efficient Lock-Free Parallel Depth-First Search. Proceedings of the ACM SIGPLAN PPoPP, 2010.
8.Rauber T., Rünger G. Parallel Programming: for Multicore and Cluster Systems. 2nd ed. Springer, 2013.
9.Grama A., Gupta A., Karypis G., Kumar V. Introduction to Parallel Computing. 2nd ed. Pearson, 2003.