# zhaoziyu0008/bgj-sieve-gpu architecture

> Architecture diagram of the GitHub repository zhaoziyu0008/bgj-sieve-gpu, generated by GitDiagram from its file tree, README and a sample of source files (last updated 2026-05-19). It is an AI-made overview: check details against the source.

- Interactive diagram: https://gitdiagram.com/zhaoziyu0008/bgj-sieve-gpu
- Repository: https://github.com/zhaoziyu0008/bgj-sieve-gpu

## Overview

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: [`src/bgj_hd.cpp`](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/bgj_hd.cpp) (BGJ control), [`src/bgj_hd_device.cu`](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/bgj_hd_device.cu) (BGJ device), [`src/lattice.cpp`](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/lattice.cpp) (Lattice), [`src/pool_hd_device.cu`](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/pool_hd_device.cu) (Pool device)

## Diagram (Mermaid)

```mermaid
flowchart TD

subgraph group_grp_host["Host orchestration"]
  node_n_app["hd_sieve<br/>CLI dispatcher<br/>[bin_hd_sieve.cu]"]
  node_n_bgj["BGJ control<br/>host orchestrator<br/>[bgj_hd.cpp]"]
  node_n_lll["LLL reduce<br/>preprocess<br/>[lll.cpp]"]
  node_n_dual["Dual setup<br/>transform<br/>[dual.cpp]"]
  node_n_sampler["Sampler<br/>candidate gen<br/>[sampler.cpp]"]
  node_n_dh["DH device<br/>workflow kernel<br/>[dh_device.cu]"]
end

subgraph group_grp_gpu["GPU compute"]
  node_n_bgj_dev["BGJ device<br/>device bridge<br/>[bgj_hd_device.cu]"]
  node_n_red["Reduction<br/>kernel<br/>[kernel_red.cu]"]
  node_n_buc["Bucketing<br/>kernel<br/>[kernel_buc.cu]"]
  node_n_ctr["Control<br/>kernel<br/>[kernel_ctr.cu]"]
  node_n_flt["Filter<br/>kernel<br/>[kernel_flt.cu]"]
  node_n_pack["Packing<br/>kernel<br/>[kernel_packf.cu]"]
  node_n_pop["Population<br/>kernel<br/>[kernel_pop.cu]"]
  node_n_v2h["Vector→hash<br/>kernel<br/>[kernel_v2h.cu]"]
  node_n_dhb["DH bucket<br/>kernel<br/>[kernel_dhb.cu]"]
  node_n_dhr["DH reduce<br/>kernel<br/>[kernel_dhr.cu]"]
  node_n_mred["Merge red<br/>kernel<br/>[kernel_mred.cu]"]
end

subgraph group_grp_state["Persistent state"]
  node_n_pool[("Pool manager<br/>disk-backed state<br/>[pool_hd.cpp]")]
  node_n_pool_dev["Pool device<br/>state kernel<br/>[pool_hd_device.cu]"]
  node_n_uid["UID table<br/>dedup index<br/>[UidTable.cpp]"]
end

subgraph group_grp_core["Core math types"]
  node_n_lattice["Lattice<br/>basis model<br/>[lattice.cpp]"]
  node_n_vec["Vector<br/>numeric type<br/>[vec.cpp]"]
  node_n_quad["Quadratic form<br/>numeric type<br/>[quad.cpp]"]
end

node_n_app -->|"dispatches"| node_n_bgj
node_n_bgj -->|"preprocesses"| node_n_lll
node_n_bgj -->|"prepares"| node_n_dual
node_n_bgj -->|"samples"| node_n_sampler
node_n_bgj -->|"loads state"| node_n_pool
node_n_bgj -->|"runs"| node_n_dh
node_n_bgj -->|"launches"| node_n_bgj_dev
node_n_sampler -->|"feeds"| node_n_pool
node_n_pool -->|"tracks"| node_n_uid
node_n_pool -->|"executes on"| node_n_pool_dev
node_n_pool_dev -->|"buckets"| node_n_buc
node_n_pool_dev -->|"filters"| node_n_flt
node_n_pool_dev -->|"packs"| node_n_pack
node_n_lattice -->|"uses"| node_n_vec
node_n_lattice -->|"evaluates with"| node_n_quad
node_n_bgj -->|"consumes"| node_n_lattice
node_n_bgj_dev -->|"launches"| node_n_red
node_n_bgj_dev -->|"launches"| node_n_buc
node_n_bgj_dev -->|"launches"| node_n_ctr
node_n_bgj_dev -->|"launches"| node_n_flt
node_n_bgj_dev -->|"launches"| node_n_pack
node_n_bgj_dev -->|"launches"| node_n_pop
node_n_bgj_dev -->|"launches"| node_n_v2h
node_n_dh -->|"uses"| node_n_dhb
node_n_dh -->|"uses"| node_n_dhr
node_n_red -->|"feeds"| node_n_mred
node_n_v2h -->|"indexes"| node_n_uid
node_n_lll -->|"rewrites"| node_n_lattice
node_n_dual -->|"transforms"| node_n_lattice

click node_n_app "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/app/bin_hd_sieve.cu"
click node_n_bgj "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/bgj_hd.cpp"
click node_n_lll "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/lll.cpp"
click node_n_dual "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/dual.cpp"
click node_n_sampler "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/sampler.cpp"
click node_n_pool "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/pool_hd.cpp"
click node_n_pool_dev "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/pool_hd_device.cu"
click node_n_uid "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/UidTable.cpp"
click node_n_lattice "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/lattice.cpp"
click node_n_vec "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/vec.cpp"
click node_n_quad "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/quad.cpp"
click node_n_bgj_dev "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/bgj_hd_device.cu"
click node_n_red "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_red.cu"
click node_n_buc "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_buc.cu"
click node_n_ctr "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_ctr.cu"
click node_n_flt "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_flt.cu"
click node_n_pack "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_packf.cu"
click node_n_pop "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_pop.cu"
click node_n_v2h "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_v2h.cu"
click node_n_dhb "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_dhb.cu"
click node_n_dhr "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_dhr.cu"
click node_n_mred "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_mred.cu"
click node_n_dh "https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/dh_device.cu"

classDef toneNeutral fill:#f8fafc,stroke:#334155,stroke-width:1.5px,color:#0f172a
classDef toneBlue fill:#dbeafe,stroke:#2563eb,stroke-width:1.5px,color:#172554
classDef toneAmber fill:#fef3c7,stroke:#d97706,stroke-width:1.5px,color:#78350f
classDef toneMint fill:#dcfce7,stroke:#16a34a,stroke-width:1.5px,color:#14532d
classDef toneRose fill:#ffe4e6,stroke:#e11d48,stroke-width:1.5px,color:#881337
classDef toneIndigo fill:#e0e7ff,stroke:#4f46e5,stroke-width:1.5px,color:#312e81
classDef toneTeal fill:#ccfbf1,stroke:#0f766e,stroke-width:1.5px,color:#134e4a
class node_n_app,node_n_bgj,node_n_lll,node_n_dual,node_n_sampler,node_n_dh toneBlue
class node_n_bgj_dev,node_n_red,node_n_buc,node_n_ctr,node_n_flt,node_n_pack,node_n_pop,node_n_v2h,node_n_dhb,node_n_dhr,node_n_mred toneAmber
class node_n_pool,node_n_pool_dev,node_n_uid toneMint
class node_n_lattice,node_n_vec,node_n_quad toneRose
```

## Components

### Host orchestration

Command dispatch, preprocessing, and run control on the CPU side.

- [hd_sieve](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/app/bin_hd_sieve.cu): CLI dispatcher · Main executable that selects sieve, pump, dh, and bkz workflows and reloads saved state when available. · `app/bin_hd_sieve.cu`
- [BGJ control](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/bgj_hd.cpp): host orchestrator · Top-level host logic for parameter setup, workflow steering, and end-to-end execution. · `src/bgj_hd.cpp`
- [LLL reduce](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/lll.cpp): preprocess · Basis reduction stage used before heavier sieving or BKZ-style progression. · `src/lll.cpp`
- [Dual setup](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/dual.cpp): transform · Dual-lattice and basis transformation support for preprocessing and sieving preparation. · `src/dual.cpp`
- [Sampler](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/sampler.cpp): candidate gen · Produces randomized candidate vectors that feed the sieve pipeline. · `src/sampler.cpp`
- [DH device](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/dh_device.cu): workflow kernel · 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](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/bgj_hd_device.cu): device bridge · Device-side orchestration and shared CUDA-side glue for the BGJ workflow. · `src/bgj_hd_device.cu`
- [Reduction](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_red.cu): kernel · Inner-loop kernel for vector reduction in the sieve pipeline. · `src/kernel_red.cu`
- [Bucketing](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_buc.cu): kernel · Groups candidates into buckets for staged GPU processing. · `src/kernel_buc.cu`
- [Control](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_ctr.cu): kernel · Coordination kernel for sieve bookkeeping and pipeline progression. · `src/kernel_ctr.cu`
- [Filter](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_flt.cu): kernel · Filters candidate vectors during sieving passes. · `src/kernel_flt.cu`
- [Packing](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_packf.cu): kernel · Packs filtered candidates for compact transfer or storage. · `src/kernel_packf.cu`
- [Population](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_pop.cu): kernel · Tracks or updates population counts and related sieve statistics. · `src/kernel_pop.cu`
- [Vector→hash](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_v2h.cu): kernel · Maps vectors into hashed or indexed forms for lookup and deduplication. · `src/kernel_v2h.cu`
- [DH bucket](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_dhb.cu): kernel · Device-side bucket processing for the dh workflow. · `src/kernel_dhb.cu`
- [DH reduce](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_dhr.cu): kernel · Device-side reduction stage for the dh workflow. · `src/kernel_dhr.cu`
- [Merge red](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/kernel_mred.cu): kernel · 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](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/pool_hd.cpp): disk-backed state · Host-side management of persistent sieve pools, buckets, and recovery state. · `src/pool_hd.cpp`
- [Pool device](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/pool_hd_device.cu): state kernel · Device-side support for manipulating pooled and bucketed working data. · `src/pool_hd_device.cu`
- [UID table](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/UidTable.cpp): dedup index · 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](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/lattice.cpp): basis model · Core lattice and basis data structures shared across preprocessing and sieving. · `src/lattice.cpp`
- [Vector](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/vec.cpp): numeric type · Vector representation used throughout candidate handling and reduction. · `src/vec.cpp`
- [Quadratic form](https://github.com/zhaoziyu0008/bgj-sieve-gpu/blob/main/src/quad.cpp): numeric type · Quadratic-form representation supporting lattice evaluation and transformations. · `src/quad.cpp`

## Connections

- 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.
