implement circular routerHEADmaster

+ Not great latency, but has a fairly high fmax and low resource usage
  on my FPGA, so go with this for now. Likely better suited for data
  path, unsure what I'll do for the control path.

5 files changed, 374 insertions, 1 deletions

diff --git a/src/common.svh b/src/common.svh
index 67a87d2..131a2ca 100644
--- a/src/common.svh
+++ b/src/common.svh
@@ -116,4 +116,6 @@ typedef enum op_t {
 `define rn(r) (REG + port_t'(r))
 `define alu(fu) (ALU + port_t'(fu))
 
+`define COUNTER(x) ((x) > 1 ? $clog2(x) : 1)
+
 `endif /* __COMMON_SVH__ */
diff --git a/src/router.sv b/src/router.sv
new file mode 100644
index 0000000..b496ab9
--- /dev/null
+++ b/src/router.sv
@@ -0,0 +1,160 @@
+/* Idea: circular router, where packets are added to a ring and popped off one
+ * when they encounter a node which they match. Relatively high minimum latency,
+ * but simple implementation and *should* be fairly cheap in hardware,
+ * let's see I guess.
+ *
+ * Skid buffers on inputs.
+ *
+ * Should fairly easily allow a form of broadcasting as well by just checking
+ * that visited is all ones, but that's not currently implemented.
+ *
+ * Should presumably also add masking so that users can check when
+ * a device matches, for now it's just a fixed integer sequence.
+ */
+
+module router #(
+	/* number of ports */
+	parameter unsigned N = 4,
+
+	/* index of this router */
+	parameter unsigned I = 0,
+
+	/* arbitrary packet payload type */
+	parameter type data_t = logic,
+
+	/* structure with to/from address info, should maybe add some macro for
+	* generating such a type? */
+	parameter type addr_t = logic
+)(
+	input clk_i,
+	input rstx_i,
+
+	/* TODO SV interfaces? */
+
+	/* first two are up/down wrt. I, in that order, then come
+	 * devices, referred to by index + 2 */
+	input  logic [N+2-1:0] valid_i,
+	output logic [N+2-1:0] ready_o,
+	input  addr_t[N+2-1:0] addr_i,
+	input  data_t[N+2-1:0] data_i,
+
+	output logic [N+2-1:0] valid_o,
+	input  logic [N+2-1:0] ready_i,
+	output addr_t[N+2-1:0] addr_o,
+	output data_t[N+2-1:0] data_o
+);
+
+localparam NW = $bits(addr_i[0].dst.node);
+localparam DW = $bits(addr_i[0].dst.dev);
+
+typedef struct packed {
+	logic alive;
+	logic[N+2-1:0] visited;
+	addr_t addr;
+	data_t data;
+} meta_t;
+
+meta_t[N+2-1:0] ring_d, ring_q;
+
+logic [N+2-1:0] send, sent, recv;
+meta_t[N+2-1:0] handle, insert;
+
+typedef struct packed {
+	addr_t addr;
+	data_t data;
+} skid_t;
+
+logic [N+2-1:0] skid_valid_i, skid_ready_o;
+addr_t[N+2-1:0] skid_addr_i;
+data_t[N+2-1:0] skid_data_i;
+
+/* skid buffers kind of make this file more difficult to read, should I start
+ * doing something like *_skid where I wrap a central block in skip buffers,
+ * presumably always on the input side or something along those lines? */
+for (genvar i = 0; i < N + 2; ++i) begin :skidbuffers
+	skid_t in, out;
+	assign in = '{addr: addr_i[i], data: data_i[i]};
+	assign skid_addr_i[i] = out.addr;
+	assign skid_data_i[i] = out.data;
+
+	skid_buffer #(
+		.W($bits(skid_t))
+	) skid_i (
+		.clk_i,
+		.rstx_i,
+
+		.valid_i(valid_i[i]),
+		.ready_o(ready_o[i]),
+		.data_i (in        ),
+
+		.valid_o(skid_valid_i[i]),
+		.ready_i(skid_ready_o[i]),
+		.data_o (out            )
+	);
+end
+
+for (genvar i = 0; i < N + 2; ++i)
+always_comb begin :gen_ring_knot
+	/* default values */
+	handle[i] = ring_d[i];
+	send[i]   = 1'b0;
+
+	/* first, try to send out an incoming packet */
+	if (ring_d[i].alive) begin
+		/* packet wasn't accepted by anyone, send it back */
+		if (&handle[i].visited)
+			handle[i].addr.dst = handle[i].addr.src;
+
+		/* up */
+		if (i == 0)
+			send[i] = handle[i].addr.dst.node > I[0+:NW];
+		/* down */
+		else if (i == 1)
+			/* slightly silly Verilator warning silencing */
+			send[i] = I == 0 ? 0 : handle[i].addr.dst.node < I[0+:NW];
+		/* dev */
+		else
+			send[i] = handle[i].addr.dst.node == I[0+:NW]
+				& handle[i].addr.dst.dev  == (i - 2);
+	end
+
+	valid_o[i] = send[i];
+	addr_o[i]  = handle[i].addr;
+	data_o[i]  = handle[i].data;
+	sent[i]    = valid_o[i] && ready_i[i];
+
+	/* mark this packet having visited us. If we did try to send it, but
+	 * the receiver wasn't ready, don't set the visited bit so the packet can
+	 * come around a second time in the future to try again. */
+	if (send[i])
+		handle[i].visited[i] |= sent[i];
+	else
+		handle[i].visited[i] |= 1'b1;
+
+	if (sent[i])
+		handle[i].alive = 1'b0;
+
+	/* next, try to insert a new packet into the ring */
+	skid_ready_o[i] = !handle[i].alive;
+	recv[i] = skid_valid_i[i] && skid_ready_o[i];
+
+	insert[i] = '{
+		alive: recv[i],
+		/* sending to oneself is nonsensical, so we automatically visit
+		 * the starting node */
+		visited: 1 << i,
+		addr: skid_addr_i[i],
+		data: skid_data_i[i]
+	};
+
+	/* send either the new packet or the existing one to the next node in
+	 * the ring */
+	ring_q[(i + 1) % (N + 2)] = recv[i] ? insert[i] : handle[i];
+end
+
+for (genvar i = 0; i < N + 2; ++i)
+always_ff @(posedge clk_i or negedge rstx_i)
+if (!rstx_i) ring_d[i] <= '0;
+else         ring_d[i] <= ring_q[i];
+
+endmodule // router
diff --git a/src/skid_buffer.sv b/src/skid_buffer.sv
new file mode 100644
index 0000000..3ea6d0d
--- /dev/null
+++ b/src/skid_buffer.sv
@@ -0,0 +1,53 @@
+/* adjusted from pulp common_cells/spill_register_flushable.sv */
+
+module skid_buffer #(
+	parameter unsigned W = 2
+)(
+	input clk_i,
+	input rstx_i,
+
+	input valid_i,
+	output ready_o,
+	input [W-1:0] data_i,
+
+	output valid_o,
+	input  ready_i,
+	output [W-1:0] data_o
+);
+
+logic a_fill, a_full, a_drain, b_fill, b_full, b_drain;
+logic [W-1:0] a, b;
+
+/* reg a */
+always_ff @(posedge clk_i or negedge rstx_i)
+if (!rstx_i)
+	a <= '0;
+else if (a_fill)
+	a <= data_i;
+
+always_ff @(posedge clk_i or negedge rstx_i)
+if (!rstx_i)
+	a_full <= '0;
+else if (a_fill || a_drain)
+	a_full <= a_fill;
+
+always_ff @(posedge clk_i or negedge rstx_i)
+if (!rstx_i)
+	b <= '0;
+else if (b_fill)
+	b <= a;
+
+/* fill A first, if upstream can't read A in time, place A into B and skid the
+ * input into A until upstream can clean out B */
+assign a_fill  = valid_i &&  ready_o;
+assign a_drain = a_full  && !b_full;
+
+assign b_fill  = a_drain && !ready_i;
+assign b_drain = b_full  &&  ready_i;
+
+assign ready_o = !a_full || !b_full;
+assign valid_o =  a_full ||  b_full;
+
+assign data_o  = b_full ? b : a;
+
+endmodule // skid_buffer
diff --git a/tb/Makefile b/tb/Makefile
index f67e6af..9f51302 100644
--- a/tb/Makefile
+++ b/tb/Makefile
@@ -1,4 +1,4 @@
-all: rv2insn sched arb ttarv32
+all: rv2insn sched arb ttarv32 router
 
 .PHONY: sched
 sched: sched_tb.sv ../src/sched.sv ../src/common.svh
@@ -18,6 +18,11 @@ arb: arb_tb.sv ../src/arb.sv
 	verilator --Mdir arb_objdir --assert --trace --binary -I../src arb_tb.sv
 	./arb_objdir/Varb_tb
 
+.PHONY: router
+router: router_tb.sv ../src/router.sv
+	verilator --Mdir router_objdir --assert --trace --binary -I../src router_tb.sv
+	./router_objdir/Vrouter_tb
+
 .PHONY: ttarv32
 ttarv32: ttarv32_tb.sv ../src/ttarv32.sv ../src/rv2insn.sv ../src/sched.sv ../src/common.svh
 	riscv32-unknown-elf-gcc -ffreestanding -nostdlib -march=rv32i -mabi=ilp32 \
diff --git a/tb/router_tb.sv b/tb/router_tb.sv
new file mode 100644
index 0000000..ba83568
--- /dev/null
+++ b/tb/router_tb.sv
@@ -0,0 +1,153 @@
+`include "common.svh"
+
+module router_tb;
+
+logic clk, rstx;
+
+typedef struct packed {
+	logic [7:0] node;
+	logic [7:0] dev;
+} ds_t;
+
+typedef struct packed {
+	ds_t src;
+	ds_t dst;
+} addr_t;
+
+typedef struct packed {
+	int unsigned i;
+} data_t;
+
+localparam N = 1;
+localparam M = 2;
+
+logic [N+2-1:0] valid_o[M], ready_i[M];
+logic [N+2-1:0] valid_i[M], ready_o[M];
+addr_t[N+2-1:0] addr_o[M],  addr_i[M];
+data_t[N+2-1:0] data_o[M],  data_i[M];
+
+for (genvar i = 0; i < M; ++i) begin :gen_router
+	router #(
+		.N(N),
+		.I(i),
+
+		.data_t(data_t),
+		.addr_t(addr_t)
+	) router (
+		.clk_i(clk),
+		.rstx_i(rstx),
+
+
+		.valid_i(valid_i[i]),
+		.ready_o(ready_o[i]),
+		.addr_i (addr_i [i]),
+		.data_i (data_i [i]),
+
+		.valid_o(valid_o[i]),
+		.ready_i(ready_i[i]),
+		.addr_o (addr_o [i]),
+		.data_o (data_o [i])
+	);
+end
+
+/* easy to get confused, but here's what we're testing:
+ *
+ *     dev0               dev1
+ *      |                  ^
+ *      v                  |
+ *      P2                 P2
+ *    +-------+          +-------+
+ * P1 | node0 | P0 -> P1 | node1 | P0
+ *    +-------+          +-------+
+ *
+ * dev0  sends a   packet to node0, 1 -> valid_i[0][2]
+ * node0 sends the packet to node1, valid_o[0][0] -> valid_i[1][1]
+ * node1 sends the packet to dev1 , valid_o[1][2]
+ */
+
+/* node0 -> node1 */
+assign valid_i[1][1] = valid_o[0][0];
+assign data_i [1][1] = data_o [0][0];
+assign addr_i [1][1] = addr_o [0][0];
+assign ready_i[1][1] = ready_o[0][0];
+
+/* node1 -> node0 */
+assign valid_i[0][0] = valid_o[1][1];
+assign data_i [0][0] = data_o [1][1];
+assign addr_i [0][0] = addr_o [1][1];
+assign ready_i[0][0] = ready_o[1][1];
+
+
+initial begin :test
+	logic found = 0;
+
+	$dumpfile("router_tb.vcd");
+	$dumpvars();
+
+	for (int i = 0; i < M; ++i)
+	for (int j = 0; j < N + 2; ++j) begin :init
+		valid_i[i][j] = '0;
+		ready_i[i][j] = '0;
+
+		addr_i [i][j] = '{
+			src: '{
+				node: 0,
+				dev:  0
+			},
+
+			dst: '{
+				node: 0,
+				dev:  0
+			}
+		};
+		data_i [i][j] = '{i: 0};
+	end
+
+	clk = 0;
+	rstx = 0;
+
+	#1
+
+	rstx = 1;
+
+	/* send value 3 from first dev to second */
+	valid_i[0][2] = 1'b1;
+	data_i [0][2] = '{i: 3};
+	addr_i [0][2] = '{
+		src: '{
+			node: 0,
+			dev:  0
+		},
+
+		dst: '{
+			node: 1,
+			dev:  0
+		}
+	};
+
+	/* mark receiver as ready */
+	ready_i[1][2] = 1'b1;
+
+	#1 clk = 1;
+	#1 clk = 0;
+
+	valid_i[0][2] = 1'b0;
+
+	for (int i = 0; i < 10; ++i) begin
+		if (valid_o[1][2]) begin
+			found = 1;
+			break;
+		end
+
+		#1 clk = ~clk;
+	end
+
+	assert (found)
+	else $error("took too long to produce output");
+
+	assert (data_o[1][2] == 3)
+	else $error("got wrong result");
+
+	#10 $finish;
+end
+endmodule