2-party DCF scheme. More...

Classes
struct	Cw
	Correction word. More...

Public Types
using	Input = In
	The caller-facing input-domain type.

Public Member Functions
	Dcf (Prg prg)
	Construct a scheme with configured backends.
void	Gen (cuda::std::span< int4 > cws, cuda::std::span< int4 > vws, In &tr, cuda::std::span< const int4, 2 > s0s, In a, int4 b_buf, size_t stride=1)
	Generate split correction arrays from caller-owned initial seeds.
int4	Eval (bool b, int4 s0, cuda::std::span< const int4 > cws, cuda::std::span< const int4 > vws, In tr, In x, size_t stride=1)
	Evaluate one input from a seed and split correction arrays.
void	EvalRange (bool b, In first, In last, int4 s0, cuda::std::span< const int4 > cws, cuda::std::span< const int4 > vws, In tr, cuda::std::span< int4 > ys, int par_depth=0, size_t stride=1)
	Evaluate the closed input interval [first, last] in input order from split arrays.
void	EvalAll (bool b, int4 s0, cuda::std::span< const int4 > cws, cuda::std::span< const int4 > vws, In tr, int4 ys[], int par_depth=0, size_t stride=1)
	Evaluate the full domain from a seed and split correction arrays.
template<int frontier_depth = 16, int threads_per_block = 256> requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 4>)
cudaError_t	EvalRangeGpu (bool b, In first, In last, int4 s0, cuda::std::span< const int4 > cws, cuda::std::span< const int4 > vws, In tr, cuda::std::span< int4 > ys, cudaStream_t stream=0, size_t stride=1) const
	Evaluate the closed interval [first, last] on the given CUDA stream from split device arrays.
template<int frontier_depth = 16, int threads_per_block = 256> requires (in_bits < sizeof(size_t) * 8)
cudaError_t	EvalAllGpu (bool b, int4 s0, cuda::std::span< const int4 > cws, cuda::std::span< const int4 > vws, In tr, cuda::std::span< int4 > ys, cudaStream_t stream=0, size_t stride=1) const
	Launch full-domain CUDA evaluation from split device arrays.
template<int frontier_depth = 16, int threads_per_block = 256> requires (in_bits < sizeof(size_t) * 8)
cudaError_t	EvalAllGpuBatch (bool b, cuda::std::span< const int4 > s0s, cuda::std::span< const int4 > cws, cuda::std::span< const int4 > vws, cuda::std::span< const In > tr, cuda::std::span< int4 > ys, cudaStream_t stream=0, size_t stride=0) const
	Launch full-domain CUDA evaluation for s0s.size() keys from split device arrays.

Static Public Attributes
static constexpr int	kCwCount = in_bits + 1
	Seed- and value-component count Gen() writes at stride 1: in_bits layers plus the terminal.

Detailed Description

template<int in_bits, typename Group, typename Prg, typename In = uint, DcfPred pred = DcfPred::kLt>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 4>)
class fss::Dcf< in_bits, Group, Prg, In, pred >

2-party DCF scheme.

Gen() and scalar Eval() support host and device calls when Prg does. EvalRange() and EvalAll() are host operations and support both predicates. EvalAllGpu() and EvalAllGpuBatch() are host CUDA launch methods.

Template Parameters

in_bits	Input domain bit size.
Group	Type for the output domain. See Groupable.
Prg	See Prgable.
In	Type for the input domain. From uint8_t to __uint128_t.
pred	See DcfPred.

Constructor & Destructor Documentation

◆ Dcf()

template<int in_bits, typename Group, typename Prg, typename In, DcfPred pred>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 4>)

fss::Dcf< in_bits, Group, Prg, In, pred >::Dcf ( Prg prg )

inlineexplicit

Construct a scheme with configured backends.

Parameters

prg	Configured Prg backend.

Member Function Documentation

◆ Eval()

template<int in_bits, typename Group, typename Prg, typename In, DcfPred pred>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 4>)

int4 fss::Dcf< in_bits, Group, Prg, In, pred >::Eval	(	bool	b,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		cuda::std::span< const int4 >	vws,
		In	tr,
		In	x,
		size_t	stride = 1 )

inline

Evaluate one input from a seed and split correction arrays.

Layer l is read from cws[l*stride] and vws[l*stride]. cws carries the left-control correction in its LSB exactly as Cw::s does, and vws holds the group value. The right-control correction is bit l of tr, and the layer LSBs of vws are ignored because the correction is read from tr; bits of tr at or above in_bits are ignored. The terminal is cws[in_bits*stride] = {0,0,0,0} and vws[in_bits*stride] = v_cw_np1, as Gen() writes them.

Parameters

b	Party index, false for party 0 and true for party 1.
s0	This party's initial seed.
cws	Seed components, with layer l at index l*stride.
vws	Group-value components, with layer l at index l*stride.
tr	Packed right-control bits, bit l for layer l.
x	Input in the scheme's domain.
stride	Positive element stride between layer entries.

Returns: This party's output share for the selected predicate.

Precondition: stride > 0.; With M = numeric_limits<size_t>::max()/sizeof(int4), stride <= (M-1)/in_bits and both arrays have at least in_bits*stride+1 elements.; vws[in_bits*stride].w & 1 == 0.; All accessed storage is accessible from the calling execution space.; A stride, capacity, or terminal violation aborts with a diagnostic in Debug builds on both the host and the device, and is undefined behavior in Release builds.

◆ EvalAll()

template<int in_bits, typename Group, typename Prg, typename In, DcfPred pred>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 4>)

void fss::Dcf< in_bits, Group, Prg, In, pred >::EvalAll	(	bool	b,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		cuda::std::span< const int4 >	vws,
		In	tr,
		int4	ys[],
		int	par_depth = 0,
		size_t	stride = 1 )

inline

Evaluate the full domain from a seed and split correction arrays.

Layer l is read from cws[l*stride] and vws[l*stride]. cws carries the left-control correction in its LSB exactly as Cw::s does, and vws holds the group value. The right-control correction is bit l of tr, and the layer LSBs of vws are ignored because the correction is read from tr; bits of tr at or above in_bits are ignored. The terminal is cws[in_bits*stride] = {0,0,0,0} and vws[in_bits*stride] = v_cw_np1, as Gen() writes them.

Parameters

b	Party index, false for party 0 and true for party 1.
s0	This party's initial seed.
cws	Seed components, with layer l at index l*stride.
vws	Group-value components, with layer l at index l*stride.
tr	Packed right-control bits, bit l for layer l.
ys	Output array with at least 2^in_bits entries, in input order.
par_depth	Nonnegative OpenMP split depth for this call. Zero runs sequentially. Positive depths require backends that support concurrent calls.
stride	Positive element stride between layer entries.

Precondition: stride > 0.; With M = numeric_limits<size_t>::max()/sizeof(int4), stride <= (M-1)/in_bits and both arrays have at least in_bits*stride+1 elements.; vws[in_bits*stride].w & 1 == 0. A violation aborts with a diagnostic in Debug builds and is undefined behavior in Release builds.; The output element count and byte size fit size_t, and ys is allocated.

Exceptions

std::invalid_argument if stride is zero or too large or the arrays are shorter than in_bits*stride+1.

◆ EvalAllGpu()

template<int in_bits, typename Group, typename Prg, typename In, DcfPred pred>
requires (in_bits < sizeof(size_t) * 8)

template<int frontier_depth, int threads_per_block>
requires (in_bits < sizeof(size_t) * 8)

cudaError_t fss::Dcf< in_bits, Group, Prg, In, pred >::EvalAllGpu	(	bool	b,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		cuda::std::span< const int4 >	vws,
		In	tr,
		cuda::std::span< int4 >	ys,
		cudaStream_t	stream = 0,
		size_t	stride = 1 ) const

inline

Launch full-domain CUDA evaluation from split device arrays.

Layer l is read from cws[l*stride] and vws[l*stride]. cws carries the left-control correction in its LSB exactly as Cw::s does, and vws holds the group value. The right-control correction is bit l of tr, and the layer LSBs of vws are ignored because the correction is read from tr; bits of tr at or above in_bits are ignored. The terminal is cws[in_bits*stride] = {0,0,0,0} and vws[in_bits*stride] = v_cw_np1, as Gen() writes them. Backend values, resource rules and tuning rules match EvalAllGpu().

Parameters

b	Party index, false for party 0 and true for party 1.
s0	This party's seed, passed by value to the kernel.
cws	Device seed components, with layer l at index l*stride.
vws	Device group-value components, with layer l at index l*stride.
tr	Packed right-control bits, bit l for layer l.
ys	Device output storage containing at least 2^in_bits int4 blocks.
stream	Stream on the device owning the referenced resources.
stride	Positive element stride between layer entries.

Returns: Immediate CUDA status. Invalid dimensions, buffers, strides, null used buffers, and unaddressable byte sizes return cudaErrorInvalidValue.

Precondition: stride > 0 and both arrays hold at least in_bits*stride+1 elements.; All referenced storage remains alive until the stream work completes.

◆ EvalAllGpuBatch()

template<int in_bits, typename Group, typename Prg, typename In, DcfPred pred>
requires (in_bits < sizeof(size_t) * 8)

template<int frontier_depth, int threads_per_block>
requires (in_bits < sizeof(size_t) * 8)

cudaError_t fss::Dcf< in_bits, Group, Prg, In, pred >::EvalAllGpuBatch	(	bool	b,
		cuda::std::span< const int4 >	s0s,
		cuda::std::span< const int4 >	cws,
		cuda::std::span< const int4 >	vws,
		cuda::std::span< const In >	tr,
		cuda::std::span< int4 >	ys,
		cudaStream_t	stream = 0,
		size_t	stride = 0 ) const

inline

Launch full-domain CUDA evaluation for s0s.size() keys from split device arrays.

The batch uses the level-major layout: key k layer l is read from cws[l*stride + k] and vws[l*stride + k], key k's packed control is tr[k], and key k's terminal is cws[in_bits*stride + k] = {0,0,0,0} and vws[in_bits*stride + k] = v_cw_np1. cws carries the left-control correction in its LSB exactly as Cw::s does, and the layer LSBs of vws are ignored because the right-control correction is read from tr[k]; bits of tr[k] at or above in_bits are ignored. stride selects the layout. 0 selects the dense level-major layout, in which the stride is the key count of this call. Any other value is a positive stride of at least s0s.size(). Resource and tuning rules match EvalAllGpu(). The batch shares one party index and backend configuration. Every key produces the complete domain.

Parameters

b	Party index shared by the batch.
s0s	Device storage containing this party's seed for each key.
cws	Device level-major seed components.
vws	Device level-major group-value components.
tr	Device packed right-control bits, one value per key.
ys	Device key-major rows of 2^in_bits output blocks per key.
stream	Stream on the device owning the referenced resources.
stride	0 for the dense level-major layout, where the stride is the key count of this call, or a positive element stride >= s0s.size().

Returns: Immediate CUDA status. An empty batch succeeds without reading buffers. Invalid dimensions, buffers, strides or byte sizes return cudaErrorInvalidValue; an oversized grid returns cudaErrorInvalidConfiguration. Work is asynchronous.

Precondition: stride is 0 or at least s0s.size().; Both arrays hold at least in_bits*stride + s0s.size() elements, where a stride of 0 counts as s0s.size().; All referenced storage remains alive until the stream work completes.

◆ EvalRange()

template<int in_bits, typename Group, typename Prg, typename In, DcfPred pred>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 4>)

void fss::Dcf< in_bits, Group, Prg, In, pred >::EvalRange	(	bool	b,
		In	first,
		In	last,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		cuda::std::span< const int4 >	vws,
		In	tr,
		cuda::std::span< int4 >	ys,
		int	par_depth = 0,
		size_t	stride = 1 )

inline

Evaluate the closed input interval [first, last] in input order from split arrays.

Layer l is read from cws[l*stride] and vws[l*stride]. cws carries the left-control correction in its LSB exactly as Cw::s does, and vws holds the group value. The right-control correction is bit l of tr, and the layer LSBs of vws are ignored because the correction is read from tr; bits of tr at or above in_bits are ignored. The terminal is cws[in_bits*stride] = {0,0,0,0} and vws[in_bits*stride] = v_cw_np1, as Gen() writes them.

Parameters

b	Party index, false for party 0 and true for party 1.
first	First input in the interval.
last	Last input in the interval, inclusive.
s0	This party's initial seed.
cws	Seed components, with layer l at index l*stride.
vws	Group-value components, with layer l at index l*stride.
tr	Packed right-control bits, bit l for layer l.
ys	Output storage. Entry x - first receives this party's share at x. Extra capacity beyond last - first + 1 entries is unchanged.
par_depth	Nonnegative OpenMP split depth for this call. Zero runs sequentially on the calling thread. Positive depths require backends that support concurrent calls.
stride	Positive element stride between layer entries.

Precondition: first <= last and both endpoints are in the input domain.; stride > 0.; With M = numeric_limits<size_t>::max()/sizeof(int4), stride <= (M-1)/in_bits and both arrays have at least in_bits*stride+1 elements.; vws[in_bits*stride].w & 1 == 0. A violation aborts with a diagnostic in Debug builds and is undefined behavior in Release builds.; The interval's output count and byte size fit size_t, and ys has at least that many entries. The full input domain need not fit size_t.

Exceptions

std::invalid_argument if first > last, either endpoint is outside the input domain, the interval does not fit size_t, ys is too short, stride is zero or too large, or the arrays are shorter than in_bits*stride+1.

◆ EvalRangeGpu()

template<int in_bits, typename Group, typename Prg, typename In, DcfPred pred>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 4>)

template<int frontier_depth, int threads_per_block>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 4>)

cudaError_t fss::Dcf< in_bits, Group, Prg, In, pred >::EvalRangeGpu	(	bool	b,
		In	first,
		In	last,
		int4	s0,
		cuda::std::span< const int4 >	cws,
		cuda::std::span< const int4 >	vws,
		In	tr,
		cuda::std::span< int4 >	ys,
		cudaStream_t	stream = 0,
		size_t	stride = 1 ) const

inline

Evaluate the closed interval [first, last] on the given CUDA stream from split device arrays.

Output ys[j] corresponds to first+j.

Layer l is read from cws[l*stride] and vws[l*stride]. cws carries the left-control correction in its LSB exactly as Cw::s does, and vws holds the group value. The right-control correction is bit l of tr, and the layer LSBs of vws are ignored because the correction is read from tr; bits of tr at or above in_bits are ignored. The terminal is cws[in_bits*stride] = {0,0,0,0} and vws[in_bits*stride] = v_cw_np1, as Gen() writes them. Resources and asynchronous error handling follow EvalAllGpu(). frontier_depth is relative to each aligned evaluation subtree and is capped to its depth.

Parameters

b	Party index, false for party 0 and true for party 1.
first	First input in the interval.
last	Last input in the interval, inclusive.
s0	This party's seed, passed by value to the kernel.
cws	Device seed components, with layer l at index l*stride.
vws	Device group-value components, with layer l at index l*stride.
tr	Packed right-control bits, bit l for layer l.
ys	Device output storage. Entry x - first receives this party's share at x.
stream	Stream on the device owning the referenced resources.
stride	Positive element stride between layer entries.

Returns: Immediate CUDA status. Invalid endpoints, buffers, strides, counts or byte sizes return cudaErrorInvalidValue. Grid limits return cudaErrorInvalidConfiguration.

Precondition: stride > 0 and both arrays hold at least in_bits*stride+1 elements.; All referenced storage remains alive until the stream work completes.

◆ Gen()

template<int in_bits, typename Group, typename Prg, typename In, DcfPred pred>
requires (ValidForInputBits<In, in_bits> && Groupable<Group> && Prgable<Prg, 4>)

void fss::Dcf< in_bits, Group, Prg, In, pred >::Gen	(	cuda::std::span< int4 >	cws,
		cuda::std::span< int4 >	vws,
		In &	tr,
		cuda::std::span< const int4, 2 >	s0s,
		In	a,
		int4	b_buf,
		size_t	stride = 1 )

inline

Generate split correction arrays from caller-owned initial seeds.

cws receives the seed components and vws the group-value components. Layer l is stored at cws[l*stride] and vws[l*stride]. cws keeps the left-control correction in its LSB exactly as Cw::s does, and vws carries the pure group value with a zero LSB. The right-control bits move out of the v LSBs into tr, bit l for layer l, and unused high bits of tr are zero. The terminal is cws[in_bits*stride] = {0,0,0,0} and vws[in_bits*stride] = v_cw_np1.

Parameters

cws	Output seed components; its capacity includes in_bits*stride+1 elements.
vws	Output group-value components, with the same layout as cws.
tr	Output packed right-control bits, bit l for layer l.
s0s	Two initial seeds, preserved by this call.
a	Comparison threshold in the input domain.
b_buf	Output value, clamped before conversion to Group.
stride	Positive element stride between layer entries. The default stride of 1 stores the correction words contiguously.

Precondition: a is in the input domain.; stride > 0.; With M = numeric_limits<size_t>::max()/sizeof(int4), stride <= (M-1)/in_bits and both arrays have at least in_bits*stride+1 elements.; Inputs and outputs do not overlap.; All accessed storage is accessible from the calling execution space.; A stride or capacity violation aborts with a diagnostic in Debug builds on both the host and the device, and is undefined behavior in Release builds.

Postcondition: cws, vws, tr and s0s[party] form the corresponding party's key.; Only the described prefix is written, and storage beyond it is untouched.

The documentation for this class was generated from the following file:

include/fss/dcf.cuh

Classes

Public Types

Public Member Functions

Static Public Attributes

Detailed Description

Constructor & Destructor Documentation

◆ Dcf()

Member Function Documentation

◆ Eval()

◆ EvalAll()

◆ EvalAllGpu()

◆ EvalAllGpuBatch()

◆ EvalRange()

◆ EvalRangeGpu()

◆ Gen()