The Law of Diminishing Returns: When Parallel Synthesis Reveals CPU Contention in a Groth16 Proving Engine

Introduction

In the high-stakes world of Filecoin proof-of-replication (PoRep) proving, every second counts. The cuzk proving engine, a custom Groth16 implementation designed for Filecoin's storage verification, had been carefully optimized through five phases of development. By the time we reach message 1873 in the conversation, the engine has already undergone significant architectural transformations: a Pre-Compiled Constraint Evaluator (PCE) for Phase 5, disk persistence for faster loading, and a slotted pipeline for Phase 6 that reduced peak memory from ~228 GiB to ~71 GiB. Yet despite these advances, a persistent problem remained — the GPU was idle nearly 30% of the time.

Message 1873 represents a pivotal moment in the optimization journey. It is the moment when a seemingly straightforward fix — parallelize the CPU synthesis step to keep the GPU fed — collides with the messy reality of shared hardware resources. The message is an analysis of the first benchmark results after implementing parallel synthesis, and it reveals a classic systems engineering lesson: moving a bottleneck does not eliminate it.

The Context: A Structural GPU Idle Gap

To understand message 1873, we must first understand what came before. The proving engine operated in a two-stage pipeline: Stage 1 performed CPU-bound Groth16 synthesis (constraint evaluation, R1CS construction, witness computation), and Stage 2 ran the GPU-accelerated prover (multi-scalar multiplication, number-theoretic transform, and final proof assembly). The stages overlapped in a producer-consumer pattern — synthesis for proof N+1 could run concurrently with GPU proving for proof N.

The waterfall timeline instrumentation, implemented in the immediately preceding messages ([msg 1851], [msg 1852]), had revealed a stark problem. Synthesis took approximately 39 seconds per proof, while GPU proving took only 27 seconds. Because synthesis was strictly sequential — a single task loop pulled one request at a time from the scheduler — the GPU would finish proof N and then sit idle for 12-14 seconds waiting for synthesis of proof N+1 to complete. GPU utilization was a mere 70.9%.

The diagnosis was clear and the fix seemed obvious: run multiple synthesis tasks concurrently. If two syntheses could run in parallel, the GPU would receive a new proof every ~20 seconds (39s / 2), which is less than the 27 seconds of GPU time. The GPU would never idle. Utilization would approach 100%. Throughput would improve by the full 30% GPU idle gap.

The assistant implemented this fix in [msg 1862] by refactoring the engine's synthesis task loop. Instead of a single process_batch().await that blocked the loop, the code was changed to use a tokio::sync::Semaphore. Each synthesis call was spawned as a fire-and-forget tokio task, with the semaphore limiting concurrency to a configurable synthesis_concurrency parameter. The implementation was clean, the reasoning was sound, and the machine had 754 GiB of RAM — plenty for two concurrent syntheses each holding ~136 GiB of intermediate data.

The first benchmark ran with synthesis_concurrency=2 and client concurrency -j 3 (three in-flight proof requests from the benchmark tool). The results, shown in [msg 1871], were underwhelming: 44.7 seconds per proof versus 45.3 seconds per proof baseline. A mere 1.3% improvement.

Message 1873 is the assistant's response to that disappointing result.

The Message: A Reality Check Through Data

The message begins with the assistant examining the waterfall timeline data from the parallel synthesis benchmark. The tone is one of discovery — the assistant is working through the data in real-time, updating their understanding as each new observation emerges.

Now this is very informative. The parallel synthesis is working — P1 and P2 start simultaneously, and we can see the GPU idle gaps are mostly eliminated (gap 1-2 are ~0.02s). GPU utilization jumped from 70.9% to 86.5%.

This first observation confirms that the implementation is correct. The semaphore-based parallel synthesis is functioning as designed: two proofs begin synthesis at nearly the same timestamp (67.10s and 67.12s), and the GPU idle gaps between the first two proofs are essentially zero. GPU utilization has increased by over 15 percentage points. The mechanical fix worked.

But then the assistant notices the problems:

1. Synthesis time inflation: When 2 syntheses run concurrently, each takes longer due to CPU/memory contention. P1 alone = 38s, but P2 running concurrently = 54s (42% slower). P4 is extreme at 97s because it overlapped with P3/P5.

This is the first crack in the hypothesis. The assistant had assumed that synthesis time would remain roughly constant under parallel execution — that two syntheses would each take ~39 seconds, just overlapping in time. Instead, the concurrent syntheses are competing for CPU resources, and each takes significantly longer. P2 is 42% slower than P1. P4, which overlaps with both P3 and P5, balloons to 97 seconds — nearly 2.5x the baseline.

2. One big 25s gap between P3 GPU end and P5 GPU start — caused by P5's synthesis taking so long due to contention.

The GPU idle gap hasn't been eliminated; it has been transformed. Instead of a consistent 12-second gap between every proof, there is now a single large gap of 25 seconds caused by a particularly slow synthesis. The pattern is more chaotic but the net result is similar.

3. GPU time also increased: avg 32s vs 27s before. The b_g2_msm CPU step (runs during GPU phase) is competing with synthesis for CPU.

This is perhaps the most surprising finding. The assistant expected GPU time to remain constant — after all, the GPU is a separate device with its own compute resources. But the GPU prover includes a CPU-bound step called b_g2_msm (a multi-scalar multiplication on the G2 curve) that runs during the GPU phase. This step uses the same rayon thread pool as synthesis. When synthesis tasks consume all available CPU cores, b_g2_msm slows down, inflating the GPU time from 27 seconds to 32 seconds.

The Root Cause: Shared Rayon Thread Pool

The assistant traces the root cause with precision:

The issue is clear: 96 cores with 2 concurrent 10-circuit syntheses means each synthesis gets ~48 cores, which slows them both. The rayon thread pool is shared.

The system has 96 CPU cores. Under the old sequential synthesis, a single synthesis task could use all 96 cores via rayon's parallel thread pool, completing in ~39 seconds. With two concurrent syntheses, each gets approximately 48 cores (though the actual division is dynamic and depends on rayon's work-stealing scheduler). But Groth16 synthesis is not perfectly parallelizable — there are synchronization points, memory bandwidth bottlenecks, and diminishing returns from additional cores. Cutting the core count in half does not simply double the time; it increases time by 42% or more due to these inefficiencies.

Furthermore, the GPU prover's b_g2_msm step also competes for these same cores. This creates a three-way contention: two synthesis tasks and one GPU CPU-step all fighting for the 96-core thread pool. The result is that everything slows down.

The Thinking Process: Hypothesis Refinement

What makes message 1873 particularly valuable is the visible thinking process. The assistant does not simply report results; they reason through the data step by step.

First, the assistant considers whether synthesis_lookahead=2 (the channel capacity for completed syntheses awaiting GPU pickup) might help buffer the jumbled order. They quickly realize this is already set and is not the issue.

Then they consider the throughput numbers quantitatively:

Let me check the actual throughput improvement (44.7s/proof vs 45.3s/proof is within noise).

This is a moment of honest assessment. The assistant recognizes that the 1.3% improvement could be measurement noise rather than a real gain. They decide to run a cleaner test with more proofs (8 instead of 5) to get better statistics.

The decision to run a larger test is itself revealing. The assistant could have concluded that parallel synthesis doesn't work and reverted the change. Instead, they recognize that the 5-proof benchmark may not be representative — the first proof always includes SRS loading overhead, and the small sample size amplifies variance. An 8-proof run would provide a more stable measurement.

Assumptions Made and Broken

Message 1873 exposes several assumptions that turned out to be incorrect:

Assumption 1: Synthesis time is independent of concurrency. The assistant assumed that running two syntheses in parallel would not significantly change the wall-clock time of each synthesis. This assumption was based on the idea that 96 cores could handle two workloads of ~48 cores each without slowdown. The reality was that rayon's work-stealing scheduler, memory bandwidth contention, and Amdahl's law effects caused 42% time inflation.

Assumption 2: GPU time is independent of CPU load. The assistant assumed that GPU proving time would remain constant at ~27 seconds regardless of what the CPU was doing. They forgot (or underestimated) the CPU-bound b_g2_msm step that runs during GPU proving. This step competes for the same rayon thread pool as synthesis.

Assumption 3: The GPU idle gap would translate directly into throughput gain. The assistant calculated that eliminating the 12-second GPU idle gap from a 45.3-second cycle would yield ~26% throughput improvement. But this calculation assumed that only the idle gap would change — that synthesis and GPU times would remain constant. In reality, both inflated, and the net gain was only ~5% at best (as later benchmarks would show with the optimal configuration).

Assumption 4: The client-side concurrency (-j) is independent of synthesis concurrency. The assistant set -j 3 (three in-flight client requests) alongside synthesis_concurrency=2 (two concurrent syntheses). This created a mismatch: the client could submit up to 3 proofs, but only 2 could be synthesized at once. The third request would queue up, creating uneven pipeline pressure. Later benchmarks would show that -j 2 with synthesis_concurrency=2 performed better (42.2s/proof) while -j 4 was catastrophic (60.2s/proof).

Input Knowledge Required

To fully understand message 1873, the reader needs knowledge of several domains:

Groth16 proof structure: Understanding that Groth16 proving involves both a CPU-bound synthesis phase (constraint evaluation, R1CS construction) and a GPU-accelerated proving phase (MSM, NTT, final proof). The synthesis phase is inherently parallelizable across partitions (the circuit is split into 10 partitions for PoRep).

The cuzk engine architecture: Knowledge of the two-stage pipeline, the synthesis task loop, the scheduler, and the bounded channel (synthesis_lookahead) that connects synthesis to GPU proving. Understanding that the engine uses tokio::spawn for async tasks and spawn_blocking for CPU-heavy work.

Rayon thread pool: Understanding that rayon uses a global thread pool (defaulting to the number of CPU cores) for parallel iteration. All rayon-based parallelism in the process shares this pool, so two concurrent rayon workloads compete for the same threads.

The b_g2_msm step: Knowledge that the GPU prover includes a multi-scalar multiplication on the G2 curve that runs on the CPU (not the GPU). This step uses Pippenger's algorithm with multi-threaded bucket accumulation, making it a heavy consumer of CPU resources during the "GPU phase."

Waterfall timeline instrumentation: Understanding the custom tracing system that records SYNTH_START, SYNTH_END, CHAN_SEND, GPU_PICKUP, GPU_START, and GPU_END events with wall-clock timestamps, enabling precise visualization of pipeline stage overlap.

Output Knowledge Created

Message 1873 creates several important pieces of knowledge:

Empirical confirmation of CPU contention as the new bottleneck. The sequential synthesis bottleneck (GPU idle) has been replaced by a CPU contention bottleneck. This shifts the optimization target: instead of "keep the GPU busy," the goal becomes "reduce the absolute CPU time of synthesis" or "decouple the CPU workloads."

Quantified synthesis time inflation under concurrency. The data shows that concurrent synthesis inflates individual synthesis times by 42% or more. This is a crucial parameter for any future optimization: the benefit of parallelism must be weighed against the cost of contention.

Evidence that GPU time is not independent of CPU load. The increase from 27s to 32s average GPU time demonstrates that the GPU prover's CPU-bound components are significant and must be accounted for in pipeline design.

A refined understanding of the optimization landscape. The message implicitly maps out the remaining optimization space: reduce synthesis CPU time (via specialized MatVec, pre-sorted SRS, or other algorithmic improvements), decouple synthesis from GPU CPU work (via separate thread pools or core pinning), or find ways to make synthesis more efficient per core rather than simply adding more parallelism.

The Deeper Lesson: Bottleneck Shifting

Message 1873 is a textbook example of bottleneck shifting in systems optimization. The assistant correctly identified the GPU idle gap as a bottleneck and correctly implemented a fix to address it. But the fix did not eliminate the bottleneck; it moved it to a different resource (CPU cores) where the contention was more complex and the gains more modest.

This is a common pattern in performance engineering. The first bottleneck is often the easiest to identify and fix. Each subsequent bottleneck is subtler, requiring deeper understanding of the system's resource interactions. The GPU idle gap was visible in the waterfall timeline as empty space between GPU bars. The CPU contention is invisible in a waterfall — it manifests as inflated bar lengths rather than gaps between bars.

The assistant's response to this discovery is instructive. They do not give up on parallel synthesis. Instead, they methodically explore the configuration space: trying different client concurrency levels (-j 2, -j 3, -j 4), different synthesis_lookahead values, and different synthesis_concurrency settings. The subsequent messages ([msg 1875] through [msg 1881]) show this exploration, eventually finding that synthesis_concurrency=2 with -j 2 yields 42.2s/proof — a more respectable 7% improvement over the 45.3s baseline, with GPU utilization reaching 99.3%.

But the fundamental lesson remains: parallel synthesis alone cannot fully close the gap. The assistant concludes in the chunk summary that "further throughput gains require reducing the absolute CPU time of synthesis (e.g., via the proposed Phase 5 Wave 2/3 optimizations like specialized MatVec and pre-sorted SRS) or decoupling the CPU workloads, rather than simply adding more parallelism to the existing architecture."

Conclusion

Message 1873 captures a pivotal moment in the optimization of a high-performance Groth16 proving engine. It is the moment when a clean theoretical fix meets messy empirical reality. The parallel synthesis implementation was correct, the waterfall instrumentation was informative, and the analysis was thorough. Yet the results defied simple expectations because the system's resources are not independent — the CPU is a shared substrate for both synthesis and GPU-accelerated proving, and contention is unavoidable without deeper architectural changes.

The message is valuable not because it solved the problem, but because it reframed it. The question shifted from "how do we keep the GPU busy?" to "how do we reduce the total CPU work such that the GPU never has to wait?" This reframing points toward the next wave of optimizations: algorithmic improvements to synthesis itself, rather than purely architectural changes to the pipeline. In the end, the law of diminishing returns applies to parallelization just as it applies to all optimization work — each successive improvement yields smaller gains and reveals deeper constraints.