Overview

This library contains code to perform a lattice enumeration (i.e. searching lattice vectors within some radius for a shortest, nonzero vector) on the GPU, using Cuda. The interface is designed to be usable as external enumerator in fplll.

Building

On Linux, the project relies on the Autotools build system. Most of the platform independent generated Autotools-files are committed to the repository, mainly to simplify the CI implementation. However, it also makes building very easy, and you will not require an installation of Autotools. For details, see the next section.

On Windows, you can use the provided Visual Studio solution. However, note that you will not be able to use the generated binaries with fplll, as fplll only supports Linux binaries.

Building using Autotools

The generated Autotools files are already part of the repository, so you should be able to execute ./configure & make to build the library (libcudaenum.so) and an executable (cudaenum_test) that will run basic test. For building, you will need the Cuda compiler (i.e. nvcc), a C++17-capable compiler and Python 3 (the latter is used for a build script that makes nvcc work with libtools). CUDA 13 requires C++17 or later.

When calling configure, you can pass further arguments to customize the build:

• you can specify the location of nvcc by passing NVCC=path/to/executable.
• you can pass additional flags to nvcc when compiling Cuda by passing CUDA_CXXFLAGS=....
• you can pass additional flags to the standard linker when linking to the Cuda library by passing CUDA_LDFLAGS=.... You might do so to specify the directory where the Cuda runtime is, e.g. by CUDA_LDFLAGS="-L/usr/local/cuda/lib64".
• Most other Autotools variables are also available, e.g. you can customize the C++ compiler by CXX=path/to/executable or pass flags to it by CXXFLAGS=...

For example, when making a production build, one should disable assertions in device code. The command would then be ./configure CUDA_CXXFLAGS="-D NDEBUG" followed by make.

On this host, the CUDA runtime is installed outside the default linker search path. Build the CUDA library with:

./configure NVCC=/usr/local/cuda/bin/nvcc CUDA_LDFLAGS="-L/usr/local/cuda/lib64"
make

For an A100-native production binary, use the provided configure profile. It embeds native sm_80 code (avoiding first-use JIT) plus a compute_80 fallback:

./configure --enable-a100 NVCC=/usr/local/cuda/bin/nvcc CUDA_LDFLAGS="-L/usr/local/cuda/lib64"
make

Add --enable-cuda-profile when collecting Nsight Compute or Nsight Systems profiles.

If you are a developer, you might want to regenerate the Autotools files, which can be achieved by the standard autoreconf. Note that Autotools is required to do so.

Linking with fplll

After the library was build using make (or make libcudaenum.la), it is possible to build fplll such that it uses its function for all enumerations. For that, configure the fplll build with ./configure --with-extenum-dir=<absolute/path/to/library/folder> --with-extenum-lib=cudaenum --with-extenum-func=fplll_cuda_enum (if you have not build fplll before, a ./autogen.sh might be necessary). Then build fplll using make. Note that by default, libcudaenum will be built into .libs, so the first argument when configuring fplll will probably look like --with-extenum-dir=/.../fplll-cuda-enumeration/.libs.

When using the in-tree builds on this host, also pass LDFLAGS="-L/usr/local/cuda/lib64 -Wl,-rpath,/.../fplll-cuda-enumeration/.libs -Wl,-rpath,/usr/local/cuda/lib64" to fplll's configure command. This lets its executable locate both libcudaenum and libcudart without setting LD_LIBRARY_PATH.

Runtime tuning

The existing external-enumerator ABI is unchanged. Runtime policy can be set through cuenum::set_runtime_config() or through environment variables:

• CUDAENUM_DEVICES=0,1 enables both GPUs for one enumeration. The default uses only the current CUDA device.
• CUDAENUM_PROFILE=auto|generic|a100 selects launch sizing. auto recognizes A100 devices.
• CUDAENUM_MEMORY_FRACTION=0.75 limits the fraction of available device memory used for tree buffers (valid range: 0.25–0.90).
• CUDAENUM_QUEUE_CAPACITY=4096 controls solution-queue backpressure (valid range: 1–4096).
• CUDAENUM_THREADS=<count> overrides automatic launch sizing; it is rounded up to the 128-thread block size.
• CUDAENUM_MULTI_GPU_MIN_DIM=65 sets the crossover below which an explicitly selected second GPU is not started. The default reflects the measured crossover on this two-A100 host: 62D exact enumeration is faster on one GPU, while traversal-heavy 65D and larger searches benefit from both.
• CUDAENUM_MULTI_GPU_BATCH_SIZE=<points> overrides the dynamically scheduled frontier batch size. For exact searches, automatic mode targets 32 batches per active GPU and shrinks batches as the queue drains, except for measured 65D--69D policies whose frontiers perform better at fixed caps. Measured two-A100 caps are 8,192 roots for three-dimensional 65D; 8,192 roots for the automatic four-dimensional 66D traversal; 16,384 roots for 67D; 40,960 roots for 68D; 131,072 roots for 69D; 8,192 roots in 70D; 16,384 roots in 71D; 65,536 roots in 72D; 14,336 roots in 73D; 8,192 roots for the automatic four-dimensional 74D traversal (20,480 for explicitly selected three-dimensional traversal); 32,768 roots for the automatic four-dimensional 75D traversal (122,880 for explicitly selected three-dimensional traversal); 65,536 roots for the automatic four-dimensional 76D traversal (10,240 for explicitly selected three-dimensional traversal); and 262,144 roots for four-dimensional 77D. Other dimensions above 77 retain a conservative 32,768 cap and lower dimensions use 1,024. Pruned searches use fixed ascending batches of 256 points at 70D and above or 512 points below 70D.
• CUDAENUM_DIMENSIONS_PER_LEVEL, CUDAENUM_MAX_SUBTREE_PATHS, CUDAENUM_MIN_ACTIVE_PARENTS, and CUDAENUM_INITIAL_NODES_PER_GROUP expose the algorithm parameters used by offline tuning.
• CUDAENUM_START_DIMENSIONS=6..16 controls safe-boundary subtree pre-splitting. The default adds one complete compact-tree level for dimensions 60 and above or for strongly pruned searches of at least 40 dimensions, producing finer independently schedulable roots without exploding unpruned 50D frontiers.
• CUDAENUM_COUNT_NODES=1 enables exact recursive node statistics for profiling. Exact four-dimensional A100 searches omit this accounting by default because it costs several percent; solution correctness and fplll control flow do not depend on the statistic. Generic, explicitly shaped non-four-dimensional, and pruned calls continue to count nodes.
• CUDAENUM_VERBOSE=1 emits CPU-frontier timing plus aggregate per-GPU batch, node, active-time, and longest-batch telemetry on standard error. Single-GPU runs also emit detailed kernel progress.

The A100 preset normally targets three 128-thread blocks per SM to hide instruction latency and uses 64-path recursive bursts for exact searches. Official 70D exact searches select a separately compiled six-block, 64-thread kernel: it preserves 12 active warps while doubling independent block work queues, improving the 70D median without imposing the measured 75D regression of that geometry. The grid is reduced when start-point count or the memory budget is smaller. Exact 60D--64D, 66D--71D, and 74D--77D searches automatically use four-dimensional compact-tree levels; profiling showed that traversal is latency/divergence bound, and this shape improves node throughput over the historical three-dimensional default. Official 61D uses its shallower compatible 9D frontier because the usual additional compact level made its 13D frontier slower. Official 65D retains three-dimensional levels because both compatible 4D frontiers were slower. Exact 78D A100 searches use a two-dimensional root followed by twenty-two three-dimensional levels, preserving the requested 10D CPU frontier while reducing device memory to about 21.2 GiB per GPU. Explicit shape overrides, generic GPUs, and pruned BKZ calls retain their requested or existing policy. The 77D shape creates a 166-million-point, roughly 39 GiB host frontier with a 10-dimensional requested boundary; use an explicit three-dimensional override when lower host memory is more important than its measured speedup. Device and pinned allocations are retained between enumeration calls and grown on demand. Large CPU frontiers use up to 32 host workers for stable radix sorting and final coefficient gathering; small frontiers remain serial. A lightweight high-occupancy kernel precomputes each batch's root center sums and prefix distances before the memory-heavy tree kernel, preserving FP64 FMA order while reducing traversal register pressure. The triangular Gram-Schmidt mu tile is packed in shared memory instead of storing its unused lower half; hot per-warp open-node counts are cached there as well when the instantiated kernel fits the static shared-memory limit. Oversized generic variants retain the global-memory representation. Enumeration distance and center recurrences use explicit FP64 fused multiply-add operations. Strict all-ones exact enumeration caches its launch-time radius per block, removing volatile global bound loads from the recursive hot path; later tighter incumbents may leave a batch searching a few obsolete nodes but cannot affect correctness. Pruned BKZ calls retain live per-level bounds. With multiple GPUs, workers pull frontier ranges from a shared queue instead of receiving a fixed partition. Automatic scheduling uses progressively smaller tail batches. The four-dimensional 75D policy keeps 32,768-root ranges throughout because its low-norm prefix is exceptionally concentrated; the explicitly selected three-dimensional policy retains a 122,880-root first range followed by wider setup-amortizing ranges. Exact, effectively unpruned searches alternate between the low- and high-norm ends of the frontier to avoid concentrating similar-cost roots on the last worker; pruned BKZ searches retain ascending norm order so early solutions tighten later pruning bounds. Verbose mode reports every incumbent-bound improvement with its scheduler-relative timestamp.

When node accounting is enabled, recursive bursts accumulate visited nodes in one scalar counter. The returned aggregate remains exact while the optional per-coordinate histogram is coarsened to compact-tree boundaries. Avoiding a counter array in recursive state materially reduces latency. Exact four-dimensional A100 searches use a separately compiled no-accounting kernel by default, eliminating even the scalar update without adding a runtime branch to recursion; their verbose worker node totals are consequently zero unless CUDAENUM_COUNT_NODES=1 is set. This fast kernel is compiled with the same three-block-per-SM launch bound used at runtime, allowing ptxas to trade otherwise unused register capacity for fewer local-stack accesses; counted and generic kernels retain their four-block compiler bound. The exact kernel also represents the identical per-level pruning bounds as one scalar loaded when a recursive burst is reconstructed, rather than issuing a volatile shared-memory load for every visited node. Counted and genuinely pruned kernels retain live per-level bounds.

Exact 74D A100 searches also use four-dimensional compact levels with an 8,192-root scheduler cap; this reduced the official seed-8100 median from 40.073 to 36.17 seconds.

Exact 76D A100 searches use a 12D frontier followed by sixteen four-dimensional compact levels and a 65,536-root cap; this reduced the official seed-4782 median from 56.23 to 43.03 seconds.

Recursive enumeration caches each level's rounded center while walking its sibling coefficients. The center is invariant for that sibling sequence, so this removes repeated FP64 rounding and comparison instructions from the hot loop at the cost of 16 bytes of generated stack in the four-dimensional exact kernel. It also caches the center's initial enumeration direction and derives the next displacement directly from the current coefficient. This removes the remaining invariant center comparison while keeping the update stateless across checkpoint and resume boundaries. The positive-only symmetry case is cached as a boolean at level initialization as well, avoiding a repeated FP64 zero comparison; the flag fits in existing state-alignment padding.

Official SVP Challenge performance runs use the seed of the shortest listed Hall-of-Fame record for each dimension, not an arbitrary generator seed. The current 60D--80D snapshot and source URL are recorded in benchmarks/svp-challenge-records.csv. Refresh and validate the complete matrix directly from the official table before benchmarking:

benchmarks/refresh_svp_challenge_records.py \
  --output benchmarks/svp-challenge-records.csv

Use the row matching the tested dimension as the generator seed and its Euclidean norm as the correctness target. A different range can be selected with --dimensions FIRST:LAST.

BKZ benchmark

benchmarks/run_bkz.sh generates deterministic 350-bit knapsack lattices for seeds 0–3 and runs one BKZ tour at block sizes 40, 50, 60, 70, and 80. It writes CSV timing data and accepts paths and workload overrides through FPLLL_BIN, FPLLL_LIBRARY_DIR, LATTICEGEN_BIN, FPLLL_STRATEGY, CUDAENUM_BENCH_BLOCKS, CUDAENUM_BENCH_SEEDS, and CUDAENUM_BENCH_RUNS.

On this two-A100 host, forcing a 10-dimensional safe-boundary frontier reduces the four deterministic 70D cases from 25.44 to 14.93 seconds on one GPU and from 22.78 to 13.17 seconds on two GPUs. The safer pruning-aware automatic policy completes seed 0 in 15.01 seconds while avoiding the explosive frontier observed for an unpruned 50D search. Per-seed results are recorded in benchmarks/a100-70d-results.csv.

Code organization

Most of the code of this project is contained in header files, as the implementation makes (extremely) heavy use of templates. In particular on the device, this this is the only efficient way to write abstractions. The following files contain significant parts of the implementation

• enum.cuh contains the actual algorithm, and the main entry point is the function enumerate()
• recenum.cuh contains a recursive enumeration (very similar to fplll) that is used as a subroutine
• cuda_wrapper.h resp. cuda_wrapper.cu contain the implementation of the interface to fplll
• streaming.cuh contains the communication between host and device during the running enumeration (notably, found solution points are passed to the host)

The other files are either test files or wrap primitives in a way that allows the CPU-only mode, i.e. testing most of the code on a system that has no GPU.

CUDA Enumeration Idea

In this part, we describe how the enumeration algorithm is parallelized on Cuda Blocks and Threads. For detailed information, see the report.

CUDA Blocks vs Warps vs Threads

In Cuda, functionality is distributed between the "host" (CPU) and the "device" (GPU). Usually, the host prepares the input, and then starts many threads executing the same function on the device. These threads are grouped into a hierarchy

• 32 threads are grouped into a warp. All threads in a warp are executed synchronously, so they always execute the same instruction. Branching within a warp is bad for performance.
• Up to 32 warps form a block. Within a block, synchronization is possible via barriers.
• All blocks form the grid that is executed on the device. Classically, grid synchronization is only possible by calling and joining multiple functions on the host. In addition to avoiding branches on warp level, memory accesses should also be aligned on warp level (i.e. all threads in a warp should address subsequent words in memory).

Enumeration tree

In principle, given a triangular basis of a rank n lattice L (usually the Gram-Schmidt coefficients), enumeration is a tree search:

The nodes on level i in the tree are given by all points with norm less than some given limit, in the projection of L into the subspace U_n-i, defined as the space perpendicular to the first n-i basis vectors. Therefore, the root of the tree is only the origin. The children of a node at level i are now given by all points in the projection of L into U_n-i-1 whose projection into U_n-i is the parent point.

The search

If each Cuda thread performed a simple depth-first search independent of each other, this would lead very inefficient branching and memory accesses. Instead, a hybrid between depth-first search of the tree and breadth-first search is chosen:

Each thread warp works independently. However, within a warp, we use a breadth-first idea, so there is always a list of nodes whose subtrees have yet to be searched ("list of open nodes"). In each step, each thread gets one of these buffer nodes assigned, and calculates its children (usually in multiple batches to prevent huge children counts), which are again added to the list. In contrast to the standard breadth-first search however, open nodes at the downmost tree level are processed first, so that we find first solutions as fast as possible, and to prevent huge list sizes. For efficiency reasons, all threads always work on nodes on the same level, and the open nodes are stored by level.

Summarized, this open node list is not used to make sure that we search nodes nearer to the root first, but to be able to assign each thread a node from the same level (leading to efficient memory access patterns), as we can choose from many open nodes.

Compacted Enumeration tree

To reduce the great overhead introduced by managing and storing enumeration tree nodes in memory, the program instead works with a compacted version of the tree. A constant count of tree levels are only one level in the compacted tree. Therefore, a correspondingly high subtree with a single root in the old tree is now a node in the compacted tree, with accordingly many children.

Formally, for a constant count of tree levels c, the tree nodes at level i are now points in the projection of L into U_n-ci with bounded norm. The root is still only the origin, but the children nodes are now lifted not only one dimension, but c dimensions. In particular, an enumeration algorithm is again required to compute the children. For this, an adaption of the recursive base enumeration is used.

Apart from these changes, the search works exactly as in the simple enumeration tree, except now the internal state of the recursive algorithm must be stored with the nodes, so that we can resume the children enumeration later.