Asynchronous distributed graph algorithms in Charm++, over the htram message-aggregation library.
Currently one kernel: ACIC single-source shortest path (sssp_smp). The
algorithm and the plan for the rest are in design/sc27-plan.md.
A non-SMP line, four CSV read-timing prototypes, and a stale copy of htram lived here until September 2026; see design/graphlib.md §1 for what went and why. Recover any of it from history if it is ever needed.
charmc's location is machine-specific, so put it in an untracked config.mk:
echo 'CHARMC_SMP = /path/to/charm_reconverse/bin/charmc' > config.mk
echo 'HTRAM_DIR = /path/to/htram' >> config.mk
make sssp_smp
Anything in config.mk can be overridden on make's command line. make tools
builds graph_digest and graph_convert, which need no Charm++ at all.
./sssp_smp <vertices> <path|edge count> <seed> <source> <mode> <p_tram> <p_pq> \
[--verify] [--result-digest] [--timeout <seconds>] [--bufsize <items>] \
[--bucket-width <units>] [--round-delay <ms>] \
[--flush-interval <rounds>] [--partition-jitter <percent>] \
[--flush-policy fixed|stale|adaptive] [--combine off|hold] \
[--bucket-policy fixed|adaptive] [--bucket-target <buckets>] \
[--idle-flush off|on|starved] [--batch-fold off|on] \
[--diag <prefix>] +ppn <threads>
| mode | input | argument 2 |
|---|---|---|
| 1 | uniform random | edge count |
| 2 | 2-D mesh | ignored; the edge count follows from the side length |
| 3 | RMAT / Kronecker | edge count. Needs a power-of-two vertex count |
| 4 | GAPBS .sg / .wsg |
path. The vertex count is read from the file |
| 0 | comma-separated edge list | path. Legacy, read serially on PE 0 |
Modes 1, 2 and 3 generate the graph in memory, identically at any PE count and on
any machine, so nothing has to be staged. --verify solves the same graph with
serial Dijkstra in-process and compares an order-independent digest; it covers
every mode but 0.
--result-digest emits the parallel distance digest after the timed solve,
without running serial Dijkstra. The comparison harness checks it against an
independent reference for every measured query. A timed-out run exits nonzero
even if its partial result happens to match.
Weights are integers in [1, 1000], a hash of the ordered endpoint pair and the
seed, so they do not depend on the order edges are read or generated in. An
unweighted .sg gets weights the same way.
graph_convert writes GAPBS .wsg files from the generators, and migrates the
legacy CSV files:
./graph_convert gen 3 16384 262144 1 rmat14.wsg
./graph_convert csv graphs/mid_graph.csv 0 1 mid_graph.wsg
./graph_convert stat rmat14.wsg
./graph_convert source 3 16384 262144 1 # a source vertex worth using
source prints the lowest-numbered vertex of at least mean out-degree, and the
graph's degree summary alongside. Many RMAT vertices have no out-edges; they
now terminate correctly with a one-vertex answer. Comparison sources follow a
separate, deterministic sampling rule described in benchmarks/README.md.
The files it writes are real GAPBS files, so GAPBS's own kernels can be run on the
identical input. Use GAPBS's converter for SNAP, DIMACS and MatrixMarket text.
scripts/verify.sh # 18 configurations, one node
scripts/check_generator_portability.sh # graphs identical across toolchains
sbatch scripts/verify_2node.sh # message-envelope invariants, two nodes (submit from the repo root)
scripts/verify.sh --update-golden re-records scripts/golden_digests.txt after a
deliberate change to the graphs. The first two run in CI on every push.
SSSP_EXTRA_ARGS="--flush-policy fixed" scripts/verify.sh runs the gate with a
solver option set; every step 7 mechanism is gated with its flag on and off.
The step 7.5 comparison report covers nine matched weighted inputs, 1–16 CPU nodes, RIKEN/GAPBS/Gluon baselines, process layout, and timed-output sensitivity. It records progress failures under both current and fixed policies; resolving them is the next correctness gate. See benchmarks/README.md for reproduction and design/step75-data for compact measurements and provenance.
scripts/diagnose.sh <h1|h2|h3|h4|all> [outdir] # the step 6 experiment matrix
scripts/diag_report.py <outdir> # turn it into tables
sbatch scripts/diagnose_delta.sbatch all 20 # how the reported runs were taken
The four knobs above exist for these A/Bs and are inert at their defaults.
--diag writes the controller's own round-by-round series; make sssp_smp_diag
adds counters on the relaxation path — bucket occupancy, per-vertex arrivals,
reject rates by destination degree, per-PE idleness — which is why they are a
separate binary. Every wall-clock number comes from sssp_smp and every
structural number from sssp_smp_diag, deliberately.
What this was for, and what it found, is in design/scale-free-diagnosis.md.
Step 7 builds the mechanisms step 6 pointed at, one at a time, each as an A/B against the configuration it replaces:
scripts/stage_scratch.sh <dir> # a private copy per batch job
sbatch [-N 2] scripts/ab_delta.sbatch scripts/ab/<variants>.txt 20
scripts/diag_report.py <outdir> ab # medians and speedups
| mechanism | flag | default | note |
|---|---|---|---|
| adaptive flush cadence | --flush-policy |
adaptive |
design/step7-flush-cadence.md |
| source-side combining hold | --combine |
off (a loss) |
design/step7-combining.md |
| batch-local fold at delivery | --batch-fold |
off (a loss) |
design/step7-combining.md |
| adaptive bucketing | --bucket-policy, --bucket-target |
adaptive, 8 |
design/step7-bucketing.md |
| idle flush | --idle-flush |
starved |
design/step7-idle-flush.md |
Ratio columns are named for their direction and always read above 1.00x as more
of the named thing: speedup is baseline/variant, so above 1 is faster;
slowdown is variant/baseline, used where the knob only ever adds time. Job
outputs under design/step7-data/ that predate 2026-09-13 print the reciprocal
under a column headed "vs base", so a number quoted from one of those files is
the inverse of what the same column prints now.