The P-Controller Epiphany: Redesigning GPU Pipeline Dispatch from Semaphore to Deficit-Based Scheduling

Introduction

In the high-stakes world of zero-knowledge proof generation, every millisecond of GPU idle time represents wasted computational capacity and delayed returns. The cuzk proving engine, a specialized system for generating Groth16 proofs at scale, had already achieved remarkable improvements through a pinned memory pool that eliminated the primary bottleneck of host-to-device (H2D) PCIe transfers. Yet the system remained unstable—not because of hardware limitations, but because of a fundamental flaw in how the dispatch scheduler decided when to start new synthesis work.

The subject message at index 3361 captures a pivotal moment in the iterative refinement of this dispatch scheduler. In this message, the assistant—an AI agent working collaboratively with a human developer—engages in an extended reasoning session to redesign the GPU pipeline dispatch mechanism. The core insight is a shift from a semaphore-based permit system to a deficit-based proportional controller (P-controller) that targets a specific queue depth of synthesized partitions waiting for the GPU. This message is remarkable not just for the technical depth of its reasoning, but for the way it exposes the thinking process of an AI system grappling with a complex control systems problem in real-time.

This article provides a deep analysis of message 3361, examining the reasoning, assumptions, decisions, and knowledge structures that make it a fascinating case study in AI-assisted software engineering.

The Context: A Pipeline in Flux

To understand message 3361, we must first understand the broader context of the cuzk proving pipeline. The system generates Groth16 proofs—a form of zero-knowledge proof used in blockchain applications like Filecoin—by processing partitions of data through a multi-stage pipeline. Each partition goes through synthesis (CPU-bound circuit evaluation) followed by GPU proving (CUDA-based multi-scalar multiplication and other cryptographic operations). The goal is to keep the GPU maximally utilized while minimizing memory pressure from excessive concurrent synthesis.

The session preceding message 3361 had been intensely focused on GPU utilization. The team had identified that H2D transfers from unpinned host memory were causing 2-14 second stalls per partition, and had implemented a CUDA pinned memory pool (PinnedPool) that reduced these transfers to near-zero milliseconds. They had also deployed a reactive dispatch throttle using a tokio::sync::Semaphore with a configurable number of permits (default 8). The idea was simple: the dispatcher acquires a permit before starting synthesis, and the GPU finalizer returns a permit after completing a proof. This limits the total number of in-flight partitions (synthesis + waiting + on-GPU) to the permit count.

But as the user pointed out in message 3356, this approach was fundamentally wrong:

"Didn't want 8 basic 'permits', that's actually wrong way to modulate scheduling; We want 8 waiting pipelines (well N, 8 is maybe high but let's start here). When GPU finishes a job, we should look at how many synthesis are Waiting, then if that number is greater than target (N, default 8) don't start new synths, if it's anything below the target start this many synths as we are below the target."

This single message from the user triggered the extended reasoning session that constitutes message 3361.

The Flawed Semaphore Model: Why Permits Failed

The assistant begins message 3361 by articulating the problem with the current mechanism:

"The current mechanism uses a semaphore with N permits - the dispatcher acquires a permit before starting synthesis, and the GPU finalizer returns a permit. This means it limits the total number of in-flight partitions (synthesis + waiting + on-GPU)."

This is a critical distinction. The semaphore model treats all in-flight work as equivalent—whether a partition is being synthesized, sitting in the GPU queue, or actively being processed by the GPU, it consumes one permit. This creates a system that is reactive in the wrong way: it limits the total pipeline depth rather than the GPU queue depth. The result is that the system can have many partitions in synthesis (consuming memory) while the GPU queue is empty, or it can have a full GPU queue while synthesis is stalled—neither of which is optimal.

The user's insight was that the correct control variable is the number of partitions waiting for the GPU (i.e., fully synthesized and queued), not the total in-flight count. This is because the GPU queue depth directly determines whether the GPU will have work to do when it finishes its current job. A deep GPU queue ensures the GPU never idles; a shallow queue risks starvation. The semaphore model conflated this with memory pressure from synthesis, leading to suboptimal trade-offs.

The Agent's Reasoning Journey: From Semaphore to P-Controller

What makes message 3361 so compelling is the visible arc of the assistant's reasoning. The message is structured as a stream-of-consciousness exploration of the problem space, with the assistant iteratively refining its understanding and proposed solution. Let us trace this journey step by step.

Phase 1: Understanding the Desired Model

The assistant immediately grasps the user's intent:

"The user wants a different model: - Target N partitions waiting in gpu_work_queue (synthesized, ready for GPU) - When GPU finishes a job, check gpu_work_queue.len() - If waiting < N, start N - waiting new syntheses - If waiting >= N, don't start any"

This is the seed of the proportional controller. The error signal is deficit = N - waiting, and the control action is to start deficit new syntheses. The gain is 1—a pure proportional controller with no integral or derivative terms.

Phase 2: Overcomplication and Simplification

The assistant then begins to overcomplicate the design:

"I need to remove the semaphore throttle, add a notification channel from the GPU finalizer back to the dispatcher, and restructure the dispatcher to wait for either new work, GPU completion signals, or startup, then check the queue depth and fill any gap up to the target."

This is followed by a moment of self-correction:

"Actually, I'm overcomplicating this. The dispatcher should simply loop: check how many items are waiting in the GPU queue, and if we're below the target N, dispatch more work from the synthesis queue. If we're at or above target, wait for a GPU completion notification before checking again. If the synthesis queue is empty, just wait regardless."

This back-and-forth between complexity and simplicity is characteristic of good engineering design. The assistant is exploring the space of possible implementations, rejecting overly complex approaches in favor of simpler ones.

Phase 3: The Timing Insight

A crucial moment occurs when the assistant identifies a timing issue:

"Actually, I'm realizing there's a timing issue here—when I dispatch synthesis work, those items are in-flight and won't show up in the GPU queue until synthesis completes. So if I'm checking the deficit against only completed items, I could end up dispatching way more synthesis tasks than intended, and then they all land in the GPU queue at once, overshooting the target."

This is the key insight that drives the entire design. The assistant realizes that the naive approach—check deficit, dispatch work, loop—would cause unbounded dispatch during ramp-up because dispatched items are invisible in the GPU queue until synthesis completes. The assistant considers tracking an in_flight counter but then re-reads the user's specification and realizes that the user wants overshoot:

"So the algorithm is: calculate the deficit as N minus the current waiting count, then spawn that many new syntheses. This naturally converges—when the first synthesis completes and waiting hits 1, the GPU starts consuming, and by the time all N initial syntheses finish, the GPU will have consumed some, leaving a gap that triggers the next batch."

This is the proportional controller in action. The overshoot is not a bug—it is a feature. By dispatching N items when the queue is empty, the system intentionally overshoots, then the GPU consumption naturally brings the queue back down, and the next dispatch cycle undershoots slightly less, converging to a steady state.

Phase 4: The Notification Mechanism

The assistant then designs the notification mechanism to replace the semaphore:

"I need to swap out the semaphore for a notification system — removing gpu_pipeline_sem and adding gpu_completion_notify that the GPU finalizer will signal. The dispatcher loop stays the same, checking deficit and dispatching work, but now it waits on the notify instead of semaphore permits."

The choice of tokio::sync::Notify over Semaphore is significant. A semaphore is a counting mechanism—it tracks how many resources are available. A notify is a signaling mechanism—it wakes up a waiting task. The shift from semaphore to notify reflects the shift from a resource-limited model (permits) to an event-driven model (GPU completions trigger dispatch decisions).

Phase 5: Edge Case Analysis

The assistant demonstrates thoroughness by walking through edge cases:

"When the dispatcher is sleeping and a GPU finishes, it wakes up and dispatches the newly available work. If two GPUs complete while the dispatcher sleeps, only one permit gets stored, but that's fine because the dispatcher will check the deficit and dispatch both items in subsequent loop iterations."

This analysis reveals a subtle property of the Notify mechanism: notify_one() stores at most one notification. If two GPU completions happen before the dispatcher wakes, only one notification is consumed, but the dispatcher's deficit check will correctly handle both because it re-evaluates gpu_work_queue.len() after each dispatch.

The assistant also considers the case where the dispatcher is waiting for work but the deficit is still positive:

"If a GPU completes but there's nothing in the queue to dispatch, the dispatcher should just keep waiting for the work queue rather than waking up unnecessarily. The GPU completion notification isn't useful if there's no actual work to send."

This is a subtle but important optimization. If the synthesis queue is empty, GPU completions shouldn't trigger dispatch attempts because there's nothing to dispatch. The dispatcher should only wake on GPU completions when it has work to send.

Phase 6: The P-Controller Formalization

The assistant formalizes the design as a proportional controller:

"I think the user wants a proportional controller where: - Error = target - waiting (= 8 - 0 = 8) - Action = start error new syntheses - This causes overshoot (too many waiting), then next time undershoot less, etc."

This is the moment where the assistant explicitly connects the dispatch mechanism to control theory. The proportional controller (P-controller) is the simplest form of feedback control: the control action is proportional to the error. In this case, the error is the deficit (target queue depth minus actual queue depth), and the control action is the number of new syntheses to start. The gain is 1, meaning we dispatch exactly as many items as the deficit.

Assumptions Made in Message 3361

The assistant's reasoning in message 3361 rests on several key assumptions, some explicit and some implicit.

Assumption 1: The GPU Queue Depth is the Right Control Variable

The assistant accepts the user's premise that targeting a specific number of waiting partitions in the GPU queue is the correct approach. This assumption is reasonable given the system's goals: the GPU should never starve for work, and memory pressure from excessive synthesis should be minimized. However, it assumes that the GPU queue depth is both a sufficient and necessary control variable. In reality, other factors—such as the memory budget, the number of GPU workers, and the synthesis throughput—also affect system performance. The P-controller implicitly handles these through feedback, but the assumption that queue depth alone is sufficient may not hold in all scenarios.

Assumption 2: Budget Will Be the Natural Bottleneck

The assistant assumes that the memory budget (budget.acquire()) will naturally limit how many syntheses can run concurrently, preventing unbounded dispatch even when the deficit is large. This is stated explicitly:

"I don't need an explicit in-flight counter; the budget and worker pool handle concurrency limits naturally."

This assumption is tested later when the user reports that only one synthesis starts per GPU completion (message 3387), revealing that budget is indeed the bottleneck but in a way that undermines the P-controller's behavior.

Assumption 3: The Notify Mechanism is Sufficient

The assistant assumes that tokio::sync::Notify with notify_one() is the right replacement for the semaphore. This assumes that only the dispatcher task needs to be notified of GPU completions, and that a single notification is sufficient even when multiple GPU completions occur. The assistant acknowledges the limitation:

"If two GPUs complete while the dispatcher sleeps, only one permit gets stored, but that's fine because the dispatcher will check the deficit and dispatch both items in subsequent loop iterations."

This assumption holds only if the dispatcher's loop is fast enough to process the deficit before the next GPU completion. If GPU completions happen faster than the dispatcher can dispatch, the system could fall behind.

Assumption 4: The Config Field Name Can Remain Unchanged

The assistant decides to keep the config field name max_gpu_queue_depth despite the semantic change from "maximum in-flight" to "target waiting count":

"Actually, I'll keep max_gpu_queue_depth as the field name since changing config names is disruptive, but I'll clarify the documentation."

This is a pragmatic assumption that prioritizes backward compatibility over semantic clarity. It assumes that users of the config will read the updated documentation rather than relying on the field name for understanding.

Assumption 5: The Dispatcher Loop Will Converge

The assistant assumes that the proportional controller will converge to a steady state where the GPU queue depth oscillates around the target value. This is a standard property of P-controllers, but it depends on the system dynamics—specifically, the relationship between synthesis time, GPU time, and the feedback delay. The assistant acknowledges this implicitly through the concept of overshoot and convergence.

Mistakes and Incorrect Assumptions

While message 3361 contains sophisticated reasoning, several aspects would prove incorrect or incomplete based on subsequent messages.

Mistake 1: Underestimating the Budget Bottleneck

The assistant's most significant oversight is underestimating how the budget constraint would interact with the P-controller. The assistant assumes that dispatching the full deficit would work naturally:

"Each iteration of the dispatcher checks the deficit and dispatches one item, so with a deficit of 5, it would dispatch 5 items across 5 iterations."

In practice, the dispatcher blocks on budget.acquire() after dispatching the first item, because the budget freed by a single GPU completion is only enough for one new synthesis. This means the P-controller degenerates into a 1:1 dispatch per GPU completion, which is exactly what the semaphore model did. The user reports this in message 3387:

"There are 6 synthesis Running, zero Waiting, and after GPU consumes one only one starts when we should start another N."

The assistant's response in message 3388 shows the realization:

"The real issue is that we're acquiring budget sequentially for each dispatch, creating a bottleneck. Instead, when a GPU completion arrives, we should calculate how many items we can dispatch based on the freed budget, pop that many from the queue, and dispatch them all at once rather than one at a time."

Mistake 2: Overcomplicating the Loop Structure

The assistant spends considerable mental energy designing a two-phase loop (Phase 1: wait for GPU event, Phase 2: dispatch deficit) that would later prove unnecessary. The simpler approach—dispatch one item per loop iteration but recalculate deficit each time—would have worked if not for the budget bottleneck. The assistant's overcomplication is a form of premature optimization, trying to solve a problem (overshoot control) that the user explicitly wanted to embrace.

Mistake 3: Misinterpreting "Waiting"

The assistant initially considers tracking an in_flight counter to account for items being synthesized but not yet in the GPU queue:

"I think tracking an in_flight counter—items currently being synthesized—is the key to capping dispatch."

This would have been a mistake because it would have defeated the P-controller's purpose. The user wanted the system to overshoot and then converge, not to precisely limit total in-flight work. The assistant correctly abandons this approach after re-reading the user's specification.

Mistake 4: Assuming the Notify Mechanism Handles All Cases

The assistant's analysis of the notification mechanism is incomplete. It considers the case where multiple GPU completions happen while the dispatcher sleeps, but it does not consider the case where GPU completions happen while the dispatcher is actively dispatching. In this case, the notification could be missed, causing the dispatcher to not re-evaluate the deficit until the next GPU completion. The assistant acknowledges this:

"The tricky part is ensuring the dispatcher doesn't miss a notification if a GPU completes while it's actively dispatching items for the current deficit."

But the proposed solution—re-evaluating the deficit on each loop iteration—only works if the dispatcher's loop is fast enough to catch up. In a system with multiple GPUs and high completion rates, this could be a real issue.

Input Knowledge Required to Understand Message 3361

To fully understand message 3361, a reader needs knowledge across several domains.

Control Theory

The concept of a proportional (P) controller is central to the message. The assistant explicitly invokes control theory:

"the P in PID stands for Proportional — our deficit acts as the error signal, and we dispatch syntheses proportional to it with a gain of 1, which is exactly what a P-controller does."

Understanding this requires familiarity with feedback control systems, including the concepts of error signals, control actions, gain, overshoot, and convergence. The P-controller is the simplest form of feedback control, but its properties—particularly the trade-off between responsiveness and stability—are critical to evaluating the design.

Async Rust and Tokio

The message deals extensively with Tokio async primitives: Semaphore, Notify, async channels, and task spawning. The assistant considers the semantics of notify_one() versus notify_waiters(), the behavior of notified() (which returns a future that resolves when a notification is received), and the interaction between Notify and async task scheduling. Understanding these requires knowledge of Rust's async model and the Tokio runtime.

GPU Pipeline Architecture

The message assumes familiarity with the cuzk proving pipeline's architecture: synthesis (CPU-bound circuit evaluation), GPU proving (CUDA kernel execution), the gpu_work_queue (a priority queue of synthesized partitions), and the finalizer (which completes proof generation after GPU kernels finish). The distinction between "in-flight" (being synthesized), "waiting" (synthesized, queued for GPU), and "on-GPU" (being processed by GPU) is essential.

Memory Management

The budget system is a critical constraint. Each partition consumes a memory budget during synthesis, which is released in stages: the a/b/c buffers are released early (during prove_start), and the remaining reservation is released later (during prove_finish). The assistant's analysis of how budget freed by GPU completions affects dispatch capacity requires understanding this staged release mechanism.

The Specific Problem Domain

Finally, the reader needs to understand the specific problem being solved: GPU underutilization in a zero-knowledge proof generation pipeline. The pinned memory pool fix had eliminated H2D transfer stalls, but the dispatch scheduler was still causing instability. The message is about refining the dispatch scheduler to work correctly with the pinned memory pool.

Output Knowledge Created by Message 3361

Message 3361 creates several important pieces of knowledge that shape the subsequent development.

The P-Controller Design

The primary output is the design of a proportional controller for GPU pipeline dispatch. This design specifies:

1. Control variable: The number of partitions waiting in the GPU queue (gpu_work_queue.len())
2. Target: A configurable target queue depth (default 8)
3. Error signal: deficit = target - waiting
4. Control action: Start deficit new syntheses
5. Trigger: GPU completion events (or startup)
6. Wait condition: When waiting >= target, sleep until next GPU completion This design is a significant departure from the semaphore model and represents a more sophisticated understanding of the system's dynamics.

The Notification Mechanism

The message creates the design for replacing Semaphore with Notify. This includes:

• Removing gpu_pipeline_sem from the dispatcher and GPU worker code
• Adding gpu_done_notify: Arc<Notify> that the GPU finalizer signals
• Updating error paths to call notify_one() instead of add_permits(1)
• Keeping the config field name max_gpu_queue_depth but updating its semantics

The Overshoot Principle

Perhaps the most important conceptual output is the acceptance of overshoot as a feature, not a bug. The assistant explicitly recognizes that the P-controller must overshoot to converge:

"We will overshoot, but we must overshoot, to then undershoot little less hopefully and so on. Essentially like a Proportional (not quite PI/PID) controller"

This principle—that the system should intentionally dispatch more work than needed to fill the queue, trusting that GPU consumption will bring it back to equilibrium—is the key insight that makes the P-controller work.

The Edge Case Analysis

The message creates a catalog of edge cases and their handling:

1. Startup: No GPU events yet, so the dispatcher does an initial fill to reach the target
2. Empty synthesis queue: The dispatcher waits for new work rather than spinning on GPU events
3. Multiple GPU completions: The deficit check handles them correctly even with single notification
4. Budget exhaustion: The dispatcher blocks on budget acquisition, which is the natural pace
5. Target disabled (max_gpu_queue_depth = 0): The dispatcher falls back to unlimited dispatch

The Implementation Plan

Finally, the message creates a concrete implementation plan:

1. Replace gpu_pipeline_sem with gpu_done_notify
2. Restructure the dispatcher loop to use deficit-based dispatch
3. Update GPU finalizer to call notify_one() instead of add_permits(1)
4. Update error paths similarly
5. Update config documentation
6. Verify compilation This plan is executed in the subsequent messages (3362-3385), with the assistant reading the code, making edits, and verifying the build.

The Thinking Process: A Window into AI Reasoning

Message 3361 is remarkable for the visibility it provides into the assistant's reasoning process. The message is structured as a stream of consciousness, with the assistant thinking through the problem in real-time. This is unusual—most AI responses present a polished, final answer. Here, we see the messy, iterative process of problem-solving.

Self-Correction

The assistant frequently corrects itself:

"Actually, I'm overcomplicating this."

"No wait, the user says count WAITING only, not in-flight. Let me re-read once more..."

"Wait, I need to reconsider what 'waiting' actually means here"

These moments of self-correction show the assistant actively engaging with the problem, testing hypotheses, and refining its understanding. They are the computational equivalent of a human engineer saying "let me think about this differently."

Explicit Re-reading

The assistant explicitly re-reads the user's specification multiple times:

"Let me re-examine what the user actually specified: they want N pipelines waiting for the GPU"

"Let me re-read once more... > When GPU finishes a job, we should look at how many synthesis are Waiting"

This is a deliberate strategy to ensure alignment with the user's intent. The assistant recognizes that its initial interpretation might be wrong and actively seeks clarification from the source material.

Hypothesis Testing

The assistant tests multiple hypotheses about the system's behavior:

1. "If I'm checking the deficit against only completed items, I could end up dispatching way more synthesis tasks than intended"
2. "If two GPUs complete while the dispatcher sleeps, only one permit gets stored, but that's fine"
3. "If a GPU completes but there's nothing in the queue to dispatch, the dispatcher should just keep waiting" Each hypothesis is evaluated, accepted, or rejected based on its implications for the system's behavior.

Control Theory Integration

The assistant explicitly connects the dispatch mechanism to control theory:

"the P in PID stands for Proportional — our deficit acts as the error signal, and we dispatch syntheses proportional to it with a gain of 1"

This shows the assistant drawing on knowledge from a different domain (control systems) to inform its software design. It is a sophisticated form of analogical reasoning.

The Unresolved Tension

Despite the thorough reasoning, the message ends with an unresolved tension. The assistant has designed a P-controller that dispatches the full deficit in a batch, but it has not fully resolved how to handle the budget constraint. The final implementation in the subsequent messages would attempt to dispatch one item per loop iteration, which the user would later identify as insufficient. This tension is visible in the assistant's vacillation between "dispatch deficit in batch" and "dispatch one per loop iteration."

Conclusion: The Value of Visible Reasoning

Message 3361 is a rare and valuable artifact: a detailed record of an AI system's reasoning process as it grapples with a complex engineering problem. It shows the assistant moving from a flawed understanding (the semaphore model) to a sophisticated one (the P-controller), while navigating the inevitable tensions between simplicity and correctness, theory and practice.

The message demonstrates several qualities that are essential for effective AI-assisted engineering:

1. Active listening: The assistant repeatedly re-reads and re-interprets the user's specification
2. Self-correction: The assistant identifies and corrects its own misunderstandings
3. Cross-domain reasoning: The assistant applies control theory to a software design problem
4. Edge case analysis: The assistant systematically considers failure modes
5. Explicit assumption-making: The assistant states its assumptions, making them available for critique These qualities are not unique to this message—they are characteristic of good engineering practice in any medium. But seeing them in an AI system's reasoning output is a powerful demonstration of how AI can participate in the design process as a genuine collaborator, not just a code generator. The P-controller design that emerges from this message would go on to be implemented, deployed, and iteratively refined in subsequent messages. The user would identify the budget bottleneck, the assistant would add dampening, and eventually a full PI controller with EMA feed-forward and synthesis throughput cap would emerge. But the foundational insight—that the dispatch scheduler should be a proportional controller targeting GPU queue depth—was born in message 3361. In the end, the message is a testament to the power of iterative, collaborative design. The user provided the initial insight (target waiting pipelines, not permits), and the assistant transformed that insight into a concrete design through extended reasoning. The result was not perfect—the budget bottleneck would need to be addressed—but it was a significant step forward in the quest for stable, high-utilization GPU scheduling.