From f4afcfa58eb90d14abd55d79640ecda13b23dc21 Mon Sep 17 00:00:00 2001 From: Kimplul Date: Sun, 27 Sep 2026 22:30:41 +0300 Subject: implement circular router + 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. --- src/common.svh | 2 + src/router.sv | 160 +++++++++++++++++++++++++++++++++++++++++++++++++++++ src/skid_buffer.sv | 53 ++++++++++++++++++ tb/Makefile | 7 ++- tb/router_tb.sv | 153 ++++++++++++++++++++++++++++++++++++++++++++++++++ 5 files changed, 374 insertions(+), 1 deletion(-) create mode 100644 src/router.sv create mode 100644 src/skid_buffer.sv create mode 100644 tb/router_tb.sv 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 -- cgit v1.3