diff options
| -rw-r--r-- | NOTES | 26 | ||||
| -rw-r--r-- | include/gran/packet.h | 7 | ||||
| -rw-r--r-- | include/gran/torus3d/node.h | 35 | ||||
| -rw-r--r-- | src/mem/simple_mem.c | 1 | ||||
| -rw-r--r-- | src/root.c | 3 | ||||
| -rw-r--r-- | src/torus3d/node.c | 221 | ||||
| -rw-r--r-- | src/torus3d/source.mk | 1 | ||||
| -rw-r--r-- | src/uart/simple_uart.c | 1 | ||||
| -rw-r--r-- | tests/simple_torus3d/sim.c | 115 | ||||
| -rw-r--r-- | tests/simple_torus3d/source.mk | 18 | ||||
| -rw-r--r-- | tests/simple_torus3d/test.c | 61 |
11 files changed, 489 insertions, 0 deletions
@@ -0,0 +1,26 @@ +Slightly drunken ramblings: + +Currently, I'm imagining that a 3D torus with one-way communication would +probably be the best way forward. It has some nice properties like a fairly +simple construction, decent average response times (but not the best minimum +response times, unfortunately) and a fairly simple broadcast scheme (though +without ack). + +Coherence is of course more difficult, but I would imagine that +changing the memory model to be a bit more loose wouldn't hurt. Essentially, we +would have one node somewhere be a global 'lock' that gives out LR/SC +permissions, fairly high latency unfortunately but arguably the simplest +approach. All caches are not coherent, but would have to respect atomic +operations. + +One maybe interesting thing could be to not have virtual memory, instead opt for +some kind of k-tree with byte-accurate permissions, kind of like cheri. Each +pointer could have a second pointer that tells which allocation it is from, and +we have a TLB-like cache for fast lookups. We could also have multiple of these +trees, one in local memory for private allocations, for example. With process +IDs, my beloved. Also, semi-cooperative interrupts? With enough cores, static +thread scheduling might also be workable. Potentially also external node access +checking, so untrusted packets can't read memory that's not for some process +(avoid stuff like the router capturing thing in Linux wifi fw). + + diff --git a/include/gran/packet.h b/include/gran/packet.h index 5f8bd9c..2fec036 100644 --- a/include/gran/packet.h +++ b/include/gran/packet.h @@ -22,6 +22,7 @@ struct packet { uint64_t from; uint64_t to; uint64_t mask; + uint64_t timestamp; uint8_t data[64]; enum packet_flags flags; }; @@ -178,14 +179,20 @@ static inline uint64_t packet_convu64(struct packet *pkt) return res; } +/* not good, should be taken from the local clock domain or something + * but eh for now */ +extern uint64_t ticker; + static inline struct packet create_packet(uint64_t from, uint64_t to, uint64_t size, void *data, enum packet_flags flags) { assert(size <= 64); assert(packet_align(from) == from); + uint64_t aligned = packet_align(to); uint64_t mask = packet_mask(to, size); struct packet pkt = (struct packet){ + .timestamp = ticker++, .from = from, .to = aligned, .mask = mask, diff --git a/include/gran/torus3d/node.h b/include/gran/torus3d/node.h new file mode 100644 index 0000000..bd02a1f --- /dev/null +++ b/include/gran/torus3d/node.h @@ -0,0 +1,35 @@ +#ifndef GRAN_TORUS3D_NODE_H +#define GRAN_TORUS3D_NODE_H + +#include <gran/component.h> +#include <stdint.h> + +struct component *create_torus3d_node(uint8_t x, uint8_t y, uint8_t z); + +stat torus3d_node_connect(struct component *node, + struct component *x_in, + struct component *y_in, + struct component *z_in, + struct component *child, + struct component *x_out, + struct component *y_out, + struct component *z_out); + +static inline void addr_torus3d(uint64_t addr, uint8_t *x, uint8_t *y, uint8_t *z, uint32_t *off) +{ + if (off) *off = addr & 0xffffffff; + if (x) *x = (addr >> 32) & 0xff; + if (y) *y = (addr >> 40) & 0xff; + if (z) *z = (addr >> 48) & 0xff; + assert(((addr >> 56) & 0xff) == 0); +} + +static inline uint64_t torus3d_addr(uint8_t x, uint8_t y, uint8_t z, uint32_t off) +{ + return off | ((uint64_t)x << 32) + | ((uint64_t)y << 40) + | ((uint64_t)z << 48) + ; +} + +#endif /* GRAN_TORUS3D_NODE_H */ diff --git a/src/mem/simple_mem.c b/src/mem/simple_mem.c index 0a3a3ce..77d8319 100644 --- a/src/mem/simple_mem.c +++ b/src/mem/simple_mem.c @@ -6,6 +6,7 @@ #include <stdbool.h> #include <gran/mem/simple_mem.h> +#include <gran/torus3d/node.h> struct simple_mem { struct component component; @@ -8,6 +8,9 @@ #define MAX_DOMAINS 512 +/** @todo ugly global, time values should be taken from local clock domain */ +uint64_t ticker = 0; + struct gran_root { size_t num_domains; struct clock_domain *(domains[MAX_DOMAINS]); diff --git a/src/torus3d/node.c b/src/torus3d/node.c new file mode 100644 index 0000000..15cc7ee --- /dev/null +++ b/src/torus3d/node.c @@ -0,0 +1,221 @@ +#include <gran/torus3d/node.h> + +struct reg { + struct packet pkt; + bool busy; +}; + +struct port { + struct reg r[2]; +}; + +struct torus3d_node { + struct component component; + uint8_t x, y, z /*, w for 4D but that might be a bit overkill*/; + + struct component *x_next, *y_next, *z_next, + *x_prev, *y_prev, *z_prev, + *child; + + struct port port_x, port_y, port_z; + + struct reg x_in, y_in, z_in, child_in; +}; + +static stat port_receive(struct torus3d_node *torus3d, struct port *port, struct reg *reg) +{ + if (!reg->busy) + return OK; + + /* source */ + uint8_t sx, sy, sz; + addr_torus3d(reg->pkt.from, &sx, &sy, &sz, NULL); + + /* dst */ + uint8_t dx, dy, dz; + addr_torus3d(reg->pkt.to, &dx, &dy, &dz, NULL); + + /* Dally/spiral routing though I'm a bit unsure if this works for 2D/3D + * toruses (1D seems to work, 2D not so much atm) */ + int chan = 0; + if (port == &torus3d->port_x) + chan = sx < dx; + else if (port == &torus3d->port_y) + chan = sy < dy; + else if (port == &torus3d->port_z) + chan = sz < dz; + else + abort(); + + if (port->r[chan].busy) + return OK; + + printf("(%d, %d, %d) to (%d, %d, %d) via (%d, %d, %d)\n", + sx, sy, sz, + dx, dy, dz, + torus3d->x, torus3d->y, torus3d->z); + + port->r[chan].pkt = reg->pkt; + port->r[chan].busy = true; + reg->busy = false; + return OK; +} + +static stat reg_receive(struct reg *r, struct packet pkt) +{ + if (r->busy) + return EBUSY; + + r->pkt = pkt; + r->busy = true; + return OK; +} + +enum match { + MX = (1 << 0), + MY = (1 << 1), + MZ = (1 << 2), + NX = (1 << 3), + NY = (1 << 4), + NZ = (1 << 5), +}; + +static void maybe_route_reg(struct torus3d_node *torus3d, struct reg *reg, enum match m, uint64_t *oldest, struct packet **pkt, bool **busy) +{ + if (!reg->busy) + return; + + uint8_t x, y, z; + addr_torus3d(reg->pkt.to, &x, &y, &z, NULL); + + if ((m & MX) && x != torus3d->x) + return; + + if ((m & MY) && y != torus3d->y) + return; + + if ((m & MZ) && z != torus3d->z) + return; + + if ((m & NX) && x == torus3d->x) + return; + + if ((m & NY) && y == torus3d->y) + return; + + if ((m & NZ) && z == torus3d->z) + return; + + if (reg->pkt.timestamp < *oldest) { + *oldest = reg->pkt.timestamp; + *busy = ®->busy; + *pkt = ®->pkt; + } +} + +static void maybe_route_port(struct torus3d_node *torus3d, struct port *port, enum match m, uint64_t *oldest, struct packet **pkt, bool **busy) +{ + maybe_route_reg(torus3d, &port->r[0], m, oldest, pkt, busy); + maybe_route_reg(torus3d, &port->r[1], m, oldest, pkt, busy); +} + +static stat route(struct torus3d_node *torus3d, struct component *next, enum match m) +{ + uint64_t oldest = -1; struct packet *pkt = NULL; bool *busy = NULL; + maybe_route_port(torus3d, &torus3d->port_x, m, &oldest, &pkt, &busy); + maybe_route_port(torus3d, &torus3d->port_y, m, &oldest, &pkt, &busy); + maybe_route_port(torus3d, &torus3d->port_z, m, &oldest, &pkt, &busy); + maybe_route_reg(torus3d, &torus3d->child_in, m, &oldest, &pkt, &busy); + + /* no suitable match */ + if (pkt == NULL) + return OK; + + assert(busy); + + stat ret = SEND(torus3d, next, *pkt); + if (ret == EBUSY) + return OK; + + *busy = false; + return OK; +} + +static stat torus3d_clock(struct torus3d_node *torus3d) +{ + stat ret = OK; + if ((ret = port_receive(torus3d, &torus3d->port_x, &torus3d->x_in))) + return ret; + + if ((ret = port_receive(torus3d, &torus3d->port_y, &torus3d->y_in))) + return ret; + + if ((ret = port_receive(torus3d, &torus3d->port_z, &torus3d->z_in))) + return ret; + + if ((ret = route(torus3d, torus3d->x_next, NX))) + return ret; + + if ((ret = route(torus3d, torus3d->y_next, NY | MX))) + return ret; + + if ((ret = route(torus3d, torus3d->z_next, NZ | MX | MY))) + return ret; + + if ((ret = route(torus3d, torus3d->child, MX | MY | MZ))) + return ret; + + return OK; +} + +static stat torus3d_receive(struct torus3d_node *torus3d, struct component *from, struct packet pkt) +{ + if (from == torus3d->child) + return reg_receive(&torus3d->child_in, pkt); + + if (from == torus3d->x_prev) + return reg_receive(&torus3d->x_in, pkt); + + if (from == torus3d->y_prev) + return reg_receive(&torus3d->y_in, pkt); + + if (from == torus3d->z_prev) + return reg_receive(&torus3d->z_in, pkt); + + abort(); + return OK; +} + +struct component *create_torus3d_node(uint8_t x, uint8_t y, uint8_t z) +{ + struct torus3d_node *node = calloc(1, sizeof(struct torus3d_node)); + if (!node) + return NULL; + + node->component.receive = (receive_callback)torus3d_receive; + node->component.clock = (clock_callback)torus3d_clock; + node->x = x; + node->y = y; + node->z = z; + return (struct component *)node; +} + +stat torus3d_node_connect(struct component *node, + struct component *x_in, + struct component *y_in, + struct component *z_in, + struct component *child, + struct component *x_out, + struct component *y_out, + struct component *z_out) +{ + struct torus3d_node *n = (struct torus3d_node *)node; + n->x_prev = x_in; + n->y_prev = y_in; + n->z_prev = z_in; + n->child = child; + n->x_next = x_out; + n->y_next = y_out; + n->z_next = z_out; + return OK; +} diff --git a/src/torus3d/source.mk b/src/torus3d/source.mk new file mode 100644 index 0000000..4770dad --- /dev/null +++ b/src/torus3d/source.mk @@ -0,0 +1 @@ +SOURCES += src/torus3d/node.c diff --git a/src/uart/simple_uart.c b/src/uart/simple_uart.c index 1528a70..e640ae1 100644 --- a/src/uart/simple_uart.c +++ b/src/uart/simple_uart.c @@ -38,6 +38,7 @@ static stat simple_uart_receive(struct simple_uart *uart, struct component *from } putchar(packet_convu8(&pkt)); + fflush(stdout); set_flags(&uart->pkt, PACKET_DONE); return OK; } diff --git a/tests/simple_torus3d/sim.c b/tests/simple_torus3d/sim.c new file mode 100644 index 0000000..b3ff41b --- /dev/null +++ b/tests/simple_torus3d/sim.c @@ -0,0 +1,115 @@ +#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/torus3d/node.h> +#include <gran/cpu/riscv/simple_riscv64.h> + +#include "../build/tests/simple_torus3d/test.inc" + +static size_t idx_1d(int x, int y, int z, uint8_t xw, uint8_t yw, uint8_t zw) +{ + uint8_t xi = (x + xw) % xw; + uint8_t yi = (y + yw) % yw; + uint8_t zi = (z + zw) % zw; + return (xi * yw * zw) + (yi * zw) + zi; +} + +static void torus3d_connect_grid(struct component **grid, struct component *c, + uint8_t x, uint8_t y, uint8_t z, + uint8_t xw, uint8_t yw, uint8_t zw) +{ + torus3d_node_connect(grid[idx_1d(x, y, z, xw, yw, zw)], + grid[idx_1d(x-1, y , z , xw, yw, zw)], + grid[idx_1d(x , y-1, z , xw, yw, zw)], + grid[idx_1d(x , y , z-1, xw, yw, zw)], + c, + grid[idx_1d(x+1, y , z , xw, yw, zw)], + grid[idx_1d(x , y+1, z , xw, yw, zw)], + grid[idx_1d(x , y , z+1, xw, yw, zw)]); +} + +static stat build_torus3d(struct clock_domain *clk, uint8_t x, uint8_t y, uint8_t z) +{ + struct component **grid = calloc(x * y * z, sizeof(struct component *)); + assert(grid); + + struct component **pes = calloc(x * y * z, sizeof(struct component *)); + assert(pes); + + for (size_t i = 0; i < x; ++i) + for (size_t j = 0; j < y; ++j) + for (size_t k = 0; k < z; ++k) { + struct component *node = create_torus3d_node(i, j, k); + clock_domain_add(clk, node); + grid[idx_1d(i, j, k, x, y, z)] = node; + + if (i == 0 && j == 0 && k == 0) + continue; + + if (i == 0 && j == 0 && k == 1) + continue; + + struct component *imem = create_simple_mem(4096); + init_simple_mem(imem, 0, + build_tests_simple_torus3d_test_bin_len, + build_tests_simple_torus3d_test_bin); + + uint64_t rcv = torus3d_addr(i, j, k, 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 */ + simple_riscv64_set_reg(rv64, 12, k); /* a2 */ + simple_riscv64_set_reg(rv64, 13, x); /* a3 */ + simple_riscv64_set_reg(rv64, 14, y); /* a4 */ + simple_riscv64_set_reg(rv64, 15, z); /* a5 */ + + clock_domain_add(clk, rv64); + clock_domain_add(clk, imem); + + pes[idx_1d(i, j, k, x, y, z)] = rv64; + } + + struct component *uart = create_simple_uart(); + clock_domain_add(clk, uart); + torus3d_connect_grid(grid, uart, 0, 0, 0, x, y, z); + + struct component *dmem = create_simple_mem(4096); + clock_domain_add(clk, dmem); + torus3d_connect_grid(grid, dmem, 0, 0, 1, x, y, z); + + for (int i = 0; i < x; ++i) + for (int j = 0; j < y; ++j) + for (int k = 0; k < z; ++k) { + if (i == 0 && j == 0 && k == 0) + continue; + + if (i == 0 && j == 0 && k == 1) + continue; + + torus3d_connect_grid(grid, pes[idx_1d(i, j, k, x, y, z)], + i, j, k, x, y, z); + } + + free(grid); + free(pes); + return OK; +} + +int main() +{ + struct clock_domain *clk = create_clock_domain(NS(1)); + + stat r = build_torus3d(clk, 1, 10, 10); + 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_torus3d/source.mk b/tests/simple_torus3d/source.mk new file mode 100644 index 0000000..e045a3c --- /dev/null +++ b/tests/simple_torus3d/source.mk @@ -0,0 +1,18 @@ +TORUS3D_TEST_OBJ != ./scripts/gen-deps --sources "tests/simple_torus3d/sim.c" +TEST_PROGS += build/tests/simple_torus3d/sim + +build/tests/simple_torus3d/test.inc: tests/simple_torus3d/test.c + riscv64-unknown-elf-gcc -O2 -Wall -Wextra -ffreestanding -nostdlib \ + -march=rv64i -mabi=lp64 \ + -o build/tests/simple_torus3d/test \ + tests/simple_torus3d/test.c + riscv64-unknown-elf-objcopy -Obinary \ + build/tests/simple_torus3d/test \ + build/tests/simple_torus3d/test.bin + xxd -i build/tests/simple_torus3d/test.bin \ + > build/tests/simple_torus3d/test.inc + +build/tests/simple_torus3d/sim.o: build/tests/simple_torus3d/test.inc + +build/tests/simple_torus3d/sim: $(TORUS3D_TEST_OBJ) $(OBJS) + $(COMPILE) $(TORUS3D_TEST_OBJ) $(OBJS) -o $@ diff --git a/tests/simple_torus3d/test.c b/tests/simple_torus3d/test.c new file mode 100644 index 0000000..2953d41 --- /dev/null +++ b/tests/simple_torus3d/test.c @@ -0,0 +1,61 @@ +__attribute__((always_inline)) +static inline void print_int8(volatile char *uart, unsigned x) +{ + *uart = ((x >> 4) & 0xf) + '0'; + *uart = ((x >> 0) & 0xf) + '0'; +} + +__attribute__((always_inline)) +static inline void print_addr(volatile char *uart, unsigned x, unsigned y, unsigned z) +{ + *uart = '('; + print_int8(uart, x); + *uart = ','; + *uart = ' '; + print_int8(uart, y); + *uart = ','; + *uart = ' '; + print_int8(uart, z); + *uart = ')'; + *uart = '\n'; +} + +__attribute__((always_inline)) +static inline unsigned wrap(unsigned x, unsigned X) +{ + return x + 1 >= X ? 0 : x + 1; +} + +__attribute__((always_inline)) +static inline unsigned next_idx(unsigned x, unsigned y, unsigned z, unsigned X, unsigned Y, unsigned Z) +{ + unsigned zi = wrap(z, Z); + unsigned yi = zi < z ? wrap(y, Y) : y; + unsigned xi = yi < y ? wrap(x, X) : x; + + return (xi << 16) | (yi << 8) | zi; +} + +void _start(unsigned x, unsigned y, unsigned z, unsigned X, unsigned Y, unsigned Z) +{ + volatile char *uart = (char *)4096; + /* x = 1ULL << 32, y = 1ULL << 40, z = 1ULL << 48 I guess */ + volatile unsigned *control = (unsigned *)(1ULL << 48); + + + if (x == 0 && y == 0 && z == 2) { + goto do_work; + } else { + while (*control != ((x << 16) | (y << 8) | z)) {} + } + +do_work: + print_addr(uart, x, y, z); + *control = next_idx(x, y, z, X, Y, Z); + + if (x == X - 1 && y == Y - 1 && z == Z - 1) + asm("ebreak"); + + /* otherwise just loop */ + while (1) {} +} |