diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/mesh/node.c | 164 | ||||
| -rw-r--r-- | src/mesh/node1d.c | 307 | ||||
| -rw-r--r-- | src/mesh/node2d.c | 281 | ||||
| -rw-r--r-- | src/mesh/source.mk | 2 | ||||
| -rw-r--r-- | src/source.mk | 2 |
5 files changed, 590 insertions, 166 deletions
diff --git a/src/mesh/node.c b/src/mesh/node.c deleted file mode 100644 index 2ac921a..0000000 --- a/src/mesh/node.c +++ /dev/null @@ -1,164 +0,0 @@ -#include <gran/mesh/node.h> - -struct reg { - struct packet pkt; - bool busy; -}; - -struct node { - struct component component; - uint16_t x, y; - - uint64_t timestamp; - - struct component *n, *s, *e, *w, *l; - - struct reg n_in, s_in, e_in, w_in, l_in; -}; - -enum order { - N, S, E, W, L -}; - -static inline void maybe_pick(struct reg *output[5], enum order d, struct reg *r) -{ - if (output[d] && output[d]->pkt.timestamp < r->pkt.timestamp) - return; - - output[d] = r; -} - -static stat node_clock(struct node *node) -{ - node->timestamp++; - - struct reg *output[5] = {NULL, NULL, NULL, NULL, NULL}; - struct reg *input[5] = { - &node->n_in, - &node->s_in, - &node->e_in, - &node->w_in, - &node->l_in - }; - - uint8_t X = node->x, Y = node->y; - for (size_t i = 0; i < 5; ++i) { - struct reg *r = input[i]; - if (!r->busy) - continue; - - uint16_t x, y; - addr_mesh(r->pkt.to, &x, &y, NULL); - if (x < X) { - maybe_pick(output, W, r); - continue; - } - - if (x > X) { - maybe_pick(output, E, r); - continue; - } - - if (y < Y) { - maybe_pick(output, S, r); - continue; - } - - if (y > Y) { - maybe_pick(output, N, r); - continue; - } - - maybe_pick(output, L, r); - } - - struct component *target[7] = { - node->n, - node->s, - node->e, - node->w, - node->l - }; - - for (size_t i = 0; i < 5; ++i) { - if (!output[i]) - continue; - - if (!target[i]) { - /* for now, should send packet back with an error or something */ - abort(); - } - - stat ret = SEND(node, target[i], output[i]->pkt); - if (ret == EBUSY) - continue; - - assert(ret == OK); - output[i]->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; -} - -static stat node_receive(struct node *node, struct component *from, struct packet pkt) -{ - if (from == node->l) { - /* add time when packet entered network */ - pkt.timestamp = node->timestamp; - return reg_receive(&node->l_in, pkt); - } - - if (from == node->n) - return reg_receive(&node->n_in, pkt); - - if (from == node->s) - return reg_receive(&node->s_in, pkt); - - if (from == node->e) - return reg_receive(&node->e_in, pkt); - - if (from == node->w) - return reg_receive(&node->w_in, pkt); - - abort(); - return OK; -} - -struct component *create_mesh_node(uint16_t x, uint16_t y) -{ - struct node *node = calloc(1, sizeof(struct node)); - if (!node) - return NULL; - - node->component.receive = (receive_callback)node_receive; - node->component.clock = (clock_callback)node_clock; - node->x = x; - node->y = y; - return (struct component *)node; -} - -stat mesh_node_connect(struct component *node, - struct component *n, - struct component *s, - struct component *e, - struct component *w, - struct component *l) -{ - struct node *nod = (struct node *)node; - nod->n = n; - nod->s = s; - nod->e = e; - nod->w = w; - nod->l = l; - return OK; -} diff --git a/src/mesh/node1d.c b/src/mesh/node1d.c new file mode 100644 index 0000000..23ba2ca --- /dev/null +++ b/src/mesh/node1d.c @@ -0,0 +1,307 @@ +#include <gran/mesh/node1d.h> + +#define left_port(n) (n)->ports[(n)->elems + 0] +#define right_port(n) (n)->ports[(n)->elems + 1] + +#define left_in(n) (n)->in[(n)->elems + 0] +#define right_in(n) (n)->in[(n)->elems + 1] + +#define left_out(n) (n)->out[(n)->elems + 0] +#define right_out(n) (n)->out[(n)->elems + 1] + +struct reg { + struct packet pkt; + bool busy; +}; + +struct node1d { + struct component component; + uint16_t cluster; + uint16_t elems; + + uint64_t timestamp; + + struct reg *in; /* countedby[elems + 2] */ + struct reg *out; /* countedby[elems + 2] */ + struct component **ports; /* countedby[elems + 2] */ +}; + +static void node1d_destroy(struct node1d *n) +{ + free(n->in); + free(n->out); + free(n->ports); +} + +static stat reg_busy(struct reg *r, struct packet pkt) +{ + bool busy = r->busy; + if (!busy) { + r->pkt = pkt; + r->busy = true; + } + + return busy ? EBUSY : OK; +} + +static void copy_reg(struct reg *r, struct reg *s) +{ + assert(s->busy); + if (r->busy) + return; + + r->pkt = s->pkt; + r->busy = true; + s->busy = false; +} + +static stat node1d_receive(struct node1d *n, struct component *from, struct packet pkt) +{ + for (int i = 0; i < n->elems + 2; ++i) { + /* add timestamp to packets that originate with us */ + if (i < n->elems) + pkt.timestamp = n->timestamp; + + if (from == n->ports[i]) + return reg_busy(&n->in[i], pkt); + } + + /* shouldn't be possible */ + abort(); + return OK; +} + +static void clock_outputs(struct node1d *n) +{ + for (int i = 0; i < n->elems + 2; ++i) { + if (!n->out[i].busy) + continue; + + stat ret = SEND(n, n->ports[i], n->out[i].pkt); + if (ret == EBUSY) + continue; + + n->out[i].busy = false; + } +} + +static void propagate_left(struct node1d *n, struct reg *a, struct reg *b) +{ + struct reg *sel_a = NULL, *sel_b = NULL; + if (a && a->busy) { + uint16_t cluster = 0; + addr_mesh1d(a->pkt.to, &cluster, NULL, NULL); + + if (cluster > n->cluster) + sel_a = a; + } + + if (b && b->busy) { + uint16_t cluster = 0; + addr_mesh1d(b->pkt.to, &cluster, NULL, NULL); + + if (cluster > n->cluster) + sel_b = b; + } + + if (!sel_a && !sel_b) + return; + + if (sel_a && !sel_b) { + copy_reg(&left_out(n), sel_a); + return; + } + + if (!sel_a && sel_b) { + copy_reg(&left_out(n), sel_b); + return; + } + + /* both available, select older */ + if (sel_a->pkt.timestamp < sel_b->pkt.timestamp) + copy_reg(&left_out(n), sel_a); + else + copy_reg(&left_out(n), sel_b); +} + +static void propagate_right(struct node1d *n, struct reg *a, struct reg *b) +{ + struct reg *sel_a = NULL, *sel_b = NULL; + if (a && a->busy) { + uint16_t cluster = 0; + addr_mesh1d(a->pkt.to, &cluster, NULL, NULL); + + if (cluster < n->cluster) + sel_a = a; + } + + if (b && b->busy) { + uint16_t cluster = 0; + addr_mesh1d(b->pkt.to, &cluster, NULL, NULL); + + if (cluster < n->cluster) + sel_b = b; + } + + if (!sel_a && !sel_b) + return; + + if (sel_a && !sel_b) { + copy_reg(&right_out(n), sel_a); + return; + } + + if (!sel_a && sel_b) { + copy_reg(&right_out(n), sel_b); + return; + } + + /* both available, select older */ + if (sel_a->pkt.timestamp < sel_b->pkt.timestamp) + copy_reg(&right_out(n), sel_a); + else + copy_reg(&right_out(n), sel_b); +} + +static void propagate(struct node1d *n, int elem, struct reg *a, struct reg *b, struct reg *c) +{ + + struct reg *sel_a = NULL, *sel_b = NULL, *sel_c = NULL; + if (a && a->busy) { + uint16_t cluster = 0, element = 0; + addr_mesh1d(a->pkt.to, &cluster, &element, NULL); + + if (cluster == n->cluster && element == elem) + sel_a = a; + } + + if (b && b->busy) { + uint16_t cluster = 0, element = 0; + addr_mesh1d(b->pkt.to, &cluster, &element, NULL); + + if (cluster == n->cluster && element == elem) + sel_b = b; + } + + if (c && c->busy) { + uint16_t cluster = 0, element = 0; + addr_mesh1d(c->pkt.to, &cluster, &element, NULL); + + if (cluster == n->cluster && element == elem) + sel_c = c; + } + + struct reg *sel_0 = NULL, *sel_1 = NULL; + if (sel_a && sel_b) + sel_0 = sel_a->pkt.timestamp < sel_b->pkt.timestamp ? sel_a : sel_b; + else + sel_0 = sel_a ? sel_a : sel_b; + + if (sel_b && sel_c) + sel_1 = sel_b->pkt.timestamp < sel_c->pkt.timestamp ? sel_b : sel_c; + else + sel_1 = sel_b ? sel_b : sel_c; + + struct reg *sel = NULL; + if (sel_0 && sel_1) + sel = sel_0->pkt.timestamp < sel_1->pkt.timestamp ? sel_0 : sel_1; + else + sel = sel_0 ? sel_0 : sel_1; + + if (!sel) + return; + + copy_reg(&n->out[elem], sel); +} + +static stat node1d_clock(struct node1d *n) +{ + n->timestamp++; + + clock_outputs(n); + + /* select oldest packet to process */ + struct reg *r = NULL; + for (int i = 0; i < n->elems; ++i) { + if (!n->in[i].busy) + continue; + + if (!r || r->pkt.timestamp > n->in[i].pkt.timestamp) + r = &n->in[i]; + } + + propagate_left(n, r, &right_in(n)); + propagate_right(n, r, &left_in(n)); + for (int i = 0; i < n->elems; ++i) + propagate(n, i, r, &right_in(n), &left_in(n)); + + return OK; +} + +stat mesh_node1d_connect(struct component *c, struct component *e, uint16_t elem) +{ + struct node1d *n = (struct node1d *)c; + if (elem >= n->elems) + return ENOSUCH; + + if (n->ports[elem]) + return EEXISTS; + + n->ports[elem] = e; + return OK; +} + +stat mesh_node1d_connect_left(struct component *c, struct component *e) +{ + struct node1d *n = (struct node1d *)c; + if (left_port(n)) + return EEXISTS; + + left_port(n) = e; + return OK; +} + +stat mesh_node1d_connect_right(struct component *c, struct component *e) +{ + struct node1d *n = (struct node1d *)c; + if (right_port(n)) + return EEXISTS; + + right_port(n) = e; + return OK; +} + +struct component *create_mesh_node1d(uint16_t cluster, uint16_t elems) +{ + struct node1d *n = (struct node1d *)calloc(1, sizeof(struct node1d)); + if (!n) + return NULL; + + n->in = (struct reg *)calloc(elems + 2, sizeof(struct reg)); + if (!n->in) { + free(n); + return NULL; + } + + n->out = (struct reg *)calloc(elems + 2, sizeof(struct reg)); + if (!n->out) { + free(n->in); + free(n); + return NULL; + } + + n->ports = (struct component **)calloc(elems + 2, sizeof(struct component *)); + if (!n->ports) { + free(n->out); + free(n->in); + free(n); + return NULL; + } + + n->component.destroy = (destroy_callback)node1d_destroy; + n->component.receive = (receive_callback)node1d_receive; + n->component.clock = (clock_callback)node1d_clock; + n->cluster = cluster; + n->elems = elems; + return (struct component *)n; +} diff --git a/src/mesh/node2d.c b/src/mesh/node2d.c new file mode 100644 index 0000000..81ef8dc --- /dev/null +++ b/src/mesh/node2d.c @@ -0,0 +1,281 @@ +#include <gran/mesh/node2d.h> + +#define north_port(n) (n)->ports[(n)->elems + 0] +#define east_port(n) (n)->ports[(n)->elems + 1] +#define south_port(n) (n)->ports[(n)->elems + 2] +#define west_port(n) (n)->ports[(n)->elems + 3] + +#define north_in(n) (n)->in[(n)->elems + 0] +#define east_in(n) (n)->in[(n)->elems + 1] +#define south_in(n) (n)->in[(n)->elems + 2] +#define west_in(n) (n)->in[(n)->elems + 3] + +#define north_out(n) (n)->out[(n)->elems + 0] +#define east_out(n) (n)->out[(n)->elems + 1] +#define south_out(n) (n)->out[(n)->elems + 2] +#define west_out(n) (n)->out[(n)->elems + 3] + +struct reg { + struct packet pkt; + bool busy; +}; + +struct node2d { + struct component component; + uint16_t elems; + uint16_t x, y; + + uint64_t timestamp; + + struct reg *in; /* countedby[elems + 4] */ + struct reg *out; /* countedby[elems + 4] */ + struct component **ports; /* countedby[elems + 4] */ +}; + +static void clock_outputs(struct node2d *n) +{ + for (int i = 0; i < n->elems + 4; ++i) { + if (!n->out[i].busy) + continue; + + stat ret = SEND(n, n->ports[i], n->out[i].pkt); + if (ret == EBUSY) + continue; + + n->out[i].busy = false; + } +} + +static void copy_reg(struct reg *r, struct reg *s) +{ + assert(s->busy); + if (r->busy) + return; + + r->pkt = s->pkt; + r->busy = true; + s->busy = false; +} + +static void propagate(struct reg *out, + size_t count, struct reg *in[static count], + bool (*sel)(struct reg *r, void *data), void *data) +{ + struct reg *r = NULL; + for (size_t i = 0; i < count; ++i) { + if (!in[i] || !in[i]->busy) + continue; + + if (!sel(in[i], data)) + continue; + + if (!r || r->pkt.timestamp > in[i]->pkt.timestamp) + r = in[i]; + } + + if (!r) + return; + + copy_reg(out, r); +} + +struct sel_helper { + uint8_t x, y; + uint16_t elem; +}; + +static bool north_sel(struct reg *r, void *data) +{ + uint8_t y = 0; + struct sel_helper *helper = data; + addr_mesh2d(r->pkt.to, NULL, &y, NULL, NULL); + return y > helper->y; +} + +static bool south_sel(struct reg *r, void *data) +{ + uint8_t y = 0; + struct sel_helper *helper = data; + addr_mesh2d(r->pkt.to, NULL, &y, NULL, NULL); + return y < helper->y; +} + +static bool east_sel(struct reg *r, void *data) +{ + uint8_t x = 0, y = 0; + struct sel_helper *helper = data; + addr_mesh2d(r->pkt.to, &x, &y, NULL, NULL); + return y == helper->y && x > helper->x; +} + +static bool west_sel(struct reg *r, void *data) +{ + uint8_t x = 0, y = 0; + struct sel_helper *helper = data; + addr_mesh2d(r->pkt.to, &x, &y, NULL, NULL); + return y == helper->y && x < helper->x; +} + +static bool elem_sel(struct reg *r, void *data) +{ + uint16_t elem = 0; + uint8_t x = 0, y = 0; + struct sel_helper *helper = data; + addr_mesh2d(r->pkt.to, &x, &y, &elem, NULL); + return x == helper->x && y == helper->y && elem == helper->elem; +} + +static stat node2d_clock(struct node2d *n) +{ + n->timestamp++; + clock_outputs(n); + + /* select oldest packet to process */ + struct reg *r = NULL; + for (int i = 0; i < n->elems; ++i) { + if (!n->in[i].busy) + continue; + + if (!r || r->pkt.timestamp > n->in[i].pkt.timestamp) + r = &n->in[i]; + } + + struct sel_helper helper = { + .elem = 0, + .x = n->x, + .y = n->y, + }; + + struct reg *north[] = {r, &east_in(n), &south_in(n), &west_in(n)}; + struct reg *east[] = {r, &north_in(n), &south_in(n), &west_in(n)}; + struct reg *south[] = {r, &north_in(n), &east_in(n), &west_in(n)}; + struct reg *west[] = {r, &north_in(n), &east_in(n), &south_in(n)}; + + propagate(&north_out(n), 4, north, north_sel, &helper); + propagate(&east_out(n), 4, east, east_sel, &helper); + propagate(&south_out(n), 4, south, south_sel, &helper); + propagate(&west_out(n), 4, west, west_sel, &helper); + + struct reg *all[] = {r, &north_in(n), &east_in(n), &south_in(n), &west_in(n)}; + for (int i = 0; i < n->elems; ++i) { + helper.elem = i; + propagate(&n->out[i], 5, all, elem_sel, &helper); + } + + return OK; +} + +static stat reg_busy(struct reg *r, struct packet pkt) +{ + bool busy = r->busy; + if (!busy) { + r->pkt = pkt; + r->busy = true; + } + + return busy ? EBUSY : OK; +} + +static stat node2d_receive(struct node2d *n, struct component *from, struct packet pkt) +{ + for (int i = 0; i < n->elems + 4; ++i) { + if (from != n->ports[i]) + continue; + + if (i < n->elems) + pkt.timestamp = n->timestamp; + + return reg_busy(&n->in[i], pkt); + } + + abort(); + return OK; +} + +struct component *create_mesh_node2d(uint8_t x, uint8_t y, uint16_t elems) +{ + struct node2d *n = calloc(1, sizeof(struct node2d)); + if (!n) + return NULL; + + n->in = calloc(elems + 4, sizeof(struct reg)); + if (!n->in) { + free(n); + return NULL; + } + + n->out = calloc(elems + 4, sizeof(struct reg)); + if (!n->out) { + free(n->in); + free(n); + return NULL; + } + + n->ports = calloc(elems + 4, sizeof(struct component *)); + if (!n->ports) { + free(n->out); + free(n->in); + free(n); + return NULL; + } + + n->component.receive = (receive_callback)node2d_receive; + n->component.clock = (clock_callback)node2d_clock; + n->elems = elems; + n->x = x; + n->y = y; + return (struct component *)n; +} + +stat mesh_node2d_connect(struct component *c, struct component *e, uint16_t elem) +{ + struct node2d *n = (struct node2d *)c; + if (elem >= n->elems) + return ENOSUCH; + + if (n->ports[elem]) + return EEXISTS; + + n->ports[elem] = e; + return OK; +} + +stat mesh_node2d_connect_north(struct component *c, struct component *e) +{ + struct node2d *n = (struct node2d *)c; + if (north_port(n)) + return EEXISTS; + + north_port(n) = e; + return OK; +} + +stat mesh_node2d_connect_east(struct component *c, struct component *e) +{ + struct node2d *n = (struct node2d *)c; + if (east_port(n)) + return EEXISTS; + + east_port(n) = e; + return OK; +} + +stat mesh_node2d_connect_south(struct component *c, struct component *e) +{ + struct node2d *n = (struct node2d *)c; + if (south_port(n)) + return EEXISTS; + + south_port(n) = e; + return OK; +} + +stat mesh_node2d_connect_west(struct component *c, struct component *e) +{ + struct node2d *n = (struct node2d *)c; + if (west_port(n)) + return EEXISTS; + + west_port(n) = e; + return OK; +} diff --git a/src/mesh/source.mk b/src/mesh/source.mk index 55a7d03..23d6014 100644 --- a/src/mesh/source.mk +++ b/src/mesh/source.mk @@ -1 +1 @@ -SOURCES += src/mesh/node.c src/mesh/node3d.c +SOURCES += src/mesh/node1d.c src/mesh/node2d.c src/mesh/node3d.c diff --git a/src/source.mk b/src/source.mk index 3ed3dba..f6e8ba9 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 src/ideal_noc.c +SOURCES += src/root.c src/clock_domain.c src/ideal_noc.c MAIN_SRC += src/main.c |