The Long Tail of Scheduling: From Budget Management to Priority Queues in the cuzk Proving Pipeline

Introduction

In the world of GPU-accelerated zero-knowledge proving, scheduling is not a detail — it is the entire game. When a proving daemon manages 400 GiB of memory, two GPUs, and multiple concurrent proof jobs each split into dozens of partitions, the question of which partition gets the next available resource determines whether throughput is measured in proofs per hour or proofs per minute. This article examines a sprawling engineering session spanning hundreds of messages, in which an AI assistant and a user collaboratively transformed the scheduling architecture of the cuzk CUDA ZK proving daemon through four distinct phases: building a budget-based memory manager, implementing FIFO ordered dispatch, discovering that FIFO was the wrong abstraction, and finally deploying a priority queue system that delivered a 24% throughput improvement.

The session is a case study in how systems engineering often proceeds not in a straight line but through a series of increasingly refined models of the problem. Each phase produced a working system that was then revealed — by live observation, user feedback, or performance measurement — to be insufficient. The final result, a priority queue keyed by (job_seq, partition_idx), is elegant in retrospect but emerged only after the team had tried and discarded simpler approaches.

Phase 1: The Budget-Based Memory Manager

The foundational achievement of this session was the implementation of a unified, budget-based memory manager for the cuzk daemon. Before this change, the system used static partition-worker allocations: a fixed number of synthesis workers would each claim a fixed amount of memory, and the system would fail if that allocation was exceeded. This was brittle and inefficient — it could not adapt to mixed workloads where PoRep partitions (~13.6 GiB each) and SnapDeals partitions (~8.6 GiB each) had different memory footprints.

The new memory manager introduced a budget system with a total capacity of 400 GiB. Partitions compete for this budget via an acquire/release mechanism: a partition cannot begin synthesis until it has secured its working memory from the budget pool, and it releases that memory when synthesis completes and the partition moves to GPU proving. This allows the system to dynamically admit as many partitions as the budget can support, up to a theoretical maximum of approximately 44 SnapDeals-sized partitions (400 GiB / ~9 GiB) or 29 PoRep-sized partitions (400 GiB / ~13.6 GiB).

The budget manager was implemented alongside a lightweight HTTP JSON status API (commit 120254b3) and an extended vast-manager HTML UI panel (commit dda96181) that allowed real-time monitoring of pipeline state, GPU worker activity, memory usage, and counters. This observability infrastructure would prove critical in the subsequent phases, as it enabled both the assistant and the user to observe scheduling behavior in real time rather than inferring it from log files.

Several bugs were fixed during the initial deployment and testing of this system. A GPU worker state race condition was discovered where partition_gpu_end was unconditionally clearing worker state, clobbering the new job's state when the finalizer task ran asynchronously after the GPU worker had already picked up a new job. The fix was surgical: only clear state if current_job_id and current_partition still match. Job IDs were being truncated to 8 characters in the status display, which was fixed by increasing the display width. And the synthesis max_concurrent display was changed from a static config parameter (which showed 4) to a dynamic budget-based computation (which correctly showed 44), preventing operators from being misled about the system's true capacity.

A critical deployment issue also emerged: the remote machine uses a Docker overlay filesystem where /usr/local/bin/cuzk cannot be replaced because the binary lives in a lower layer. Every attempt to copy, move, or SCP a new binary to that path resulted in the old binary showing through. The solution was to deploy binaries to /data/ instead, which is backed by a real XFS filesystem. This workaround, while effective, added operational complexity that would surface again in later deployment attempts.

Phase 2: The FIFO Ordered Synthesis Fix

With the budget manager in place and the system running, a fundamental scheduling problem became visible. The original implementation dispatched every partition from every job as an independent tokio::spawn task, each racing on a tokio::sync::Notify-based semaphore to acquire budget. The Notify primitive, when released, wakes all waiters simultaneously — a classic thundering herd pattern. When budget became available, every waiting partition would wake up, contend, and only one would succeed while the others went back to sleep. The result was random partition selection across multiple pipelines: partitions from Job A and Job B would interleave arbitrarily, causing all pipelines to stall together instead of completing sequentially.

The fix replaced per-partition tokio::spawn with an mpsc::channel<PartitionWorkItem> and a synthesis worker pool that pulls from the channel in strict FIFO order. This ensured that partitions from earlier jobs would be processed before partitions from later jobs. The change also unified the synthesis worker pool to handle both PoRep and SnapDeals via a ParsedProofInput match, eliminating approximately 300 lines of duplicated synthesis and error-handling logic. The commit (ddf3fd60) was tested with two concurrent PoRep C2 proofs that completed successfully at 0.485 proofs per minute, and SnapDeals jobs from a live Curio instance were observed processing correctly.

The assistant declared the FIFO fix complete. The commit history showed six commits forming a coherent narrative: the memory manager foundation, the evictor panic fix, the status API, the UI panel, the GPU worker race fix, and finally the ordered synthesis dispatch. The system was stable and processing real workloads.

Phase 3: The User's Correction — FIFO Is Not Enough

Then the user spoke.

In message [msg 2852], the user wrote: "GPU assignments still seem more or less random, neither gpu assignments nor synthesis assignments should really be fifo, instead they should be 'lowest partition in oldest pipeline'."

This single sentence derailed the assistant's sense of completion and redirected the entire scheduling architecture. The user's observation was precise: FIFO preserves insertion order, but it does not guarantee completion order when multiple workers consume from the queue concurrently. With 28 synthesis workers and only 20 partitions across two jobs, every partition started synthesizing immediately. The order in which they finished — and therefore the order in which they became available for GPU proving — was determined by the variable computational cost of each partition, not by their position in the dispatch queue. The GPU was receiving synthesized partitions in essentially random order.

The user's proposed policy — "lowest partition in oldest pipeline" — was a fundamentally different abstraction. Instead of saying "process work items in the order they arrived," it said "at any moment, among all pending work, pick the one that belongs to the pipeline that has been waiting the longest, and within that pipeline, pick the lowest partition index." This is a global priority policy that actively selects the most important work at each scheduling decision point, rather than passively accepting whatever order emerges from a queue.

The assistant's response (message [msg 2853]) is a remarkable piece of design reasoning. The assistant acknowledged the failure mode, traced through the mechanism by which FIFO fails under concurrent consumption, and designed a PriorityWorkQueue<T> structure using a BTreeMap wrapped in a Mutex with a tokio::sync::Notify for coordination. The priority key was (job_seq ASC, partition_idx ASC), where job_seq is a monotonically increasing counter assigned at job dispatch time. The assistant worked through multiple iterations of the pop synchronization logic, each time identifying a potential race condition and refining the approach, ultimately arriving at a correct understanding of Tokio's Notify permit model.

Phase 4: Priority Queue Implementation and Validation

The priority queue implementation touched both the synthesis work queue and the GPU proving queue. Items were keyed on (job_seq, partition_idx), ensuring that both synthesis workers and GPU workers always pick the lowest partition in the oldest pipeline. The change was substantial — 298 insertions and 225 deletions in engine.rs alone — and required adding the job_seq field to both PartitionWorkItem and SynthesizedJob, replacing both mpsc channels with priority queues, and updating the worker loops to use the new pop pattern.

The deployment was not smooth. The assistant encountered a zombie process holding the default ports (9820/9821), requiring a fallback to alternative ports (9830/9831). The overlay filesystem issue resurfaced, requiring careful binary placement. And the assistant learned the hard way that killing a GPU daemon requires patience — approximately 120 seconds for the kernel to tear down ~400 GiB of pinned GPU memory mappings. Each of these operational lessons was encoded into the deployment process for future attempts.

When the priority queue system was finally running and tested with two concurrent PoRep proofs, the results were unambiguous. The assistant's measurement message ([msg 2934]) reported: "Both PoRep proofs completed. Throughput improved too: 0.602 proofs/min (99.7s/proof) vs the previous 0.485 proofs/min (123.7s/proof) — that's a 24% improvement from ordered scheduling, because Job A finished faster without GPU contention from Job B."

The key observation was even more revealing: "Job A took 114.4s (GPU had it all to itself), Job B took 199.5s (waited for Job A to finish first). Previously both took ~245s because they were interleaving randomly." This decomposition of wall time into individual job times demonstrated the mechanism of the improvement: by eliminating random GPU interleaving, the first job finished in less than half its previous time, and the total throughput increased by 24%.

The Screenshot That Changed Everything (Again)

But even this victory was incomplete. Immediately after the priority queue commit, the user sent another observation (message [msg 2938]): "Commit; GPU seem now in order, synth still not quite." Accompanied by a screenshot from the real-time status dashboard, this message revealed that the synthesis workers were still processing partitions in a scrambled order within individual pipelines. One pipeline showed P0 through P6 synthesized, but then P9, P11, and P12 completed while P7, P8, and P10 were still pending.

The root cause was that the synthesis worker pool operated on a decoupled pop-and-acquire pattern: workers would pop the highest-priority item from the BTreeMap queue, then race for budget acquisition. The Notify-based budget mechanism did not guarantee fairness or ordering, so a worker holding a low-priority item could acquire budget before a worker holding a high-priority one. The priority queue ensured items were popped in order, but it could not control the order in which they were executed.

The insight that emerged from this observation was that ordering must be enforced at the resource acquisition layer, not just the queue layer. The correct design requires a single dispatcher that serializes both the queue pop and the budget acquisition: peek at the highest-priority item, determine its memory requirement, acquire the necessary budget, pop the item, and hand it to a worker through a bounded channel. This ensures that budget is acquired before the item is popped, and that only one item is in flight at the dispatch level.

Lessons and Architecture

The session as a whole reveals several enduring lessons about concurrent systems design. First, observability is not optional. Without the status API and the vast-manager dashboard, neither the assistant nor the user could have observed the scheduling pathologies that drove the successive refinements. The investment in building real-time monitoring paid for itself many times over within the same session.

Second, scheduling policy is a first-order design decision, not an implementation detail. The choice between FIFO channels and priority queues determined not just performance but correctness — whether jobs completed sequentially or stalled together. The user's articulation of the desired policy ("lowest partition in oldest pipeline") was the critical input that the assistant, focused on the mechanics of channels and workers, had not independently derived.

Third, the gap between "working" and "correct" is often visible only under load. The FIFO channel system passed its initial tests — proofs completed, SnapDeals processed — but failed to achieve the desired scheduling behavior when observed in real time. The 24% throughput improvement from the priority queue was not a marginal gain but a structural correction of a fundamental design flaw.

Fourth, deployment is not a single event but a process that reveals hidden assumptions. The overlay filesystem issue, the zombie process port conflict, the 120-second GPU memory cleanup wait — each of these operational surprises taught the team something about the environment that was not captured in any design document or configuration file.

Conclusion

The cuzk proving pipeline scheduling saga is a microcosm of systems engineering under real-world constraints. It began with a budget-based memory manager that solved the resource allocation problem, proceeded through a FIFO channel fix that addressed the thundering herd but not the priority problem, and culminated in a priority queue system that delivered measurable throughput improvement. Each phase was driven by observation — of status API output, of user feedback, of benchmark numbers — and each phase revealed that the previous model of the problem was incomplete.

The final architecture — priority queues keyed by (job_seq, partition_idx) for both synthesis and GPU dispatch, with a dispatcher that serializes pop and budget acquisition — is the product of this iterative refinement. It is not the architecture anyone would have designed on the first attempt. But it is the architecture that emerged from the only reliable teacher in systems engineering: the behavior of the system itself under real workloads.