Acceleration of Forward-Backward Algorithm in CUDA

The Problem

Finding a directed graph's Strongly Connected Components — maximal groups of nodes that can all reach each other — shows up everywhere from compiler loop detection to social-network community discovery to image segmentation. The classic serial algorithms (Kosaraju's, Tarjan's) are both built on depth-first search, which is notoriously hard to parallelize. The Forward-Backward (FB) algorithm sidesteps that by using breadth-first search instead, which does parallelize well, and prior work by Barnat et al. had already ported FB to CUDA — but without using one of CUDA's strongest tools for it: streams.

Approach

CUDA streams let independent sequences of GPU operations run concurrently instead of blocking on a single default stream. In the FB algorithm, computing a pivot's forward closure and its backward closure (via a transposed graph) are independent operations — so we merged the existing FWD/BWD host functions into a single wrapper that launches both kernels asynchronously on separate non-default streams, letting the GPU overlap their execution instead of running them back-to-back.

We benchmarked the streamed and non-streamed versions against graphs generated with the GTGraph/SSCA#2 suite, ranging from 32 to 128 nodes at sparse (25%), medium (45%), and dense (70%) connectivity, on a single GTX 1650 Max-Q.

Results

• The streamed implementation matched or slightly underperformed the baseline on small graphs, where kernel runtime is too short for the streaming overhead to pay off.
• On larger, denser graphs — starting around N=128, E=4143 — streaming pulled ahead, with up to 40% faster execution than the non-streamed baseline, and the gap widened further as graph density increased.
• We had hypothesized that CUDA's unified memory would help, since the device only reads the graph data — it didn't; manually managed memory outperformed it for this workload, so we used manual memory management for both versions in the final comparison.

Conclusion & Future Work

Overlapping the forward and backward reach kernels via CUDA streams delivered a meaningful, close-to-real-world speedup on the FB algorithm with a relatively small implementation change. Planned next steps include overlapping the host-side graph transpose with the forward kernel's execution (only the backward kernel actually needs the transposed graph), fixing memory leaks that currently crash the algorithm on larger graphs, and testing against real-world, not just synthetically generated, graphs.

Advised by Dr. Muhammad Mobeen Movania at Habib University.