Arbitration Policies and QoS · arch

Computer Architecture · All levels

On this page

Four policies and their bounds

Every arbiter answers two questions: what share each class gets, and how long any grant can wait. Only the second question bounds starvation.

Policy	Share under contention	Worst-case wait	Starves when
Fixed priority	All to the top live class	Unbounded for the rest	A high class bursts without pause
Round robin	Equal per live client	3 grant slots for 4 clients	Never by itself; idles on empty requests
Weighted round robin 4:2:1:1	4/8, 2/8, 1/8, 1/8 of link	7 flit-times for the lowest class	Weights mismatch the SLA for too long
Age-based (oldest first)	To the longest waiter	Bounded by the oldest grant age	Timestamps skew across routers

Shares are not deadlines

Weights set throughput shares, not latency bounds. A hard deadline needs the worst-case grant interval derived from weights plus quantum, with admission control holding offered load inside the plan.

Diagram

Link 32 GB/s shared with weights 4:2:1:1 (sum 8)
class A: 4/8 * 32 = 16 GB/s; class B: 2/8 * 32 = 8 GB/s
class C: 1/8 * 32 = 4 GB/s;  class D: 1/8 * 32 = 4 GB/s
worst-case wait for class D = quanta ahead of it = (4+2+1) flit-times = 7 cycles = 7 ns at 1 GHz, 1 flit per cycle
watchdog threshold = 3 * 7 = 21 cycles

AXI carries QoS as 4-bit ARQOS and AWQOS sidebands, where a higher value means higher priority. The numbers are a hint, not a guarantee: the NoC maps them onto classes with real bounds.

Shaping lives at injection

A token bucket caps a noisy source before it enters the fabric. Tokens accrue at the allowed rate and each injected byte spends tokens; debt from a burst drains at the capped rate.

Diagram

Bucket 4 KB, rate 10 GB/s, sudden 16 KB burst
excess = 16 - 4 = 12 KB; drain time = 12 KB / 10 GB/s = 1.2 us
refill 1 KB per 100 ns tick -> a 4 KB line accumulates every 400 ns

Testbench

The model below races fixed priority against round robin for 8 cycles with all four clients requesting: fixed priority must grant 8-0-0-0 while round robin grants 2-2-2-2.

fixed_prio4.sv

module fixed_prio4 (
  input  logic [3:0] req,
  output logic [3:0] grant
);
  always_comb begin
    grant = 4'b0000;
    if (req[0]) grant = 4'b0001;
    else if (req[1]) grant = 4'b0010;
    else if (req[2]) grant = 4'b0100;
    else if (req[3]) grant = 4'b1000;
  end
endmodule

module rr_arb4 (
  input  logic clk,
  input  logic rst_n,
  input  logic [3:0] req,
  output logic [3:0] grant
);
  logic [1:0] ptr;
  logic [3:0] hi_mask;
  logic [3:0] masked;
  logic [3:0] g_hi;
  logic [3:0] g_lo;
  always_comb begin
    case (ptr)
      2'd0: hi_mask = 4'b1111;
      2'd1: hi_mask = 4'b1110;
      2'd2: hi_mask = 4'b1100;
      default: hi_mask = 4'b1000;
    endcase
  end
  assign masked = req & hi_mask;
  always_comb begin
    g_hi = 4'b0000;
    g_lo = 4'b0000;
    if (masked[0]) g_hi = 4'b0001;
    else if (masked[1]) g_hi = 4'b0010;
    else if (masked[2]) g_hi = 4'b0100;
    else if (masked[3]) g_hi = 4'b1000;
    if (req[0]) g_lo = 4'b0001;
    else if (req[1]) g_lo = 4'b0010;
    else if (req[2]) g_lo = 4'b0100;
    else if (req[3]) g_lo = 4'b1000;
  end
  assign grant = (|masked) ? g_hi : g_lo;
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) ptr <= 2'd0;
    else if (|grant) begin
      case (grant)
        4'b0001: ptr <= 2'd1;
        4'b0010: ptr <= 2'd2;
        4'b0100: ptr <= 2'd3;
        default: ptr <= 2'd0;
      endcase
    end
  end
endmodule

Check yourself Class D waits 7 cycles worst-case under the weights above. Why is the watchdog set to 21, not 7?

The bound assumes the plan holds. Three times the bound tolerates normal burst jitter while still catching a stuck arbiter long before software-visible failure.

Check yourself A DMA flood correlates with missed CPU deadlines. Source throttle or arbiter retune first, and why?

Prove source causality first with per-class traces, then throttle at injection: the noisy-neighbor fix lives at the source, because no arbiter shares fairly when one client never pauses.

Related topics

Up nextNoC Triage Playbook

Practice this lesson Report an error

Four policies and their bounds

Every arbiter answers two questions: what share each class gets, and how long any grant can wait. Only the second question bounds starvation.

Policy	Share under contention	Worst-case wait	Starves when
Fixed priority	All to the top live class	Unbounded for the rest	A high class bursts without pause
Round robin	Equal per live client	3 grant slots for 4 clients	Never by itself; idles on empty requests
Weighted round robin 4:2:1:1	4/8, 2/8, 1/8, 1/8 of link	7 flit-times for the lowest class	Weights mismatch the SLA for too long
Age-based (oldest first)	To the longest waiter	Bounded by the oldest grant age	Timestamps skew across routers

Shares are not deadlines

Weights set throughput shares, not latency bounds. A hard deadline needs the worst-case grant interval derived from weights plus quantum, with admission control holding offered load inside the plan.

Diagram

Link 32 GB/s shared with weights 4:2:1:1 (sum 8)
class A: 4/8 * 32 = 16 GB/s; class B: 2/8 * 32 = 8 GB/s
class C: 1/8 * 32 = 4 GB/s;  class D: 1/8 * 32 = 4 GB/s
worst-case wait for class D = quanta ahead of it = (4+2+1) flit-times = 7 cycles = 7 ns at 1 GHz, 1 flit per cycle
watchdog threshold = 3 * 7 = 21 cycles

AXI carries QoS as 4-bit ARQOS and AWQOS sidebands, where a higher value means higher priority. The numbers are a hint, not a guarantee: the NoC maps them onto classes with real bounds.

Shaping lives at injection

A token bucket caps a noisy source before it enters the fabric. Tokens accrue at the allowed rate and each injected byte spends tokens; debt from a burst drains at the capped rate.

Diagram

Bucket 4 KB, rate 10 GB/s, sudden 16 KB burst
excess = 16 - 4 = 12 KB; drain time = 12 KB / 10 GB/s = 1.2 us
refill 1 KB per 100 ns tick -> a 4 KB line accumulates every 400 ns

Testbench

The model below races fixed priority against round robin for 8 cycles with all four clients requesting: fixed priority must grant 8-0-0-0 while round robin grants 2-2-2-2.

fixed_prio4.sv

module fixed_prio4 (
  input  logic [3:0] req,
  output logic [3:0] grant
);
  always_comb begin
    grant = 4'b0000;
    if (req[0]) grant = 4'b0001;
    else if (req[1]) grant = 4'b0010;
    else if (req[2]) grant = 4'b0100;
    else if (req[3]) grant = 4'b1000;
  end
endmodule

module rr_arb4 (
  input  logic clk,
  input  logic rst_n,
  input  logic [3:0] req,
  output logic [3:0] grant
);
  logic [1:0] ptr;
  logic [3:0] hi_mask;
  logic [3:0] masked;
  logic [3:0] g_hi;
  logic [3:0] g_lo;
  always_comb begin
    case (ptr)
      2'd0: hi_mask = 4'b1111;
      2'd1: hi_mask = 4'b1110;
      2'd2: hi_mask = 4'b1100;
      default: hi_mask = 4'b1000;
    endcase
  end
  assign masked = req & hi_mask;
  always_comb begin
    g_hi = 4'b0000;
    g_lo = 4'b0000;
    if (masked[0]) g_hi = 4'b0001;
    else if (masked[1]) g_hi = 4'b0010;
    else if (masked[2]) g_hi = 4'b0100;
    else if (masked[3]) g_hi = 4'b1000;
    if (req[0]) g_lo = 4'b0001;
    else if (req[1]) g_lo = 4'b0010;
    else if (req[2]) g_lo = 4'b0100;
    else if (req[3]) g_lo = 4'b1000;
  end
  assign grant = (|masked) ? g_hi : g_lo;
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) ptr <= 2'd0;
    else if (|grant) begin
      case (grant)
        4'b0001: ptr <= 2'd1;
        4'b0010: ptr <= 2'd2;
        4'b0100: ptr <= 2'd3;
        default: ptr <= 2'd0;
      endcase
    end
  end
endmodule

Check yourself Class D waits 7 cycles worst-case under the weights above. Why is the watchdog set to 21, not 7?

The bound assumes the plan holds. Three times the bound tolerates normal burst jitter while still catching a stuck arbiter long before software-visible failure.

Check yourself A DMA flood correlates with missed CPU deadlines. Source throttle or arbiter retune first, and why?

Prove source causality first with per-class traces, then throttle at injection: the noisy-neighbor fix lives at the source, because no arbiter shares fairly when one client never pauses.