CKKS workload cost model

Performance work begins with a real evaluator and a decomposition of its measured cost.

Cost structure of packed linear workloads

A common diagonal formulation is:

y = \sum_{i} p_{i} ⊙ Rot (x, s_{i}) .

Its dominant costs can include:

A small plaintext pointwise multiply can be surrounded by a much more expensive rotation/key-switch path.

Optimize from the highest useful layer

Higher layers often change total work more dramatically:

Packing determines the number of rotations and diagonals.
Scheduling determines rescale/relinearization placement and reuse.
Execution determines launch and transfer overhead.
Distribution determines communication and key replication.
Backend policy determines transform tables and stage grouping.
Kernel work determines occupancy, memory traffic, and local arithmetic.

Move to a lower layer when measurements show that it controls the target workload.

Main optimization mechanisms

Mechanism	Removes or changes	Adds or risks
Late relinearization	Repeated key switches across compatible triplets	Larger three-component live state
Operation-ready plaintexts	Repeated encode/lift/NTT preparation	Larger persistent weight footprint
Reused NTT operands	Repeated transforms of fixed operands	Depth/state coupling
NTT-domain product accumulation	Per-term inverse transforms in additive PT×CT regions	Quotient-rounding and output-representation constraints
NTT grouping/compact tables	Launches and table/global-memory traffic	Registers, occupancy, index arithmetic
Rotation hoisting	Repeated decomposition/ModUp/NTT prefix	Hoist temporaries and output memory
CUDA Graph	Repeated host/dispatcher submission	Fixed signatures, retained graph memory
Budget-constrained residency	All-resident CUDA footprint	Host-to-device (H2D) traffic and event coordination
Multi-GPU partition	Rank-local dominant work	Communication, imbalance, key placement
Minimal keyset	Key memory and movement	Possible extra operations with decomposition

Each mechanism has a shape-, depth-, platform-, and workload-dependent crossover.

Hoisting has a memory curve

Multiple rotations can share preparation that depends only on the input component, but each step still needs its own automorphism, direct key products, ModDown, and output storage.

Chunk size is a workload policy. Measure latency and peak memory together.

Homogeneous batching has a working-set crossover

A homogeneous batch adds independent-message dimensions while keeping one depth, scale, polynomial domain, modulus basis, device, dtype, and component count. The public ciphertext layout keeps its structural component axis first, followed by *batch, limb, and polynomial-index axes. Message batch axes are distinct from RNS limbs, ciphertext components, hybrid-decomposition digits, and distributed ranks.

Batching can reduce launches and expose parallel work, but it also multiplies the tensors active inside NTT, automorphism, ModUp, key accumulation, ModDown, and result assembly. For one extended key-switch digit with flattened batch size $B$ , $L_{Q P}$ active prime rows, ring dimension $N$ , and $w$ bytes per residue, its payload size is:

W_{d i g i t} = B L_{Q P} N w . w = 4 for int32, w = 8 for int64 .

The full active set is larger because transforms read and write data while keys, accumulators, temporaries, and outputs are live. Once that set exceeds effective cache capacity, a larger batch can replace cache reuse with DRAM traffic and become slower than an explicit loop. Later CKKS depths use fewer Q rows, so the crossover may reverse without changing N or B.

Two cache regimes are useful when interpreting the crossover:

text

B1 fits, B2/B4 spills:
    batching introduces a fit-to-spill transition and can regress abruptly

B1 already streams beyond cache:
    increasing B does not create the same new transition; backend structure,
    occupancy, bandwidth, and launch count determine the relative result

For example, 19 prime rows at $N = 32768$ and eight bytes per residue occupy 4.75 MiB per digit and batch member. Against a 6 MiB cache, that payload approaches capacity at $B = 1$ and exceeds it at $B = 2$ . A 39-row digit at $N = 65536$ occupies 19.5 MiB even at $B = 1$ . These cases begin in different cache regimes; the complete active set also includes keys, tables, accumulators, and outputs.

This is why B1 compatibility, operator speedup, workload speedup, and peak memory are separate measurements. The application selects batching or looping from those measurements while FHElium preserves either value layout.

CUDA Graph and homogeneous batching also overlap as launch-amortization mechanisms. Batching reduces the number of launches by operating on a larger message tensor; graph replay reduces host submission gaps while preserving an explicit loop's smaller per-message working set. A batching win under eager execution can therefore become a loop win when both paths are captured. The valid comparison is batch graph versus loop graph, with graph capture and retained memory reported separately from replay latency.

Compilation and compact materials change different costs

Compile can reuse repeated transforms, share rotation preparation, and combine compatible arithmetic into generated regions. These changes affect operation count, temporary storage, and device work. Prepared host calls reduce repeated interpretation and dispatch work. CUDA Graph replay further reduces host submission overhead for a fixed sequence. The wall-clock benefit depends on whether device execution, submission, data transfer, or synchronization limits the workload.

A generated region can launch several kernels. In particular, a fused NTT region can use generated endpoint stages and native middle stages. Region count, kernel count, and elapsed device time therefore describe different parts of the cost model. Retaining a whole operation can also keep a streaming implementation that limits the lifetime of intermediate digits.

Compressed plaintext reduces the stored payload for a represented polynomial from $L N w$ to $L U w$ bytes, plus implicit row values for sparse layouts, where $U < N$ . Arithmetic still computes a full ciphertext result. A smaller plaintext working set can reduce memory traffic and improve cache use, while rotation keys and ciphertext intermediates may remain dominant. Value representations defines compact storage, and the Compile lifecycle describes implementation selection.

NTT grouping has workload-dependent optima

Combining multiple radix-2 stages can reduce launches and global-memory round-trips, but wider grouping can increase register pressure, reduce occupancy, or interact poorly with active row count.

The best backend depends on:

ring dimension;
active depth/row count;
transform batch shape;
GPU architecture;
table footprint and traffic;
surrounding workload and graph capture.

A name such as group16 identifies one execution strategy. Controlled measurements determine its ranking, and direct-radix algorithms retain separate implementation identities.

Multi-GPU time model

For additive-term parallelism, a useful first approximation is:

T_{p} \approx T_{l o c a l} / p + T_{i n p u t} + T_{k e y p r o v i s i o n i n g} + T_{r e d u c t i o n} + T_{i m b a l a n c e} + T_{s t a r t u p} .

Data parallelism tends to scale most simply because requests are independent. Additive-term parallelism can move communication to the beginning and end phases. Limb parallelism pays repeated complete-row reconstruction whenever the next operation cannot be row-local.

Topology, per-rank key footprint, and the synchronization rule determine the scope of a distributed timing result.

Numerical limits are performance constraints

Scale, active modulus, input amplitude, and summation width interact:

A valid performance comparison preserves the required value state, stays within the intended numerical range, and meets the justified output-error criterion.

Measurement layers answer different questions

Layer	Good question	Invalid overclaim
Kernel	Which NTT/RNS implementation is faster for this shape?	The application has the same speedup
Operator	What dominates rotate, rescale, or relinearize?	Distributed scaling is solved
Workload	How do packing, hoisting, graph, and memory combine?	One kernel caused all gains
Distributed	What are compute, communication, imbalance, and memory?	Every topology behaves identically

Measurement identity

A reproducible report records:

GPU model/count/topology, driver, PyTorch, and CUDA;
FHElium version/commit and source or installed wheel;
preset, logN, depth, scale, Q/P row counts;
NTT backend and grouping policy;
warmup, measured runs, and statistic;
synchronization and event-completion rule;
whether setup, keygen, encryption, and decryption are timed;
hoist chunk, graph mode, rank count, and partition;
peak allocated and reserved memory;
decrypt error and expected tolerance.

Bottlenecks and corresponding mechanisms

A controlled comparison holds the cleartext calculation and required value state fixed while varying the mechanism under study. The resulting latency, throughput, and memory changes describe that mechanism within the stated measurement conditions.

Residency lifetimes

CKKS workload cost model ​

Cost structure of packed linear workloads ​

Optimize from the highest useful layer ​

Main optimization mechanisms ​

Hoisting has a memory curve ​

Homogeneous batching has a working-set crossover ​

Compilation and compact materials change different costs ​

NTT grouping has workload-dependent optima ​

Multi-GPU time model ​

Numerical limits are performance constraints ​

Measurement layers answer different questions ​

Measurement identity ​

Bottlenecks and corresponding mechanisms ​

Related concepts ​