The Command Queue

Chapter 17.1 built the scheduler pipeline and treated one box as given: the entries the derivation stage reads every cycle. This chapter builds that box.

It has to start by disagreeing with its own name.

The structure universally called the command queue does not hold commands, is frequently not organised per bank, and is not a queue in any sense that survives contact with a DDR device.

That is not word-play. Each of the three errors leads to a specific broken architecture, and engineers build all three.

1. Three Words, Three Bugs

Take the name apart, because each word carries a plausible and wrong design.

“Command.” Chapter 17.1 §3 killed this one: a structure holding pre-expanded PRE / ACT / RD sequences holds answers computed against state that has since moved. The entry must hold transaction intent so the command can be re-derived against state as it is now.

“Queue.” A queue implies the head is next. But the head may be a row conflict in a bank that is mid-precharge, while the third entry is a row hit in an idle bank that could issue this cycle. Forcing head-first order serialises a device built for bank concurrency (Chapter 16.1). The structure must permit selection of any valid entry.

“Per bank.” This one is not wrong, it is a choice — and §6 is about when it is the right one. The registry's own description of this chapter says “per-bank / per-rank command queues”, which is a real and common organisation; it is simply not the only one, and the trade is worth understanding before adopting it.

2. What an Entry Must Retain

Work it out from what downstream consumers need, rather than listing fields.

The derivation stage (17.1 §1) needs to classify the entry against bank state: for that it needs the target bank and the target row. Arbitration needs to distinguish candidates: for that it needs age or some ordering metadata, and what kind of access this is. The commit stage needs to advance exactly this entry: for that the entry needs progress. The completion path needs to return data to the right requester: for that it needs the upstream identity. And the column command itself needs the column.

What is deliberately absent is as instructive as what is present. There is no next_command field — that is derived, not stored, and storing it is §1's first bug. There is no legal field — legality is recomputed combinationally every cycle and 17.1 §8's ownership table marks it never stored across cycles. There is no priority field — priority is a function the arbiter applies to the entry, not a property the entry carries, and freezing it at allocation prevents urgency from ever changing.

3. Progress Is Not a Position

An entry's progress field is the per-request FSM from 17.1 §6, stored per entry:

  WAITING     classification pending against current bank state
  NEEDS_PRE   target bank holds a different row
  NEEDS_ACT   target bank is closed
  NEEDS_COL   target row is open — the column command is next
  DATA        column command committed; burst outstanding
  DONE        burst complete; awaiting free

Two points that are easy to get wrong.

WAITING is not a starting queue position — it is a classification that has not resolved yet, and an entry can be re-classified repeatedly. An entry whose bank is mid-precharge sits in WAITING across many cycles, generating no candidate, while entries allocated after it issue freely.

WAITING can be re-entered. If an entry is in NEEDS_COL because its row was open, and some other entry's committed PRE closes that bank, the entry's classification is now wrong. A pool that only ever moves progress forward will issue a column command to a closed bank. Either the derivation stage must re-classify from live state every cycle — which is what this architecture does, making progress an optimisation rather than the authority — or the pool must invalidate progress when its bank changes underneath it.

4. One Piece of State, One Writer

The rule, stated once and then enforced everywhere: every field has exactly one writer.

The metadata row is worth stating explicitly because it is a property a checker can hold the design to: an entry's target is written once at allocation and never again. If bank or row changes while valid is high, something has written into a live entry — which happens when allocation and free collide on the same index and the allocation path does not see that the free happened.

5. Three Orders

The single most useful thing to hold in mind about a DDR controller: allocation order, scheduling order and completion order are three different orders, and no two of them are required to match.

  ALLOCATION ORDER     the order requests were accepted at ingress
                       R0, R1, R2, R3

  SCHEDULING ORDER     the order their commands were issued
                       R2's ACT, R0's RD, R3's RD, R1's PRE, R1's ACT,
                       R2's RD, R1's RD

  COMPLETION ORDER     the order bursts finished and entries freed
                       R0, R3, R2, R1

Read the middle line carefully: R1's commands are not contiguous. R2's ACT and R0's RD and R3's RD all issue between R1's PRE and R1's ACT, because the device makes R1 wait out a tRP it cannot shorten, and refusing to use those cycles for other banks would waste them. Interleaving is not an optimisation bolted on afterwards — it is the reason the pool exists.

And R2 completes before R1 despite arriving later, because R1 was a row conflict and R2 was not.

6. One Pool or Many?

The registry describes this chapter as covering per-bank and per-rank queues, and that organisation is real. It is a genuine engineering choice with a genuine trade, so here is the trade rather than a verdict.

The per-bank organisation's real cost is structural. If eight requests all target bank 3, a shared pool of eight entries holds them all; eight per-bank queues of one entry each hold one, and the other seven apply backpressure upstream while seven queues sit empty. Whether that matters depends entirely on address mapping — which is Module 18's subject, and the reason these two modules are adjacent.

The per-bank organisation's real benefit is also structural. Selecting one candidate per bank and then choosing among banks decomposes a wide selection into two narrow ones, which is a meaningful frequency argument at real DDR rates. And 16.2's bank_candidate_mask takes exactly one request per bank as its input — the interface it publishes assumes per-bank selection has already happened, which is a design already leaning this way.

The RTL below builds a shared pool, because it exhibits allocation, free and out-of-order selection in their general form, and because a per-bank organisation is a shared pool with a target constraint on allocation. Neither is the right answer everywhere, and Module 23 is where the performance question belongs.

7. The Pool

Count the arrows entering the entry array: three, from three different owners, matching §4's table exactly. Count the arrows leaving toward derivation and arbitration: those are reads. A fourth arrow into the array is the bug §4 warns about, and on a drawing it is immediately visible — which is a reason to draw it.

8. The Entry Pool

// ─────────────────────────────────────────────────────────────────────
// request_entry_pool
//
// CLASSIFICATION
//   Synthesizable educational RTL. Sequential. One responsibility:
//   owning request entries — allocation, immutable target metadata,
//   commit-driven progress, and free — and PUBLISHING them.
//
// WHAT IT DOES NOT MODEL
//   - No selection or policy. It publishes every valid entry and
//     expresses no preference; Chapter 17.4 chooses.
//   - No classification. It stores the target; Chapter 9.3's
//     row_request_classifier compares it against live bank state.
//   - No legality. Chapters 13.1 and 16.2 own that.
//   - No progress advance of its own: progress moves ONLY when
//     Chapter 17.1's advance_onehot says a command committed.
//   - No address mapping. The target arrives decoded (Module 18).
//   - No data storage. Write data and read return buffers are a
//     separate structure entirely.
// ─────────────────────────────────────────────────────────────────────
module request_entry_pool #(
  parameter int NUM_ENTRIES = 8,
  parameter int NUM_BANKS   = 8,
  parameter int ROW_W       = 16,
  parameter int COL_W       = 10,
  parameter int ID_W        = 6,
  parameter int AGE_W       = 8,
  parameter int EN_W = (NUM_ENTRIES <= 1) ? 1 : $clog2(NUM_ENTRIES),
  parameter int BK_W = (NUM_BANKS   <= 1) ? 1 : $clog2(NUM_BANKS),
  // OCCUPANCY IS A COUNT, NOT AN INDEX. A pool of NUM_ENTRIES can hold
  // NUM_ENTRIES items, so the counter must represent NUM_ENTRIES+1
  // distinct values (zero through full). Sizing this as $clog2(N) --
  // the index width -- truncates full to zero for every power-of-two
  // pool, which is the most common depth there is. §14's first corner
  // case is exactly this bug.
  parameter int OCC_W = $clog2(NUM_ENTRIES + 1)
) (
  input  logic                     clk,
  input  logic                     rst_n,

  // ── Allocation. Chapter 17.5 drives this from an accepted handshake.
  input  logic                     alloc_en,
  input  logic                     alloc_is_write,
  input  logic [BK_W-1:0]          alloc_bank,
  input  logic [ROW_W-1:0]         alloc_row,
  input  logic [COL_W-1:0]         alloc_col,
  input  logic [ID_W-1:0]          alloc_id,
  output logic                     alloc_ready,
  output logic [EN_W-1:0]          alloc_entry,

  // ── Progress. The ONLY writer of progress, sourced from Chapter
  //    17.1's commit point. Not a grant. Not a candidate.
  input  logic [NUM_ENTRIES-1:0]   advance_onehot,
  // The burst-complete event that moves DATA to DONE. Chapter 17.5
  // owns where it comes from; Modules 19-21 own what produces it.
  input  logic [NUM_ENTRIES-1:0]   burst_done,

  // ── Free. Completion releases the entry.
  input  logic                     free_en,
  input  logic [EN_W-1:0]          free_entry,

  // ── Published state. Read by derivation and arbitration; written by
  //    neither.
  output logic [NUM_ENTRIES-1:0]              entry_valid,
  output logic [NUM_ENTRIES-1:0]              entry_is_write,
  output logic [NUM_ENTRIES-1:0][BK_W-1:0]    entry_bank,
  output logic [NUM_ENTRIES-1:0][ROW_W-1:0]   entry_row,
  output logic [NUM_ENTRIES-1:0][COL_W-1:0]   entry_col,
  output logic [NUM_ENTRIES-1:0][ID_W-1:0]    entry_id,
  output logic [NUM_ENTRIES-1:0][2:0]         entry_progress,
  output logic [NUM_ENTRIES-1:0][AGE_W-1:0]   entry_age,

  // ── Occupancy and backpressure.
  output logic [OCC_W-1:0]         occupancy,
  output logic                     pool_full,
  output logic                     pool_empty,

  // ── Design-error observability. None of these should ever assert;
  //    they exist so that when one does, it is named rather than
  //    silently corrupting an entry.
  output logic                     err_alloc_when_full,
  output logic                     err_free_invalid,
  output logic                     err_advance_invalid
);

  if (NUM_ENTRIES < 1) $fatal(1, "request_entry_pool: NUM_ENTRIES must be >= 1");
  if (NUM_BANKS   < 1) $fatal(1, "request_entry_pool: NUM_BANKS must be >= 1");
  if (AGE_W       < 1) $fatal(1, "request_entry_pool: AGE_W must be >= 1");

  // ── Progress encoding. §3.
  localparam logic [2:0] P_WAITING   = 3'd0;
  localparam logic [2:0] P_NEEDS_PRE = 3'd1;
  localparam logic [2:0] P_NEEDS_ACT = 3'd2;
  localparam logic [2:0] P_NEEDS_COL = 3'd3;
  localparam logic [2:0] P_DATA      = 3'd4;
  localparam logic [2:0] P_DONE      = 3'd5;

  logic [NUM_ENTRIES-1:0]            vld;
  logic [NUM_ENTRIES-1:0]            is_wr;
  logic [NUM_ENTRIES-1:0][BK_W-1:0]  bnk;
  logic [NUM_ENTRIES-1:0][ROW_W-1:0] rw;
  logic [NUM_ENTRIES-1:0][COL_W-1:0] cl;
  logic [NUM_ENTRIES-1:0][ID_W-1:0]  idq;
  logic [NUM_ENTRIES-1:0][2:0]       prg;
  logic [NUM_ENTRIES-1:0][AGE_W-1:0] age;

  // ── Deterministic allocation: lowest free index. Determinism matters
  //    for debuggability -- the same stimulus must place the same
  //    request in the same entry on every run, or a waveform from one
  //    run cannot be compared against another.
  logic       have_free;
  logic [EN_W-1:0] free_idx;
  always_comb begin
    have_free = 1'b0;
    free_idx  = '0;
    for (int i = NUM_ENTRIES - 1; i >= 0; i--)
      if (!vld[i]) begin
        have_free = 1'b1;
        free_idx  = EN_W'(i);
      end
  end

  assign alloc_ready = have_free;
  assign alloc_entry = free_idx;
  assign pool_full   = !have_free;
  assign pool_empty  = (vld == '0);

  // ── Occupancy, carried as a counter rather than recomputed as a
  //    popcount. Both are correct; the counter is cheaper at depth and
  //    makes the simultaneous-event arithmetic explicit below.
  logic do_alloc, do_free;
  assign do_alloc = alloc_en && alloc_ready;
  assign do_free  = free_en  && vld[free_entry];

  assign err_alloc_when_full = alloc_en && !alloc_ready;
  assign err_free_invalid    = free_en  && !vld[free_entry];
  always_comb begin
    err_advance_invalid = 1'b0;
    for (int i = 0; i < NUM_ENTRIES; i++)
      if (advance_onehot[i] && !vld[i]) err_advance_invalid = 1'b1;
  end

  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      vld       <= '0;
      occupancy <= '0;
      for (int i = 0; i < NUM_ENTRIES; i++) begin
        is_wr[i] <= 1'b0;
        bnk[i]   <= '0;
        rw[i]    <= '0;
        cl[i]    <= '0;
        idq[i]   <= '0;
        prg[i]   <= P_WAITING;
        age[i]   <= '0;
      end
    end else begin

      // ── FREE FIRST in program order, so that a same-cycle allocate
      //    targeting the freed index behaves correctly. Note that it
      //    CANNOT collide in practice: alloc_entry is chosen from the
      //    CURRENT valid bits, so a still-valid entry being freed this
      //    cycle is not offered as the free index. The ordering is
      //    defensive, and §14 walks the case.
      if (do_free) begin
        vld[free_entry] <= 1'b0;
        prg[free_entry] <= P_WAITING;
      end

      if (do_alloc) begin
        vld[alloc_entry]   <= 1'b1;
        is_wr[alloc_entry] <= alloc_is_write;
        bnk[alloc_entry]   <= alloc_bank;
        rw[alloc_entry]    <= alloc_row;
        cl[alloc_entry]    <= alloc_col;
        idq[alloc_entry]   <= alloc_id;
        prg[alloc_entry]   <= P_WAITING;
        age[alloc_entry]   <= '0;
      end

      // ── Occupancy arithmetic. Simultaneous allocate and free is a
      //    NET ZERO change, not two separate updates -- writing it as
      //    two independent increments/decrements in separate branches
      //    is how a pool ends up permanently full after a burst.
      case ({do_alloc, do_free})
        2'b10:   occupancy <= occupancy + OCC_W'(1);
        2'b01:   occupancy <= occupancy - OCC_W'(1);
        default: occupancy <= occupancy;
      endcase

      // ── Progress. ONE writer. §4.
      for (int i = 0; i < NUM_ENTRIES; i++) begin
        if (vld[i] && !(do_free && (int'(free_entry) == i))) begin

          // Ageing, saturating: an age that wraps makes the oldest
          // entry appear youngest, which converts a fairness mechanism
          // into a starvation mechanism. Chapter 17.4 §9.
          if (!(&age[i])) age[i] <= age[i] + AGE_W'(1);

          // Commit-driven advance. The pool does not decide WHICH
          // command committed -- it advances one step along §3's
          // sequence, and derivation re-establishes the classification
          // from live bank state next cycle.
          if (advance_onehot[i]) begin
            case (prg[i])
              P_NEEDS_PRE: prg[i] <= P_NEEDS_ACT;
              P_NEEDS_ACT: prg[i] <= P_NEEDS_COL;
              P_NEEDS_COL: prg[i] <= P_DATA;
              // WAITING advancing means derivation produced a command
              // for an unclassified entry. Left explicit rather than
              // folded into the default so the intent is readable.
              P_WAITING:   prg[i] <= P_NEEDS_COL;
              default:     prg[i] <= prg[i];
            endcase
          end else if (burst_done[i] && prg[i] == P_DATA) begin
            prg[i] <= P_DONE;
          end
        end
      end
    end
  end

  assign entry_valid    = vld;
  assign entry_is_write = is_wr;
  assign entry_bank     = bnk;
  assign entry_row      = rw;
  assign entry_col      = cl;
  assign entry_id       = idq;
  assign entry_progress = prg;
  assign entry_age      = age;

endmodule

9. Allocation and Free, Cycle by Cycle

NUM_ENTRIES = 4. Watch occupancy across a simultaneous allocate and free at cycle 304, and the full condition at 303.

  cyc  alloc_en  rdy  a_ent  free_en  f_ent  occ  full  valid
  ───  ────────  ───  ─────  ───────  ─────  ───  ────  ─────
  300     1       1     0       0       -     1     0    0001
  301     1       1     1       0       -     2     0    0011
  302     1       1     2       0       -     3     0    0111
  303     1       1     3       0       -     4     1    1111
  304     1       0     -       1       1     3     0    1101   ←
  305     1       1     1       0       -     4     1    1111
  306     0       0     -       1       0     3     0    1110
  307     0       1     -       1       3     2     0    0110

Cycle 303 is the count-versus-index trap made visible. Occupancy reaches 4 in a four-entry pool. With OCC_W sized as $clog2(4) = 2, the value 4 is not representable: it wraps to 0, pool_full computed from it would read empty, and the pool would allocate over live entries. OCC_W = $clog2(NUM_ENTRIES+1) = 3 holds it. The bug hides on every non-power-of-two depth and appears on every power-of-two one.

Cycle 304 is the simultaneous case. alloc_en is high but alloc_ready is low — the pool was full when the cycle began, and alloc_ready is computed from the current valid bits, which do not yet reflect the free happening this cycle. So the allocation does not happen, the free does, occupancy goes 4 to 3, and the upstream request is re-presented at 305 and accepted.

That is a deliberately conservative choice and it costs one cycle of throughput. A more aggressive design computes alloc_ready as have_free || do_free, allowing allocation into the slot being freed in the same cycle. It is correct if — and only if — the allocate path then targets the freed index rather than the stale free_idx, and the occupancy arithmetic treats it as net zero. Getting one of those two right and not the other produces a pool that is permanently full, which is §16's fourth symptom.

10. One Entry, End to End

Follow entry 2 from allocation to free. It is a row conflict — the expensive case, and the one that exercises every progress state.

Request: READ, bank 5, row 0x0140, id 0x0C. Bank 5 currently holds row 0x0099. EDUCATIONAL TIMING — NOT JEDEC VALUES: tRP and tRCD are three cycles here, CL is four.

  cyc  event                         progress   valid  age   notes
  ───  ───────────────────────────   ─────────  ─────  ───   ───────────────
  400  alloc_en, entry 2             WAITING      1      0   metadata written
  401  derivation: bank 5 row 0x0099 WAITING      1      1   conflict → PRE
  402  candidate PRE, not granted    WAITING      1      2   17.4 chose another
  403  grant PRE, phy stalls         WAITING      1      3   NO commit, NO advance
  404  grant PRE, COMMITS            NEEDS_ACT    1      4   advance_onehot[2]
  405  tRP                           NEEDS_ACT    1      5   no candidate
  406  tRP                           NEEDS_ACT    1      6   no candidate
  407  candidate ACT, COMMITS        NEEDS_COL    1      7   bank 5 now row 0x0140
  408  tRCD                          NEEDS_COL    1      8   no candidate
  409  tRCD                          NEEDS_COL    1      9   no candidate
  410  candidate RD, COMMITS         DATA         1     10   column launched
  411  CL                            DATA         1     11   NO candidate — §3
  412  CL                            DATA         1     12   NO candidate
  413  CL                            DATA         1     13   NO candidate
  414  burst_done[2]                 DONE         1     14   data collected
  415  free_en, entry 2              WAITING      0      —   slot released

Fifteen cycles for one read. Three commands, three waits, a data phase, and a completion — and the entry occupied a slot for all of it.

Four rows deserve attention.

Cycle 403. The grant did not commit, and the entry did not advance. Had it advanced, cycle 404's derivation would have produced a candidate ACT against a bank still holding row 0x0099 — and 17.1 §7's ghost activate would be in flight.

Cycles 405–406 and 408–409. The entry generates no candidate at all. It is valid, it is progressing, and it is invisible to arbitration. This is the normal condition, not an exception: across these fifteen cycles the entry offered a candidate on only five of them. A pool whose entries were candidates every cycle would be a pool with no timing in it.

Cycles 411–413. The entry is in DATA and must generate no candidate, and this is the one place where progress is genuinely authoritative rather than a hint. Derivation cannot work this out from bank state: bank 5 is open on row 0x0140, so a row-hit comparison says “column command is legal” — which would issue a second RD for a request already being served. §3's rule has exactly one exception and this is it.

Cycle 415. age reaches 14 before the entry frees — and is shown as don't-care afterwards, because the RTL neither clears it on free nor uses it while valid is low; it is zeroed by the next allocation into that slot. An AGE_W of 4 would saturate at 15 — barely adequate for a single conflicting read, and hopeless once the entry waits behind others. Sizing age from the best case is a real and common mistake; 17.4 §9 sizes it from the starvation bound instead.

11. What the Assertions Prove

// ── P1. Metadata is immutable for a live entry. The strongest
//    structural property the pool has: if a target changes while valid
//    is high, allocation has written into an occupied slot.
generate
  for (genvar g = 0; g < NUM_ENTRIES; g++) begin : g_imm
    property p_metadata_stable;
      @(posedge clk) disable iff (!rst_n)
        (entry_valid[g] && $past(entry_valid[g], 1) && !$past(do_alloc && int'(alloc_entry) == g, 1))
          |-> (entry_bank[g] == $past(entry_bank[g], 1)
            && entry_row[g]  == $past(entry_row[g], 1)
            && entry_id[g]   == $past(entry_id[g], 1));
    endproperty
    a_metadata_stable: assert property (p_metadata_stable);
  end
endgenerate

// ── P2. Occupancy agrees with the valid bits. Two independent
//    representations of the same fact, deliberately: the counter is
//    what backpressure uses, the popcount is the ground truth, and the
//    §9 wrap bug breaks their agreement immediately.
property p_occupancy_matches;
  @(posedge clk) disable iff (!rst_n)
    occupancy == OCC_W'($countones(entry_valid));
endproperty
a_occupancy_matches: assert property (p_occupancy_matches);

// ── P3. No allocation into an occupied entry.
property p_no_double_alloc;
  @(posedge clk) disable iff (!rst_n)
    (alloc_en && alloc_ready) |-> !entry_valid[alloc_entry];
endproperty
a_no_double_alloc: assert property (p_no_double_alloc);

// ── P4. Progress moves only on a commit or a burst completion. The
//    pool-side half of Chapter 17.1's central discipline: 17.1 proves
//    advance_onehot implies commit, and this proves nothing else moves
//    progress. Together they close the loop.
generate
  for (genvar g = 0; g < NUM_ENTRIES; g++) begin : g_prog
    property p_progress_only_on_commit;
      @(posedge clk) disable iff (!rst_n)
        (entry_valid[g] && $past(entry_valid[g], 1)
         && entry_progress[g] != $past(entry_progress[g], 1))
          |-> ($past(advance_onehot[g], 1) || $past(burst_done[g], 1));
    endproperty
    a_progress_only_on_commit: assert property (p_progress_only_on_commit);
  end
endgenerate

// ── P5. A full pool refuses allocation. The backpressure contract
//    Chapter 17.5 relies on.
property p_full_blocks_alloc;
  @(posedge clk) disable iff (!rst_n)
    pool_full |-> !alloc_ready;
endproperty
a_full_blocks_alloc: assert property (p_full_blocks_alloc);

// ── Covers.
c_simultaneous: cover property
  (@(posedge clk) disable iff (!rst_n) do_alloc && do_free);
c_full_then_free: cover property
  (@(posedge clk) disable iff (!rst_n) pool_full ##1 !pool_full);
c_out_of_order: cover property
  (@(posedge clk) disable iff (!rst_n)
     free_en && int'(free_entry) != 0 && entry_valid[0]);

What they do not prove. Nothing here shows the pool is deep enough, or that selection is fair, or that an entry eventually completes. P1 through P5 are structural integrity properties: they establish that the pool never corrupts or loses an entry, not that the controller makes progress. c_out_of_order matters more than it looks — if it never hits, every test has completed entries in allocation order, and §5's entire point is unverified.

12. The Independent Model

Model the pool as a dictionary from entry index to transaction record, not as an array with valid bits — a genuinely different representation, so that an indexing bug in the RTL cannot be mirrored by an identical indexing bug in the checker.

On each observed allocation handshake, insert a record. On each observed free, delete one and assert it was present. On each observed advance_onehot, look up the record and advance its expected progress. At end of test, assert the dictionary is empty — every request that entered left, which is the property most likely to be quietly false.

  ENTRY LEAK
    entries never freed : 2
    entry 3  id 0x11  bank 2 row 0x0140  write
             allocated cycle   412
             last advance      cycle 455 (NEEDS_COL -> DATA)
             burst_done seen   never
             age at end        1,318 cycles
    entry 6  id 0x17  bank 2 row 0x0140  write
             allocated cycle   470
             last advance      never  (still WAITING)
             classification    row hit against bank 2 open row 0x0140
             candidate seen    never
    diagnosis : entry 3 is waiting on a burst completion that was never
                signalled; entry 6 is a legal, ready candidate that was
                never granted while entry 3 held the bank.
    ordering  : entry 6 starved BEHIND a stuck entry — the leak in 3 is
                the cause, the starvation in 6 is the symptom.

The final line is the point of an independent model. Two entries are stuck; only one of them has a bug. Reporting both as “starved” would send the investigation to the arbiter, which is working correctly.

13. Simultaneous Events

Every row is a cycle where two things happen at once, which is where pools break.

The advance and burst_done row is the one most likely to be written as two independent if statements. Written that way, an entry in DATA that receives a spurious advance skips to DONE and is freed with its burst still outstanding — and the read data returns to a slot that has been reallocated to a different request.

14. Synthesis, Cost and Limits

Cost. The array is NUM_ENTRIES × (1 + 1 + BK_W + ROW_W + COL_W + ID_W + 3 + AGE_W) flops, and for a realistic eight-entry pool with a sixteen-bit row that is on the order of four hundred flops — trivial. The expense is elsewhere: every valid entry is published in parallel, so the fan-out into derivation and arbitration scales with depth, and the selection logic downstream scales with it too.

This is the real argument against deep pools, and it is not the usual one. A deeper pool does not cost storage; it costs a wider combinational selection in the cycle that already contains derivation, legality and arbitration (17.1 §14's critical path). Doubling the depth can cost frequency, and frequency is bandwidth. More entries do not automatically improve performance — whether they help at all depends on whether there was untapped bank parallelism to find, which is Module 23's question and not one this chapter answers.

The priority encoder. free_idx is a descending loop that leaves the lowest free index set, synthesising to a priority encoder of depth logarithmic in NUM_ENTRIES. It is on the allocation path, not the issue path, so it is rarely critical.

What a production pool has that this does not. No write-data buffer association. No read-return reorder tracking. No per-entry ordering or barrier attributes from the upstream protocol. No quality-of-service class. No speculative or prefetch entries. No entry merging for requests to the same column. Each adds fields; none changes §4's one-writer rule.

15. How Deep?

The question every design review asks, and the one with the least satisfying honest answer. §14 gave the cost side; here is how to reason about the benefit without wandering into Module 23's territory.

Depth buys exactly one thing: the ability to find independent work. An entry is useful only if, on a cycle when the pool's other entries cannot issue, it can. So the question is not “how many requests do we want outstanding” but “how many independent targets can the device actually serve at once?” — and Module 16 already answered that.

Three bounds, and the smallest wins:

Bound 1 — the bank count. Entries beyond the number of banks cannot find a new bank to occupy. With eight banks, the ninth entry can only ever be a second request to a bank that already has one; it adds value only if that bank's request is a row hit that can follow the first without a row change.

Bound 2 — the activation budget. Chapter 16.1 established that tFAW limits activations to four in a rolling window, and that this binds before tRRD does on every DDR4 width and grade verified there. A pool whose entries all need ACT cannot open rows faster than that window permits, however deep it is. Depth beyond the budget converts into queueing delay, not bandwidth.

Bound 3 — the address mapping. If mapping concentrates traffic onto few banks, a deep pool fills with entries that are mutually blocked, and §6's head-of-line problem reappears inside a shared pool. This is Module 18's subject and the sharpest of the three, because it is the one a controller designer does not control alone.

A practical heuristic, offered as a starting point rather than a rule: size the pool near the bank count, verify against the activation budget, and then check whether the mapping delivers the spread that assumption requires. If any of the three disagrees, the disagreement is the finding.

16. Debugging

Symptom: the pool reports full forever after a burst of completions. The classic, and there are exactly three usual causes. Check occupancy against $countones(entry_valid) — P2 does this continuously. If they disagree, the counter arithmetic is wrong, and the simultaneous allocate-and-free case is the first suspect. If they agree, valid bits genuinely are not clearing: look at whether free_en is being driven with an entry index that is already invalid, which is silently ignored and leaves the intended entry live.

Symptom: read data returns for a request that has already completed. An entry was freed while its burst was outstanding. Check the advance versus burst_done precedence of §13, then check whether anything frees on column-command commit rather than on completion — freeing at issue is 17.1 §16's misconception about READ completion, expressed in hardware.

Symptom: one request is never selected although it is legal. Not a pool bug by default — publish is unconditional, so confirm first that entry_valid for that index really is high and its metadata really is the expected target. If so, the pool has done its job and the investigation belongs in 17.4. If the metadata is wrong, P1 has been violated and allocation wrote into a live entry.

Symptom: the same request issues its ACT twice. Progress is not advancing. Either advance_onehot is not reaching the pool, or the entry was freed and immediately reallocated with the same metadata — which looks identical on a command trace and is distinguished only by watching the valid bit between the two.

17. Misconceptions

“It is a FIFO.” §1. Consequence: head-of-line blocking that destroys bank parallelism. Clue: a controller whose bank utilisation collapses under mixed traffic.

“Entries hold commands.” They hold intent; commands are re-derived (17.1 §3). Clue: a PRE to an already-closed bank.

“Allocation order is issue order.” §5. Clue: a design that adds a reorder buffer to fix something the scheduler should never have constrained.

“Completion order matches request order.” It does not, and if the upstream protocol needs it to, that is an obligation satisfied above the scheduler. Clue: responses returned in issue order to a master that required request order.

“Progress is the authority on what command is next.” §3 — bank state is the authority, progress is a hint. Clue: a column command to a bank another entry just precharged.

“Queue full is a performance problem.” It is a correctness contract: full must deassert alloc_ready, or an accepted request is dropped. Performance is what it costs; correctness is what it is. Clue: a request accepted at ingress that never appears in any entry.

“More entries are better.” §14. Deeper pools cost frequency in the cycle that matters, and help only if unexploited bank parallelism exists. Clue: a depth chosen without reference to the bank count or the address mapping.

“Arbitration can update the entry it selects.” §4. Clue: progress that changes on a cycle with no commit.

18. Interview Reasoning

“What information must a request queue entry retain?” Derive it from consumers rather than reciting a list — target for classification, identity for the response, progress for the commit stage, age for fairness. The strong follow-up is what must it not retain, and the answer is anything derived: next command, legality, priority.

“Why is it not a FIFO?” Because the head may be blocked on a device obligation while a later entry is ready in an idle bank, and forcing order discards the concurrency the device was built to offer.

“Allocation order, scheduling order, completion order — which may a system rely on?” None from the scheduler. Any ordering requirement is imposed from above and satisfied above.

“How wide is your occupancy counter for an eight-entry pool, and why?” Four bits, because it counts to eight and nine values need four bits. Answering three shows the count-versus-index confusion §9 makes visible.

“Walk me through a simultaneous allocate and free.” Occupancy net zero; alloc_ready computed from current valid bits; the conservative and aggressive variants and exactly what the aggressive one must get right.

“Per-bank queues or a shared pool?” §6 — name the head-of-line cost, the frequency benefit, and the dependence on address mapping. An answer that simply prefers one is weaker than one that names what the choice depends on.

19. Exercises

1. A pool has NUM_ENTRIES = 16 and OCC_W mistakenly sized $clog2(16). At what occupancy does it first misbehave, what does pool_full read at that moment, and what is the first corrupted entry?

2. Write the aggressive alloc_ready = have_free || do_free variant of §8 correctly. State both things it must change beyond the ready expression.

3. Entry 2 is in NEEDS_COL for bank 5. Entry 6 commits a PRE to bank 5. Give the two architectures of §3 and say what each does next cycle.

4. Construct a stimulus where P2 passes and P1 fails. What has gone wrong, and which cycle does the violation name?

5. The ageing counter saturates rather than wrapping. Write the starvation scenario a wrapping counter would create, and say which entry becomes permanently invisible to a fairness mechanism.

6. c_out_of_order is unhit after a full regression. What does that tell you about the test suite, and which of §5's three orders has never been exercised?

7. Design the per-bank variant: NUM_BANKS queues of depth 2 versus a shared pool of 16. Give a request stream where the shared pool accepts every request and the per-bank version backpressures with 14 slots free.

8. Add a field so that two requests to the same bank, row and column can be merged. Name the two fields in §2's table that must become non-immutable, and say what that does to P1.

20. Where This Goes

The pool publishes entries; something must gate them, and something must choose.

Chapter 17.3 builds the gate — the manager that turns Module 15's obligation into the normal_issue_allowed bit that 17.1's commit condition consumes. 17.4 builds the chooser, and shows what happens to an entry in this pool when policy never selects it. 17.5 builds the ingress that fills the pool and the completion that empties it, and follows the backpressure from a full pool all the way to the upstream master.