GraphAlgorithms

本项目提供 BFS、Connected Components（CC）、KCore 和 PageRank 的 CUDA/MPI/NCCL 实现。每种算法维护同一份算法源码，并按两个正交维度生成可执行文件：

方法名	GPU 模式	容错
single_gpu_baseline	单 GPU	否
single_gpu_fault_tolerant	单 GPU	是
multi_gpu_baseline	一 rank 一 GPU	否
multi_gpu_fault_tolerant	一 rank 一 GPU	是

queue 等具体实现细节不再出现在方法名中。每个方法又编译为两个 instrumentation profile：

• performance：正式绝对时间、容错开销和扩展性实验；不包含逐轮 trace/NVTX 路径。
• profiling：逐轮活跃顶点、idle lane、critical/redundant 任务、细粒度 CUDA event 与 NVTX/NSys 分析。

完整设计和计时字段见 algorithms/README.md 与 docs/profiling.md。

构建

正式实验统一使用 Release：

cmake -S . -B build \
  -DCMAKE_BUILD_TYPE=Release \
  -DNCCL_ROOT=/path/to/nccl

cmake --build build --target performance -j
cmake --build build --target profiling -j

两条聚合 target 分别生成 16 个程序。命名格式为：

build/bin/<algorithm>/<algorithm>_<method>_<profile>

例如：

build/bin/bfs/bfs_single_gpu_baseline_performance
build/bin/bfs/bfs_multi_gpu_fault_tolerant_profiling

也可以直接构建某一个完整 target：

cmake --build build --target cc_multi_gpu_fault_tolerant_performance -j

命令行参数

所有入口接受统一形式：

<dataset_id> [-s src] [-k k] [-a alpha] [-b beta] [-t threshold] [-n] [-h]

dataset_id=flickr 对应 dataset/flickr.mtx。-s 仅 BFS 使用，-k 仅 KCore 使用，-a/-b/-t 仅容错方法使用；其它组合会接受并明确标为 ignored。-n 关闭算法结束后的 CPU oracle，正式 overhead 实验默认使用它。

手动运行

以下以 cit-HepPh 和物理 GPU 6、7 为例。

单 GPU baseline：

CUDA_VISIBLE_DEVICES=6 \
./build/bin/bfs/bfs_single_gpu_baseline_performance \
  cit-HepPh -s 8180 -n

单 GPU 容错：

CUDA_VISIBLE_DEVICES=6 \
./build/bin/bfs/bfs_single_gpu_fault_tolerant_performance \
  cit-HepPh -s 8180 -a 0.5 -b 0.5 -t 0.3 -n

双 GPU baseline：

CUDA_VISIBLE_DEVICES=6,7 \
mpirun -np 2 --bind-to none \
  ./build/bin/bfs/bfs_multi_gpu_baseline_performance \
  cit-HepPh -s 8180 -n

双 GPU 容错：

CUDA_VISIBLE_DEVICES=6,7 \
mpirun -np 2 --bind-to none \
  ./build/bin/bfs/bfs_multi_gpu_fault_tolerant_performance \
  cit-HepPh -s 8180 -a 0.5 -b 0.5 -t 0.3 -n

多 GPU 代码没有写死为 2 卡。mpirun -np N、CUDA_VISIBLE_DEVICES 中至少 N 张可见卡以及实验配置中的 mpi_ranks=N 必须一致。每个节点内按 node-local rank 映射一张独占 GPU；可见 GPU 少于本地 rank 数时程序会明确终止，不会让多个 rank 静默共享同一张卡。

批量实验

仓库本地 Python 环境可用以下方式准备：

uv venv .venv
uv pip install --python .venv/bin/python matplotlib

完整 performance 流水线：

CUDA_VISIBLE_DEVICES=6,7 \
CUDA_DEVICE_ORDER=PCI_BUS_ID \
PMIX_MCA_pcompress_base_silence_warning=1 \
MPLCONFIGDIR=/tmp/matplotlib-graphalg \
MPI_RANKS=2 \
CONFIG=scripts/experiments/configs/overhead.json \
RUN_TAG=overhead_$(date +%Y%m%d_%H%M%S) \
REPEAT=5 WARMUP=1 TIMEOUT=3600 \
bash scripts/experiments/run_local.sh

profiling 数据使用同一个入口，但需要设置 INSTRUMENTATION_PROFILE=profiling；该流水线在严格收集后停止，不把受统计扰动的时间送入 performance 分析：

CUDA_VISIBLE_DEVICES=6,7 \
MPLCONFIGDIR=/tmp/matplotlib-graphalg \
MPI_RANKS=2 \
INSTRUMENTATION_PROFILE=profiling \
CONFIG=scripts/experiments/configs/overhead.json \
RUN_TAG=profiling_$(date +%Y%m%d_%H%M%S) \
bash scripts/experiments/run_local.sh

实验会保留 immutable raw attempt、stdout/stderr、每-rank timing、逐轮 trace、收集表和派生分析。完整目录契约、恢复运行、Slurm、等价性检查与 NSys 命令见 scripts/experiments/README.md。

多节点 MPI/NCCL

多节点仍采用一 rank 一 GPU。下面只展示启动骨架；host、网络接口与工作目录必须按集群实际环境填写：

mpirun -np 4 \
  -H host-a:2,host-b:2 \
  --bind-to none \
  --wdir /shared/GraphAlgorithms \
  -x CUDA_DEVICE_ORDER=PCI_BUS_ID \
  -x NCCL_DEBUG=INFO \
  ./build/bin/pagerank/pagerank_multi_gpu_fault_tolerant_performance \
  cit-HepPh -a 0.5 -b 0.5 -t 0.3 -n

每台机器必须在相同工作目录看到同一份可执行文件和数据集。MPI 每轮终止规约、NCCL ghost 交换，以及容错版 worker drain 后的 batched post-check 都会分别计时；最终全局检测不再执行“每轮 4–5 次小 Allreduce”。

机器可读输出

每次成功运行至少输出：

BENCHMARK_TIMING ...
BENCHMARK_ITERATIONS iterations=<N>
BENCHMARK_RESULT hash=<digest> elements=<N> element_bytes=<bytes>
BENCHMARK_DETECTION supported=... dmr=... monotonic=... trend_increase=... checked=... skipped=... first_dmr_iter=... first_monotonic_iter=... first_trend_increase_iter=...

三个 first_*_iter 在未发现对应异常时为 -1。多 GPU 还为每个 rank输出 BENCHMARK_RANK_TIMING。总时间同时保留 process_wall_ms、algorithm_e2e_ms 和稳态 algorithm_total_ms 三种边界；不能把父区间与 kernel/通信/checker 子集重复相加。