Certified Schedules for Multi-Frame Polar Decoding Hardware

Polar codes, the error-correcting codes used for control channels in 5G, are decoded by successive cancellation. This algorithm walks a binary tree and decides one bit only after every earlier bit has been decided, so a decoder chip spends much of its time with most of its arithmetic units idle. The standard remedy is to keep several codewords ("frames") or several candidate decodings in flight at once, letting their independent work fill the idle units. How to interleave that work is a scheduling problem, and it is NP-hard in general. It is also unusual in one useful respect: for a fixed code, every frame's dependency graph is identical and fully known before any data arrives. The hard optimization can therefore be solved once, at design time, and burned into the decoder's control logic.

We propose to treat the decoder controller as the output of an exact scheduler. Each node operation in the simplified decoding tree becomes a task whose duration depends on how many processing elements it is given. Shared memory ports become exclusive resources. A constraint-programming solver, modeled on one that branches over the order fed to a greedy dispatcher, then finds latency-optimal or throughput-optimal interleavings and comes with a matching lower bound. What would be new is a certified latency–throughput–area frontier for concrete finite-length polar decoders, together with the microcode that achieves it. Existing work offers either asymptotic bounds or hand-designed architectures.

Core Claim

Asymptotic analysis already tells us how simplified successive cancellation (SSC) latency scales with block length $N$ and the number of processing elements $P$. SSC is the variant that resolves all-frozen and all-information subtrees in one step. Parallelism versus Latency in Simplified Successive-Cancellation Decoding of Polar Codes shows the latency is $O(N^{1-1/\mu} + (N/P)\log_2\log_2(N/P))$, where $\mu$ is the channel's scaling exponent. It also shows that adding processing elements beyond $P = N^{1/\mu}$ buys almost nothing for a single frame. That result motivates our proposal and is also its starting point. The bound concerns one frame and hides constants. Real decoders process several frames or list paths at once, use specialized units for repetition and parity-check nodes, and are throttled by memory ports and routing.

Our claim is that, in this multi-frame and resource-constrained setting, the gap between what designers actually build and what is achievable is measurable and possibly large. The gap can be closed by solving the scheduling problem exactly. Because the code's frozen-bit pattern is fixed, the static, clairvoyant assumptions that limit exact schedulers elsewhere hold exactly here. Our deliverable is a set of certified optimal schedules, or schedules with proven gaps of a few percent, for standard block lengths. We also report how far common heuristics fall short of them.

Research Program

The first step is the task model. For a polar code of length $N$ with a fixed frozen set, we prune the decoding tree using the Rate-0 and Rate-1 rules of Sublinear Latency for Simplified Successive Cancellation Decoding of Polar Codes. In a second variant we also prune repetition and single-parity-check nodes. Each surviving tree edge gives one task: an LLR combination (the "f" step), a combination conditioned on earlier decisions (the "g" step), or a partial-sum update. A width-$n$ step run on $p$ processing elements takes $\lceil n/p \rceil$ cycles, plus a pipeline-fill constant taken from the target microarchitecture. Tasks of this kind, whose duration depends on how many processors they receive, are called moldable tasks. For $F$ concurrent frames, or for a list decoder with $L$ paths plus its sorting stage, the instance is $F$ (or $L$) copies of the same precedence chain. They share $P$ general processing elements, a few special-node units, and $r$ memory banks, and each bank can serve one reader per cycle. This bank model is the same exclusive-resource structure that Using Approximation within Constraint Programming to Solve the Parallel Machine Scheduling Problem with Additional Unit Resources uses for satellite memory banks.

The second step is the solver. We reuse the core idea of that paper. Instead of branching on start times, the solver branches on the priority order handed to a deterministic greedy list scheduler, and it prunes a subtree whenever an approximation-style bound proves that greedy completion is already optimal. That paper reports this approach proving optimality on 213 of 234 satellite downlink instances. We add two problem-specific pieces. The first is lower bounds derived from the critical path of a single frame and from total work divided by $P$; these are in effect finite-length, constant-exact versions of the Hashemi et al. bound. The second is symmetry breaking across identical frame copies. Because the schedule repeats in steady state, we search over periodic schedules with initiation interval $I$ (a new frame enters every $I$ cycles). We minimize per-frame latency $\Lambda$ subject to $I \le I^*$ and to a fixed number of processing elements and banks. The output is a frontier of $(\Lambda, I, P, r)$ points, each certified optimal or reported with its proven gap.

The third step is to make the schedules physical. Each schedule compiles to a microcode table that drives a parameterized decoder datapath. For a subset of frontier points we synthesize that datapath for FPGA. The aim is to check that the cycle model predicts real latency, and to see whether schedules that respect the bank constraint ease the routing congestion that Efficient Hardware Realization of SC Polar Decoders Using Compound Pipelined Processing Units and Auxiliary Registers reports above $N=2048$.

Our stance differs from the works closest to this intersection. Semi-Clairvoyant Scheduling of Speculative Decoding Requests to Minimize LLM Inference Latency schedules whole requests on a GPU because their durations are stochastic and only partly predictable. We schedule sub-operations inside one decoder, where durations are known exactly. SWIPER breaks a serial dependency in quantum syndrome decoding by guessing at window boundaries and rolling back when wrong, and it aligns gates along a single time axis. We neither guess nor roll back; we solve a multi-resource placement problem exactly. Breaking the Temporal Complexity Barrier coarsens time into buckets and accepts gaps of up to 5.1%. Our horizon is already discrete clock cycles, so we keep exactness and use buckets only as a warm start.

Baselines

The naive reference point is a single-frame SSC decoder that uses all $P$ processing elements on each node operation in the natural depth-first order and admits a new frame only when the previous one finishes. It shows how much idle capacity exists. It will be run on the same codes, with the same $P$, $r$ and pipeline constants, under our cycle model.

The strongest practical competitor is greedy list scheduling of interleaved frames: round-robin across frames, or critical-path-first priority, with no search. This is roughly what hand-designed multi-frame decoders do. It is the strongest competitor because a well-chosen priority rule is often near-optimal on regular DAGs, and it costs nothing at design time. We run it under the same resource model and give it the same tuning budget as our solver's warm start, namely the best of every priority rule we implement. Beating it means a lower $\Lambda$ at equal $I$ and $P$, or equal $\Lambda$ with fewer processing elements, by a margin larger than the cycle model's validated prediction error.

The strongest existing exact method is Google OR-Tools CP-SAT given a direct interval-variable formulation of the same instances with the same wall-clock limit. We take it as the reference because Deep Reinforcement Learning Guided Improvement Heuristic for Job Shop Scheduling and Self-Labeling the Job Shop Scheduling Problem use it as their exact solver. Lacuna has no reported result for CP-SAT or any exact scheduler on polar decoder task graphs, so this comparison is new. To confirm our solver is a faithful reimplementation, we will first rerun it on the satellite PMSPAUR benchmark. The paper's reported figures are 213 of 234 instances proved optimal, against 86 for the domOverWDeg heuristic, and a 199 ms average on instances with 120 or more jobs. The architectural reference point is the CPPU design, which reports a 17.34% speedup at $N=128$ and 2672 Mbps at $N=16$ on a Virtex UltraScale. Its numbers are for single-frame pipelines, so we compare against it only where the setups match.

One ablation isolates the key ingredient. We run the same solver with the approximation-based pruning and the frame-symmetry breaking removed. This shows whether certification at realistic $N$ depends on the Godet-style structure or would follow from any CP model.

Why not just…?

Why not just use greedy list scheduling and skip the NP-hard search? This is the real threat. If greedy schedules land within one or two percent of optimal, the exact solver adds little to the hardware. We will settle the question directly by reporting the certified gap between the best greedy rule and the optimum across $N$, $F$, $L$, $P$ and $r$. A uniformly small gap is still a publishable result, because it is a proof that designers can stop searching. We expect the gap to grow where memory banks are scarce and special-node units are heterogeneous. That is where the satellite study found greedy-order choices mattered most, with the domOverWDeg heuristic proving 86 instances optimal against 213 for the structured search.

Why not just add processing elements until latency stops improving? Hashemi et al. show this stops paying off at $P = N^{1/\mu}$ for a single frame. That leaves throughput, and the area spent on banks and routing, untouched. Our frontier asks the more useful question: for a given area, which mix of frames and processing elements minimizes latency? Over-provisioning cannot answer that.

Why not replace serial decoding with belief propagation, which is parallel by nature? Algorithm and Architecture for Hybrid Decoding of Polar Codes reports a 10x throughput gain at 4 dB, but it still falls back to successive cancellation when belief propagation fails to converge. Its worst-case latency is therefore set by the serial stage, which is exactly what we schedule. The two approaches compose rather than compete.

Why not learn a scheduler with a graph neural network? Learned schedulers such as Generalizable Resource Allocation in Stream Processing via Deep Reinforcement Learning are built to generalize across many unseen graphs at run time. Our graph is fixed per code and known in advance, so a one-time exact solve dominates. A learned scheduler also cannot certify optimality.

Proposed Experiments

We will use polar codes at $N \in \{128, 256, 512, 1024, 2048\}$ at rates 1/4, 1/2 and 3/4, built for AWGN using the standard polar/PAC simulators of this literature, with SSC and Fast-SSC pruning. List decoding uses $L \in \{2, 4, 8\}$, and multi-frame decoding uses $F \in \{1, \dots, 8\}$. Metrics are per-frame latency in cycles, initiation interval, processing-element utilization, solver time, and proven optimality gap. Frame error rate serves only as a sanity check that schedules leave the decoding output unchanged. On FPGA we measure achieved clock frequency, LUT count, and measured latency.

The first decisive check is the size of the gap: across the grid, how far does the best greedy schedule sit from the certified optimum? The second is scalability: can certification be reached at $N=1024$ with $F$ or $L$ of 8 within hours, and does it fail without the ablated ingredients? The third is model fidelity: for synthesized frontier points, does the cycle model predict measured latency within a few percent, and do bank-aware schedules raise the clock frequency at $N=2048$, where CPPU-style designs suffer routing congestion? If greedy is near-optimal everywhere, the contribution reduces to a certified negative result and a finite-length constant for the Hashemi bound. If greedy is not near-optimal, the solver becomes a design-time tool that turns NP-hardness into cheaper, faster decoders.