Дослідження та реалізація паралельного алгоритму пошуку Breadth-First Search за допомогою OpenMP

Abstract

У роботі розглянуто розробку та програмну реалізацію паралельного алгоритму пошуку в ширину BreadthFirst Search (BFS), орієнтованого на обробку великих графових структур у середовищі спільної пам’яті.

The paper considers the development and software implementation of a parallel Breadth-First Search (BFS) algorithm designed for processing large graph structures in a shared-memory environment. The relevance of the topic is driven by the widespread use of graph traversal in practical tasks such as social network analysis, shortest path search in unweighted graphs, routing, reachability tree construction, and various big data processing pipelines. BFS is a fundamental algorithm that builds a level-by-level traversal structure, which naturally enables parallel execution: vertices belonging to the same level can be processed independently before moving to the next level. Within the study, the principles of level-synchronous (frontier-based) BFS execution are analyzed and the main parallelization challenges are identified. In particular, special attention is paid to data races and shared-state conflicts when updating common