Coherent Accelerators

The previous three chapters built the coherence machinery. This one puts it underneath a compute pipeline and asks the question an architect actually has to answer: what does it cost, and where does the time go?

1. The Engineering Problem — Two Clients, One Cache

An accelerator's cache exists to serve the accelerator. Once it is coherent, that stops being true.

There is now a second client — the coherence path from 8.3 — and it differs from the first in every way that matters:

The second client does not run your workload and does not care about your throughput. Every structure in this chapter exists because of that asymmetry: the cache port has to be shared, misses have to be tracked so the pipeline can continue past them, and the stall counters have to be able to say which client caused a given idle cycle.

2. The One-Sentence Model

Coherence is a second client of your cache, and it does not run your workload. So the accelerator must be built to make progress while another agent it does not control takes the cache port, answers on its own schedule, and occasionally takes a line away — which means outstanding-miss tracking, request merging, and stall accounting that can tell the two clients apart.

Call it the second client. Everything below follows from admitting it exists.

3. What This Chapter Owns

4. The Accelerator, End to End

The edge worth staring at is coherence agent → cache, because it is the only arrow in the picture whose rate the accelerator's designer does not control. Everything upstream of the cache is your workload; that one arrow is somebody else's.

5. Teaching-model boundary

6. RTL 1 — Misses in Flight, and the Second Miss That Costs Nothing

An accelerator with many lanes will miss the same line more than once — that is what shared data means. The structure that handles it is the miss-status tracker, and its most valuable behaviour is merging.

    // A second miss to a line already in flight MERGES: one fetch, two waiters.
    for (k = 0; k < NENT; k = k + 1)
      if (live_q[k[1:0]] && (line_m[k] == miss_line)) begin
        line_hit = 1'b1; hit_id = k[1:0];
      end

=== EXP1: a second miss to the same line MERGES ===
  two lanes, one line : correct allocs=1 merges=1 occupancy=1
                       no-merge variant allocs=2 occupancy=2
  one fetch serves both lanes                        : ok
  the no-merge variant spent two entries and two fetches: ok
  MSHR peak occupancy was exactly 1                  : ok
  fill wakes mask=00100010 (lanes 1 and 5 merged)
  the fill woke both merged lanes, from one fetch    : ok

Merging saves two scarce resources at once: a tracker entry, and an external fetch. On shared data the saving is large and it is invisible in a hit-rate number — the second lane's access was a miss, and it cost no external traffic at all.

The entry is released at the fill, never at the response:

=== EXP1b: an entry is held until the FILL, not the response ===
  after response only : live=1000 occupancy=1
  the entry survived the response                    : ok
  and was released by the fill                       : ok

The reason is sharper here than in earlier chapters: the entry holds the waiter set. Releasing at the response discards the record of which lanes are waiting, so the fill wakes nobody and those lanes hang forever.

7. Waveform — One Fetch, Two Lanes

allocs reaches one and stops. merges reaches one. occupancy never exceeds one. Two lane misses, one external fetch — and the wake mask at cycle 7 is 0x22, exactly lanes 1 and 5.

8. RTL 2 — Waking Exactly the Lanes That Waited

=== EXP2: the fill wakes exactly the lanes that waited ===
  waiters=00100010 : correct wake=00100010 | wake-all wake=11111111
  exactly the waiting lanes were woken               : ok
  the wake-all variant woke lanes that never asked   : ok

Waking a lane that was not waiting delivers data to a lane that did not ask for it. On a wide machine the broken variant is not a small error — it wakes every lane on every fill, and each spurious wake is a lane resuming with data for an address it never requested.

9. RTL 3 — A Stall Has a Cause, and It Is Usually Not the One You Assume

This is the most valuable module in the chapter, because it changes what an architect does with the data.

      if (BLAME_COMPUTE) begin
        n_miss_q <= n_miss_q + 16'd1;          // everything blamed on misses
      end else begin
        if (cause_miss) n_miss_q <= n_miss_q + 16'd1;
        if (cause_coh)  n_coh_q  <= n_coh_q  + 16'd1;
        if (cause_mshr) n_mshr_q <= n_mshr_q + 16'd1;
      end

Thirty stall cycles, evenly caused:

=== EXP3: a stall has a cause, and it is not always the cache ===
  30 stall cycles : miss=10 coherence=10 mshr-full=10
  every stall cycle attributed to exactly one cause  : ok
  blame-compute variant : miss=30 coherence=0 mshr-full=0
  the broken variant blamed all 30 on cache misses   : ok
  it reports 100% miss-bound; the truth is 33%

The broken counter reports the accelerator as 100% miss-bound when only a third of its stalls are misses. The other two thirds are coherence taking the cache port and the miss tracker being full — and those have completely different fixes:

A team reading the inflated number buys a bigger cache. It does not help, because the cache was never the constraint.

10. RTL 4 — No Lane Is Structurally Last

Eight lanes, one cache port, forty-eight cycles of full contention:

=== EXP4: no lane is structurally last ===
  8 lanes, 48 cycles : round-robin grants=48 max_lane_wait=7
                       fixed-priority grants=48 max_lane_wait=48
  round-robin worst wait was exactly 7 = lanes minus 1: ok
  fixed priority made one lane wait 48 cycles        : ok
  and flagged lane starvation                        : ok

Both schedulers issued exactly the same number of grants — 48. Throughput is identical. What differs is the distribution: round-robin bounds the worst lane's wait at lanes minus one, while fixed priority left one lane waiting for the entire run.

Equal throughput, completely different behaviour. On an accelerator this matters because lanes usually have to converge — a kernel finishes when its slowest lane finishes, so the worst-case lane wait, not the average, sets the kernel's time.

11. RTL 5 — Hit Rate Is Not the Whole Story

=== EXP5: external traffic is misses MINUS merges ===
  requests=40 hits=30 misses=10 merged=5 external=5
  traffic split matched an independent oracle        : ok
  every miss either merged or went external          : ok
  hit rate 75%, but external traffic is only 12% of requests

A 75% hit rate suggests 25% of requests go out to the host. The measured external traffic is 12% — half the misses merged onto fetches already in flight.

The relationship worth remembering:

external fetches = requests × (1 − hit rate) − merged misses

The merge term is invisible in a hit-rate number and grows with lane count and with data sharing. A wide accelerator on shared data can have a mediocre hit rate and modest external traffic, and an architect who sizes the link from hit rate alone will over-provision it.

12. RTL 6 — The Counter That Has Now Broken Four Times

      if (TWO_ASSIGNS) begin
        // Both assign outstanding_q; the second one wins outright.
        if (alloc) outstanding_q <= outstanding_q + 5'd1;
        if (free)  outstanding_q <= outstanding_q - 5'd1;
      end else begin
        case ({alloc, free})

=== EXP6: allocate and free in the same cycle ===
  4 allocated : correct=4 | two-assign variant=4
  3 cycles of alloc+free together : correct=4 | two-assign=1
  the case-based counter held steady                 : ok
  the two-assign variant drifted down to 1           : ok

This defect has now appeared in an event queue, a traversal work queue, an outstanding-transaction count and here — four times in this track. Two non-blocking assignments to one variable in one cycle: the second wins, so allocate-and-free together decrements instead of holding.

It survives fill-then-drain testing perfectly and appears only under steady-state traffic, which is the operating point an accelerator spends its life in.

13. RTL 7 — What Outstanding Capacity Buys

=== EXP7: outstanding capacity bounds throughput ===
  4 outstanding, latency 8 : issued=36 stalled=44
  unlimited                : issued=80 stalled=0
  the outstanding limit held every cycle             : ok
  more lanes cannot beat outstanding/latency         : ok
  achieved 36 issues in 102 cycles = 1 per 2 cycles (limit/latency = 1 per 2)
  every offered cycle either issued or stalled       : ok

Four outstanding misses and eight cycles of latency bound throughput at one issue per two cycles, and the measurement lands exactly there. Adding lanes changes nothing once that bound binds — the lanes simply stall earlier.

Illustrative worked example. Take 64 lanes, each issuing a 64-byte access every 4 cycles at 1 GHz:

offered      = 64 / 4 = 16 accesses per cycle
              = 16 × 64 B × 1e9 = 1024 GB/s offered
at 75% hit   → 4 misses per cycle
with merging → measured 12% external ≈ 1.9 external fetches per cycle

That last number is the one to size the link against, and it is less than half what the hit rate alone suggests. Then the outstanding bound applies on top: to sustain 1.9 fetches per cycle at 200 cycles of round-trip latency needs roughly 380 outstanding misses. If the design has 64, it will sustain 64/200 ≈ 0.32 per cycle — a sixth of what the workload offers.

That arithmetic, not the hit rate, is what decides whether the accelerator is memory-bound.

14. Reading a Stall Cycle

The bottom row is why the attribution matters. Three causes, three unrelated fixes — and a merged counter picks one of them for you, usually the middle column, usually wrongly.

15. Assertions

Icarus Verilog 13.0 does not support concurrent SVA here; each property is synthesisable checker logic verified in simulation.

Safety

Liveness

Performance goals

16. Mutation Testing

Nineteen mutations. Nineteen killed — but this page needed the most repair of the batch.

The first run scored 9 of 19 — the weakest result in the batch, and it was correct to be. The testbench was exercising the modules without checking most of what they produce. The eight escapes were:

• Three signals never asserted at all: MSHR peak, max lane wait, and the bandwidth model's stall count. The designs computed them; nothing looked.
• Two paths never stimulated: the response-before-fill sequence, and the merged waiter set surviving to the wake.
• Three checkers unreachable by construction: unattributed stall, two-cause stall, and the traffic conservation law — all true by construction under legal stimulus.

Two of the repairs are worth naming.

A bound became an equality, for the second time in this batch. The lane-wait assertion said "no more than 8"; the design has an exact answer of 7. 8.3 hit the identical problem on its coherence-wait counter. Twice in one batch is a pattern, not an accident: when a design has a computable exact value, asserting a bound is settling.

The merge test was checking the wrong end. It verified that a merge happened — allocation count stayed at one — without ever verifying that the merged lane was woken. A design that merges correctly and forgets the waiter passes the first check and hangs a lane forever. Asserting the wake mask closed it:

  fill wakes mask=00100010 (lanes 1 and 5 merged)
  the fill woke both merged lanes, from one fetch    : ok

17. Verification Plan

The coverage cross is lane concurrency against line sharing against coherence activity. The middle axis is the one that produces merging, and a testbench where every lane touches a distinct line will never exercise it — which is exactly the testbench most people write, because distinct addresses are easier to generate.

18. Silicon Observability

The single most valuable is the stall split, because it is the one that redirects effort. Everything else refines a decision; that one decides which decision you are making.

19. Debug Lab

assign grant_coh   = coh_req && !accel_req;   // accelerator first, always
assign grant_accel = accel_req;

  24 cycles of contention : fair accel=20 coh=4 max_coh_wait=4
                          : strict accel=24 coh=0 max_coh_wait=24

assign promote   = (coh_wait_q >= COH_AGE_LIMIT);
assign grant_coh = coh_req && (!accel_req || promote);

if (rsp_valid) live_q[rsp_id] <= 1'b0;   // released when answered

  after response only : live=1000 occupancy=1
  the entry survived the response                    : ok

if (rsp_valid && live_q[rsp_id]) answered_q[rsp_id] <= 1'b1;   // answered
if (fill_done)                   live_q[fill_id]    <= 1'b0;   // finished

assign wake = fill ? {NLANE{1'b1}} : '0;   // wake everyone

  waiters=00100010 : correct wake=00100010 | wake-all wake=11111111
  the wake-all variant woke lanes that never asked   : ok

assign wake = fill ? waiters_m[fill_id] : '0;
if (wake[k] && !waiters[k]) spurious_wake_err <= 1'b1;

assign alloc_ok = miss && found;    // no in-flight check

  two lanes, one line : correct allocs=1 merges=1 occupancy=1
                       no-merge variant allocs=2 occupancy=2

for (k = 0; k < NENT; k = k + 1)
  if (live_q[k] && (line_m[k] == miss_line)) begin line_hit = 1'b1; hit_id = k; end
assign merged = miss && line_hit;
// attach this lane to the existing entry rather than allocating

if (miss && found) allocate();   // and if !found, nothing at all

  5 distinct lines into 4 entries : occupancy=4 full-refusals=1
  the fifth miss was refused and counted             : ok

end else if (miss) begin
  n_full_q <= n_full_q + 8'd1;   // refused: count it, and stall the lane
end

if (stalled) n_miss_stall_q <= n_miss_stall_q + 1;   // one bucket

  30 stall cycles : miss=10 coherence=10 mshr-full=10
  blame-compute variant : miss=30 coherence=0 mshr-full=0
  it reports 100% miss-bound; the truth is 33%

if (cause_miss) n_miss_q <= n_miss_q + 1;
if (cause_coh)  n_coh_q  <= n_coh_q  + 1;
if (cause_mshr) n_mshr_q <= n_mshr_q + 1;
if (hot != 1)   attribution_err <= 1'b1;      // exactly one cause per cycle

if (alloc) outstanding_q <= outstanding_q + 1;
if (free)  outstanding_q <= outstanding_q - 1;

  3 cycles of alloc+free together : correct=4 | two-assign=1
  the two-assign variant drifted down to 1           : ok

case ({alloc, free})
  2'b10: outstanding_q <= outstanding_q + 1;
  2'b01: outstanding_q <= outstanding_q - 1;
  default: ;                                  // both or neither: hold
endcase

20. Industry Roles

Accelerator architect. Sizes the cache, the MSHR count and the outstanding budget. The key realisation from §13 is that outstanding capacity, not cache size, is usually what binds on a latency-heavy link — and that the merge rate makes hit rate a poor proxy for link demand.

RTL engineer. Owns the tracker, the lane arbiter and the wake path. The two defects that bite are entry lifetime — release at fill, not response — and the waiter set surviving to the wake.

DV engineer. Must generate shared addresses to exercise merging, must drive coherence concurrently with compute, and must assert exact values where the design has them. A testbench of distinct addresses with an idle coherence path covers almost none of this chapter.

Performance engineer. Lives in the stall split and the outstanding/latency bound. The first question on any regression is which stall cause moved.

Firmware and runtime. Data placement decides the sharing pattern, which decides both the merge rate and the coherence traffic. It is often the cheapest lever available.

21. Design Review

1. How many misses can be outstanding, and how does that compare to bandwidth × latency?
2. Does a second miss to a line in flight merge, or allocate?
3. When is an MSHR entry released — at the response or at the fill?
4. Does the fill wake exactly the lanes that waited?
5. Can coherence starve? Can a lane starve?
6. What happens when the miss tracker fills — stall, or drop?
7. Can a line be evicted while an MSHR references it?
8. Which counters separate cache misses from coherence stalls?
9. Is the worst lane wait bounded, and is the bound asserted exactly?
10. What happens on reset with outstanding misses and waiting lanes?

22. Common Misconceptions

23. Interview Reasoning

24. Exercises

1. Analysis. An accelerator reports 90% hit rate, 40% stall cycles, MSHR peak equal to its depth, and zero coherence stalls. Name the constraint, the one change that would help, and the change that would not.

2. Design. Add per-lane fairness weighting so some lanes may be prioritised. State what breaks in the worst-lane-wait bound and what new counter is needed to detect it.

3. RTL task. Extend the MSHR so a merged waiter can attach to an entry whose response has already arrived but whose fill has not. State the new race and the assertion that catches it.

4. DV task. Write the address-generation policy that exercises merging, and explain why the natural policy — distinct addresses per lane — gives high coverage numbers while testing none of it.

5. Debug task. Lanes intermittently resume with data for addresses they never requested. Give your investigation order and the single counter that confirms the cause.

6. Design review. A colleague proposes removing merging because "it complicates the tracker and the hit rate is already good". Give the strongest version of that argument, then name the two resources it costs and the workload where it is most expensive.

25. Summary

Coherence is a second client of your cache, and it does not run your workload.

• The cache now has two clients with opposite characteristics: one you control and one you do not.
• MSHRs let the pipeline continue past a miss, and merging makes a second miss to an in-flight line cost nothing.
• An entry is released at the fill, never at the response — it holds the waiter set, and losing that hangs lanes.
• A fill must wake exactly the lanes that waited. Spurious wakes deliver data to lanes that never asked, silently.
• Measured: a broken stall counter reported 100% miss-bound where the truth was 33%, with the rest split between coherence and a full tracker — three causes, three different fixes.
• Measured: round-robin and fixed priority delivered identical throughput; the worst lane wait was 7 versus 48. Kernels converge, so the tail sets the runtime.
• Hit rate is a poor proxy for link traffic. A 75% hit rate produced 12% external traffic because half the misses merged.
• Measured: four outstanding at eight cycles of latency bounds throughput at one issue per two cycles, exactly. More lanes do not help past that.
• The two-assignment counter defect appeared for the fourth time in this track.
• Verification lesson: the first mutation run scored 9 of 19. Three signals the design computed were never named by any assertion, and the merge test verified the optimisation triggered without verifying the deferred work happened.

Chapter 8.5 takes the hardest question in the module: what must be proven before writable ownership of a line may move.