Performance-Driven Optimization of Parallel Breadth-First Search

Marati Bhaskar, Raghavendra Kanakagiri · 2025

Read Performance-Driven Optimization of Parallel Breadth-First Search by Marati Bhaskar, Raghavendra Kanakagiri (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2503-00430.txt.

Introduction

Marati Bhaskar and Raghavendra Kanakagiri work on speeding up breadth-first search on many-core machines in a twenty twenty-five paper. Breadth-first search walks a graph level by level and is a core tool in data work. In parallel it is held back by scattered memory access, uneven work, and sync costs.

The pair tests a set of fixes: a hybrid walk that flips direction, a bitmap for visited nodes, and a new way to update distances without atomic locks. They run the tests on a twenty-four-core Intel chip and a one hundred twenty-eight-core AMD chip. For graphs of small width the hybrid walk ran three to ten times faster. Wide graphs gave mixed results.

Catalog record

CREATORMarati Bhaskar, Raghavendra Kanakagiri
YEAR2025
COLLECTIONPAPERS
FORMATTXT
FILE SIZE19 KB
VERSION1.0
LICENSEhttp://creativecommons.org/licenses/by/4.0/
RIGHTSCC BY
SOURCEarXiv

Source: https://arxiv.org/abs/2503-00430

Browse the full library · About the Tower of Babel

Full text

The opening of the work, from the library's hosted text:

Performance-Driven Optimization of Parallel Breadth-First Search Marati Bhaskar, Raghavendra Kanakagiri Abstract . Breadth-first search (BFS) is a fundamental graph algorithm that presents significant challenges for parallel implementation due to irregular memory access patterns, load imbalance and synchronization overhead. In this paper, we introduce a set of optimization strategies for parallel BFS on multicore systems, including hybrid traversal, bitmap-based visited set, and a novel non-atomic distance update mechanism. We evaluate these optimizations across two different architectures - a 24-core Intel Xeon platform and a 128-core AMD EPYC system - using a diverse set of synthetic and real-world graphs. Our results demonstrate that the effectiveness of optimizations varies significantly based on graph characteristics and hardware architecture. For small-diameter graphs, our hybrid BFS implementation achieves speedups of 3 − 8 × 3-8\times on the Intel platform and 3 − 10 × 3-10\times on the AMD system compared to a conventional parallel BFS implementation. However, the performance of large-diameter graphs is more nuanced, with some of the optimizations showing varied performance across platforms including performance degradation in some cases. Conference: ; ; CCS: Software and its engineering General programming languages CCS: Social and professional topics History of programming languages 1. Introduction Graphs are data structures that represent relationships between entities, with vertices denoting entities and edges capturing their connections. Graph algorithms analyze these relationships and are crucial in applications ranging from social networks to bioinformatics. Breadth-first search (BFS) is a fundamental graph algorithm that explores vertices level by level from a source vertex, serving as a building block for many other graph algorithms. Despite its simple design, parallelizing BFS efficiently is challenging due to irregular memory access patterns, load imbalance and synchronization overheads. While several works have explored BFS optimizations across different architectures using various techniques ( McCune et al., 2015 ; Shun and Blelloch, 2013 ; Wang et al., 2016 ; Liu and Huang, 2015 ; Yang et al., 2022 ; Wang et al., 2023 ; Beamer et al., 2012 ) , achieving high performance remains difficult. In this paper, we investigate various optimization strategies for parallel BFS on multicore systems. We evaluate these optimizations across two different architectures and analyze their impact on BFS performance using diverse graph datasets. In this paper, we make the following contributions: • We introduce a novel optimization strategy that uses non-atomic updates for distance values in BFS kernels. We quantify the opportunities for non-atomic updates and evaluate the impact on performance. • We propose a simple yet effective heuristic for dynamically switching between top-down and bottom-up BFS phases based on the frontier size. • We present a bitmap-based approach for tracking visited vertices in BFS, which reduces memory overheads and improves cache locality. • We evaluate our optimizations on two different platforms: SpeedCode ( Kaler et al., 2024 ) and an in-house x86 server, and show that the effectiveness of optimizations is influenced by both graph characteristics and hardware architecture. 2. Optimization Strategies In this section, we describe several optimizations to improve the performance of parallel BFS on multicore processors. We present these optimizations in the context of the parallel BFS kernel shown in Listing 1 (excluding the highlighted code block in blue). We refer to this kernel as the BFS-Conventional kernel, which uses atomic operations to ensure single-threaded updates to vertex distances. Throughout our discussion of optimizations, the term ‘local frontier’ refers to the vertices collected by each individual thread during an iteration, before they are merged into the global frontier. While we experimented with various parallel scheduling approaches, including dynamic scheduling with different chunk sizes, static scheduling consistently showed the best average performance on the Speedcode platform ( Kaler et al., 2024 ) in our experiments. BFS-NonAtomic: In the BFS-Conventional kernel, we use atomic operations to update vertex distances. These atomic operations are expensive and can lead to contention. In our bulk-synchronous BFS implementation, since threads update vertex distances synchronously level by level, a vertex’s distance is updated with the same value even when multiple threads attempt to update it. Removing atomic updates introduces two issues: (1) Duplicate work: The same vertex can be added to the frontier multiple times by different threads, leading to redundant processing in the next iteration, (2) Data races: Since multiple threads update the same memory location without synchronization, this creates a data race according to the C++11 standard, which defines it as concurrent conflicting actions where at least one is non-atomic. (Section 1.10.21 in ( for Standardization, 2013 ) ). While multiple threads updating the same memory location without synchronization is technically undefined behavior according to the C++ standard, our implementation exploits the fact that all concurrent updates write the same distance value due to the level-synchronized nature of BFS. In Section 3 , we quantify the performance impact of this optimization and caution that its usage should be limited to architectures that provide the necessary hardware guarantees and contexts where compiler optimizations won’t affect the intended behavior. Also note that this optimization is specific to BFS’s distance updates and cannot be employed if a node’s data must be strictly updated only once. In Figure 1 (left), we show the average percentage of duplicates in the frontier across iterations without atomic updates. We observe that the percentage of duplicates is less than 1\% of the total frontier size across several datasets. The dataset kNN_graph has the highest average duplicates at 31.6\% . Figures 1 (middle and right) show the percentage of duplicates and frontier sizes across iterations for the kNN_graph , respectively. We observe that the percentage of duplicates increases in later iterations when the frontier size becomes small (less than 1\% of total vertices). Therefore, although the percentage of duplicates appears high, the actual number of duplicate vertices is small. Since many threads would be idle during these small-frontier iterations anyway, having them process duplicate vertices does not negatively impact performance. Figure 1 . Analysis of duplicates and frontier size across iterations. ⬇ 1 #pragma omp parallel 2 { 3 while ( cfsz != 0) { 4 // Traverse all vertices in current frontier 5 #pragma omp for nowait 6 for ( uint32_t i = 0; i < cfsz ; ++ i ) { 7 vidType src = curr_frontier [ i ]; 8 // Traverse all neighbors of frontier vertex 9 for ( uint32_t j = rptr [ src ]; j < rptr [ src +1]; ++ j ) { 10 vidType dst = col [ j ]; 11 // if neighbor is not visited 12 if ( dist [ src ] + 1 < dist [ dst ]) { 13 // BFS-Conventional: atomically update the neighbor’s distance 14 15 if (__sync_bool_compare_and_swap(&dist[dst], MAX_DISTANCE, dist[src] + 1)) { 16 17 // BFS-NonAtomic: Update the distance directly. See issue 2 as detailed in BFS-NonAtomic 18 19 dist[dst] = dist[src] + 1; 20 21 // Add to local frontier 22 lf [ lfsz ++] = dst ; 23 } 24 } 25 } 26 } 27 if ( lfsz != 0) { 28 // collect local frontiers 29 fstart = __atomic_fetch_add (& nxt_fsz , lfsz , __ATOMIC_SEQ_CST ); 30 for ( uint32_t i = 0; i < lfsz ; ++ i ) 31 next_frontier [ fstart + i ] =

Read the complete text