add an idealized NoC

+ Purely virtual, doesn't exist, but would be 'theoretically' ideal.

6 files changed, 310 insertions, 1 deletions

diff --git a/include/gran/ideal_noc.h b/include/gran/ideal_noc.h
new file mode 100644
index 0000000..638454a
--- /dev/null
+++ b/include/gran/ideal_noc.h
@@ -0,0 +1,34 @@
+#ifndef GRAN_IDEAL_NOC_H
+#define GRAN_IDEAL_NOC_H
+
+/**
+ * Essentially, this is the behaviour of a NoC that everyone wants, but nobody
+ * knows how to get. All-to all, single cycle, with oldest-first arbitration.
+ *
+ * I don't think it's been proven to be physically/mathematically
+ * impossible to build such a system (with reasonable performance/area costs),
+ * but at least there's no known way with existing mainstream technologies.
+ * There are some interesting future research areas, like adding wireless elements
+ * to the NoC, optical interconnects, superconducting routers and pulse computing,
+ * but nothing definite as far as I'm aware. Still, might be fun to compare how
+ * close to an idealized situation we can get, and maybe just daydream.
+ */
+
+#include <stdint.h>
+#include <gran/component.h>
+
+struct component *create_ideal_noc(uint32_t elems, size_t latency);
+stat ideal_noc_connect(struct component *noc, struct component *component, uint32_t elem);
+
+static inline void addr_ideal_noc(uint64_t addr, uint32_t *elem, uint32_t *off)
+{
+	if (off) *off = addr & 0xffffffff;
+	if (elem) *elem = (addr >> 32) & 0xffffffff;
+}
+
+static inline uint64_t ideal_noc_addr(uint32_t elem, uint32_t off)
+{
+	return ((uint64_t)elem << 32) | off;
+}
+
+#endif /* GRAN_IDEAL_NOC_H */
diff --git a/src/ideal_noc.c b/src/ideal_noc.c
new file mode 100644
index 0000000..0ebc17e
--- /dev/null
+++ b/src/ideal_noc.c
@@ -0,0 +1,131 @@
+#include <gran/ideal_noc.h>
+
+struct reg {
+	struct packet pkt;
+	bool busy;
+};
+
+struct noc {
+	struct component component;
+	uint32_t elems;
+	size_t latency;
+
+	size_t counter;
+
+	struct reg *in; /* countedby[elems] */
+	struct reg *out; /* countedby[elems] */
+	struct component **lower; /* countedby[elems] */
+};
+
+stat ideal_noc_receive(struct noc *n, struct component *from, struct packet pkt)
+{
+	(void)from; /* unused */
+	uint32_t elem;
+	addr_ideal_noc(pkt.to, &elem, NULL);
+	assert(elem < n->elems);
+
+	if (n->in[elem].busy)
+		return EBUSY;
+
+	pkt.timestamp = n->counter;
+	n->in[elem].pkt = pkt;
+	n->in[elem].busy = true;
+	return OK;
+}
+
+stat ideal_noc_clock(struct noc *n)
+{
+	size_t counter = n->latency == 0 ? 0 : (n->counter + 1) % n->latency;
+	if (counter != 0)
+		return OK;
+
+	for (size_t i = 0; i < n->elems; ++i) {
+		struct reg *in = &n->in[i];
+		if (!in->busy)
+			continue;
+
+		uint32_t elem;
+		addr_ideal_noc(in->pkt.to, &elem, NULL);
+		assert(elem < n->elems);
+
+		struct reg *out = &n->out[elem];
+		if (out->busy && out->pkt.timestamp < in->pkt.timestamp)
+			continue;
+
+		out->pkt = in->pkt;
+		out->busy = true;
+		in->busy = false;
+	}
+
+	for (size_t i = 0; i < n->elems; ++i) {
+		struct reg *out = &n->out[i];
+		if (!out->busy)
+			continue;
+
+		uint32_t elem;
+		addr_ideal_noc(out->pkt.to, &elem, NULL);
+		struct component *lower = n->lower[elem];
+		assert(lower);
+
+		stat ret = SEND(n, lower, out->pkt);
+		if (ret == EBUSY)
+			continue;
+
+		assert(ret == OK);
+		out->busy = false;
+	}
+
+	return OK;
+}
+
+void ideal_noc_destroy(struct noc *n)
+{
+	free(n->in);
+	free(n->out);
+	free(n->lower);
+	free(n);
+}
+
+stat ideal_noc_connect(struct component *node, struct component *component, uint32_t elem)
+{
+	struct noc *n = (struct noc *)node;
+	assert(elem < n->elems);
+	assert(n->lower[elem] == NULL);
+	n->lower[elem] = component;
+	return OK;
+}
+
+struct component *create_ideal_noc(uint32_t elems, size_t latency)
+{
+	struct noc *n = (struct noc *)calloc(1, sizeof(struct noc));
+	if (!n)
+		return NULL;
+
+	n->in = (struct reg *)calloc(elems, sizeof(struct reg));
+	if (!n->in) {
+		free(n);
+		return NULL;
+	}
+
+	n->out = (struct reg *)calloc(elems, sizeof(struct reg));
+	if (!n->out) {
+		free(n->in);
+		free(n);
+		return NULL;
+	}
+
+	n->lower = (struct component **)calloc(elems, sizeof(struct component *));
+	if (!n->lower) {
+		free(n->out);
+		free(n->in);
+		free(n);
+		return NULL;
+	}
+
+	n->component.destroy = (destroy_callback)ideal_noc_destroy;
+	n->component.receive = (receive_callback)ideal_noc_receive;
+	n->component.clock = (clock_callback)ideal_noc_clock;
+	n->latency = latency;
+	n->elems = elems;
+	return (struct component *)n;
+}
diff --git a/src/source.mk b/src/source.mk
index dd92722..3ed3dba 100644
--- a/src/source.mk
+++ b/src/source.mk
@@ -1,4 +1,4 @@
 include src/*/source.mk
 
-SOURCES += src/root.c src/clock_domain.c src/vec.c
+SOURCES += src/root.c src/clock_domain.c src/vec.c src/ideal_noc.c
 MAIN_SRC += src/main.c
diff --git a/tests/simple_ideal_noc/sim.c b/tests/simple_ideal_noc/sim.c
new file mode 100644
index 0000000..4aba71d
--- /dev/null
+++ b/tests/simple_ideal_noc/sim.c
@@ -0,0 +1,74 @@
+#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/ideal_noc.h>
+#include <gran/cpu/riscv/simple_riscv64.h>
+
+#include "../build/tests/simple_ideal_noc/test.inc"
+
+static stat build_ideal_noc(struct clock_domain *clk, uint32_t x)
+{
+	struct component **pes = calloc(x, sizeof(struct component *));
+	assert(pes);
+
+	/* very much ideal noc */
+	struct component *noc = create_ideal_noc(x, 0);
+	clock_domain_add(clk, noc);
+
+	for (uint32_t i = 0; i < x; ++i) {
+		if (i == 0 || i == 1)
+			continue;
+
+		struct component *imem = create_simple_mem(4096);
+		init_simple_mem(imem, 0,
+				build_tests_simple_ideal_noc_test_bin_len,
+				build_tests_simple_ideal_noc_test_bin);
+
+		uint64_t rcv = ideal_noc_addr(i, 0);
+		struct component *rv64 = create_simple_riscv64(rcv, 0, imem, noc);
+		simple_riscv64_set_reg(rv64, 10, i); /* a0 */
+		simple_riscv64_set_reg(rv64, 11, x); /* a1 */
+
+		clock_domain_add(clk, rv64);
+		clock_domain_add(clk, imem);
+
+		pes[i] = rv64;
+	}
+
+	struct component *uart = create_simple_uart();
+	clock_domain_add(clk, uart);
+	ideal_noc_connect(noc, uart, 0);
+
+	struct component *dmem = create_simple_mem(4096);
+	clock_domain_add(clk, dmem);
+	ideal_noc_connect(noc, dmem, 1);
+
+	for (size_t i = 0; i < x; ++i) {
+		if (i == 0 || i == 1)
+			continue;
+
+		ideal_noc_connect(noc, pes[i], i);
+	}
+
+	free(pes);
+	return OK;
+}
+
+int main()
+{
+	struct clock_domain *clk = create_clock_domain(NS(1));
+
+	stat r = build_ideal_noc(clk, 64);
+	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/simple_ideal_noc/source.mk b/tests/simple_ideal_noc/source.mk
new file mode 100644
index 0000000..2cf271b
--- /dev/null
+++ b/tests/simple_ideal_noc/source.mk
@@ -0,0 +1,18 @@
+IDEAL_NOC_TEST_OBJ	!= ./scripts/gen-deps --sources "tests/simple_ideal_noc/sim.c"
+TEST_PROGS		+= build/tests/simple_ideal_noc/sim
+
+build/tests/simple_ideal_noc/test.inc: tests/simple_ideal_noc/test.c
+	riscv64-unknown-elf-gcc -O2 -Wall -Wextra -ffreestanding -nostdlib \
+		-march=rv64i -mabi=lp64 \
+		-o build/tests/simple_ideal_noc/test \
+		tests/simple_ideal_noc/test.c
+	riscv64-unknown-elf-objcopy -Obinary \
+		build/tests/simple_ideal_noc/test \
+		build/tests/simple_ideal_noc/test.bin
+	xxd -i build/tests/simple_ideal_noc/test.bin \
+		> build/tests/simple_ideal_noc/test.inc
+
+build/tests/simple_ideal_noc/sim.o: build/tests/simple_ideal_noc/test.inc
+
+build/tests/simple_ideal_noc/sim: $(IDEAL_NOC_TEST_OBJ) $(OBJS)
+	$(COMPILE) $(IDEAL_NOC_TEST_OBJ) $(OBJS) -o $@
diff --git a/tests/simple_ideal_noc/test.c b/tests/simple_ideal_noc/test.c
new file mode 100644
index 0000000..2e4a22c
--- /dev/null
+++ b/tests/simple_ideal_noc/test.c
@@ -0,0 +1,52 @@
+__attribute__((always_inline))
+static inline char hex_char(unsigned x)
+{
+	if (x <= 9)
+		return x + '0';
+
+	return (x - 10) + 'a';
+}
+
+__attribute__((always_inline))
+static inline void print_int32(volatile char *uart, unsigned x)
+{
+	*uart = hex_char((x >> 28) & 0xf);
+	*uart = hex_char((x >> 24) & 0xf);
+	*uart = hex_char((x >> 20) & 0xf);
+	*uart = hex_char((x >> 16) & 0xf);
+	*uart = hex_char((x >> 12) & 0xf);
+	*uart = hex_char((x >>  8) & 0xf);
+	*uart = hex_char((x >>  4) & 0xf);
+	*uart = hex_char((x >>  0) & 0xf);
+}
+
+__attribute__((always_inline))
+static inline void print_addr(volatile char *uart, unsigned x)
+{
+	*uart = '(';
+	print_int32(uart, x);
+	*uart = ')';
+	*uart = '\n';
+}
+
+void _start(unsigned x, unsigned X)
+{
+	volatile char *uart = (char *)4096;
+	volatile unsigned *control = (unsigned *)(1ULL << 32);
+
+	if (x == 2) {
+		goto do_work;
+	} else {
+		while (*control != x) {}
+	}
+
+do_work:
+	print_addr(uart, x);
+	*control = x + 1;
+
+	if (x == X - 1)
+		asm("ebreak");
+
+	/* otherwise just loop */
+	while (1) {}
+}