Skip to content

Edge Centric and GAS

Jump to bottom
Abdullah Mughrabi edited this page Aug 14, 2026 · 1 revision

Edge-Centric and GAS CPU Baselines

GraphBrew keeps the existing GAPBS-derived programs as the canonical vertex/frontier baselines and adds edge-centric schedules as separate CPU implementations. Gather-Apply-Scatter (GAS) is added only where its phases match the algorithm rather than being forced onto every graph problem.

The executable contract is:

bench/contracts/edge_gas_algorithms.json

Validate it with:

make check-edge-contracts
make check-edge-contract-profiles

Canonical algorithms

Algorithm Edge-centric GAS Required structure
BFS yes no sparse push plus dense pull
BC yes no forward BFS plus ordered backward gather
CC yes yes edge linking; optional active min-label propagation
CC-SV yes no separate GAS atomic hooking plus pointer jumping
PR yes yes incoming gather and residual convergence
PR-SPMV yes no separate GAS deterministic synchronous gather
SSSP yes yes Delta-Stepping edge baseline; active-set GAS reference
TC yes no oriented edges plus sorted adjacency intersection

bfs_p and tc_p are specialized consumers, not separate semantic algorithms. Canonical baselines remain isolated in bench/src/; edge drivers live in bench/src_edge/, GAS drivers in bench/src_gas/, and simulation drivers in bench/src_sim/. Existing src_sim files are legacy instrumented forks and are not the semantic contract authority; some have already drifted from canonical source/verifier behavior. New cache-simulation binaries must instantiate shared kernels through access hooks instead of copying algorithm bodies.

Correctness rules

  • Existing verifier functions remain authoritative.
  • BFS parent identity may vary, but it must be a valid shortest-path tree.
  • CC labels are representative-invariant; compare partitions, not label bytes.
  • BC backward accumulation preserves stored CSR successor order because the verifier compares normalized floats at FLT_EPSILON scale.
  • SSSP distances and TC counts are exact.
  • PR variants pass the existing residual threshold.
  • Kernel and verifier SourcePicker instances must select the same source.

Data and scheduling

  • CSR/source order serves push and scatter.
  • CSC/destination order serves pull and Gather.
  • Undirected graphs expose both all directed CSR entries and an oriented one-entry-per-edge stream.
  • Edge-stream construction is outside timed trials unless conversion itself is the benchmark.
  • Dense gathers use destination ownership and deterministic segmented reduction.
  • Sparse traversals use thread-local frontier queues and CAS/min updates.
  • Work counters are informational; verifier-defined output is the cross-thread correctness gate.

Shared edge primitives

bench/include/graphbrew/edge/ provides the common CPU schedule layer:

  • source-major and destination-major flat views preserve logical (source, destination) edge identity;
  • non-owning EdgeStream views reject temporary flat graphs at compile time;
  • ordinal partitions cover every directed entry exactly once, while oriented undirected iteration retains only source < destination;
  • Frontier combines sorted sparse IDs with a dense bit map; FrontierBuilder atomically deduplicates parallel producers into thread-local queues;
  • integer min/max/CAS helpers report whether an update won;
  • edge-map access policies are invoked concurrently and must be thread-safe.

Run the primitive and thread-count checks with:

make check-edge-primitives

View construction is intentionally measured separately from algorithm trials:

make edge_view_benchmark
OMP_NUM_THREADS=4 bench/bin/edge_view_benchmark -g 18

Dense iterative edge baselines

The first four edge binaries share algorithm headers under bench/include/graphbrew/algorithms/:

  • pr_spmv_edge is synchronous Jacobi PageRank. Each iteration freezes outgoing contributions, then performs destination-owned incoming gathers in stored edge order.
  • pr_edge is an explicitly asynchronous destination-owned PageRank schedule. Cross-owner contributions use atomic floats, so immediate visibility is data-race-free. Iteration counts may differ by thread count; the existing residual verifier is the semantic gate.
  • cc_edge preserves Afforest neighbor sampling, skips proven sampled prefixes, then performs edge-balanced atomic union. Directed edges connect endpoints for weak connectivity; symmetric graphs use one oriented edge.
  • cc_sv_edge performs CAS-safe monotone root hooking followed by atomic shortcutting.

All flat views are built before BenchmarkKernel, so trial timing excludes representation conversion. The paired matrix runs every declared profile, including directed, disconnected, synthetic, and dangling-vertex cases, against the canonical binary and the edge binary at OMP 1/2/4/8:

make check-edge-dense

The matrix gates verifier-defined output. It does not require equal PageRank iterations or bit-identical asynchronous scores.

Frontier and weighted edge baselines

  • bfs_edge keeps one sparse-plus-bitmap frontier. Sparse phases push outgoing edges with CAS parent claims; dense phases own destinations and pull from the incoming flat view, so directed traversal uses true predecessors. The canonical alpha/beta switching and scout/awake work metrics are preserved.
  • sssp_edge retains Delta-Stepping rather than scanning every edge. One persistent OpenMP team processes the shared current bin, relaxes only active vertices' weighted outgoing ranges, fuses small same-bin thread-local work, and selects the globally smallest remaining bin.
  • weighted outgoing flattening preserves (source, destination, weight) and is built before timed trials.

Both kernel and verifier use separately constructed, identically seeded SourcePicker instances. Run all registered graph/thread profiles plus paired multi-trial source checks with:

make check-edge-frontier

The current matrix passes 36/36 verifier-backed edge trials at OMP 1/2/4/8.

Irregular multi-phase edge baselines

  • bc_edge runs sampled-source Brandes with level-synchronous outgoing edge push, CAS depth discovery, and atomic double path counts. Backward dependency gathers run deepest-to-source and preserve each vertex's stored outgoing CSR order so the existing float-epsilon verifier remains authoritative.
  • tc_edge optionally applies the canonical degree-relabel heuristic before timing, then processes one oriented undirected edge and intersects the two sorted adjacency prefixes below its middle vertex. Each triangle is counted exactly once; TC is not represented as scalar GAS.

Run the canonical/edge matrix, paired BC sources, and triangle/no-triangle profiles with:

make check-edge-irregular

The current matrix passes 32/32 verifier-backed edge trials at OMP 1/2/4/8.

Reusable GAS executor

bench/include/graphbrew/gas/executor.h defines synchronous supersteps over destination-major Gather and source-major Scatter views:

  • Gather programs provide an identity, associative combine, and per-edge contribution.
  • Apply returns the new state, changed flag, and convergence contribution.
  • Scatter cannot mutate graph/state; it only requests destination activation.
  • Dense mode applies every vertex and swaps a reusable next-state buffer.
  • Active mode touches only sorted active vertices and incident edges, scatters before committing updates, and preserves inactive state in place.
  • Convergence combines in deterministic node/active order.
  • Program methods are const and must be reentrant because Gather/Apply/Scatter execute concurrently.

Frontier builders adapt if the OpenMP team grows between supersteps and retain a safe overflow path. Run synchronous, active-only, mixed-schedule, thread-growth, and validation tests with:

make check-gas-runtime

Natural GAS baselines

  • pr_gas runs dense synchronous incoming Gather, damp/base Apply, and residual Scatter activation. Dense scheduling remains authoritative, so the Scatter pass is intentionally measured even though its frontier is informational.
  • cc_gas performs active minimum-label propagation over a symmetric weak-neighbor view. Directed graphs include both outgoing and incoming neighbors; changed labels activate adjacent vertices.
  • sssp_gas is explicitly an active-set Bellman-Ford-class reference: destinations gather dist[source] + weight, Apply min, and changed vertices activate outgoing neighbors. Delta-Stepping remains the optimized edge baseline; the accepted -d option is CLI compatibility and is not hidden inside GAS.

Run canonical/GAS verifier profiles and paired SSSP sources with:

make check-gas

The current matrix passes 48/48 GAS trials at OMP 1/2/4/8.

There is no separate GAS binary for BFS (first-parent GAS is artificial), BC (forward and reverse phases differ), PR-SPMV (already the useful synchronous Gather/Apply core), TC (requires sorted two-list intersection), or MEMCPY (not a graph algorithm).

CPU qualification gate

Build every implementation with:

make edge-all gas-all

Run the complete contract, primitive, canonical-control, edge, GAS, source-pair, thread-count, topology, and repeatability qualification with:

make check-edge-gas

The gate covers directed asymmetric, undirected isolated, path, star, disconnected, weighted isolated/path/star, synthetic power-law-like, triangle, no-triangle, and dangling-vertex cases. It currently passes:

  • 112 dense-edge verifier cells;
  • 60 frontier-edge verifier trials;
  • 56 irregular-edge verifier trials;
  • 84 GAS verifier trials;
  • 22 two-trial repeatability checks across all 11 edge/GAS binaries;
  • canonical smoke/source controls plus primitive and GAS-runtime tests.

Only verifier-defined semantic output is gated. Iteration counts, active work, and examined-edge counters remain informational because legal schedules differ.

Structural performance qualification

The contract records each algorithm's work class, balance policy, ownership, and GAS work class where applicable. Validate those claims against the source with:

make check-edge-structure

The audit binds direction-optimized BFS, active Delta-Stepping bins and fusion, sampled Brandes, oriented TC intersection, destination-segment PageRank, Afforest/SV, and dense/active GAS schedules to their implementations. It also checks conversion/relabel placement before BenchmarkKernel and rejects unapproved critical sections; only the guarded FrontierBuilder overflow path is allowed.

Generate an on-demand verified comparison report with:

make report-edge-gas-performance
# or customize:
python3 scripts/experiments/edge_gas_report.py \
  --threads 8 --trials 5 --synthetic-scale 14

The JSON reports local average time, nominal input-edge rate, canonical-relative speedup, per-trial and median time, and the structural work/balance/ownership contract. Source-driven algorithms use the same deterministic SourcePicker sequence instead of a potentially degenerate fixed source. It explicitly has hard_speed_gate=false; nominal input-edge rate is not actual examined-edge work.

Current performance assessment

The 2026-07-21 four-thread audit used repeated interleaved median trials. This is a shared host, so unmodified near-parity variants remain inconclusive. The research-aligned optimization pass brought three previously stable regressions to parity:

Variant Canonical-relative speed Assessment
bfs_edge 1.08x parity / slight win
cc_edge 0.94x near parity
tc_edge 1.01x parity
cc_sv_edge 0.58-0.63x vertex baseline wins
bc_edge 0.61-1.37x inconclusive
sssp_edge 0.48-1.56x inconclusive
pr_spmv_edge 0.80-1.44x inconclusive
pr_edge 0.41-1.91x inconclusive
GAS variants below 0.27x reference-only

The successful changes match the cited research: Beamer/GAPBS queue+bitmap DOBFS, Afforest's whole-row giant-component skip, and dynamic forward triangle intersection scheduling. CC-SV now uses direct CSR rows and has near-parity single-thread cost, but parallel root-hook contention remains; the canonical implementation uses racy plain writes while the edge version preserves atomic root hooking. BC, PR, PR-SPMV, and SSSP still require a quiescent/dedicated-host rerun before any performance verdict or tuning.

Implications for .blox acceleration

  • BFS: sparse queue production, bitmap materialization, dynamic incoming pull, and sparse/dense switching are schedule primitives; sorting is not.
  • Afforest CC: fixed neighbor sampling and row-level skip of the sampled giant component are the critical flow controls, not a full oriented-edge scan.
  • TC: sorted SET_OPS intersection is already the right compute primitive; the missing gain is work-aware scheduling across oriented source rows.
  • CC-SV: atomic root CAS/min plus pointer jumping is the remaining hot path and directly matches the D2 atomic-RMW blocker. This is the strongest edge-centric hardware acceleration candidate.

Literature

Start

Core idea

Experiments

Reference

Development

Clone this wiki locally