The Waterfall That Revealed the Ceiling: Diagnosing and Addressing the GPU Idle Gap in the cuzk Proving Engine

Introduction

In the relentless pursuit of Filecoin proof generation efficiency, the cuzk proving engine had already undergone five phases of systematic optimization. Phase 0 established the core daemon architecture with gRPC API and priority scheduling. Phase 1 extended support to all four Filecoin proof types. Phase 2 introduced the pipelined architecture that decoupled CPU-bound circuit synthesis from GPU-accelerated proving via a bounded channel. Phase 3 added cross-sector batching for a 1.46× throughput improvement. Phase 4 delivered compute-level synthesis optimizations yielding a 13.2% end-to-end gain. Phase 5 implemented the Pre-Compiled Constraint Evaluator (PCE) to eliminate redundant constraint generation. Phase 6 introduced the slotted partition pipeline for finer-grained overlap. Each phase had moved the needle, but by the end of Phase 6, a stubborn performance ceiling remained.

The benchmark data told a clear story: the standard pipeline (slot_size=0) achieved approximately 45.3 seconds per proof, with the GPU processing each proof in roughly 27 seconds. Yet the pipeline was not keeping the GPU continuously busy — there were idle gaps between proofs. The question was whether these gaps were structural (an architectural limitation) or incidental (a configuration tuning issue), and whether closing them would yield proportional throughput gains.

This article synthesizes the work of Segment 21, which represents a complete optimization cycle: from diagnosis through intervention to the sobering discovery of diminishing returns. The arc begins with the implementation of a detailed waterfall timeline instrumentation system that revealed a structural GPU idle gap of approximately 12 seconds per proof cycle. It proceeds through the design and implementation of parallel synthesis using a tokio::sync::Semaphore, which successfully saturated the GPU to 99.3% utilization. And it culminates in the paradoxical finding that near-perfect GPU utilization yielded only a 5–7% throughput improvement — because the bottleneck had merely shifted from the GPU to the CPU, where resource contention between parallel synthesis tasks and the GPU prover's CPU-bound b_g2_msm step created a new ceiling.

This is a case study in the art of performance engineering: the critical importance of instrumentation before optimization, the power of precise measurement to reveal hidden bottlenecks, and the sobering reality that fixing one bottleneck merely reveals the next. 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.

The Fork in the Road: Three Paths Forward

The segment opens with the assistant facing a fork in the road ([msg 1821]). Three forward paths for optimization lay ahead, each with uncertain payoff. Rather than committing to any of them, the assistant insisted on first building a measurement framework that would convert hypotheses into empirical data. This methodological choice — instrument before optimizing — proved critical to everything that followed.

The assistant recognized that the existing benchmark metrics (total time, prove time, queue time) were insufficient to diagnose the pipeline's behavior. What was needed was a precise, event-level timeline showing exactly when each phase of each proof started and ended, with wall-clock timestamps. Only with such data could the assistant determine whether the GPU was truly being starved, and if so, by how much and why.

This decision reflects a mature engineering discipline. In many optimization efforts, the temptation is to jump directly to a fix — "the GPU is idle, so we need more parallelism" — without first quantifying the gap or understanding its root cause. The assistant's insistence on measurement first prevented wasted effort on the wrong solution and ensured that whatever intervention was attempted would have a clear, falsifiable hypothesis behind it.

Building the Waterfall Timeline Instrumentation

The resulting "waterfall timeline" instrumentation was a custom logging system that recorded wall-clock timestamps for every phase of the proving pipeline. The assistant added structured TIMELINE log lines that captured five critical events for each proof:

SYNTH_START — when circuit synthesis began
SYNTH_END — when circuit synthesis completed
CHAN_SEND — when the synthesized data was sent to the GPU channel
GPU_START — when the GPU prover began processing
GPU_END — when the GPU prover completed These log lines were emitted to stderr using eprintln!, separate from the normal tracing output, making them easy to extract and parse. The assistant also wrote a Python script (/tmp/cuzk-waterfall.py) that parsed these structured log lines and rendered them as an ASCII waterfall visualization — a Gantt-style chart showing exactly where time was spent and where parallelism was lost. The choice of ASCII rendering was deliberate: it allowed the assistant to inspect the timeline directly in the terminal without needing external visualization tools, making the debugging loop tight and interactive. The waterfall chart used S characters to represent synthesis duration and G characters to represent GPU duration, with time flowing left to right. This simple visualization proved remarkably effective at communicating the pipeline's behavior at a glance.

The Waterfall Reveals the Gap

The waterfall data, analyzed across multiple messages ([msg 1850] through [msg 1854]), was devastatingly clear. Each proof's synthesis ran strictly sequentially — no proof's synthesis began until the previous proof's synthesis completed. Meanwhile, the GPU processed each proof in approximately 27 seconds, but had to wait approximately 12 seconds between proofs for the next synthesis to finish.

The waterfall visualization told the story in stark ASCII:

        P1  SSSSSSSSSGGGGGGGG
        P2           SSSSSSSSSSSGGGGGGGG
        P3                      SSSSSSSSSSSGGGGGGGG
        P4                                 SSSSSSSSSSGGGGGGGG
        P5                                           SSSSSSSSSSSGGGGGGGGG

The pattern was unmistakable: each proof's synthesis bar started exactly where the previous proof's synthesis bar ended. The GPU bars (G) were shorter than the synthesis bars (S), and the gap between consecutive GPU bars was exactly the difference. The numbers quantified the observation:

| Metric | Value | |---|---| | Synthesis time per proof | 37–41 seconds (avg ~39s) | | GPU time per proof | 26–28 seconds (avg ~27s) | | GPU idle gap | 12–14 seconds per proof | | GPU utilization | 70.9% |

The gap was structural, not incidental. It was synth_time - gpu_time = 39s - 27s = 12s. Since synthesis was strictly sequential and took longer than GPU proving, the GPU was forced to idle after finishing proof N until synthesis of proof N+1 completed. This was not a hardware limitation — the assistant checked system memory ([msg 1855]) and found 754 GiB total RAM with 490 GiB available, plenty of headroom for running multiple syntheses concurrently. The sequential synthesis was purely an architectural choice baked into the engine's design.

The waterfall analysis transformed an abstract suspicion into a precisely quantified bottleneck with a clear remedy: close the 12-second gap by running multiple syntheses in parallel. If two syntheses could run concurrently, the effective inter-arrival time of proofs to the GPU would halve from ~39 seconds to ~20 seconds, which is less than the GPU's 27-second processing time. The GPU would never idle.

Designing Parallel Synthesis with a Semaphore

The assistant's reasoning in [msg 1857] is compact but dense. Three key architectural facts drove the design:

The blocking pattern: The engine's synthesis task loop called process_batch().await, which blocked the loop from accepting new work until the current synthesis completed. This was the root cause of sequential synthesis.
The required mechanism: process_batch had to be spawned as a fire-and-forget task rather than awaited inline. This would allow the loop to immediately return to the scheduler and pull the next request.
The concurrency control: A semaphore was needed to limit how many concurrent syntheses could run, preventing memory exhaustion. Each synthesis holds approximately 136 GiB of intermediate data (10 partitions), so two concurrent syntheses would require ~272 GiB just for synthesis, plus PCE (26 GiB) and SRS (44 GiB) for a total of ~342 GiB. The machine had sufficient RAM, but uncontrolled parallelism could easily exhaust it. The assistant chose to wrap process_batch calls in tokio::spawn and use a tokio::sync::Semaphore to cap concurrency. This design respected the existing codebase architecture (which already used Tokio extensively) and correctly handled the need to share the GPU channel (synth_tx) across tasks. The synthesis loop could keep pulling from the scheduler as long as semaphore permits were available, decoupling the rate of job acceptance from the rate of job completion. The implementation was cleanly integrated across several files: - config.rs ([msg 1858]): A new synthesis_concurrency configuration parameter was added to the engine's config, defaulting to 1 (preserving backward compatibility). - engine.rs ([msg 1862]): The synthesis task loop was refactored. Instead of awaiting process_batch inline, the loop now acquires a semaphore permit and spawns the synthesis work as a separate task. The loop immediately returns to pull the next request from the scheduler, allowing multiple syntheses to run concurrently up to the semaphore limit. - cuzk.example.toml ([msg 1864]): The example configuration was updated to document the new parameter. The build succeeded cleanly ([msg 1865]), and the daemon was started with the new parallel synthesis infrastructure ([msg 1869]). The stage was set for the moment of truth.

The Moment of Truth: Benchmarking Parallel Synthesis

The assistant started the daemon with synthesis_concurrency=2 and ran an initial benchmark with 5 proofs at client concurrency -j 3 ([msg 1871]). The initial result was underwhelming: 44.7 seconds per proof versus 45.3 seconds per proof baseline — a mere 1.3% improvement. Given the dramatic change to the pipeline architecture, this was disappointing.

The assistant's immediate response — running the waterfall visualization — demonstrated disciplined engineering. The waterfall revealed that parallel synthesis was working as designed: two proofs (P1 and P2) started synthesis simultaneously, and the GPU idle gaps between the first two proofs were essentially zero. GPU utilization jumped from 70.9% to 86.5%.

But two problems emerged ([msg 1873]):

1. Synthesis time inflation. When two syntheses ran concurrently, each took longer due to CPU/memory contention. P1 alone completed in 38 seconds, but P2 (running concurrently with P1) took 54 seconds — 42% slower. The extreme case was P4, which took 97 seconds because it overlapped with P3 and P5. The rayon thread pool, shared across all synthesis tasks, was being partitioned between competing workloads. With 96 CPU cores available, a single synthesis could use all 96 cores. With two concurrent syntheses, each got approximately 48 cores (though the actual division was dynamic and depended 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 did not simply double the time; it increased time by 42% or more due to these inefficiencies.

2. GPU time inflation. GPU prove time increased from an average of 27 seconds to 32–37 seconds. This was because the GPU proving phase includes a CPU-bound step called b_g2_msm (multi-scalar multiplication on the G2 curve), which uses multi-threaded Pippenger and competes with synthesis for CPU cores. With two syntheses and the GPU's CPU step all fighting for the same 96 cores, everything slowed down.

The assistant refined the experiment, running 8 proofs at -j 3 with synthesis_concurrency=2 ([msg 1875]). This time, GPU utilization reached 99.3% — a stunning achievement. The GPU idle gaps were essentially eliminated. The waterfall showed the pipeline working beautifully, with consecutive GPU bars touching each other.

Yet throughput improved only to 43.0 seconds per proof — a 5% gain over the 45.3-second baseline. The paradox was clear: near-perfect GPU utilization, but minimal throughput improvement. The assistant compiled a comparison table that told the story:

| Config | s/proof | proofs/min | GPU util | GPU avg | Synth avg | |---|---|---|---|---|---| | concurrency=1 (old) | 45.3 | 1.326 | 70.9% | 26.7s | 39.3s | | concurrency=2 | 43.0 | 1.395 | 99.3% | 37.6s | 47.2s |

GPU utilization was way up, but GPU time was way up too. The net gain was small because CPU contention inflated both synthesis and GPU times. The bottleneck had shifted.

Exploring the Configuration Space

The assistant systematically explored the configuration space to understand the system's response surface. The key parameters were:

synthesis_concurrency: The number of concurrent synthesis tasks (set to 2).
Client concurrency (-j): The number of in-flight proofs submitted by the benchmark tool.
synthesis_lookahead: The capacity of the channel buffer between synthesis and GPU. The assistant tested three client concurrency levels: -j 2 (starved pipeline): With only 2 in-flight proofs, the pipeline was starved ([msg 1878]). The benchmark tool could not submit new proofs fast enough to keep the synthesis tasks busy. The result was 42.2 seconds per proof — actually the best result of all the tests, at 1.422 proofs/min. But this was because the lower concurrency reduced CPU contention, even though it left the pipeline underutilized. The waterfall showed that with -j 2, the two syntheses ran cleanly without piling up, and GPU times stayed lower (avg ~29s) because there was less CPU competition. -j 3 (sweet spot): With 3 in-flight proofs and synthesis_concurrency=2, the pipeline achieved 99.3% GPU utilization and 43.0 seconds per proof. This was a 5% improvement over the baseline. The system was balanced: the semaphore allowed 2 syntheses at once, and the third request queued up, providing backpressure that kept the pipeline fed without overwhelming the CPU. -j 4 (catastrophic contention): With 4 in-flight proofs, the system collapsed ([msg 1881]). The result was 60.2 seconds per proof — worse than the original sequential baseline. The assistant's diagnosis was precise: "The CPU is completely saturated with 2 concurrent syntheses already." With 4 client requests arriving simultaneously, the semaphore allowed 2 syntheses at once, but the 3rd and 4th piled up in the queue, creating scheduling pathologies that cascaded through the entire pipeline. P2's GPU time ballooned to 118 seconds — a 4.4× increase over normal — because b_g2_msm was completely starved of CPU resources. The contention with -j 4 was catastrophic, demonstrating that the system had a nonlinear response to client concurrency: -j 2 starved the pipeline, -j 3 was the sweet spot, and -j 4 was disastrous.

The Shifting Bottleneck: CPU Contention

The assistant's analysis across multiple messages ([msg 1875], [msg 1877], [msg 1878]) traced the root cause with precision. The system has 96 CPU cores. Under sequential synthesis, a single synthesis task could use all 96 cores via rayon's parallel thread pool, completing in approximately 39 seconds. With two concurrent syntheses, each got approximately 48 cores. 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 did not simply double the time; it increased time by 42% or more due to these inefficiencies.

Furthermore, the GPU prover's b_g2_msm step also competed for these same cores. This created a three-way contention: two synthesis tasks and one GPU CPU-step all fighting for the 96-core thread pool. The result was that everything slowed down. GPU prove time inflated from 26.7 seconds to 37.6 seconds — a 41% increase — because the CPU-bound b_g2_msm was starved for cores.

The b_g2_msm step is particularly insidious because it runs during what is nominally the "GPU phase" of proof generation. The GPU handles the bulk of the MSM computation, but a portion of the G2 multi-scalar multiplication is performed on the CPU using multi-threaded Pippenger's algorithm. This CPU-bound component is not optional — it is an inherent part of the Groth16 proving protocol. The implication is profound: the GPU prover is not purely a GPU workload. It has a significant CPU footprint that must be accounted for in any pipeline design.

The assistant considered several mitigations:

Limiting rayon's thread pool during synthesis to leave headroom for GPU's CPU work. This would require a deeper change to how rayon is configured, potentially using a custom thread pool with a reduced thread count for synthesis tasks.
Using separate thread pools for synthesis and GPU CPU work, preventing them from competing for the same cores. This is architecturally more complex but could yield better isolation.
Reducing the absolute CPU time of synthesis through algorithmic improvements, which was already planned as Phase 5 Wave 2/3 optimizations. The assistant correctly identified that the first two options were band-aids — they would reduce contention but not address the fundamental issue that synthesis is too CPU-intensive. The third option was the real path forward.

The Law of Diminishing Returns

The overarching theme of this segment is the law of diminishing returns in pipeline optimization. The assistant had successfully closed the GPU idle gap — a textbook pipeline optimization. GPU utilization reached 99.3%. Yet the net throughput improvement was only 5–7% because the optimization addressed the wrong layer of the bottleneck hierarchy.

This is a universal pattern in systems 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 was invisible in a waterfall — it manifested as inflated bar lengths rather than gaps between bars.

The assistant's disciplined approach — immediately comparing utilization against throughput, quantifying the inflation in both synthesis and GPU times, and systematically exploring the configuration space — is a model of rigorous engineering analysis. The waterfall instrumentation, built precisely for this moment, proved its value by making the invisible visible. Without the waterfall, the assistant might have concluded that parallel synthesis was ineffective and abandoned the approach. With the waterfall, the assistant could see that parallel synthesis was working exactly as designed — it was the system's resource dependencies that limited the gain.

The key insight is that GPU utilization is a misleading metric when the GPU workload has a significant CPU component. High GPU utilization can coexist with poor overall throughput if the CPU is the true bottleneck. The assistant's analysis correctly identified that the 99.3% GPU utilization figure was a pyrrhic victory — it came at the cost of 41% inflated GPU times due to CPU starvation.

What Was Learned

This segment produced several critical pieces of knowledge that will inform future optimization efforts:

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

Quantified synthesis time inflation under concurrency. Concurrent synthesis inflated 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. The relationship is not linear — halving the available cores does not double the time, but increases it by a factor of 1.42× or more due to synchronization overhead and memory bandwidth saturation.

Evidence that GPU time is not independent of CPU load. The increase from 27s to 37.6s average GPU time demonstrated that the GPU prover's CPU-bound components are significant and must be accounted for in pipeline design. The b_g2_msm step is a first-class citizen in the CPU resource allocation problem, not a minor overhead.

A refined understanding of the optimization landscape. The remaining optimization space was mapped: reduce synthesis CPU time (via specialized MatVec operations, 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.

A documented failure mode. Excessive client concurrency combined with parallel synthesis led to CPU thrashing between synthesis and b_g2_msm, inflating GPU prove times by up to 4.4×. The system had a nonlinear response to client concurrency: -j 2 starved the pipeline, -j 3 was the sweet spot, and -j 4 was catastrophic. This nonlinearity means that careful tuning is required for each deployment configuration.

The Path Forward

The segment concludes with a clear-eyed assessment of what needs to be done next. The assistant identified that further throughput gains require reducing the absolute CPU time of synthesis — through the Phase 5 Wave 2/3 optimizations like specialized MatVec kernels and pre-sorted SRS access patterns — or decoupling the CPU workloads through thread pool isolation. Simply adding more parallelism to the existing architecture had reached its limit.

This insight reframes the entire optimization problem. The low-hanging fruit has been picked. The remaining gains require deeper architectural changes — algorithmic improvements to synthesis itself, rather than purely architectural changes to the pipeline. The waterfall instrumentation, the parallel synthesis implementation, and the benchmarking campaign have together produced a detailed map of the system's performance landscape. The next engineer to work on this system — whether human or AI — will have a running start.

The specific next steps identified include:

Phase 5 Wave 2 optimizations: Specialized MatVec operations that exploit the known structure of Filecoin's constraint systems (SHA-256 dominance, boolean witnesses) to reduce CPU time.
Phase 5 Wave 3 optimizations: Pre-sorted SRS access patterns that eliminate random-access overhead and improve cache locality during synthesis.
Thread pool isolation: Separating the rayon thread pools used by synthesis and GPU CPU work to prevent them from competing for the same cores. This could be implemented as a configuration option that limits the number of threads available to synthesis tasks.
Core pinning: Pinning specific CPU cores to specific workloads (synthesis, GPU CPU work, system tasks) to eliminate contention entirely. This is a more advanced technique that requires operating system support and careful benchmarking.
Asynchronous GPU submission: Exploring whether the GPU's CPU-bound work can be overlapped with synthesis more aggressively, perhaps by submitting GPU work asynchronously and using the CPU idle time during GPU execution for additional synthesis.

Conclusion

Segment 21 of the cuzk proving engine optimization journey is a case study in the art of performance engineering. It demonstrates the critical importance of instrumentation before optimization, the power of precise measurement to reveal hidden bottlenecks, and the sobering reality that fixing one bottleneck merely reveals the next. The parallel synthesis implementation was technically sound and correctly executed. The waterfall instrumentation was informative and well-designed. The analysis was thorough and honest. 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 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. The lesson is not that parallel synthesis was a failure — it successfully saturated the GPU and provided a 5–7% throughput improvement — but that the next wave of optimization must target the fundamental CPU cost of synthesis itself. That insight, hard-won through measurement and iteration, is the most valuable output of this entire optimization cycle.

The waterfall timeline instrumentation, in particular, proved its worth as a diagnostic tool. It revealed the GPU idle gap, confirmed that parallel synthesis closed it, and then revealed the CPU contention that limited the gain. Without the waterfall, the assistant would have been flying blind. With it, every intervention was guided by empirical data. This methodological lesson — instrument first, optimize second — is perhaps the most important takeaway for anyone engaged in performance engineering of complex hardware-software pipelines.

The cuzk proving engine is now at a critical juncture. The architectural optimizations (pipelining, batching, parallel synthesis) have been largely exhausted. The remaining gains require algorithmic improvements to the core synthesis logic. This is a fundamentally harder problem, but also one with potentially larger rewards. The Phase 5 Wave 2/3 optimizations — specialized MatVec, pre-sorted SRS, and constraint-structure exploitation — target the synthesis CPU time directly, which is now confirmed as the primary bottleneck. If these optimizations can reduce synthesis time by even 20–30%, the throughput improvement would be significant and would not suffer from the contention problems that limited parallel synthesis.

The path forward is clear, even if the work is hard. The cuzk engine's performance landscape has been mapped. The bottlenecks have been identified and quantified. The next phase of optimization will require deeper algorithmic work, but the payoff — a faster, more efficient Filecoin proof generation pipeline — is well worth the effort.## References

The Law of Diminishing Returns: When Saturating the GPU Reveals the CPU Bottleneck — The companion chunk article covering the same optimization cycle with a focus on the GPU saturation and CPU bottleneck discovery.