How zhaoziyu0008/bgj-sieve-gpu works
1. What this repository is
- BGJ-Sieve-GPU is a CUDA/C++ implementation of the Becker–Gama–Joux lattice sieving family.
- Its architecture is centered on a host orchestrator, GPU kernels, and a disk-backed working set for large sieving jobs and crash recovery.
2. Main executable and task dispatcher
- The primary binary is app/bin_hd_sieve.cu, which builds the hd_sieve executable.
- That executable is a command-line dispatcher with several workflows: sieve, pump, dh, and bkz.
- The README shows that the same binary also handles recovery by detecting existing on-disk state and reloading it when appropriate.
3. Core host-side control layer
- The main host-side logic lives in src/bgj_hd.cpp, src/pool_hd.cpp, src/dh_device.cu, src/dual.cpp, src/lll.cpp, and supporting utilities.
- This layer parses parameters, sets up the lattice instance, coordinates preprocessing, and drives the sieving phases.
- It is also where task-specific orchestration happens, such as BKZ-style stepping before a heavier sieve.
4. Lattice and basis representation
- The repository defines its own lattice/vector/quadratic form data structures in include/lattice.h, include/vec.h, include/quad.h, and their corresponding .cpp files.
- These types are the shared in-memory representation passed through preprocessing, sieving, and solution extraction.
- The code also includes include/config.h for hardware- and workload-specific tuning.
5. Preprocessing pipeline before sieving
- src/lll.cpp and src/dual.cpp indicate a preprocessing stage for basis reduction and dual-lattice transformations.
- The README’s workflow confirms that heavy sieving is typically preceded by lighter reduction, often BKZ-like, before the sieve proper.
- This creates a clear boundary: input lattice basis in, reduced/structured basis out, then the sieve consumes it.
6. GPU compute layer
- CUDA device code is concentrated in src/*.cu and matching device headers under include/*_device.h.
- The device side is split into specialized kernels such as kernel_red.cu, kernel_buc.cu, kernel_ctr.cu, kernel_flt.cu, kernel_packf.cu, kernel_pop.cu, kernel_v2h.cu, kernel_dhb.cu, kernel_dhr.cu, and kernel_mred.cu.
- From the filenames, this layer handles the high-throughput inner loops: reduction, filtering, packing, bucketing, hashing, and related sieving primitives.
7. Sieving state and external storage
- A major subsystem is the disk-backed pool in src/pool_hd.cpp, src/pool_hd_device.cu, and include/pool_hd.h.
- The README documents persistent directories such as .pool/, .bucket/, .sol/, and .uid/, which store intermediate sieve state externally rather than in RAM.
- This storage layer is part of the algorithmic design, not just an implementation detail: it enables low-memory operation and restart/recovery after interruption.
8. UID and deduplication bookkeeping
- include/UidTable.h and src/UidTable.cpp implement unique-ID tracking for sieve elements.
- Combined with the uid/ directory on disk, this subsystem appears to support duplicate detection, stable indexing, and recovery of partially processed work.
- This is an important boundary between raw candidate vectors and the persistent bookkeeping needed for large-scale sieving.
9. Sampling, randomness, and candidate generation
- Candidate generation is handled by src/sampler.cpp, include/sampler.h, and include/random_device.h.
- These pieces feed the sieve with initial vectors and randomized sampling needed by the probabilistic search.
- In the overall flow, sampling is the entry point into the GPU-intensive candidate processing pipeline.
10. Support libraries and infrastructure
- dep/g6k/thread_pool.hpp suggests threaded host-side scheduling, and dep/phmap provides a high-performance hash map implementation.
- The README states dependencies on nvcc, g++, ntl, gmp, and libnuma, so the code spans CUDA, C++, big-integer arithmetic, and NUMA-aware host execution.
- The build is split between src/Makefile and app/Makefile, reflecting a core library plus final executable structure.
11. End-to-end data flow
- Typical flow is: load lattice basis → optionally reduce/preprocess → initialize sieve state → sample candidates → run GPU kernels for filtering/bucketing/reduction → spill and reload intermediate state from disk-backed pools → extract short vectors or progress the BKZ/pump/dh workflow.
- The architecture is therefore best drawn as three main planes: host orchestration, CUDA compute, and persistent external state, with data moving repeatedly between them during long runs.
12. Why the repo is organized this way
- The design is optimized for very large lattice attacks where the bottleneck is not only compute but also memory pressure and crash resilience.
- That is why the repository emphasizes GPU kernels for the hot path, specialized host-side scheduling, and durable intermediate storage as first-class subsystems.
Main entry points: bgj_hd.cpp BGJ control · bgj_hd_device.cu BGJ device · lattice.cpp Lattice · pool_hd_device.cu Pool device
Components 23
Host orchestration
Command dispatch, preprocessing, and run control on the CPU side.
- hd_sieve · Main executable that selects sieve, pump, dh, and bkz workflows and reloads saved state when available.
app/bin_hd_sieve.cu - BGJ control · Top-level host logic for parameter setup, workflow steering, and end-to-end execution.
src/bgj_hd.cpp - LLL reduce · Basis reduction stage used before heavier sieving or BKZ-style progression.
src/lll.cpp - Dual setup · Dual-lattice and basis transformation support for preprocessing and sieving preparation.
src/dual.cpp - Sampler · Produces randomized candidate vectors that feed the sieve pipeline.
src/sampler.cpp - DH device · Host-facing CUDA workflow for dh-style execution and coordination.
src/dh_device.cu
GPU compute
CUDA kernels and device-side execution paths for the sieve.
- BGJ device · Device-side orchestration and shared CUDA-side glue for the BGJ workflow.
src/bgj_hd_device.cu - Reduction · Inner-loop kernel for vector reduction in the sieve pipeline.
src/kernel_red.cu - Bucketing · Groups candidates into buckets for staged GPU processing.
src/kernel_buc.cu - Control · Coordination kernel for sieve bookkeeping and pipeline progression.
src/kernel_ctr.cu - Filter · Filters candidate vectors during sieving passes.
src/kernel_flt.cu - Packing · Packs filtered candidates for compact transfer or storage.
src/kernel_packf.cu - Population · Tracks or updates population counts and related sieve statistics.
src/kernel_pop.cu - Vector→hash · Maps vectors into hashed or indexed forms for lookup and deduplication.
src/kernel_v2h.cu - DH bucket · Device-side bucket processing for the dh workflow.
src/kernel_dhb.cu - DH reduce · Device-side reduction stage for the dh workflow.
src/kernel_dhr.cu - Merge red · Merged reduction kernel used by the high-throughput sieve path.
src/kernel_mred.cu
Persistent state
Disk-backed pools and bookkeeping used for long runs and recovery.
- Pool manager · Host-side management of persistent sieve pools, buckets, and recovery state.
src/pool_hd.cpp - Pool device · Device-side support for manipulating pooled and bucketed working data.
src/pool_hd_device.cu - UID table · Unique-ID tracking and duplicate detection for sieve elements and recovery bookkeeping.
src/UidTable.cpp
Core math types
Shared lattice, vector, and quadratic-form representations.
- Lattice · Core lattice and basis data structures shared across preprocessing and sieving.
src/lattice.cpp - Vector · Vector representation used throughout candidate handling and reduction.
src/vec.cpp - Quadratic form · Quadratic-form representation supporting lattice evaluation and transformations.
src/quad.cpp
Connections 29
- hd_sieve → BGJ control: dispatches · Main binary selects and drives the host orchestrator.
- BGJ control → LLL reduce: preprocesses · Host control may run basis reduction before sieving.
- BGJ control → Dual setup: prepares · Host control can transform the lattice into a dual representation.
- BGJ control → Sampler: samples · Host control requests candidate generation.
- BGJ control → Pool manager: loads state · Host control initializes or restores persistent sieve state.
- BGJ control → DH device: runs · Host control can enter dh-style workflow execution.
- BGJ control → BGJ device: launches · Host orchestrator hands work to CUDA-side coordination.
- Sampler → Pool manager: feeds · Generated candidates enter the persistent sieve pool.
- Pool manager → UID table: tracks · Persistent pool uses UID bookkeeping to avoid duplicates and support recovery.
- Pool manager → Pool device: executes on · Disk-backed pool operations have a device-side implementation.
- Pool device → Bucketing: buckets · Bucketed working data flows into GPU bucket processing.
- Pool device → Filter: filters · Device-side state supports filtering of candidates.
- Pool device → Packing: packs · Packed candidate representations are prepared for transfer or storage.
- Lattice → Vector: uses · Lattice structures are expressed through vector types.
- Lattice → Quadratic form: evaluates with · Quadratic forms support lattice evaluation and scoring.
- BGJ control → Lattice: consumes · Host orchestration operates on the lattice basis model.
- BGJ device → Reduction: launches · CUDA orchestration invokes reduction kernels.
- BGJ device → Bucketing: launches · CUDA orchestration invokes bucketing kernels.
- BGJ device → Control: launches · CUDA orchestration invokes control kernels.
- BGJ device → Filter: launches · CUDA orchestration invokes filtering kernels.
- BGJ device → Packing: launches · CUDA orchestration invokes packing kernels.
- BGJ device → Population: launches · CUDA orchestration invokes population/statistics kernels.
- BGJ device → Vector→hash: launches · CUDA orchestration invokes vector hashing for indexing and deduplication.
- DH device → DH bucket: uses · The dh workflow depends on its bucket-processing kernel.
- DH device → DH reduce: uses · The dh workflow depends on its reduction kernel.
- Reduction → Merge red: feeds · Reduction work can be merged into the merged-reduction path.
- Vector→hash → UID table: indexes · Hashed vector identities support UID tracking and duplicate detection.
- LLL reduce → Lattice: rewrites · Reduction transforms the lattice basis representation.
- Dual setup → Lattice: transforms · Dual preprocessing produces a related lattice representation.