starvation seems to work

+ With the limitation that a grid node can only attempt one move per
  clock, which *seems* to be the easiest strategy to implement in hardware,
  but I should try experimenting with more complex routing/priority
  assignment schemes to speed up the system overall

3 files changed, 186 insertions, 0 deletions

diff --git a/tests/starved_grid/sim.c b/tests/starved_grid/sim.c
new file mode 100644
index 0000000..d858917
--- /dev/null
+++ b/tests/starved_grid/sim.c
@@ -0,0 +1,134 @@
+/* testcase for a 64x64 grid of processors, that all just spam the first memory
+ * region due to there being a 'lock' variable there, more or less the worst
+ * possible program for performance. */
+#include <assert.h>
+
+#include <gran/root.h>
+#include <gran/mem/simple_mem.h>
+#include <gran/bus/simple_bus.h>
+#include <gran/uart/simple_uart.h>
+#include <gran/grid/node.h>
+#include <gran/cpu/riscv/simple_riscv64.h>
+
+unsigned char _tmp_test_bin[] = {
+  0x1b, 0x86, 0x05, 0x00, 0x63, 0x18, 0x05, 0x00, 0x93, 0x07, 0x20, 0x00,
+  0x1b, 0x86, 0x05, 0x00, 0x63, 0x88, 0xf5, 0x0c, 0x93, 0x16, 0x05, 0x01,
+  0x13, 0x07, 0x10, 0x00, 0xb3, 0xe6, 0xb6, 0x00, 0x13, 0x17, 0x07, 0x03,
+  0x83, 0x37, 0x07, 0x00, 0xe3, 0x9e, 0xd7, 0xfe, 0x1b, 0x57, 0x35, 0x00,
+  0xb7, 0x17, 0x00, 0x00, 0x93, 0x06, 0x80, 0x02, 0x13, 0x77, 0x77, 0x00,
+  0x23, 0x80, 0xd7, 0x00, 0x13, 0x07, 0x07, 0x03, 0x93, 0x76, 0x75, 0x00,
+  0x23, 0x80, 0xe7, 0x00, 0x13, 0x87, 0x06, 0x03, 0x23, 0x80, 0xe7, 0x00,
+  0x93, 0x06, 0xc0, 0x02, 0x1b, 0xd7, 0x35, 0x00, 0x23, 0x80, 0xd7, 0x00,
+  0x13, 0x77, 0x77, 0x00, 0x93, 0x06, 0x00, 0x02, 0x23, 0x80, 0xd7, 0x00,
+  0x13, 0x07, 0x07, 0x03, 0x93, 0xf6, 0x75, 0x00, 0x23, 0x80, 0xe7, 0x00,
+  0x13, 0x87, 0x06, 0x03, 0x23, 0x80, 0xe7, 0x00, 0x13, 0x07, 0x90, 0x02,
+  0x23, 0x80, 0xe7, 0x00, 0x13, 0x07, 0xa0, 0x00, 0x23, 0x80, 0xe7, 0x00,
+  0x93, 0x07, 0xf0, 0x00, 0x1b, 0x07, 0x05, 0x00, 0x63, 0x06, 0xf5, 0x02,
+  0x63, 0x08, 0xf6, 0x02, 0x1b, 0x87, 0x15, 0x00, 0x13, 0x17, 0x07, 0x03,
+  0x13, 0x57, 0x07, 0x03, 0x93, 0x17, 0x05, 0x01, 0xb3, 0xe7, 0xe7, 0x00,
+  0x13, 0x07, 0x10, 0x00, 0x13, 0x17, 0x07, 0x03, 0x23, 0x30, 0xf7, 0x00,
+  0x6f, 0x00, 0x00, 0x00, 0xe3, 0x1e, 0xe6, 0xfc, 0x73, 0x00, 0x10, 0x00,
+  0x1b, 0x05, 0x15, 0x00, 0x13, 0x15, 0x05, 0x03, 0x13, 0x55, 0x05, 0x03,
+  0x13, 0x07, 0x00, 0x00, 0x6f, 0xf0, 0x1f, 0xfd, 0x93, 0x07, 0x10, 0x00,
+  0x93, 0x97, 0x07, 0x03, 0x23, 0xb0, 0x07, 0x00, 0x13, 0x07, 0x00, 0x03,
+  0xb7, 0x17, 0x00, 0x00, 0x23, 0x80, 0xe7, 0x00, 0x13, 0x07, 0xa0, 0x00,
+  0x23, 0x80, 0xe7, 0x00, 0x6f, 0xf0, 0xdf, 0xf2
+};
+unsigned int _tmp_test_bin_len = 260;
+
+static struct component *get_grid(struct component **grid, int i, int j, uint8_t x, uint8_t y)
+{
+	if (i < 0)
+		return NULL;
+
+	if (j < 0)
+		return NULL;
+
+	if (i >= x)
+		return NULL;
+
+	if (j >= y)
+		return NULL;
+
+	return grid[i * x + j];
+}
+
+static stat build_grid(struct clock_domain *clk, uint8_t x, uint8_t y)
+{
+	struct component **grid = calloc(x * y, sizeof(struct component *));
+	assert(grid);
+
+	struct component **pes = calloc(x * y, sizeof(struct component *));
+	assert(pes);
+
+	for (size_t i = 0; i < x; ++i)
+	for (size_t j = 0; j < y; ++j) {
+		struct component *node = create_grid_node(i, j);
+		clock_domain_add(clk, node);
+		grid[i * x + j] = node;
+
+		if (i == 0 && j == 0)
+			continue;
+
+		if (i == 0 && j == 1)
+			continue;
+
+		struct component *imem = create_simple_mem(4096);
+		init_simple_mem(imem, 0, _tmp_test_bin_len, _tmp_test_bin);
+
+		uint64_t rcv = grid_addr(i, j, 0);
+		struct component *rv64 = create_simple_riscv64(rcv, 0, imem, node);
+		simple_riscv64_set_reg(rv64, 10, i); /* a0 */
+		simple_riscv64_set_reg(rv64, 11, j); /* a1 */
+
+		clock_domain_add(clk, rv64);
+		clock_domain_add(clk, imem);
+
+		pes[i * x + j] = rv64;
+	}
+
+	struct component *uart = create_simple_uart();
+	clock_domain_add(clk, uart);
+	grid_node_connect(grid[0], NULL, grid[x], grid[1], NULL, uart);
+
+	struct component *dmem = create_simple_mem(4096);
+	clock_domain_add(clk, dmem);
+	grid_node_connect(grid[1], NULL, grid[x + 1], grid[2], grid[0], dmem);
+
+	for (int i = 0; i < x; ++i)
+	for (int j = 0; j < y; ++j) {
+		if (i == 0 && j == 0)
+			continue;
+
+		if (i == 0 && j == 1)
+			continue;
+
+		struct component *node  = grid[i * x + j];
+		struct component *lower = pes[i * x + j];
+		struct component *left  = get_grid(grid, i - 1, j    , x, y);
+		struct component *right = get_grid(grid, i + 1, j    , x, y);
+		struct component *up    = get_grid(grid, i    , j + 1, x, y);
+		struct component *down  = get_grid(grid, i    , j - 1, x, y);
+		grid_node_connect(node, left, right, up, down, lower);
+	}
+
+	free(pes);
+	free(grid);
+	return OK;
+}
+
+int main()
+{
+	struct clock_domain *clk = create_clock_domain(NS(1));
+
+	stat r = build_grid(clk, 16, 16);
+	assert(r == OK);
+
+	struct gran_root *root = create_root();
+	root_add_clock(root, clk);
+
+	r = root_run(root);
+	assert(r == OK);
+
+	destroy_root(root);
+}
diff --git a/tests/starved_grid/source.mk b/tests/starved_grid/source.mk
new file mode 100644
index 0000000..428435f
--- /dev/null
+++ b/tests/starved_grid/source.mk
@@ -0,0 +1,6 @@
+STARVED_TEST_OBJ	!= ./scripts/gen-deps --sources "tests/starved_grid/sim.c"
+
+TEST_PROGS	+= build/tests/starved_grid/sim
+
+build/tests/starved_grid/sim: $(STARVED_TEST_OBJ) $(OBJS)
+	$(COMPILE) $(STARVED_TEST_OBJ) $(OBJS) -o $@
diff --git a/tests/starved_grid/test.c b/tests/starved_grid/test.c
new file mode 100644
index 0000000..c91868c
--- /dev/null
+++ b/tests/starved_grid/test.c
@@ -0,0 +1,46 @@
+#define X 16
+#define Y 16
+
+void _start(unsigned short x, unsigned short y)
+{
+	volatile unsigned long *counter = (unsigned long *)((unsigned long)1 << 48);
+	volatile char *uart = (char *)4096;
+
+	/* very hacky, not recommended but good enough for testing */
+	if (x == 0 && y == 2) {
+		*counter = 0;
+		*uart = '0';
+		*uart = '\n';
+	}
+	else
+		while (*counter != (((unsigned long)x << 16) | y))
+			;
+
+	*uart = '(';
+	/* [0 - 16] as two octal numbers */
+	*uart = ((x >> 3) & 0x7) + '0';
+	*uart = ((x >> 0) & 0x7) + '0';
+
+	*uart = ',';
+	*uart = ' ';
+
+	*uart = ((y >> 3) & 0x7) + '0';
+	*uart = ((y >> 0) & 0x7) + '0';
+
+	*uart = ')';
+	*uart = '\n';
+
+	if (x == 15 && y == 15)
+		asm ("ebreak\n");
+
+	if (y == 15) {
+		x++;
+		y = 0;
+	}
+	else
+		y++;
+
+	*counter = ((unsigned long)x << 16) | y;
+	while (1)
+		;
+}