Muxes and crossbars at scale

From one 2:1 mux to a tree

A multiplexer (mux) passes one of its data inputs to its output, chosen by a select. A 2:1 mux of 8-bit words is eight 1-bit muxes, one per bit: 8 cells and 1 level of logic on this flow.

A wider mux is a tree of 2:1 muxes. Select bit 0 picks within pairs, bit 1 picks between the pairs, and so on. An 8:1 mux has 7 muxes per bit in 3 levels: 7 x 8 = 56 cells. You get that tree by writing an array index, d[sel], or a case on the select.

A chain of ? : tests says something else: test select 0, else test select 1, else test select 2. That is a priority chain (R1.5). Every test sits behind the one before, so the levels grow with N instead of log2(N).

A crossbar is one mux per output

A crossbar connects M inputs to N outputs. Each output has its own M:1 mux and its own select, so any output can show any input. Two outputs may show the same input in the same cycle.

Read the table two ways. Width scales the cells and not the levels: 4 x 4 at 32 bits is four times 4 x 4 at 8 bits, at the same 2 levels. Ports scale both: 8 x 8 costs 4.7 times 4 x 4 and adds a level.

When the crossbar is too big

A crossbar lets every output move a word in every cycle. If the brief does not need that, it is paying for parallel paths nobody uses. Two cheaper shapes follow from this module.

1. A shared bus with an arbiter

   One M:1 mux and an arbiter (R5.4) give one transfer per cycle among all sources. Here that is a single mux row instead of N of them.

2. Time multiplexing

   Fewer ports, more cycles: sources take turns on a smaller crossbar. This works when the brief's rate leaves cycles to spare.

Whichever shape you choose, write each mux as an array index or a case, and let the synthesizer build the tree. Keep ? : chains for real priority, where the order is part of the function.

The lab

Run the lab: six cycles, 0 outputs wrong. Synthesize: 96 cells and 2 levels of logic. Now change the defaults of xbar and synthesize again. W = 32 gives 384 cells. M = 16, N = 1 makes the crossbar one 16:1 mux: 180 cells and 6 levels.

Last, set the defaults back and replace the assign in mux_n with the chain below, which is right for M = 4 only. Run: still 0 outputs wrong. Synthesize: 108 cells and 4 levels of logic.

assign y = (sel == 0) ? d[0] : (sel == 1) ? d[1] : (sel == 2) ? d[2] : d[3];

Try it

Each line lists the four selects, then the four outputs, out[0] first. With sel = 1 1 1 1 every output shows input 1. At e4 the input words change and the paths stay: each output follows its select to the new word.

With the ? : chain in mux_n, the run prints the same seven lines. The function is the same; Synthesize reports 108 cells and 4 levels of logic instead of 96 and 2.

`timescale 1ns/1ps
module tb;
  logic clk = 0;
  always #5 clk = ~clk;                   // rising edges at 5, 15, 25, ...
  int edge_n = -1;
  always @(posedge clk) edge_n = edge_n + 1;
  logic [3:0][7:0] in;
  logic [3:0][1:0] sel;
  logic [3:0][7:0] out;
  int wrong = 0, cycles = 0;
  // Set the four selects: output j shows input s<j>; then advance one cycle.
  task automatic route(input int s0, input int s1, input int s2, input int s3);
    sel[0] = 2'(s0); sel[1] = 2'(s1); sel[2] = 2'(s2); sel[3] = 2'(s3);
    tick();
  endtask
  xbar #(.M(4), .N(4), .W(8)) dut (.in(in), .sel(sel), .out(out));
  // Advance to the next rising edge, wait for the design to settle, then print one line.
  task automatic tick();
    @(posedge clk); #1;
    cycles++;
    for (int j = 0; j < 4; j++) if (out[j] !== in[sel[j]]) wrong++;   // the model: out[j] = in[sel[j]]
    $display("e%0d sel=%0d %0d %0d %0d  out=%h %h %h %h", edge_n, sel[0], sel[1], sel[2], sel[3], out[0], out[1], out[2], out[3]);
  endtask
  initial begin
    in = {8'h43, 8'h32, 8'h21, 8'h10};    // in[0] = 10, in[1] = 21, in[2] = 32, in[3] = 43
    route(0, 1, 2, 3);                    // straight through
    route(3, 2, 1, 0);                    // reversed
    route(1, 1, 1, 1);                    // one input to every output
    route(2, 0, 3, 1);
    in = {8'hdd, 8'hcc, 8'hbb, 8'haa};    // new words on the same paths
    route(2, 0, 3, 1);
    route(0, 0, 3, 3);
    $display("%0d cycles, %0d outputs wrong", cycles, wrong);
    $finish(0);                             // quiet: no "$finish called" line
  end
endmodule

Check yourself

// mux_n: an N-to-1 multiplexer of W-bit words. y shows word sel of d.
module mux_n #(parameter int N = 4, parameter int W = 8) (
  input  logic [N-1:0][W-1:0]   d,
  input  logic [$clog2(N)-1:0] sel,
  output logic [W-1:0]         y
);
  assign y = d[sel];             // an array index: the synthesizer builds a tree of 2:1 muxes
endmodule

// xbar: M inputs, N outputs, W bits each. Output j shows input sel[j];
// two outputs may show the same input, and an input may go nowhere.
module xbar #(parameter int M = 4, parameter int N = 4, parameter int W = 8) (
  input  logic [M-1:0][W-1:0]         in,
  input  logic [N-1:0][$clog2(M)-1:0] sel,
  output logic [N-1:0][W-1:0]         out
);
  for (genvar j = 0; j < N; j++) begin : g_out
    mux_n #(.N(M), .W(W)) u_mux (.d(in), .sel(sel[j]), .y(out[j]));
  end
endmodule

module tb;
  logic [3:0][7:0] in;
  logic [3:0][1:0] sel;
  logic [3:0][7:0] out;
  xbar #(.M(4), .N(4), .W(8)) dut (.in(in), .sel(sel), .out(out));
  initial begin
    in[0] = 8'h11; in[1] = 8'h22; in[2] = 8'h33; in[3] = 8'h44;
    sel[0] = 2'd3; sel[1] = 2'd3; sel[2] = 2'd0; sel[3] = 2'd1;
    #1 $display("out: %h %h %h %h", out[0], out[1], out[2], out[3]);
    $finish(0);
  end
endmodule

assign y = sel[1] ? (sel[0] ? d[3] : d[2]) : (sel[0] ? d[1] : d[0]);

assign y = (sel == 2'd0) ? d[0] : (sel == 2'd1) ? d[1] : (sel == 2'd2) ? d[2] : d[3];

assign y = d[sel];

assign y = sel[0] ? (sel[1] ? d[3] : d[2]) : (sel[1] ? d[1] : d[0]);