Issue Queue Wakeup and Select: The Scheduler Inside the Window

Renaming gives every value a unique name, and the reorder buffer gives the machine a place to keep unordered work. What remains is the combinatorial problem in the middle: several hundred decoded instructions, each wanting a functional unit, with the machine required to pick the right ones every single cycle.

The problem statement

On each cycle, for each issue port, the scheduler must choose one instruction from the set that (a) is resident in the queue, (b) has all its operands available, and (c) can be issued to a functional unit of the right class and reachable through the bypass network. When multiple candidates exist, an age-based policy is typical, because issuing the oldest ready instruction preserves the largest number of in-flight younger instructions — it drains the head of the window first.

A naive implementation stores, for each queue entry, the tags of its sources and compares them against the tag broadcast by every completing instruction. That is a comparator per source per entry per broadcast bus. With 64 entries, two sources, four result buses, and four ports, the comparison matrix is thousands of gates wide and its output feeds a priority encoder of comparable size. The wakeup network does not grow linearly with window size; the classic analyses of superscalar complexity show it becoming the dominant term.

Wakeup: how an entry learns its operand is ready

Wakeup is the notification path. A result produced in cycle t must be usable by a consumer issued in cycle t+1 at the earliest, and in designs with a deeper execute stage the timing gets harder. Three families of design exist.

Tag matching (single-cycle wakeup). Each completing result broadcasts its physical register number on a result bus. Every queue entry compares its source tags against the bus. A match sets the corresponding ready bit. The comparison occurs in the same cycle the result is produced, and the consumer is eligible to be selected in the following cycle. This is the smallest-latency scheme and the most expensive, because the comparison network is fully connected.

Speculative wakeup. The producer’s latency is known at dispatch from its opcode and its operands’ likely sources. Rather than wait for the result to arrive, the scheduler schedules the wakeup for cycle t + L where L is the nominal latency. The consumer’s ready bit is set on that schedule and cleared if the result fails to arrive. This removes the broadcast comparison from the critical loop but must handle the case where L is wrong: a cache-missing load has an unpredictable latency, so the consumer wakes up, issues, reads a register that has not been written, and must be replayed. Loads whose address hits a store with unknown address, and loads that miss, are the usual sources of these false wakeups. The replay mechanism is part of the memory disambiguation story in Load-Store Ordering and Memory Disambiguation.

Wakeup with a checking pass. A hybrid: speculatively wake, then verify on the cycle the value is actually written, and cancel the issue if the check fails. This trades a comparator on the issue path for a comparator on the cancel path, and is sensitive to how often the speculation is wrong.

The choice among these interacts with bypass latency. A result that must travel from a functional unit output through a bypass multiplexer to a consumer’s ALU input constrains the whole cycle: wakeup at the end of cycle t, select at the start of t+1, read operands and bypass in t+1, execute in t+2. Shrinking that to wakeup, select, and issue in one cycle is often impossible at high clock rates, which is why some designs insert a pipeline stage for wakeup and accept a one-cycle bubble between a producer and its consumer.

Select: choosing without a quadratic

Selection is a priority arbitration among ready entries, and the concern is that the arbitration network grows with the square of the queue size once age priority is computed. To see why, consider that each entry must know whether any older ready entry is also a candidate for the same port. When the queue is organized as a single age-ordered structure with per-port priority encoders, the encoders are linear in entries per port but the grant signals must feed back to mark entries as granted.

The widely used structural fix is to partition the queue into banks by functional unit type and by issue port, and to grant per bank. Partitioning reduces the comparator and encoder width, at the cost of imbalance: a bank full of ready integer multiplies while another bank is idle cannot lend capacity. Research designs have proposed stealing entries between partitions, resizable queues, and a “reservation station + issue queue” split where entries are held centrally and only a few are copied into a small scheduling window in age order. The last idea is the one that scales best, because the expensive network is then sized by the small window rather than by the resident population.

The asymmetry that makes this hard for a compiler-like analysis is that the machine does not know the schedule in advance. Static scheduling assigns operations to slots with knowledge of the whole block; a dynamic scheduler knows only the ready set at this cycle. Anything the hardware does to reduce the select cost — partitioning, restricting the age window, speculating on idle banks — is a heuristic whose effectiveness depends on the instruction mix.

Bypass and the read-at-issue decision

Two ways exist to give an instruction its operands. In collect-at-dispatch, the register file is read when the instruction is renamed, and the values travel with the entry through the queue. This costs a register file read port per dispatch, a wide value payload in each queue entry, and forces a re-read when the source was not yet available. In read-at-issue, the entry holds only physical register numbers and the register file is read when the instruction is selected. This keeps entries small and identical to issue, at the cost of read ports per issue port and the need for wakeup to be accurate.

Read-at-issue is the common choice for wide out-of-order cores, because entry payload width scales with value width and vector registers make values very wide. Its consequence is that the register file sits in the middle of the select-to-execute path: read data, then bypass from in-flight writers, then compute. Designs that must also support a producer writing the same register in the same cycle as the consumer reads it add a comparator to that path.

A concrete model of the trade

The cost of waiting is easy to underestimate when reasoning about a single instruction. Consider a queue processed with and without an age-based ordering over a fixed ready set. The following Python drains a stream of instructions that become ready over time, granting up to a fixed number of ports per class each cycle, and reports the total cycles and the worst delay any single instruction suffers after it became ready. The two policies drain the stream in the same number of cycles; the difference is in the worst delay, which is the head-of-line effect of missing age ordering.

def schedule(ready_stream, ports_per_class, age_ordered):
    """Issue arbitration for instructions that become ready over time.

    ready_stream: [(cycle_available, class)] in program order.
    Returns (cycles_to_drain, worst_delay), the largest number of cycles any
    single instruction waited after it became ready.
    """
    pending = list(ready_stream)
    waiting = []                        # [(class, cycle_ready)], oldest first
    cycle = 0
    worst_delay = 0

    while pending or waiting:
        # admit everything that has become ready
        while pending and pending[0][0] <= cycle:
            avail, cls = pending.pop(0)
            waiting.append((cls, avail))

        # Age-ordered grants visit oldest first; an unordered grant visits the
        # youngest first, so a stream of new arrivals can jump ahead.
        order = range(len(waiting)) if age_ordered else range(len(waiting) - 1, -1, -1)
        granted = {}
        issued = set()
        for idx in order:
            cls, ready = waiting[idx]
            if granted.get(cls, 0) < ports_per_class.get(cls, 1):
                granted[cls] = granted.get(cls, 0) + 1
                issued.add(idx)
                worst_delay = max(worst_delay, cycle - ready)

        waiting = [e for i, e in enumerate(waiting) if i not in issued]
        cycle += 1

    return cycle, worst_delay

The result of interest is not a specific cycle count but the mechanism: an unordered grant can starve an older instruction indefinitely if younger instructions keep arriving in the same class, whereas strict age priority guarantees that the oldest ready instruction issues within the number of cycles it takes to clear the older ones. Starvation in a hardware scheduler is bounded by the queue size rather than by time, because entries cannot be younger than the queue, but the effect on occupancy is the same.

Structural hazards in the queue itself

An issue queue is a CAM-like structure with read, write, and clear operations on the same cycle, and its port count is a real constraint. Cases worth knowing:

• Multiple writes in one cycle. Dispatching four instructions per cycle requires four write ports; if the queue is full, the dispatch is partial and the front end must handle a non-uniform group.
• Selective clear. When a squashed instruction leaves the queue, its entry must be freed without disturbing valid entries. Designs use a valid bit and reset it, which is cheap, but the free list must also be restored.
• Wakeup of an entry being written. A source tag can match an entry the same cycle that entry is allocated; the match must be suppressed so the new entry does not see its own destination.
• Simultaneous multiple-source readiness. An instruction awaiting two operands may have one wake up this cycle and the other next cycle; the select logic must not treat it as ready in between.

Why the scheduler is where the energy goes

The wakeup-select loop touches every entry on every cycle whether or not anything changes. Its switching activity is proportional to the product of entries, source tags, and result buses, which is why energy research on out-of-order cores concentrates here: reducing the number of wakeups, gating the select network, and narrowing the tag comparisons all reduce dynamic power in a way that scaling the window does not. The corresponding cost is that gating introduces latency, and latency in the select loop either adds cycles between consumer and producer or forces deeper speculation. That trade has no settled answer: a design with a cheap, gated select loop usually compensates with speculative wakeup, which pushes the cost onto the replay path, and a design with a fast, unavoidable select loop pays for it in area. Which side a machine lands on shows up most clearly in the load path, where the latency is unpredictable and the wakeup cannot be scheduled at all. A load that returns late has already woken its dependants, and unwinding that mistake is Load-Store Ordering and Memory Disambiguation territory rather than the scheduler’s; the scheduler’s contribution is limited to replaying the entries it issued too early.