Fabric Topologies

15.1 built the manager that configures the fabric.

This chapter is about the fabric it configures: what shape it is, and what that shape costs.

Not a catalogue of topologies. A set of properties that any proposed shape either has or does not have, each one built as a checkable model rather than a diagram.

1. The Engineering Problem — A Topology Is A Set Of Claims, Not A Picture

Draw a fabric on a whiteboard and you have made five claims at once. Every one of them is checkable, and every one of them is routinely wrong.

That everything reaches everything. The drawing shows links. Reachability is the transitive closure of those links, and a fabric with one cable not seated has an adjacency the drawing does not. Section 5 computes the closure and asks the question directly.

That the worst pair is close enough. Two endpoints being connected says nothing about how far apart they are. What a topology costs is hops, and the number that matters is the worst pair, not the average one. Section 6 measures both and shows the gap.

That the middle is wide enough. Cut the fabric in half and every transfer between the halves crosses that cut. Its width is a hard ceiling that no amount of switch bandwidth elsewhere relieves. Section 8 fills it and drops traffic.

That independent transfers are actually independent. Non-blocking is a claim about disjoint transfers — two pairs sharing no endpoint must proceed at once. A blocking topology serialises them through a shared internal link, and neither endpoint can see why. Section 10 builds both.

That no single link takes it down. Sweep every link, remove it, ask whether the fabric is still whole. The answer is a count, and the count is usually not zero. Section 11 produces it.

And underneath all five, the constraint that ends every topology argument: a switch has a fixed number of ports. Section 13 is where "just add another link" becomes "add another switch", which is where a hop comes from.

This chapter against 15.1, stated precisely. That chapter owns the machinery that changes a fabric safely. This one owns whether the shape being configured is a shape worth having. If a section here could be moved into 15.1 without loss, it is in the wrong chapter.

2. The One-Sentence Model

A topology is a claim that every endpoint reaches every other, closely enough, across a middle wide enough, without false contention, surviving any single failure, within the ports a switch has — and each of those six is a measurement rather than an opinion.

Call it reach, distance, width, independence, survival, radix. Every failure below is one of those six unchecked.

3. What This Chapter Owns

Deferred:

4. Teaching-Model Boundary

The models below use four nodes for the graph properties and eight endpoints where a wider fabric is needed to make a case reachable. A real fabric has hundreds of each.

What is faithful: the transitive closure, the partition test, the bisection ceiling, the disjointness definition, the single-failure sweep, the channel-dependency cycle, and the radix limit. Those are structural and scale-independent.

What is not: the node count, the hop costs in nanoseconds, the switch radix of eight, and every width. The numbers are chosen so a property is visible in a short transcript.

Every model is parameterised so that a correct topology and a specific plausible flaw are the same source under a different parameter, instantiated together, driven by one stimulus stream.

5. RTL 1 — Does It Connect What It Claims To

Take the adjacency, close it, and ask.

module topo_reach #(parameter int DROP_LINK = 0) (
  input  logic clk, rst_n,
  input  logic        evaluate,
  input  logic [3:0]  adj0, adj1, adj2, adj3,   // adjacency, one row per node
  input  logic [1:0]  src, dst,
  output logic [3:0]  reach0, reach1, reach2, reach3,
  output logic        connected,
  output logic        unreachable_err,
  output logic        partitioned_err,
  output logic [7:0]  n_eval, n_unreachable, n_partitioned
);
  logic [3:0] a [0:3];
  logic [3:0] r [0:3];
  integer it, i, j;
  always_comb begin
    a[0] = adj0; a[1] = adj1; a[2] = adj2; a[3] = adj3;
    // DROP_LINK removes one edge before the closure runs. It is the fabric as
    // built rather than as drawn: one cable not seated.
    if (DROP_LINK != 0) begin
      a[1][2] = 1'b0;
      a[2][1] = 1'b0;
    end
    // Transitive closure. Every node reaches itself to begin with.
    for (i=0;i<4;i=i+1) r[i] = a[i] | (4'b0001 << i);
    for (it=0; it<3; it=it+1)
      for (i=0;i<4;i=i+1)
        for (j=0;j<4;j=j+1)
          if (r[i][j]) r[i] = r[i] | r[j];
  end
  assign connected = r[src][dst];
  assign unreachable_err = evaluate && !connected;
  // A node that reaches only itself is not merely far away, it is not in the
  // fabric at all -- and that is a different repair.
  assign partitioned_err = evaluate &&
    ((r[0]==4'b0001) || (r[1]==4'b0010) || (r[2]==4'b0100) || (r[3]==4'b1000));

All sixteen ordered pairs of the four-node tree are swept and every one is connected. Then one link is removed:

  reach   : evaluated=18 connected=1 unreachable=1 | dropped-link build unreachable=1 partitioned=1

Two failures, deliberately kept apart, because they call for different repairs:

• Unreachable is a pair. The dropped-link build's reach sets are 0011 and 1100 — two halves, each internally whole. Nothing is isolated; the fabric has been split. Every endpoint still has neighbours and every local test passes.
• Partitioned is a node that reaches only itself. Driven separately, with an adjacency where node 3 has no links at all, and its reach set is 1000.

A split fabric is the more dangerous of the two precisely because it looks healthier: half the endpoints can talk to half the endpoints, and the failure appears as a subset of traffic that fails for no reason anything local can see.

6. RTL 2 — How Far Apart The Endpoints Are

Connected is not close. The tree above prices a same-subtree pair at two hops and a cross-root pair at four.

module hop_depth #(parameter int FLAT = 0) (
  input  logic clk, rst_n,
  input  logic       sample,
  input  logic [1:0] src, dst,
  output logic [3:0] hops,
  output logic [7:0] n_samples, total_hops, max_hops, mean_hops,
  output logic       oversize_err          // a pair further than the budget
);
  localparam logic [3:0] BUDGET = 4'd2;
  logic [3:0] h;
  always_comb begin
    if (FLAT != 0)             h = 4'd1;
    else if (src == dst)       h = 4'd0;
    else if (src[1] == dst[1]) h = 4'd2;   // same subtree: up one, down one
    else                       h = 4'd4;   // across the root
  end
  assign oversize_err = sample && (h > BUDGET);
  assign hops = h;
  assign mean_hops = (n_samples == 8'd0) ? 8'd0 : (total_hops / n_samples);
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_samples <= 8'd0; total_hops <= 8'd0; max_hops <= 8'd0;
    end else if (sample) begin
      n_samples  <= n_samples + 8'd1;
      total_hops <= total_hops + {4'd0, h};
      // The worst pair is what a budget is written against; the mean is what
      // gets quoted. Both come from this one sweep.
      if ({4'd0, h} > max_hops) max_hops <= {4'd0, h};
    end
  end
endmodule

  hops    : worst pair=4 mean=2 over budget=1 | single-switch worst=1

The worst pair is four hops and the mean across all sixteen pairs is two. The mean is the number that gets quoted and the worst is the number that gets designed against, and here they differ by a factor of two on a fabric with four nodes. On a real fabric the gap is wider.

The budget test is h > BUDGET, not h >= BUDGET, and the testbench drives a pair at exactly two hops to prove it. At the budget is inside it. A comparison one off here rejects every same-subtree pair in the fabric — a topology refused for a property it has.

The FLAT build is the single-switch fabric where every pair is one hop and nothing is ever outside the budget. It is the best topology by every measure in this section, and section 13 is where it stops being possible.

7. Waveform — Eight Cycles At The Bisection

Transcribed from the printed trace. Both cut widths see one stimulus stream.

Read the crosses row against pair. Cycles 0, 5 and 6 are transfers within one half — they consume nothing at the cut and they are what lets it drain. Every other cycle crosses. The fabric is not busy in any endpoint's view at any point in this trace; the cut is.

8. RTL 3 — What Has To Cross The Middle

module bisect_load #(parameter int NARROW = 0) (
  input  logic clk, rst_n,
  input  logic       xfer,
  input  logic [1:0] src, dst,
  output logic       crosses,
  output logic [3:0] cut_width,
  output logic       oversubscribed_err,
  output logic [7:0] n_xfer, n_crossing, n_dropped, peak_demand, cross_pct
);
  // Nodes 0 and 1 on one side, 2 and 3 on the other.
  logic [3:0]  demand_q;
  logic [15:0] weighted;
  assign cut_width = (NARROW != 0) ? 4'd1 : 4'd2;
  assign crosses   = xfer && (src[1] != dst[1]);
  // Demand above the cut's width is not slow, it is dropped.
  assign oversubscribed_err = crosses && (demand_q >= cut_width);
  assign weighted  = {8'd0, n_crossing} * 16'd100;
  assign cross_pct = (n_xfer == 8'd0) ? 8'd0 : (weighted / {8'd0, n_xfer});
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      demand_q <= 4'd0; n_xfer <= 8'd0; n_crossing <= 8'd0;
      n_dropped <= 8'd0; peak_demand <= 8'd0;
    end else begin
      if (xfer) n_xfer <= n_xfer + 8'd1;
      if (crosses) begin
        n_crossing <= n_crossing + 8'd1;
        if (demand_q >= cut_width) n_dropped <= n_dropped + 8'd1;
        else begin
          demand_q <= demand_q + 4'd1;
          if ({4'd0, demand_q} + 8'd1 > peak_demand)
            peak_demand <= {4'd0, demand_q} + 8'd1;
        end
      // Local traffic is what lets the cut drain.
      end else if (demand_q != 4'd0) demand_q <= demand_q - 4'd1;
    end
  end
endmodule

  bisect  : width=2 peak demand=2 dropped=1 (narrow build 2) | 57% of load crossed

Three properties are load-bearing and each is a mutation that was caught:

• The cut fills, and full means dropped. Demand rises to exactly the cut width and the next crossing transfer is refused. It is not queued and it is not slow; a fabric whose cut is narrower than its offered load loses traffic that every endpoint-side measurement reports as sent.
• The cut drains. Local traffic lets the occupancy fall, and the testbench then drives another crossing transfer and confirms it fits. Checking that the error simply stops is not enough — with no crossing traffic the error is low whether the cut drained or not.
• The crossing share is measured against the offered load, not against the crossings. Fifty-seven percent of what was offered had to cross the middle. That fraction is the property of the traffic pattern; the cut width is the property of the topology; and an oversubscription is the two meeting.

9. RTL 4 — Two Transfers That Share Nothing

Non-blocking is a claim about disjoint transfers, and the definition has to come first.

module blocking_fabric #(parameter int BLOCKING = 0) (
  input  logic [2:0] a_src, a_dst, b_src, b_dst,   // eight endpoints
  ...
);
  assign endpoint_conflict = a_req && b_req &&
    ((a_src == b_src) || (a_src == b_dst) || (a_dst == b_src) || (a_dst == b_dst));
  assign disjoint = a_req && b_req && !endpoint_conflict;
  assign a_go = a_req;
  assign b_go = b_req && !endpoint_conflict &&
                ((BLOCKING == 0) ||
                 !((a_src[2] != a_dst[2]) && (b_src[2] != b_dst[2])));
  assign false_contention_err = disjoint && !b_go;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_pairs <= 8'd0; n_both <= 8'd0;
      n_serialised <= 8'd0; n_real_conflicts <= 8'd0;
    end else if (a_req && b_req) begin
      n_pairs <= n_pairs + 8'd1;
      if (a_go && b_go)         n_both <= n_both + 8'd1;
      if (false_contention_err) n_serialised <= n_serialised + 8'd1;
      if (endpoint_conflict)    n_real_conflicts <= n_real_conflicts + 8'd1;
    end
  end
endmodule

  blocking: disjoint=1 both served=1 | blocking build serialised=1 real conflicts=1

The distinction the model exists to draw is between real contention and false contention, and it is the difference between a fabric that is working and a fabric that is broken.

The last row is why the model has eight endpoints. At four, a disjoint pair in which one transfer crosses and the other does not cannot exist — and a mutation that blocked on the first transfer alone survived, not because the testbench was weak but because the model could not express the case.

The failure is invisible from either endpoint. Both see a transfer that took longer than it should; neither sees the other; and nothing in the fabric reports an error. false_contention_err exists to make it something other than a performance mystery.

10. RTL 5 — How Many Single Failures Take It Down

Remove one link. Ask whether the fabric is still whole. Sweep every link and the answer is a count.

module spof_probe #(parameter int SINGLE_UPLINK = 0) (
  input  logic clk, rst_n,
  input  logic       probe,
  input  logic [2:0] link_id,          // which link to remove for this probe
  output logic       still_connected,
  output logic       spof_err,
  output logic [3:0] reach_after,
  output logic [7:0] n_probes, n_spof
);
  logic [3:0] a [0:3];
  logic [3:0] r [0:3];
  integer it, i, j;
  always_comb begin
    a[0] = 4'b0010; a[1] = 4'b0101; a[2] = 4'b1010; a[3] = 4'b0100;
    // The redundant fabric adds a second path across the middle.
    if (SINGLE_UPLINK == 0) begin
      a[0][3] = 1'b1; a[3][0] = 1'b1;
    end
    case (link_id)
      3'd0: begin a[0][1]=1'b0; a[1][0]=1'b0; end
      3'd1: begin a[1][2]=1'b0; a[2][1]=1'b0; end
      3'd2: begin a[2][3]=1'b0; a[3][2]=1'b0; end
      3'd3: begin a[0][3]=1'b0; a[3][0]=1'b0; end
      default: ;
    endcase
    ...
  end
  // Every node must reach every node.
  assign still_connected = (r[0] == 4'b1111) && (r[1] == 4'b1111)
                        && (r[2] == 4'b1111) && (r[3] == 4'b1111);
  assign spof_err = probe && !still_connected;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_probes <= 8'd0; n_spof <= 8'd0;
    end else if (probe) begin
      n_probes <= n_probes + 8'd1;
      if (spof_err) n_spof <= n_spof + 8'd1;
    end
  end
endmodule

  spof    : redundant fabric spof=0 of 4 probed | single-uplink spof=3

Zero against three, on one sweep. The single-uplink fabric is a chain, and every link in a chain is a cut.

The testbench asserts more than the count. For each probe it checks which nodes are stranded — cutting link 0–1 leaves node 0 alone, cutting the middle leaves 0011, cutting 2–3 leaves 0111 — because a count alone cannot distinguish a correct probe from one that removes a different link every time. That mutation survived until the per-link reach sets were asserted.

And a control probe removes nothing and confirms the fabric is whole, which is what makes the other four probes mean anything.

11. RTL 6 — Whether The Routing Can Deadlock

A cycle in the channel dependency graph is a deadlock waiting for the right traffic to arrive.

module route_order #(parameter int ADAPTIVE = 0) (
  input  logic clk, rst_n,
  input  logic [3:0] hold,        // which channels are held
  input  logic [3:0] want,        // which channel each holder waits for
  input  logic       turn_req,    // a transfer wants the forbidden turn
  output logic       turn_ok,
  output logic       cycle_err,
  output logic [7:0] n_turns, n_refused, n_cycles, max_wait, wait_cycles
);
  logic [7:0] w_q;
  // Dimension-ordered routing takes every hop in one dimension before any hop
  // in the other. The turn back into the first dimension closes a cycle, and
  // it is the one that is refused.
  assign turn_ok = turn_req && (ADAPTIVE != 0);
  assign cycle_err = (hold == 4'b1111) && (want == 4'b1111) && (ADAPTIVE != 0);
  assign wait_cycles = w_q;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_turns <= 8'd0; n_refused <= 8'd0; n_cycles <= 8'd0;
      max_wait <= 8'd0; w_q <= 8'd0;
    end else begin
      if (turn_req) begin
        n_turns <= n_turns + 8'd1;
        if (!turn_ok) n_refused <= n_refused + 8'd1;
      end
      if (cycle_err) n_cycles <= n_cycles + 8'd1;
      // How long the fabric sat with every channel held. In the adaptive
      // build this never ends on its own.
      if (hold == 4'b1111) begin
        w_q <= w_q + 8'd1;
        if (w_q + 8'd1 > max_wait) max_wait <= w_q + 8'd1;
      end else w_q <= 8'd0;
    end
  end
endmodule

  routing : turns refused=1 cycles formed=0 | adaptive build cycle=1 held for 4 cycles

The cycle condition is two things, not one: every channel held and every holder waiting on the next. The testbench drives hold = 1111 with want = 0111 and confirms neither build reports a cycle — three of four waiting is a busy fabric, not a deadlocked one. A model that flagged a deadlock on occupancy alone would report one on every busy fabric it ever saw.

The adaptive build's hold counter runs for four cycles and does not stop, because nothing in a deadlock ends it. The ordered build's counter never starts.

And the price of the guarantee is one line in the transcript: one turn refused. That is what deadlock freedom costs here — a path that is sometimes longer than the shortest one, in exchange for a fabric that cannot stop.

12. RTL 7 — The Port Count That Ends The Argument

Every topology argument eventually meets a real switch.

module radix_limit #(parameter int OVERSUBSCRIBE = 0) (
  input  logic clk, rst_n,
  input  logic       attach, detach,
  output logic       accept,
  output logic [3:0] ports_used,
  output logic       over_radix_err,
  output logic [7:0] n_attached, n_refused, peak_ports, util_pct
);
  localparam logic [3:0] RADIX = 4'd8;
  logic [3:0]  used_q;
  logic [15:0] weighted;
  assign ports_used = used_q;
  assign accept = attach && ((used_q < RADIX) || (OVERSUBSCRIBE != 0));
  assign over_radix_err = accept && (used_q >= RADIX);
  assign weighted = {12'd0, used_q} * 16'd100;
  assign util_pct = weighted / {12'd0, RADIX};
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      used_q <= 4'd0; n_attached <= 8'd0; n_refused <= 8'd0; peak_ports <= 8'd0;
    end else begin
      if (accept) begin
        used_q <= used_q + 4'd1;
        n_attached <= n_attached + 8'd1;
        if ({4'd0, used_q} + 8'd1 > peak_ports)
          peak_ports <= {4'd0, used_q} + 8'd1;
      // A refusal nobody counts is a capacity problem that presents as a
      // missing device.
      end else if (attach) n_refused <= n_refused + 8'd1;
      else if (detach && used_q != 4'd0) used_q <= used_q - 4'd1;
    end
  end
endmodule

  radix   : 8 of 8 ports used (100%), ninth refused=1 | oversubscribing build attached it=1

Eight endpoints fill the switch. The ninth is refused and counted, not silently dropped — a refusal nobody counts is a capacity planning problem that presents as a missing device.

Utilisation is measured against the radix, not against the ports in use. Measured against the ports in use it reads 100 percent always, which is a metric that cannot ever tell you anything; the testbench detaches a port and asserts 87 percent to prove the denominator is the fixed one.

Detaching is guarded. Detaching from an empty switch does not wrap the port count to fifteen, and the testbench drives nine detaches into a switch holding seven to prove it.

This is the section that makes the rest of the chapter necessary. The FLAT topology in section 6 — one hop between every pair — is optimal on distance, bisection and blocking simultaneously. It is available up to exactly eight endpoints. Every hop, every cut and every single point of failure in this chapter exists because the ninth endpoint has to attach to a second switch.

13. RTL 8 — What A Hop Costs In Time

Hops are not the number that matters. Time is.

module hop_latency (
  input  logic clk, rst_n,
  input  logic        sample,
  input  logic [3:0]  hops,
  input  logic [7:0]  per_hop_ns, endpoint_ns,
  output logic [15:0] latency_ns,
  output logic [15:0] n_samples, total_ns, max_ns,
  output logic [15:0] mean_ns, hop_share_pct
);
  logic [15:0] hop_total, weighted;
  assign hop_total  = {12'd0, hops} * {8'd0, per_hop_ns};
  assign latency_ns = hop_total + {8'd0, endpoint_ns};
  assign mean_ns    = (n_samples == 16'd0) ? 16'd0 : (total_ns / n_samples);
  // What fraction of the latency the FABRIC is responsible for.
  assign weighted      = hop_total * 16'd100;
  assign hop_share_pct = (latency_ns == 16'd0) ? 16'd0 : (weighted / latency_ns);
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_samples <= 16'd0; total_ns <= 16'd0; max_ns <= 16'd0;
    end else if (sample) begin
      n_samples <= n_samples + 16'd1;
      total_ns  <= total_ns + latency_ns;
      if (latency_ns > max_ns) max_ns <= latency_ns;
    end
  end
endmodule

  latency : worst=220ns mean=170ns | fabric share worst=45% near=29%

At 25ns per hop on a 120ns endpoint, the worst path is 220ns and the fabric is 45 percent of it. The near pair is 170ns and the fabric is 29 percent. A local access is 120ns and the fabric is zero percent of it.

That last row is the one worth sitting with. The endpoint cost is charged once, not per hop, and a model that charges it per hop makes the fabric look responsible for everything. The share is what tells an architect whether a topology change is worth making at all: removing two hops from the worst path saves 50ns out of 220, and no topology change ever touches the other 120.

14. RTL 9 — What The Shape Costs To Build

module topo_cost (
  input  logic clk, rst_n,
  input  logic       add_switch, add_link, add_host,
  output logic [7:0] n_switches, n_links, n_hosts,
  output logic [7:0] links_per_host, fabric_port_pct, switches_per_host
);
  logic [15:0] fabric_ports, total_ports, weighted;
  // Each link consumes a port at both ends.
  assign fabric_ports = {8'd0, n_links} * 16'd2;
  assign total_ports  = fabric_ports + {8'd0, n_hosts};
  assign weighted     = fabric_ports * 16'd100;
  assign fabric_port_pct = (total_ports == 16'd0) ? 8'd0
                         : (weighted / total_ports);
  assign links_per_host    = (n_hosts == 8'd0) ? 8'd0 : (n_links / n_hosts);
  assign switches_per_host = (n_hosts == 8'd0) ? 8'd0 : (n_switches / n_hosts);
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_switches <= 8'd0; n_links <= 8'd0; n_hosts <= 8'd0;
    end else begin
      if (add_switch) n_switches <= n_switches + 8'd1;
      if (add_link)   n_links    <= n_links + 8'd1;
      if (add_host)   n_hosts    <= n_hosts + 8'd1;
    end
  end
endmodule

  cost    : 4 hosts 2 switches 3 links | 60% of ports spent on the fabric

Sixty percent of the ports in this fabric are spent connecting the fabric to itself. Only forty percent attach anything a user cares about.

That ratio is what a topology charges for its own existence, and it is the number that makes the radix limit bite twice: every inter-switch link consumes a port at both ends, so adding a link to fix a bisection problem removes two endpoint ports and may force another switch.

The empty-fabric guard returns 0, not 100, and the testbench asserts it before anything is added. A fabric with nothing in it does not spend all of its ports on itself.

15. RTL 10 — The Topology Accepted, Or Refused, And Why

module topo_top #(parameter int SKIP_SPOF = 0) (
  input  logic clk, rst_n,
  input  logic       propose,
  input  logic       connected, within_radix, within_hops, no_spof, non_blocking,
  output logic       accept,
  output logic [4:0] failed_mask,   // which constraint refused it
  output logic       weak_accept_err,
  output logic [7:0] n_proposed, n_accepted, n_refused, n_weak
);
  assign failed_mask = {~non_blocking, ~no_spof, ~within_hops,
                        ~within_radix, ~connected};
  assign accept = propose && connected && within_radix && within_hops
                  && non_blocking
                  && ((SKIP_SPOF != 0) || no_spof);
  assign weak_accept_err = accept && !no_spof;
 
  always_ff @(posedge clk or negedge rst_n) begin
    if (!rst_n) begin
      n_proposed <= 8'd0; n_accepted <= 8'd0; n_refused <= 8'd0; n_weak <= 8'd0;
    end else if (propose) begin
      n_proposed <= n_proposed + 8'd1;
      if (accept) n_accepted <= n_accepted + 8'd1;
      else        n_refused  <= n_refused + 8'd1;
      if (weak_accept_err) n_weak <= n_weak + 8'd1;
    end
  end
endmodule

Six topologies are proposed: one meeting every constraint, and five each failing exactly one.

  accept  : 1 of 6 accepted, mask for spof=8 | weak review accepted 2 weak=1

The mask is the part that matters. A refusal with no reason sends an architect back to redraw the whole shape; a refusal that names the constraint sends them to widen one link. Each of the five failing topologies sets exactly one bit, and the testbench asserts every bit position individually — a mask with two fields transposed passes any check that only asks whether the mask is non-zero.

SKIP_SPOF is the review that checks everything except whether one cable cuts the fabric in half. It accepts two topologies where the correct review accepts one, and the one it adds is a fabric that works perfectly until a single link fails.

16. Quantitative Reasoning

Every number is printed by the models, not asserted here.

Three deserve a sentence.

Worst 4, mean 2. Both come from the same sweep. The mean is what a topology comparison quotes and the worst is what a latency budget has to survive.

Zero SPOFs against three. One extra link across the middle is the entire difference, and it costs two ports out of the switch's eight.

45 percent and 0 percent. The same fabric, two different accesses. Whether a topology change is worth making depends entirely on which of those two the workload actually does.

17. Assertions

Icarus Verilog 13.0 has no concurrent SVA, so every property is an immediate check written as cond !== 1'b1 — so that x fails rather than passing vacuously — and sampled after a settle.

18. Mutation Testing

108 mutations injected one at a time across the three source files, each required to make the baseline print RESULT: FAIL.

108 of 108 were killed.

The first run killed 92 and left 16 survivors, and this batch's classification produced a category the previous chapter did not have.

The third row is the one worth reporting. Three mutations survived not because the testbench was weak but because at four nodes the correct and faulty behaviours cannot differ:

• A disjoint pair where one transfer crosses the middle and the other does not requires six endpoints. The model was widened to eight.
• A hop budget of 3 is never equal to any hop count the tree produces (0, 2, 4), so > and >= are the same expression. The budget was changed to 2, which makes "at the budget" a real case — and a better teaching point than the mutation was.
• A closure that merges rows in place converges identically whether it runs one pass or three on four nodes. That mutation was provably equivalent and was replaced rather than recorded, with one that merges unconditionally and destroys the partition test.

The stimulus gaps were more ordinary and just as instructive. The cut was never re-tested after draining, so "the cut never drains" survived — checking that the error stops proves nothing when the traffic that caused it also stopped. The SPOF sweep asserted only the total count, so a probe that removed a different link every time scored identically; per-link reach sets fixed it. And n_turns, n_eval and the weak review's own n_weak were never read at all.

A representative sample:

19. Verification Strategy

Parameterised twin builds. DROP_LINK, FLAT, NARROW, BLOCKING, SINGLE_UPLINK, ADAPTIVE, OVERSUBSCRIBE, SKIP_SPOF. One source, two instances, one stimulus stream, so every claim in section 16 is a difference measured rather than asserted.

Independent oracles. Hop distance, disjointness and latency are each checked against a function written in plain integers. The disjointness oracle is four explicit inequalities; the design's expression is one boolean. A mutation that rewrites the boolean is caught by something that does not share its shape.

Control cases. The SPOF sweep begins with a probe that removes nothing. Without it, a still_connected stuck high scores identically to a correct one on a redundant fabric — every probe returns "whole" either way.

Boundary cases in both directions. A pair exactly at the hop budget, a switch at exactly its radix, a cut at exactly its width, and a fabric with exactly nothing in it. Three mutations in section 18 lived entirely at those boundaries.

Per-item assertions, not aggregate counts. The SPOF sweep asserts which nodes are stranded by each probe; the acceptance gate asserts each mask bit individually. An aggregate count cannot distinguish "the right five things failed" from "five things failed".

Delta discipline. Every combinational sample is preceded by a settle. In a $display a missing settle corrupts a transcript; in a check it produces a false failure and sends you hunting a design bug that does not exist.

20. Synthesis and Implementation Reality

Almost nothing in this chapter is hardware, and saying so precisely is the point.

The closure is not synthesised. topo_reach and spof_probe compute a transitive closure in a combinational loop. That is a design-time analysis, and in practice it runs in the fabric manager's software or in a design tool, not in a switch. It appears as RTL here because expressing it as executable, mutation-tested logic is the only way to make "the topology is connected" a claim that can be wrong.

What is in silicon is the small, cheap part: the port counter and its radix comparison, the routing rule that refuses a turn, and the counters. The routing restriction in particular is one comparator on the path — deadlock freedom is nearly free in gates and expensive only in the paths it forbids.

The bisection model is a queue. bisect_load is an occupancy counter with a threshold, and that is exactly what an inter-switch link's credit scheme is. The difference between "dropped" and "backpressured" here is a modelling choice made to keep the failure visible; a real fabric backpressures, and the traffic that would have been dropped becomes latency instead — which is why peak_demand matters more than n_dropped in a real design.

The divisions are not synthesisable as written. Every percentage uses /. In silicon these are firmware reads of raw counters, or a sequential divider running once per interval. They appear as combinational divisions because the chapter is about what to measure.

The counter widths are the model's, not a design's. Eight bits survives a testbench and nothing else. Everything latched here — peak demand, worst hops, max latency — needs to survive a run in the field.

21. Silicon Observability

Three to alarm on rather than log.

peak_demand at the cut width means the fabric is at its bisection ceiling, and every additional crossing transfer from here is latency or loss. It is a capacity alarm that no endpoint measurement produces.

max_wait growing on held channels is a routing problem forming. In an ordered fabric it should be bounded; unbounded growth means something is holding a channel across a dependency it should not.

n_refused on a switch's ports means a device was attached and the fabric had nowhere to put it. That is a planning failure that presents to an operator as a missing device.

22. Debug Lab

22.1 Some hosts cannot see some devices

Symptom. A subset of hosts cannot reach a subset of devices. Everything else works.

The wrong move. Check the bindings. 15.1 owns bindings; this is a shape problem and the symptom is different.

The signature. Compute the reach sets and look at their shape.

The first two look the same to an operator — "some things cannot reach some things" — and they call for different repairs. A split is one cable; a partition is one endpoint. The reach sets separate them in one read, and neither is visible from any endpoint.

22.2 Cross-rack traffic is slow and nothing is busy

Symptom. Transfers between halves of the fabric are slow. Every switch reports low utilisation. Every endpoint reports low utilisation.

The reading. peak_demand at the inter-switch links, and cross_pct.

The diagnosis. The bisection is the bottleneck and it is invisible to every per-device measurement, because it is not a property of any device. Figure 2 is exactly this: at cycles 3 and 4 the fabric is dropping traffic while no endpoint in it is busy.

The two sub-cases. If cross_pct is high, the traffic pattern is crossing more than the topology was designed for — the fix is placement, not links. If cross_pct is normal and peak_demand is still at the ceiling, the cut is genuinely too narrow and the fix is more links across the middle, at two ports each.

22.3 Two unrelated transfers interfere

Symptom. Two transfers sharing no host and no device slow each other down. Running either alone is fast.

The reading. false_contention_err, and whether both transfers cross the bisection.

The diagnosis. The topology is blocking. The transfers share an internal link neither endpoint knows about, and no endpoint-side measurement can ever show it — from each side this is a transfer that was slow for no reason.

Why it is worth a counter. Without false_contention_err this is indistinguishable from a general performance problem, and teams spend weeks on endpoint tuning for a fault whose fix is a link.

22.4 One cable failed and half the fabric went down

Symptom. A single link failure took out far more than the endpoints on that link.

The reading. n_spof from the topology analysis — which should have been non-zero before the failure.

The diagnosis. The fabric has single points of failure and nobody swept for them. The information was available at design time: remove each link in turn and compute the closure, which the model in section 10 does in four probes.

The uncomfortable part. This is the one failure in the chapter that is fully knowable in advance and routinely is not known, because the sweep is a design-time analysis that nothing forces anyone to run.

23. Design Review

1. Has anyone computed the transitive closure of the topology as built, not as drawn? The drawing is the intent; the closure is the fabric.

2. What is the worst-case hop count, and what is the budget it has to fit? If the answer is a mean, no budget has been checked.

3. What is the bisection width, and what fraction of the offered load crosses it? Both numbers are needed; either alone says nothing.

4. Can two transfers sharing no endpoint contend? If yes, the topology is blocking, and that must be a decision rather than a discovery.

5. How many single link failures disconnect something? Not "is it redundant" — the count, from a sweep.

6. Is the routing provably deadlock-free, and what does the proof cost in path length? One refused turn here; in a real fabric, a measurable share of paths.

7. Does the topology fit the radix of switches that exist? Including the ports the inter-switch links consume at both ends.

8. What fraction of all ports is spent on the fabric rather than on endpoints? That is the topology's overhead, and it competes directly with capacity.

9. What fraction of end-to-end latency is the fabric? If it is small, topology work is not where the latency is.

10. When a proposed topology is refused, does the refusal say which constraint refused it? A refusal without a reason sends an architect back to redraw everything.

24. How This Appears In Real Engineering

The single-switch fabric is always the right answer until it is not available. One hop, no bisection, no blocking, no single point of failure. Every property in this chapter is optimal at once, right up to the port count. Every topology argument is really an argument about what to do past that boundary.

Bisection is the number that gets designed for and then invalidated by the workload. A topology sized for a traffic pattern is a topology that fails when the pattern changes, and the pattern changes when the placement policy changes — which is a different team.

Blocking is discovered as a performance mystery. It presents as unrelated transfers interfering, and endpoint instrumentation cannot see it, so it is usually investigated as an endpoint problem first.

The SPOF sweep is cheap and rarely run. Four probes here; a few hundred in a real fabric; seconds in software either way. It is the highest ratio of information to effort in this chapter and it is typically run for the first time after an outage.

Radix decides the shape. The topology is not chosen and then implemented — the available switch port count is a given, and the topology is what falls out of it. Arguments about mesh versus tree are usually arguments about radix wearing a different hat.

25. Common Misconceptions

"Connected means it works." Connected means a path exists. Section 6 measures how long it is, section 8 measures whether the middle can carry it, and section 9 measures whether anything else is using it.

"The average hop count is what matters." The average is what a topology comparison quotes. The worst pair is what a latency budget has to survive, and here they differ by a factor of two.

"More bandwidth per switch fixes a bisection problem." No. The cut is a count of links, and a transfer crossing it uses one. Faster switches on both sides change nothing about how many transfers fit through the middle.

"Non-blocking means no transfer ever waits." It means no disjoint transfers wait for each other. Two transfers to one endpoint are serialised by every fabric, correctly. The defect is serialising transfers that share nothing.

"Redundant means no single point of failure." Only if someone swept. A fabric with two of everything except one link is redundant everywhere it was looked at.

"Adaptive routing is strictly better." It takes shorter paths and it can form a dependency cycle. Ordered routing refuses one turn and cannot. The trade is real in both directions and the transcript prices it: one refused turn.

"The topology determines the latency." It determines the hop component. On a local access the fabric is zero percent of the latency, and on the worst path here it is 45 percent — so more than half of even the worst case is not a topology problem.

"Adding a link is cheap." It costs two ports, one at each end, out of a fixed radix. Section 14's fabric spends 60 percent of its ports on itself.

26. Interview Reasoning

Q1. What makes a topology a checkable claim rather than a drawing? Every property in it is computable from the adjacency: reachability by transitive closure, distance by path length, bisection by the cut, blocking by disjointness, survival by a link sweep. A drawing asserts them; a closure decides them.

Q2. What is the difference between a split fabric and a partitioned node? A split is two halves each internally whole — reach sets like 0011 and 1100. A partition is a node reaching only itself. The first is one cable, the second is one endpoint, and both present to an operator as "some things cannot reach some things".

Q3. Which of those is more dangerous? The split, because it looks healthier. Every endpoint still has neighbours and every local test passes; the failure is a subset of traffic failing for no locally visible reason.

Q4. Why is the worst-case hop count more useful than the mean? The mean is what a comparison quotes; the worst is what a budget must survive. In the four-node tree they are 2 and 4, and the gap widens with scale.

Q5. A hop budget of 2 and a pair at exactly 2 hops — inside or outside? Inside. > not >=. A comparison one off rejects every same-subtree pair in the fabric, which refuses a topology for a property it actually has.

Q6. What is the bisection and why can bandwidth not fix it? It is the number of links crossing a cut that divides the fabric in half. A crossing transfer consumes one, so the ceiling is a count. Faster switches on either side do not add links to the middle.

Q7. How do you tell a bisection problem from a placement problem? cross_pct. If an unusually high fraction of the offered load is crossing, the traffic pattern changed and the fix is placement. If the fraction is normal and the cut is still at its ceiling, the cut is too narrow.

Q8. Why is a bisection bottleneck invisible to endpoint monitoring? Because it is not a property of any endpoint or any switch. In the trace at Figure 2 the fabric drops traffic at cycles 3 and 4 while nothing in it is busy.

Q9. What exactly does non-blocking claim? That two transfers sharing no endpoint proceed simultaneously. It does not claim that transfers to a common endpoint do — that serialisation is correct.

Q10. How do you distinguish real contention from false contention? By whether the transfers share an endpoint. Sharing one is real and every fabric serialises it. Sharing none and still being serialised is a property of the topology, and it needs its own counter or it is invisible.

Q11. Why did the blocking model need eight endpoints? Because at four, a disjoint pair where one transfer crosses the middle and the other does not cannot exist. A mutation that blocked on the first transfer alone survived — not from a weak testbench but from a model too small to express the difference.

Q12. What do you do when a mutation survives for that reason? Widen the model, or replace the mutation if it is provably equivalent, and say which. Deleting it because it is inconvenient removes the record that the model has a blind spot.

Q13. How do you find a fabric's single points of failure? Remove each link in turn and recompute the closure. The output is a count, and the count is the answer to "how many single failures take this down" — which is a more useful question than "is it redundant".

Q14. Why assert which nodes each probe strands rather than just the total? Because a probe that removes a different link every time produces the same total. That mutation survived until per-link reach sets were asserted.

Q15. Cutting one link strands one endpoint out of four. Is the fabric still connected? No. It has lost every transfer that endpoint was part of. A still_connected that ignores one node is a check that passes on a fabric missing an endpoint.

Q16. What is a channel dependency cycle? Every channel held, and every holder waiting on the next one in the ring. Nothing releases, so nothing advances.

Q17. Is every channel being held a deadlock? No — that is a busy fabric. The cycle needs holding and waiting on the next. A model flagging occupancy alone reports a deadlock on every busy fabric it sees.

Q18. How does dimension-ordered routing prevent it? It forbids the turn that closes the cycle: all hops in one dimension before any in the other. It costs one refused turn and paths that are sometimes longer.

Q19. When would you accept adaptive routing anyway? When the traffic pattern makes the ordered path much longer and the deadlock risk is handled another way — escape channels, or virtual channels that break the cycle. The trade is real; what is not acceptable is taking it without knowing.

Q20. Why is radix the constraint that ends the argument? Because a switch cannot be talked into more ports. Every hop, every cut and every single point of failure in this chapter exists because the ninth endpoint needs a second switch.

Q21. Why measure port utilisation against the radix rather than the ports in use? Against the ports in use it reads 100 percent always. The testbench detaches one port and asserts 87 percent so the denominator cannot be the numerator.

Q22. What should a switch do with an attachment past its radix? Refuse it and count it. A refusal nobody counts becomes a capacity problem that presents as a missing device.

Q23. Is the endpoint latency charged once or per hop? Once. A model charging it per hop makes the fabric look responsible for everything, and it is the mutation that section 13's oracle exists to catch.

Q24. What does a fabric share of 0 percent tell you? That the access never left the endpoint, and no topology change will ever make it faster. If the workload is mostly local accesses, topology work is the wrong work.

Q25. Why does adding a link cost more than a link? Two ports, one at each end, out of a fixed radix. Section 14's fabric already spends 60 percent of its ports on itself, and those ports are not attaching anything a user asked for.

Q26. Why must the empty-fabric guard return zero rather than a hundred? Because a fabric with nothing in it does not spend all of its ports on itself. The testbench asserts it before anything is added, which is the only moment the guard is reachable.

Q27. Why does the acceptance gate produce a mask rather than a boolean? Because a refusal with no reason sends an architect back to redraw the whole shape. A mask sends them to widen one link. Each bit is asserted individually, because a mask with two fields transposed passes any check that only asks whether it is non-zero.

Q28. What is the failure mode of a review that checks everything except single points of failure? It accepts a fabric that works perfectly until one cable fails. Every other property is genuinely satisfied, which is what makes the acceptance convincing.

Q29. You have one extra port pair to spend. Where does it go? Across the bisection, unless the SPOF sweep says otherwise. It relieves the cut and removes a single point of failure at the same time — the redundant fabric in section 10 differs from the chain by exactly that link.

Q30. If you could compute one thing before building a fabric, which? The SPOF count. It is a few hundred closures in software, it is knowable entirely at design time, it is the one failure in this chapter that gives no warning at all, and it is routinely computed for the first time after an outage.

27. Exercises

1. Extend topo_reach to eight nodes and build a fat-tree adjacency. Compute its bisection by hand, then confirm it with bisect_load.

2. Add a DIRECTED parameter that makes one link one-way. Show that still_connected reading only r[0] misses it, and that reading every row does not.

3. Replace the drop-one-link probe in spof_probe with a drop-two-link sweep. Report how many pairs of failures cut the redundant fabric, and decide whether that number should change the design.

4. Give bisect_load backpressure instead of dropping. Show that n_dropped goes to zero and that peak_demand does not, and explain which one a real fabric should alarm on.

5. Build a topology that is non-blocking, within radix, and has a bisection of one. Show which constraint in topo_top refuses it and argue whether the refusal is right.

6. Add virtual channels to route_order so the forbidden turn becomes legal without forming a cycle. Measure the cost in state, and compare it to the one refused turn.

7. Parameterise hop_latency with a per-hop cost that grows with fabric size. Find the point at which adding a switch costs more latency than the capacity it adds is worth.

8. Take the 108-mutation suite and re-run it against a four-node blocking_fabric. Confirm the three model-size survivors return, and write down what each one would have cost in silicon.

28. Summary

A topology is six claims, and each one is a measurement.

• Reach: the closure, not the drawing. A split leaves two healthy halves; a partition leaves one endpoint outside the fabric.
• Distance: worst 4 hops against a mean of 2, from the same sweep. The mean gets quoted; the worst gets designed against.
• Width: a two-link cut dropped 1 of the same stream the one-link cut dropped 2 of, while no endpoint in the fabric was busy.
• Independence: three disjoint pairs served together, one falsely serialised by the blocking build — invisible from either endpoint.
• Survival: 0 single failures cut the redundant fabric and 3 cut the chain, one sweep apart.
• Radix: 8 ports, and the ninth endpoint is the reason every other property in this chapter is not free.

The two numbers to carry forward: 60 percent of the ports are spent on the fabric itself, and 45 percent of the worst-case latency is the fabric — so more than half of even the worst path is not a topology problem at all.

108 mutations, 108 killed. Three of the sixteen first-run survivors were not testbench gaps: they were cases a four-node model could not express. Widening the model was the fix, and it is the one worth remembering — when a mutation survives because your model is too small, the model is the thing that is wrong.

15.3 asks how the manager learns what is actually out there.