CPU Issue Queue Interview: Wakeup, Selection, and Starvation

A CPU issue queue answers two different questions: which operations have usable operands, and which ready operations can obtain a compatible execution port now? Wakeup updates operand eligibility; selection grants an execution resource. A ready instruction can remain queued because of port compatibility, unit availability or the scheduling policy.

The original traces below separate those decisions and show a finite priority-delay counterexample. PracHub's CPU microarchitecture and simulator-design question gives broader discussion context. These models are interview practice, not a claim about a particular employer's questions or measured processor performance.

BOOM's public documentation is the concrete implementation reference. The queue entries, cycles, policies and numerical results here are original simplified models. We ran bounded Python checks; we did not execute BOOM RTL, synthesize a scheduler or prove a complete out-of-order core correct.

Define what an issue entry owns

An issue entry represents an operation waiting to execute. For our model, store its operation kind, source physical-register tags, source-ready bits, age and validity. The destination tag belongs to the operation's result path, while the source tags identify the values it needs.

A source-ready bit must mean the value will be available through a supported read or bypass path when required. It should not merely mean that some producer has been selected. Selection, execution and usable result availability can occur at different points in a pipeline.

BOOM's issue-unit documentation describes operand presence, requesting slots, compatible issue ports and both unordered and age-ordered queue policies. Treat those as details of the documented design, not a universal organization for every CPU. BOOM issue unit

Before drawing a timing table, state whether the queue is split by operation class, how many ports exist and which units each port can reach. Also state whether issued entries leave immediately or remain until a speculative assumption is confirmed. Those choices determine how capacity and recovery are accounted for.

Trace wakeup with an explicit availability boundary

Use three original operations: producer P writes physical register p10; consumer C needs p10; independent operation I is ready initially. One port can issue one operation per cycle. P issues in cycle zero, and its result becomes available only at the end of cycle one.

In this model, selection uses ready state established before the cycle. The end-of-cycle broadcast updates readiness for the next cycle. We deliberately exclude a same-cycle combinational wakeup/select path so the timing contract is visible.

If you issue C in cycle one, you have changed the timing assumption. That might be supported by a different design with an appropriate bypass path, but it is not a correction to this table unless the interface contract changes too.

BOOM's register-file and bypass discussion provides an implementation example of operand delivery. Use it to ask where data travels and when it can be consumed. Do not assume a readiness broadcast magically supplies data to every possible port. Register files and bypass

A useful negative test marks p10 ready immediately when P issues. The model should reject a consumer selected before the declared availability boundary. This tests whether readiness has a meaningful timing interpretation rather than functioning as an optimistic label.

Make port compatibility part of the selection problem

Now use two ports. P0 can execute ALU or multiply operations; P1 can execute ALU operations only. Two ready instructions wait: older A is an ALU operation, and younger M is a multiply operation. Both units are available for the cycle.

A naive port-by-port oldest-first picker assigns A to P0 first. It then considers P1, which cannot execute M. Only one operation issues even though a feasible two-operation assignment exists: M on P0 and A on P1.

Our small checker enumerated legal assignments for the two ports, excluding duplicate selection of an entry. It found the two-grant assignment. The enumeration checks this finite example. It does not establish that a general matching circuit meets the required clock frequency.

The example exposes a policy conflict. Strict local age preference, global issue count, critical-operation priority and implementation timing need not favor the same choice. State which objective the scheduler implements before calling one result optimal.

A production scheduler may use static port preferences or staged arbitration to reduce the conflict cheaply. It may also accept occasional unused capacity to simplify timing. An interview answer should explain the cost and failure case of the chosen heuristic, rather than claiming that every unused port is an implementation bug.

Construct a priority-delay witness without overclaiming starvation

Consider a single compatible port and a static-priority queue. An old ready branch B occupies low-priority slot three. Each cycle, a new ready ALU operation enters higher-priority slot zero after the previous occupant issues. Both kinds can use the port.

For eight refill cycles, the static policy issues Y0 through Y7 while B waits. When refilling stops, B finally issues on the ninth grant. Under an oldest-ready policy with the same eligibility, B receives the first grant, followed by the younger operations.

Static slot priority: Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7 B
Oldest-ready policy: B Y0 Y1 Y2 Y3 Y4 Y5 Y6 Y7

The nine-grant sequence is a finite delay witness. It proves that the static policy can defer an eligible old operation under the supplied arrival pattern. It does not prove infinite starvation in a real CPU, whose reorder-buffer capacity, dispatch rules and branch behavior constrain how long younger work can continue arriving.

If an abstract queue permits unlimited replenishment and no fairness mechanism, the same pattern can continue indefinitely. State those additional assumptions before using the word starvation in its strict liveness sense. For a bounded machine, ask what eventually stops refilling and forces the queue to drain.

This distinction matters when discussing an old branch. Delaying it can delay discovery of a misprediction, increasing wrong-path work, but our trace contains no branch predictor or recovery penalty. It supports a scheduling argument, not a numerical IPC or power claim.

Compare age ordering with its implementation costs

Age ordering prioritizes older eligible work, but it does not make unavailable operands ready or give an instruction access to an incompatible unit. An old divide still waits if the divider cannot accept another operation. A fairness claim must include eventual operand availability and eventual resource service.

BOOM documents a collapsing age-ordered queue and notes its potential energy cost from moving entries. Another design could retain entries in place and compare age tags. Those implementations have different movement, comparison, wiring and timing costs; “age ordered” names a policy, not one mandatory circuit.

For a design review, ask how age is represented and how wraparound is handled. If a finite age tag is compared naively after wrapping, a young operation can appear older than an existing one. A bounded window or an explicit wrap-aware ordering relation is part of the correctness argument.

Also separate age from criticality. The oldest ready operation may not lie on the longest dependency chain, while a younger load could unblock many consumers. A policy that favors critical work needs evidence about that criticality and a mechanism to prevent other work from waiting indefinitely.

Distinguish selection from execution-unit acceptance

An arbitration grant is meaningful only if the downstream unit accepts the operation under the interface contract. If a unit deasserts availability, a selected operation must either remain queued or be retained elsewhere. Removing it without a successful handoff loses work.

BOOM's execution-stage documentation describes functional units and their issue interfaces. It is useful for identifying whether a resource is pipelined, variable-latency or restricted to particular operations. Our two-port exercise abstracts all those units as available for one selection event. Execution stages

A nonpipelined divide unit can remain occupied across several cycles. A fully pipelined unit may accept a new operation each cycle while older results are still in flight. Latency and initiation interval therefore answer different questions. Do not infer one from the other.

For replay or speculative wakeup, explain who retains the operation and its dependencies if an assumption fails. A result predicted to arrive is not the same as a result known to have arrived. The simple consumer trace uses confirmed availability precisely to avoid hiding that extra protocol.

One more selection test should make both ports compatible with the same ready operation while no other operation is ready. The operation may receive only one accepted grant. Two local priority encoders that act independently can otherwise dispatch the same entry twice.

Next make the multiply unit unavailable in the two-operation example. The two-grant assignment is no longer feasible, even though both source operands remain ready. A checker that considers only operand presence would incorrectly demand throughput the execution interface cannot support.

These are proposed extensions to the finite enumeration, not additional RTL tests already executed. They identify the assumptions an implementation checker needs: unique operation identity, port compatibility and downstream availability in the same selection event.

Verify safety separately from eventual progress

A scheduler checker should first enforce safety: no invalid entry issues, every selected operation has required operands, each port receives a compatible operation, and one entry is not issued twice in the same cycle. Capacity and accepted-removal accounting need separate checks.

Then examine progress under stated environmental assumptions. If an operand never arrives, waiting is not necessarily a scheduler defect. If a unit becomes available repeatedly and an eligible instruction is never selected, the policy or fairness mechanism deserves investigation.

Our local checks retained the three-cycle wakeup trace, enumerated the legal two-port assignments and compared the nine-grant priority sequences. They expose specific mistakes, but do not cover queue wraparound, flush interaction, multiple result buses or physical timing closure. Those are explicit extensions, not results already established by the model.

A defensible interview explanation names the next counterexample it would test. For example, combine a result broadcast with a branch flush and require that a killed entry never becomes eligible again. You need an identity or generation rule to distinguish valid work from a reused slot.

Practice issue decisions with changed assumptions

The following PracHub records cover microarchitecture, scheduling, hazards and verification. The GPU and VLIW records use different execution models; transfer the discipline of declaring timing and dependencies, not their exact scheduling rules. None predicts a particular employer's interview.

Use the CPU microarchitecture question and present the two-port example. Explain why one greedy policy leaves a legal issue slot unused, then defend an alternative under a timing or energy constraint. Finish by distinguishing your finite delay witness from a liveness proof.

Sources and Further Reading

• BOOM: issue units, wakeup and queue policies
• BOOM: register files and bypass networks
• BOOM: execution stages and functional units

Sources checked November 3, 2026. Original scheduler models are bounded reasoning exercises, not measurements or complete RTL verification.