add simple round-robin arbiter

+ Should check how well it synthesises with OpenROAD or something,
  Vivado seemed to kind of choke on it and it was way slower/bigger than
  I was expecting.

3 files changed, 185 insertions, 1 deletions

diff --git a/src/arb.sv b/src/arb.sv
new file mode 100644
index 0000000..15d89b3
--- /dev/null
+++ b/src/arb.sv
@@ -0,0 +1,101 @@
+module first_set #(
+	parameter WIDTH = 32
+)(
+	input  reg[WIDTH-1 :0] cand,
+	output reg[WIDTH-1 :0] selected
+);
+
+/* base case */
+if (WIDTH == 1) begin :base
+	assign selected  = cand;
+end
+
+/* recursive case */
+else begin :recursive
+	localparam SLICE_WIDTH = WIDTH / 2;
+	logic[SLICE_WIDTH-1:0] left, right;
+	logic pref_left, pref_right;
+	logic empty_left, empty_right;
+
+	first_set #(
+		.WIDTH(SLICE_WIDTH)
+	) first_set_left (
+		.cand(cand[SLICE_WIDTH +: SLICE_WIDTH]),
+		.selected (left)
+	);
+
+	first_set #(
+		.WIDTH(SLICE_WIDTH)
+	) first_set_right (
+		.cand(cand[0 +: SLICE_WIDTH]),
+		.selected (right)
+	);
+
+	assign selected = right != '0
+			? {{SLICE_WIDTH{1'b0}}, right}
+			: {left, {SLICE_WIDTH{1'b0}}}
+			;
+end
+
+always_comb begin
+	assert ($onehot0(selected));
+end
+
+`ifdef NOSUCHDEF
+/* assertions that verilator don't support, apparently */
+assert property (WIDTH >= 1)
+else $error("input width too narrow");
+
+assert property (1 << $clog2(WIDTH) == WIDTH)
+else $error("width not pow2");
+
+`endif
+
+endmodule // arb_recursive
+
+module arb #(
+	parameter WIDTH = 32
+)(
+	input clk,
+	input rstx,
+
+	input [WIDTH-1:0] cand,
+	output[WIDTH-1:0] selected
+);
+
+localparam W2 = 1 << $clog2(WIDTH);
+localparam DEPTH = W2 == 1 ? 1 : $clog2(W2);
+
+logic[W2-1:0] w2_cand, w2_selected, mask, next_mask, rot_selected;
+
+/* if there are candidates within the mask of 'above preferred index', use them,
+ * otherwise invert the mask and use candidates 'below' preferred index. */
+assign w2_cand = ((cand & mask) == '0) ? cand & ~mask : cand & mask;
+
+first_set #(
+	.WIDTH(W2)
+) first_set_i (
+	.cand    (w2_cand),
+	.selected(w2_selected)
+);
+
+assign selected = w2_selected;
+
+assign rot_selected = {
+	w2_selected[0 +: W2-1],
+	w2_selected[W2-1]
+};
+
+assign next_mask = ~(rot_selected - 1) | rot_selected;
+
+always_ff @(posedge clk or negedge rstx)
+if (!rstx) begin
+	mask  <= ~0;
+end else begin
+	if (selected != 0 && mask != next_mask)
+		mask <= next_mask;
+	else
+		mask <= mask;
+end
+
+endmodule // arb
diff --git a/tb/Makefile b/tb/Makefile
index f34cb5e..f67e6af 100644
--- a/tb/Makefile
+++ b/tb/Makefile
@@ -1,4 +1,4 @@
-all: rv2insn sched ttarv32
+all: rv2insn sched arb ttarv32
 
 .PHONY: sched
 sched: sched_tb.sv ../src/sched.sv ../src/common.svh
@@ -13,6 +13,11 @@ rv2insn: rv2insn_tb.sv ../src/rv2insn.sv ../src/common.svh
 	verilator --Mdir rv2insn_objdir --assert --trace --binary -I../src rv2insn_tb.sv
 	./rv2insn_objdir/Vrv2insn_tb
 
+.PHONY: arb
+arb: arb_tb.sv ../src/arb.sv
+	verilator --Mdir arb_objdir --assert --trace --binary -I../src arb_tb.sv
+	./arb_objdir/Varb_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/arb_tb.sv b/tb/arb_tb.sv
new file mode 100644
index 0000000..909c5b2
--- /dev/null
+++ b/tb/arb_tb.sv
@@ -0,0 +1,78 @@
+module arb_tb;
+
+localparam WIDTH = 32;
+
+reg clk;
+reg rstx;
+logic[WIDTH-1:0] cand;
+logic[WIDTH-1:0] selected;
+
+arb #(
+	.WIDTH(32)
+) arb_i (
+	.clk(clk),
+	.rstx(rstx),
+	.cand(cand),
+	.selected(selected)
+);
+
+initial begin
+	clk = 0;
+	forever begin
+		#5 clk = ~clk;
+	end
+end
+
+initial begin
+	$dumpfile("arb_tb.fst");
+	$dumpvars();
+
+	/* trigger resets */
+	rstx = 0;
+	#10 rstx = 1;
+
+	/* honestly, I'm a bit confused about this, if I try to make this be at
+	* a positive clock edge, the selected == 1 condition disappears because
+	* cand apparently triggers `selected` to be recalculated first, which
+	* then is fed into `mask` which then re-triggers `selected` and causes
+	* it to 'skip' ahead to selected == 2. When looking at the waveforms,
+	* the next @(posedge clk) shows 2 while the assert passes. I guess the
+	* assert is run first in the time step...? */
+	cand = ~0;
+
+	@(posedge clk);
+	assert (selected == 1)
+	else $error("expected 1, got ", selected);
+
+	@(posedge clk);
+	assert (selected == 2)
+	else $error("expected 2, got ", selected);
+
+	/* wait one clock cycle, should move forward by one */
+	@(posedge clk);
+	assert (selected == 4)
+	else $error("expected 4, got ", selected);
+
+	/* skip next index */
+	cand = '0;
+
+	@(posedge clk);
+	assert (selected == 0)
+	else $error("expected 0, got ", selected);
+
+	cand = ~8;
+
+	@(posedge clk);
+	assert (selected == 16)
+	else $error("expected 16, got ", selected);
+
+	/* check that ID wraps around nicely */
+	for (int i = 0; i < 32 - 4; ++i)
+		@(posedge clk);
+
+	assert (selected == 1)
+	else $error("wraparound broken, expected 1, got ", selected);
+
+	$finish;
+end
+endmodule