GPU-Accelerated Graph Analytics for Irregular Security Graphs

Project Background

Many problems in my field produce graphs with the same difficult shape: power-law, highly imbalanced degree distributions. A binary’s call-graph has a handful of hot helper functions called from everywhere while most functions are called once; a network-flow graph for intrusion detection has a few scanning hosts touching thousands of peers while most hosts touch a handful. On a GPU, this imbalance is exactly what wrecks performance — one thread grinds through a hub with tens of thousands of edges while its 31 warp-mates sit idle.

This project is a reproducible empirical study — not a claim of a new algorithm — of how the standard GPU-acceleration techniques perform on these irregular security graphs. Four classic graph algorithms are implemented at every optimization tier, so each speedup is attributable to a specific technique, and every GPU number is reported against both a single CPU core and a full 8-core CPU — never just one core.

Code: github.com/Emad-Mahmodi/gpu-graph-study

Algorithms × Optimization Tiers

Every algorithm is implemented at each tier, so a speedup can be traced to one technique rather than a rewrite. The sequential tier doubles as a correctness oracle — every faster tier (including all GPU kernels, on a 254-level high-diameter case) is diffed against it in CI.

• T0 Sequential — the correctness oracle.
• T1 OpenMP — multi-core CPU baseline (8 threads).
• T2 Naïve CUDA — one thread per vertex, CSR in global memory: the honest starting point.
• T3 Optimized CUDA — block-level parallel reductions, precomputed inverse degree, frontier / active-set traversal.
• T4 Load-balanced — degree-bucketed scheduling (thread / warp / block per vertex), documented as an established technique (Gunrock/Merrill), not a novel contribution.

Headline Result — the PageRank optimization ladder

The clearest story in the study. Naïve GPU PageRank loses — its two per-iteration reductions are single-address atomics that all N threads fight over. Each optimization removes one named bottleneck, and the speedups compound. Measured on an NVIDIA T600 (entry-level, 4 GB, Turing) vs an Intel i7-11850H (8-core), on a power-law RMAT graph (2²⁰ vertices, 33.5M edges, max degree 138,626), median of 10 runs.

Two techniques, each attributable: T3 = parallel reduction (fixes the write/reduce), T4 = degree-bucketed scheduling (fixes the read/gather). The third bucket level — a whole block per extreme hub — was implemented and measured to give no gain on this graph (a documented point of diminishing returns), because RMAT’s power-law tail holds too few very-high-degree vertices for it to matter.

Key Finding — the optimal strategy depends on graph diameter

For traversal (BFS, WCC), the T3 “only launch active vertices” optimizations (frontier worklist, active-set label propagation) are not unconditional wins. Whether they pay off depends on the graph’s diameter — so I measured both regimes: a shallow power-law RMAT graph (BFS depth 4) and a high-diameter 2D grid (depth 2046).

An honest bottom line

On this hardware — an entry-level 4 GB T600 against a strong 8-core mobile CPU — the multi-core CPU is the sensible default on these mid-size graphs; the GPU optimizations are large and real as techniques but the T600 does not overtake the CPU at this scale. That is exactly the kind of candid, hardware-grounded result a tiered study exists to produce, rather than a single flattering “GPU vs one core” number. The transferable contributions are the technique attribution (each speedup tied to one named optimization), the diameter-crossover finding, and the launch-bound characterization — all reproducible from committed CSVs and figure scripts.

Domain Bridge — Real Binary Graphs

The analytics engine is domain-agnostic: it consumes a graph in CSR form and never parses a binary or a packet. A companion extractor turns a real symbol-bearing binary into a call-graph (functions → vertices, call instructions → edges) that the same engine analyzes — so one codebase spans both binary-analysis and network-security graphs, tying the systems/HPC work directly to my reverse-engineering background.

Engineering & Reproducibility

Built in raw C++/CUDA with CMake (MSVC and GCC, CPU-only builds fall back gracefully with no GPU), the project ships a CI-gated correctness suite (GPU kernels validated against the sequential oracle, including a high-diameter case), a deterministic RMAT generator, a 2D-grid generator for the diameter study, a median-of-N timing harness, committed result CSVs, and Python scripts that regenerate every figure from one dataset. GPU timings are end-to-end and reported against both CPU baselines.

Full methodology, tier-by-tier code, roadmap, and results: github.com/Emad-Mahmodi/gpu-graph-study