eval_all_gpu.cuh File Reference

GPU full-domain evaluation (EvalAll) for DPF and HalfTree DPF. More...

#include <cuda_runtime.h>
#include <fss/dpf.cuh>
#include <fss/half_tree_dpf.cuh>

Functions
template<int z = -1, int b1 = 8, int bs = 256, int in_bits, typename Group , typename Prg , typename In >
void	fss::gpu::HalfTreeDpfEvalAllGpu (bool b, int4 s0, const typename HalfTreeDpf< in_bits, Group, Prg, In >::Cw *cws, int4 ocw, int4 *ys, const HalfTreeDpf< in_bits, Group, Prg, In > &dpf, cudaStream_t stream=0)
	GPU full-domain evaluation of a HalfTree DPF key: ys[x] = Eval(b, s0, cws, ocw, x) for all x.
template<int z = -1, int b1 = 8, int bs = 256, int in_bits, typename Group , typename Prg , typename In >
void	fss::gpu::DpfEvalAllGpu (bool b, int4 s0, const typename Dpf< in_bits, Group, Prg, In >::Cw *cws, int4 *ys, const Dpf< in_bits, Group, Prg, In > &dpf, cudaStream_t stream=0)
	GPU full-domain evaluation of a DPF key: ys[x] = Eval(b, s0, cws, x) for all x.
template<int z = -1, int b1 = 8, int bs = 256, int in_bits, typename Group , typename Prg , typename In >
void	fss::gpu::DpfEvalAllGpuBatch (bool b, const int4 *s0s, const typename Dpf< in_bits, Group, Prg, In >::Cw *cws, int nkeys, int4 *ys, const Dpf< in_bits, Group, Prg, In > &dpf, cudaStream_t stream=0)
	GPU full-domain evaluation of nkeys DPF keys in one launch: per-key time drops toward the PRG bound as the grid fills the device (tail waves and launch overhead amortized).
template<int z = -1, int b1 = 8, int bs = 256, int in_bits, typename Group , typename Prg , typename In >
void	fss::gpu::HalfTreeDpfEvalAllGpuBatch (bool b, const int4 *s0s, const typename HalfTreeDpf< in_bits, Group, Prg, In >::Cw *cws, const int4 *ocws, int nkeys, int4 *ys, const HalfTreeDpf< in_bits, Group, Prg, In > &dpf, cudaStream_t stream=0)
	GPU full-domain evaluation of nkeys HalfTree DPF keys in one launch, see DpfEvalAllGpuBatch.

Detailed Description

GPU full-domain evaluation (EvalAll) for DPF and HalfTree DPF.

Copyright

Apache License, Version 2.0. Copyright (C) 2026 Yulong Ming i@myl.nosp@m.7.or.nosp@m.g.

Author

Yulong Ming i@myl.nosp@m.7.or.nosp@m.g

The tree-expansion strategy follows the hybrid approach of GPU-DPF (facebookresearch/GPU-DPF, dpf_hybrid.cu, Z=128): expand the tree toward a frontier of 2^z nodes, then expand each frontier node's subtree down to the leaves. Single kernel launch.

Structure (no redundant expansion):

• Phase 0: each block walks the b1 top levels to its own subtree root (2^b1 blocks, b1 serial steps per block — negligible).
• Phase 1: the block breadth-parallel-expands its subtree from depth b1 to depth z in shared memory (one __syncthreads per level, every node expanded exactly once).
• Phase 2: each thread DFS-expands its own depth-z subtree and converts the last level into leaf outputs.

This keeps the total PRG work at ~2^(n+1) calls (the tree size) instead of the ~n * N of point evals, and avoids the redundant per-thread path re-expansion of a naive breadth-to-z / DFS split.

References

1. Facebookresearch GPU-DPF: https://github.com/facebookresearch/GPU-DPF
2. EzPC GPU-MPC: https://github.com/mpc-msri/EzPC (see doc/bench_third_parties.md)

Function Documentation

DpfEvalAllGpu()

template<int z = -1, int b1 = 8, int bs = 256, int in_bits, typename Group , typename Prg , typename In >

void fss::gpu::DpfEvalAllGpu	(	bool	b,
		int4	s0,
		const typename Dpf< in_bits, Group, Prg, In >::Cw *	cws,
		int4 *	ys,
		const Dpf< in_bits, Group, Prg, In > &	dpf,
		cudaStream_t	stream = 0
	)

GPU full-domain evaluation of a DPF key: ys[x] = Eval(b, s0, cws, x) for all x.

Template Parameters

z	Frontier depth. 2^z threads each expand a subtree of 2^(in_bits - z) leaves. Defaults to min(in_bits, 16).
b1	Block-root depth. Each block walks b1 levels to its own subtree root, then expands levels b1..z breadth-parallel. Must satisfy 2^(z - b1) == bs. Defaults to 8.

Parameters

b	Party index. False for 0 and true for 1.
s0	Initial seed of the party.
cws	Correction words returned by Gen().
ys	Pre-allocated output array. Its size must be at least 2 ** in_bits.
dpf	A Dpf instance (holds the PRG). Used on the host side.
stream	CUDA stream to launch on.

DpfEvalAllGpuBatch()

template<int z = -1, int b1 = 8, int bs = 256, int in_bits, typename Group , typename Prg , typename In >

void fss::gpu::DpfEvalAllGpuBatch	(	bool	b,
		const int4 *	s0s,
		const typename Dpf< in_bits, Group, Prg, In >::Cw *	cws,
		int	nkeys,
		int4 *	ys,
		const Dpf< in_bits, Group, Prg, In > &	dpf,
		cudaStream_t	stream = 0
	)

GPU full-domain evaluation of nkeys DPF keys in one launch: per-key time drops toward the PRG bound as the grid fills the device (tail waves and launch overhead amortized).

This matches the workload that evaluates many keys, e.g. a Gen() loop followed by EvalAll per key.

Layouts: s0s has nkeys entries (party b's seed each); cws is flat, key-major, with stride (in_bits + 1) per key; ys is flat with stride (1 << in_bits) per key. All sizes must be pre-allocated by the caller.

Template Parameters

z	Frontier depth, see DpfEvalAllGpu.
b1	Block-root depth, see DpfEvalAllGpu.
bs	Block size, see DpfEvalAllGpu.

Parameters

b	Party index. False for 0 and true for 1.
s0s	nkeys seeds, one per key.
cws	Flat correction words, key-major, stride (in_bits + 1).
nkeys	Number of keys to evaluate.
ys	Output array, flat, stride (1 << in_bits) per key.
dpf	A Dpf instance (holds the PRG). Used on the host side.
stream	CUDA stream to launch on.

HalfTreeDpfEvalAllGpu()

template<int z = -1, int b1 = 8, int bs = 256, int in_bits, typename Group , typename Prg , typename In >

void fss::gpu::HalfTreeDpfEvalAllGpu	(	bool	b,
		int4	s0,
		const typename HalfTreeDpf< in_bits, Group, Prg, In >::Cw *	cws,
		int4	ocw,
		int4 *	ys,
		const HalfTreeDpf< in_bits, Group, Prg, In > &	dpf,
		cudaStream_t	stream = 0
	)

GPU full-domain evaluation of a HalfTree DPF key: ys[x] = Eval(b, s0, cws, ocw, x) for all x.

Template Parameters

z	Frontier depth. 2^z threads each expand a subtree of 2^(in_bits - z) leaves. Defaults to min(in_bits, 16).
b1	Block-root depth. Each block walks b1 levels to its own subtree root, then expands levels b1..z breadth-parallel. Must satisfy 2^(z - b1) == bs. Defaults to 8.

Parameters

b	Party index. False for 0 and true for 1.
s0	Initial seed of the party.
cws	Correction words returned by Gen().
ocw	Output correction word returned by Gen().
ys	Pre-allocated output array. Its size must be at least 2 ** in_bits.
dpf	A HalfTreeDpf instance (holds the PRG and hash key). Used on the host side.
stream	CUDA stream to launch on.

HalfTreeDpfEvalAllGpuBatch()

template<int z = -1, int b1 = 8, int bs = 256, int in_bits, typename Group , typename Prg , typename In >

void fss::gpu::HalfTreeDpfEvalAllGpuBatch	(	bool	b,
		const int4 *	s0s,
		const typename HalfTreeDpf< in_bits, Group, Prg, In >::Cw *	cws,
		const int4 *	ocws,
		int	nkeys,
		int4 *	ys,
		const HalfTreeDpf< in_bits, Group, Prg, In > &	dpf,
		cudaStream_t	stream = 0
	)

GPU full-domain evaluation of nkeys HalfTree DPF keys in one launch, see DpfEvalAllGpuBatch.

cws stride is in_bits per key; ocws has nkeys entries.