initial scheduler

3 files changed, 249 insertions, 0 deletions

diff --git a/src/common.svh b/src/common.svh
new file mode 100644
index 0000000..42fdb71
--- /dev/null
+++ b/src/common.svh
@@ -0,0 +1,6 @@
+`ifndef __COMMON_SVH__
+`define __COMMON_SVH__
+
+`define NOP 0
+
+`endif /* __COMMON_SVH__ */
diff --git a/src/sched.sv b/src/sched.sv
new file mode 100644
index 0000000..c538dc2
--- /dev/null
+++ b/src/sched.sv
@@ -0,0 +1,109 @@
+`include "common.svh"
+
+module sched
+#(
+	parameter QUE_DEPTH,
+	parameter SLOT_COUNT,
+	parameter SLOT_DEPTH,
+	type port_t,
+	type mov_t,
+	type insn_t,
+	type slot_t
+)(
+	input insn_t[QUE_DEPTH-1:0] que_i,
+	output insn_t[QUE_DEPTH-1:0] que_o,
+	input slot_t[SLOT_COUNT-1:0] slots_i,
+	output slot_t[SLOT_COUNT-1:0] slots_o
+);
+
+/* check_* don't always use whole signal they're given, so I think it's best to
+ * just silence this */
+/* verilator lint_off UNUSEDSIGNAL */
+
+function automatic insn_t[QUE_DEPTH-1:0] next_insn(insn_t[QUE_DEPTH-1:0] que);
+	return que >> $bits(insn_t);
+endfunction
+
+/* check if a write is to the same destination port */
+function automatic logic check_dst(mov_t d1, mov_t[SLOT_DEPTH-1:0] d2);
+	logic[SLOT_DEPTH-1:0] dep = '0;
+	for (int i = 0; i < SLOT_DEPTH; ++i) begin
+		dep[i] = d1.dst != `NOP & d1.dst == d2[i].dst;
+	end
+	return dep != 0;
+endfunction
+
+/* check if any read is from an output port that's not free */
+function automatic logic check_overlap(mov_t d1, mov_t[SLOT_DEPTH-1:0] d2);
+	logic[SLOT_DEPTH-1:0] dep = '0;
+	for (int i = 0; i < SLOT_DEPTH; ++i) begin
+		dep[i] = d1.src != `NOP & d1.src == d2[i].dst;
+	end
+	return dep != 0;
+endfunction
+
+/* check if instruction depends on any existing slots */
+function automatic logic depends(insn_t i, slot_t[SLOT_COUNT-1:0] slots);
+	logic[SLOT_COUNT-1:0] dep = '0;
+	for (int ii = 0; ii < SLOT_COUNT; ++ii) begin
+		logic same_dst = check_dst(i.out, slots[ii].out);
+		logic overlap1 = check_overlap(i.in[0], slots[ii].out);
+		logic overlap2 = check_overlap(i.in[1], slots[ii].out);
+
+		logic same_src1 = i.in[0].dst != `NOP
+				& i.in[0].dst == slots[ii].in[0].dst;
+
+		/* op must have trigger so don't need to check against NOP */
+		logic same_src2 = i.in[1].dst == slots[ii].in[1].dst;
+
+		dep[ii] = same_dst | overlap1 | overlap2 | same_src1 | same_src2;
+	end
+	return dep != 0;
+endfunction
+
+function automatic logic is_noop(mov_t m);
+	return m.src == `NOP && m.dst == `NOP;
+endfunction
+
+function automatic mov_t[SLOT_DEPTH-1:0] place_out(int i, logic placed,
+	mov_t o, mov_t[SLOT_DEPTH-1:0] out);
+	if (i < SLOT_DEPTH) begin
+		logic ok = !placed & is_noop(out[i]);
+		out[i] = ok ? o : out[i];
+		return place_out(i + 1, ok ? 1 : placed, o, out);
+	end else begin
+		return out;
+	end
+endfunction
+
+/* place instruction into slot */
+function automatic slot_t place(insn_t i, slot_t src);
+	slot_t slot;
+	slot.op = i.op;
+	slot.in = i.in;
+	slot.out = place_out(0, 0, i.out, src.out);
+	return slot;
+endfunction
+
+typedef struct packed {
+	insn_t[QUE_DEPTH-1:0] que;
+	slot_t[SLOT_COUNT-1:0] slots;
+} stages_out_t;
+
+function automatic stages_out_t stages(int i,
+	insn_t[QUE_DEPTH-1:0] que, slot_t[SLOT_COUNT-1:0] slots);
+	if (i < SLOT_COUNT) begin
+		logic ok = !depends(que[0], slots);
+		slots[i] = ok ? place(que[0], slots[i]) : slots[i];
+		return stages(i + 1, ok ? next_insn(que) : que, slots);
+	end else begin
+		return {que, slots};
+	end
+endfunction
+
+always_comb begin
+	stages_out_t out = stages(0, que_i, slots_i);
+	que_o = out.que;
+	slots_o = out.slots;
+end
+endmodule
diff --git a/tb/sched_tb.sv b/tb/sched_tb.sv
new file mode 100644
index 0000000..8db66b3
--- /dev/null
+++ b/tb/sched_tb.sv
@@ -0,0 +1,134 @@
+`include "common.svh"
+
+module sched_tb;
+
+typedef enum logic [7:0] {
+	NOP = `NOP,
+	R0,
+	R1,
+	R2,
+	R3,
+	R4,
+	R5,
+	R6,
+	R7,
+	R8,
+	R9,
+	R10,
+	R11,
+	R12,
+	R13,
+	R14,
+	R15,
+	R16,
+	R17,
+	R18,
+	R19,
+	R20,
+	R21,
+	R22,
+	R23,
+	R24,
+	R25,
+	R26,
+	R27,
+	R28,
+	R29,
+	R30,
+	R31,
+
+	ALU0,
+	ALU1
+} port_t;
+
+typedef logic [19:0] op_t;
+
+typedef struct packed {
+	port_t src;
+	port_t dst;
+} mov_t;
+
+typedef struct packed {
+	mov_t[1:0] in;
+	mov_t out;
+	op_t op;
+} insn_t;
+
+typedef struct packed {
+	mov_t[1:0] in;
+	mov_t[0:0] out;
+	op_t op;
+} slot_t;
+
+slot_t[1:0] prev_slots;
+slot_t[1:0] next_slots;
+insn_t[2:0] prev_que;
+insn_t[2:0] next_que;
+
+sched #(
+	.QUE_DEPTH(3),
+	.SLOT_COUNT(2),
+	.SLOT_DEPTH(1),
+	.port_t(port_t),
+	.mov_t(mov_t),
+	.insn_t(insn_t),
+	.slot_t(slot_t)
+) sched (
+	.que_i(prev_que),
+	.que_o(next_que),
+	.slots_i(prev_slots),
+	.slots_o(next_slots)
+);
+
+`define assert(signal, value) \
+	if (signal !== value) begin \
+		$error("%m: signal != value"); \
+	end
+
+slot_t[1:0] first_check = {68'b0, {R2, ALU0}, {R3, ALU0}, {ALU0, R1}, 20'h123};
+slot_t[1:0] second_check = {
+		{{R2, ALU0}, {R1, ALU0}, {ALU0, R5}, 20'h789},
+		{{R2, ALU1}, {R1, ALU1}, {ALU1, R4}, 20'h456}
+		};
+
+initial begin
+	$dumpfile("sched_tb.vcd");
+	$dumpvars();
+
+	/* pretend we've queued something like
+	* add r1, r2, r3
+	* add r4, r2, r1
+	* add r5, r2, r1
+	*
+	* should end up with something like
+	* add r1, r2, r3 noop
+	* add r4, r2, r1 add r5, r2, r1
+	*/
+	prev_que = {
+		/* src2, src1, out, op, apparently. Have to get used to
+		* systemverilog's way of laying out bits, huh. */
+		{{R2, ALU0}, {R1, ALU0}, {ALU0, R5}, 20'h789},
+		{{R2, ALU1}, {R1, ALU1}, {ALU1, R4}, 20'h456},
+		{{R2, ALU0}, {R3, ALU0}, {ALU0, R1}, 20'h123}
+		/* also, 'reverse' order, first instruction at bottom */
+	};
+
+	prev_slots = '0;
+
+	#10
+
+	assert (next_slots == first_check)
+	else $error("\nwanted:\t%h", first_check, "\ngot:%h\t", next_slots);
+
+	/* pretend all operations finished */
+	prev_slots = '0;
+	prev_que = next_que;
+
+	#10
+
+	assert (next_slots == second_check)
+	else $error("\nwanted:\t%h", second_check, "\ngot:\t%h", next_slots);
+
+	#10 $finish;
+end
+endmodule