diff options
| -rw-r--r-- | .gitignore | 1 | ||||
| -rw-r--r-- | src/grid/node.c | 96 | ||||
| -rw-r--r-- | tests/starved_grid/sim.c | 134 | ||||
| -rw-r--r-- | tests/starved_grid/source.mk | 6 | ||||
| -rw-r--r-- | tests/starved_grid/test.c | 46 |
5 files changed, 250 insertions, 33 deletions
@@ -3,3 +3,4 @@ docs/output build gran !include/gran +pdf diff --git a/src/grid/node.c b/src/grid/node.c index df237c7..512cae3 100644 --- a/src/grid/node.c +++ b/src/grid/node.c @@ -20,87 +20,117 @@ struct grid_node { uint16_t x, y; struct port left, right, up, down, lower; + + unsigned priority; }; -static void port_clock(struct grid_node *grid, struct port *port) +static stat port_clock(struct grid_node *grid, struct port *to, struct port *from) { - if (!port->busy) - return; - - stat r = SEND(grid, port->send, port->pkt); - if (r == EBUSY) - return; - - port->busy = false; -} + assert(from->busy); + stat r = SEND(grid, to->send, from->pkt); + if (r == EBUSY) { + grid->priority++; + return OK; + } -static stat grid_clock(struct grid_node *grid) -{ - port_clock(grid, &grid->left); - port_clock(grid, &grid->right); - port_clock(grid, &grid->up); - port_clock(grid, &grid->down); - port_clock(grid, &grid->lower); + from->busy = false; return OK; } -static stat port_receive(struct port *port, struct packet pkt) +static struct port *select_input(struct grid_node *grid) { - if (port->busy) - return EBUSY; + struct port *ports[5] = { + &grid->left, + &grid->right, + &grid->up, + &grid->down, + &grid->lower, + }; + for (size_t i = 0; i < 5; ++i) { + size_t idx = (i + grid->priority) % 5; + struct port *port = ports[idx]; + if (!port) + continue; - port->pkt = pkt; - port->busy = true; - return OK; + if (!port->busy) + continue; + + return port; + } + + return NULL; } -static stat grid_receive(struct grid_node *grid, struct component *from, struct packet pkt) +static stat clock_once(struct grid_node *grid) { - if (rand() % 256 == 0) - return EBUSY; + struct port *input = select_input(grid); + if (!input) + return OK; uint16_t x; uint16_t y; - uint64_t addr = pkt.to; + uint64_t addr = input->pkt.to; addr_grid(addr, NULL, &x, &y); if (grid->x == x && grid->y == y) { if (!grid->lower.send) goto nosuch; - return port_receive(&grid->lower, pkt); + return port_clock(grid, &grid->lower, input); } if (y < grid->y) { if (!grid->down.send) goto nosuch; - return port_receive(&grid->down, pkt); + return port_clock(grid, &grid->down, input); } if (y > grid->y) { if (!grid->up.send) goto nosuch; - return port_receive(&grid->up, pkt); + return port_clock(grid, &grid->up, input); } if (x < grid->x) { if (!grid->left.send) goto nosuch; - return port_receive(&grid->left, pkt); + return port_clock(grid, &grid->left, input); } if (x > grid->x) { if (!grid->right.send) goto nosuch; - return port_receive(&grid->right, pkt); + return port_clock(grid, &grid->right, input); } nosuch: - set_flags(&pkt, PACKET_ERROR); + abort(); + return OK; +} + +static stat grid_clock(struct grid_node *grid) +{ + clock_once(grid); + return OK; +} + + +static stat port_receive(struct port *port, struct packet pkt) +{ + if (port->busy) + return EBUSY; + + port->pkt = pkt; + port->busy = true; + return OK; +} + +static stat grid_receive(struct grid_node *grid, struct component *from, struct packet pkt) +{ if (from == grid->lower.send) return port_receive(&grid->lower, pkt); 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) + ; +} |