The Resource Deadlock That Almost Was: Designing Phase 10's Two-Lock Architecture for GPU-Proving Overlap

Introduction

In the high-stakes world of Filecoin SNARK proving, every millisecond counts. The cuzk project—a persistent GPU-resident SNARK proving engine—had just completed Phase 9, which cut GPU kernel time by 51% through PCIe transfer optimization. But this victory revealed a new bottleneck: the CPU critical path of prep_msm (1.9s) and b_g2_msm (0.48s) now dominated the per-partition wall time at ~2.4s, leaving the GPU idle for 600ms every partition. The user proposed a bold architectural change: split the single GPU mutex into two locks—a compute_mtx for GPU kernel execution and a mem_mtx for VRAM management—to better overlap CPU and GPU work across multiple workers.

Message 2575 captures the assistant's deep design analysis of this proposal. It is a masterclass in concurrent systems thinking under severe hardware constraints, where the assistant systematically identifies a resource deadlock, designs a cooperative handoff protocol, discovers a fundamental conflict with GPU kernel lifetime, and ultimately asks the critical question that determines whether the entire approach is viable. This message is the intellectual pivot point of Phase 10—the moment where a seemingly clean software abstraction collides with the unforgiving physics of GPU memory capacity.

The Context: A Bottleneck Shift

To understand why message 2575 matters, we must first understand what Phase 9 had accomplished and what problem Phase 10 needed to solve.

Phase 9 introduced pre-staging of NTT buffers onto the GPU, exploiting PCIe Gen5 bandwidth to cut GPU kernel execution from 3.75s to 1.82s per partition. This was a dramatic improvement—a 51% reduction in GPU time. But the overall throughput only improved 14% (from 37.4s to 32.1s per proof in isolation, and ~41s under high concurrency). The bottleneck had shifted from the GPU to the CPU.

The critical path was now:

The Deadlock Analysis

Message 2575 opens with the assistant having just received a comprehensive VRAM allocation trace from a subagent task. This trace mapped every cudaMalloc, cudaFree, and memory operation across the entire partition proof lifecycle. With this data in hand, the assistant could finally analyze the two-lock design rigorously.

The first thing the assistant does is validate the user's deadlock concern. The user had warned that the locks needed to be "ordered correctly to not deadleck." The assistant formalizes this into a concrete scenario:

Worker A: holds compute_mtx
          → kernels done, needs mem_mtx to free 12 GiB
          → BLOCKED waiting for mem_mtx

Worker B: holds mem_mtx
          → needs to cudaMalloc 12 GiB, but VRAM is full (A hasn't freed yet)
          → cudaMalloc blocks internally waiting for VRAM
          → can never release mem_mtx

The assistant correctly identifies this as a resource deadlock—not a lock-ordering deadlock (which would be resolved by acquiring locks in a consistent global order), but a capacity deadlock. Worker B holds mem_mtx but cannot complete its cudaMalloc because Worker A hasn't freed its 12 GiB buffers. Worker A holds compute_mtx but cannot free because it needs mem_mtx. Neither can proceed.

This distinction is crucial. A lock-ordering deadlock can be prevented by establishing a hierarchy (e.g., always acquire compute_mtx before mem_mtx). A resource deadlock requires a fundamentally different approach—you must ensure that the resource (VRAM) is never in a state where one thread holds a lock needed by another thread to release the resource.

The assistant then states the fundamental constraint with remarkable clarity:

peak VRAM during H-MSM is ~13.8 GiB (d_a 4G + d_bc 8G + msm buckets 184M + msm d_temp 1.6G). On a 16 GiB GPU, there's no room for TWO workers' pre-staged buffers to coexist. So the alloc and free MUST be serialized — you can't have Worker B pre-stage while Worker A's buffers are still live.

This is the key insight that shapes everything that follows. The VRAM capacity is the immovable constraint. No amount of clever locking can change the fact that a 16 GiB GPU cannot hold two 12 GiB pre-staged allocations simultaneously. The two-lock design cannot achieve its primary goal—overlapping pre-staging with kernel execution—because the hardware simply doesn't have enough memory.

The Cooperative Handoff Design

Despite this constraint, the assistant doesn't abandon the two-lock approach. Instead, it pivots to a different goal: using the lock split to enable a cooperative handoff protocol that avoids the deadlock entirely.

The proposed design is elegant:

Worker flow:
1. [no lock] CPU: cudaHostRegister, prep_msm starts
2. lock(mem_mtx)
   - If predecessor left buffers to free: free them now
   - pool_trim + cudaMemGetInfo
   - cudaMalloc d_a + d_bc (12 GiB)
   - async upload to upload_stream
   unlock(mem_mtx)
3. lock(compute_mtx)
   - stream.wait(upload_events)
   - NTT + batch_add + tail_msm kernels
   - Register our d_bc/d_a/events in a "to_free" slot
   unlock(compute_mtx)
4. [no lock] CPU: cudaHostUnregister, b_g2_msm join, epilogue

The key innovation is the shared to_free slot. Instead of each worker freeing its own buffers, the next worker frees the predecessor's buffers at step 2, before allocating its own. This eliminates the need for nested locks entirely:

The Critical Flaw: Kernel Lifetime

But then the assistant catches a critical flaw in its own design:

But wait — there's a critical problem: the GPU kernels in step 3 are still USING d_a during H-MSM. We can't let the next worker free d_a while kernels are running.

The d_a buffer (4 GiB) is used throughout the H-MSM computation, which runs inside compute_mtx. If the next worker frees d_a at step 2 of its own flow, it might free memory that the previous worker's kernels are still actively reading. This is a use-after-free bug on the GPU—a class of error that can cause silent data corruption or GPU crashes.

The assistant proposes a solution: the to_free handoff happens at the END of compute (after kernels finish, inside compute_mtx), and the next worker's mem_mtx acquisition does a cudaDeviceSynchronize to ensure the predecessor's kernels actually finished before freeing.

But this brings the design back to the same problem. If the next worker must wait for the predecessor's kernels to finish before it can free and allocate, then the serialization is still there. The cudaDeviceSynchronize is a device-global operation that blocks until all kernels on the device complete—effectively serializing the two workers.

The assistant recognizes this tension and pivots to a direct question to the user about VRAM capacity:

Actually, this brings us back to the same problem. Let me reconsider whether there's actually room for this on 16 GiB.

The question presents two options:

  1. Proceed with two-lock + 3 workers: Split locks, free d_a/events under mem_mtx only. Aim to overlap b_g2_msm + epilogue with next worker's compute. Theoretical gain: ~600ms/partition.
  2. Abandon two-lock, keep single mutex: The VRAM constraint makes two-lock impossible. Focus on other optimizations. The user's answer (visible in the conversation data) chooses option 1, acknowledging that pre-staging must be serialized but that there IS a viable win from overlapping the CPU prep_msm + b_g2_msm with the next worker's GPU compute. This sets the stage for the actual Phase 10 implementation.

Assumptions and Knowledge

This message rests on several key assumptions and bodies of knowledge:

Assumptions:

Thinking Process and Reasoning Quality

What makes message 2575 exceptional is the quality of its reasoning. The assistant doesn't just accept or reject the user's proposal—it systematically analyzes it, discovers a subtle deadlock scenario, designs a workaround, finds a flaw in its own workaround, and then frames the remaining question for the user to decide.

The reasoning follows a clear structure:

  1. Validate the concern: The assistant immediately confirms the user's deadlock worry is real and formalizes it with a concrete scenario.
  2. Classify the deadlock type: By distinguishing resource deadlock from lock-ordering deadlock, the assistant demonstrates deep understanding of concurrent systems theory. This classification matters because it determines what solutions are viable.
  3. Identify the root constraint: The VRAM capacity of 13.8 GiB peak on a 16 GiB GPU is identified as the fundamental limiting factor. This grounds the discussion in physical reality.
  4. Design a solution within constraints: The cooperative handoff protocol is a creative workaround that avoids the deadlock without requiring more VRAM.
  5. Self-critique the solution: The assistant catches its own design flaw—the kernel lifetime issue—before the user has to point it out. This self-correction is a hallmark of rigorous engineering thinking.
  6. Frame the decision: Rather than pushing forward with a flawed design, the assistant asks the user to make the call, presenting the tradeoffs clearly. The message also shows the assistant's willingness to change its mind. Earlier in the conversation (msg 2573), the assistant had proposed a nested locking approach. By msg 2575, after analyzing the VRAM trace, it has abandoned that approach in favor of the cooperative handoff. This intellectual flexibility is a strength.

Mistakes and Incorrect Assumptions

The message is remarkably free of outright mistakes, but there are a few areas where the assistant's analysis is incomplete or potentially incorrect:

The cudaMalloc behavior assumption: The assistant assumes that cudaMalloc will "block internally waiting for VRAM" when memory is exhausted. In reality, CUDA driver behavior on allocation failure depends on the memory pool configuration and the CUDA version. With cudaMemPoolTrimTo being called before allocation, the behavior might be different. The assistant hedges this correctly by saying "depending on the CUDA driver behavior."

The cooperative handoff's cudaDeviceSynchronize problem: The assistant identifies that the next worker would need to call cudaDeviceSynchronize before freeing the predecessor's buffers, but doesn't fully analyze the performance implications of this device-global synchronization. In practice, cudaDeviceSynchronize would serialize all pending operations on the device, potentially destroying any overlap benefit. This issue would later manifest in the Phase 10 implementation as the root cause of performance regression.

The assumption that d_a and d_bc are the only large allocations: The VRAM trace focused on the pre-staged buffers, but there may be other transient allocations (e.g., MSM temporary buffers) that affect the peak memory calculation. The assistant's 13.8 GiB figure may be an underestimate.

The missing analysis of upload_stream synchronization: The design assumes that the async upload completes before the kernels start, via stream.wait(upload_events). But if the upload stream and compute stream are different streams, the synchronization must be correct. The assistant doesn't analyze whether the existing stream/event infrastructure supports this pattern.

The Broader Significance

Message 2575 is a microcosm of the entire cuzk optimization journey. The project has been a series of bottleneck shifts: from CPU synthesis to GPU kernels, from GPU kernels to PCIe transfers, from PCIe transfers to CPU memory bandwidth. Each optimization reveals the next constraint. Phase 10 represents the attempt to address the CPU memory bandwidth bottleneck by architectural means—more workers, better overlap—rather than by algorithmic changes.

The message also illustrates a recurring theme in systems optimization: the tension between software abstractions and hardware constraints. The two-lock design is a clean software abstraction—separating memory management from computation into two independent locks. But the hardware (a single GPU with 16 GiB of VRAM and device-global synchronization semantics) refuses to honor this abstraction. The locks cannot be truly independent because the operations they protect interact through shared resources (VRAM capacity, device-wide synchronization barriers).

This is a lesson that extends far beyond GPU proving. Any system that attempts to parallelize access to a shared, capacity-constrained resource must contend with the fact that the resource itself imposes a serialization order that no amount of locking can eliminate. The locks can only control access to the resource, not the resource's capacity.

Conclusion

Message 2575 is the intellectual pivot point of Phase 10—the moment where a promising architectural idea meets the unforgiving reality of GPU memory constraints. The assistant's analysis is thorough, rigorous, and self-critical. It identifies a resource deadlock, designs a cooperative handoff protocol, discovers a fundamental conflict with kernel lifetimes, and frames the critical decision for the user.

The message demonstrates what makes great systems engineering: the ability to reason about concurrency at multiple levels (lock ordering, resource capacity, device semantics), to design creative solutions within constraints, and to recognize when a design has reached its limits. The cooperative handoff protocol, though ultimately not the final solution, is a beautiful piece of concurrent design that shows deep understanding of both CUDA programming and deadlock theory.

In the next chunk, the assistant would implement the two-lock design based on the user's decision, only to discover that cudaDeviceSynchronize and cudaMemPoolTrimTo inside mem_mtx are device-global operations that effectively serialize the two locks, causing OOM failures and performance regression. The analysis in message 2575 correctly identified the theoretical deadlock but underestimated the practical impact of device-global synchronization—a reminder that in GPU programming, the gap between theory and practice is often measured in milliseconds of unexpected serialization.