URL https://opencores.org/ocsvn/an-fpga-implementation-of-low-latency-noc-based-mpsoc/an-fpga-implementation-of-low-latency-noc-based-mpsoc/trunk

Subversion Repositories an-fpga-implementation-of-low-latency-noc-based-mpsoc

[/] [an-fpga-implementation-of-low-latency-noc-based-mpsoc/] [trunk/] [mpsoc/] [remove_cycle/] [agony/] [graph.cpp] - Blame information for rev 48

Details | Compare with Previous | View Log


#include "graph.h"
#include <assert.h>
 
void
graph::reset(uint32_t n, uint32_t m)
{
        m_nodes.resize(n);
        m_edges.resize(m);
 
        for (uint32_t i = 0; i < n; i++) {
                TAILQ_INIT(&m_nodes[i].out);
                TAILQ_INIT(&m_nodes[i].in);
                m_nodes[i].id = i;
                m_nodes[i].ind = m_nodes[i].outd = 0;
        }
 
        for (uint32_t i = 0; i < m_edges.size(); i++) {
                m_edges[i].id = i;
                m_edges[i].bound = false;
        }
}
 
 
graph::graph(const graph & g) {copy(g);}
 
void
graph::copy(const graph & g)
{
        reset(g.m_nodes.size(), g.m_edges.size());
 
        for (uint32_t i = 0; i < m_edges.size(); i++) {
                if (g.m_edges[i].bound)
                        bind(i, g.m_edges[i].parent->id, g.m_edges[i].child->id);
        }
 
}
 
uint32_t
agony::cost()
{
        uint32_t t = 0;
 
        for (uint32_t i = 0; i < m_edges.size(); i++) {
                node *n = from(i);
                node *m = to(i);
                if (m->rank <= n->rank) t += n->rank - m->rank + 1;
 
        }
 
        return t;
}
 
 
void
agony::cycledfs()
{
        graph dfs(m_graph);
 
 
        nodehead active;
        TAILQ_INIT(&active);
 
        for (uint32_t i = 0; i < size(); i++) TAILQ_INSERT_TAIL(&active, &m_nodes[i], entries);
 
        while (!TAILQ_EMPTY(&active)) {
                node *seed = TAILQ_FIRST(&active);
                node *u = seed;
 
                u->parent = 0;
 
                while (u) {
 
                        graph::node *n = dfs.getnode(u->id);
                        if (TAILQ_EMPTY(&n->out)) {
                                TAILQ_REMOVE(&active, u, entries);
                                dfs.unbind(n);
                                u = u->parent;
                        }
                        else {
                                graph::edge *e = TAILQ_FIRST(&n->out);
                                graph::node *m = e->child;
                                node *v = getnode(m->id);
 
                                if (v->parent == 0 && v != seed) {
                                        v->parent = u;
                                        v->paredge = e->id;
                                        u = v;
                                }
                                else {
                                        for (node *w = u; w != v; w = w->parent) {
                                                getedge(w->paredge)->eulerian = true;
                                                dfs.unbind(dfs.getedge(w->paredge));
                                        }
 
                                        getedge(e->id)->eulerian = true;
                                        dfs.unbind(e);
 
                                        for (node *w = u, *wnext; w != v; w = wnext) {
                                                wnext = w->parent;
                                                w->parent = 0;
                                        }
 
                                        u = v;
                                }
                        }
                }
        }
}
 
void
agony::initagony()
{
        m_dag.copy(m_graph);
        m_euler.copy(m_graph);
 
        for (uint32_t i = 0; i < m_edges.size(); i++) {
                if (getedge(i)->eulerian) {
                        m_dag.unbind(m_dag.getedge(i));
                        m_dual++;
                }
                else {
                        m_euler.unbind(m_euler.getedge(i));
                }
        }
 
        m_primal = m_dual;
}
 
void
agony::initrank()
{
        nodelist sources;
 
        for (uint32_t i = 0; i < size(); i++) {
                node *n = getnode(i);
                n->count = m_dag.getnode(i)->ind;
                if (n->count == 0) {
                        n->newrank = n->rank = 0;
                        sources.push_back(n);
                }
        }
 
        while (!sources.empty())  {
                node *n = sources.front();
                sources.pop_front();
 
                graph::node *u = m_dag.getnode(n->id);
                graph::edge *e;
                TAILQ_FOREACH(e, &u->out, from) {
                        node *m = getnode(e->child->id);
                        m->count--;
                        m->newrank = m->rank = std::max(m->rank, n->rank + 1);
                        if (m->count == 0) sources.push_back(m);
                }
        }
 
        m_slacks.resize(size());
        for (uint32_t i = 0; i < size(); i++) {
                TAILQ_INIT(&m_slacks[i]);
        }
 
        m_curslack = -1;
        for (uint32_t i = 0; i < m_edges.size(); i++) {
                if (getedge(i)->eulerian) addslack(i);
                m_curslack = std::max(int32_t(slack(i)), m_curslack);
        }
}
 
void
agony::minagony()
{
        for (uint32_t i = 0; i < size(); i++) {
                graph::node *n = m_dag.getnode(i);
                graph::edge *e;
 
                TAILQ_FOREACH(e, &n->out, from) {
                        assert(from(e->id)->rank < to(e->id)->rank);
                }
        }
 
        while(true) {
                while (m_curslack >= 0 && TAILQ_EMPTY(&m_slacks[m_curslack])) m_curslack--;
                if (m_curslack < 0) break;
 
                edge *e = TAILQ_FIRST(&m_slacks[m_curslack]);
 
                relief(e->id);
                printf("%d %d\n", primal(), dual());
        }
}
 
 
void
agony::relief(uint32_t edge)
{
        graph::edge *e = m_euler.getedge(edge);
        node *p = getnode(e->parent->id);
        node *s = getnode(e->child->id);
 
        p->parent = 0;
        p->diff = slack(p, s);
        assert(p->diff > 0);
 
        // Add and init queue
        nodequeue q(p->diff);
        for (uint32_t i = 0; i < q.size(); i++)
                TAILQ_INIT(&q[i]);
        TAILQ_INSERT_TAIL(&q[p->diff - 1], p, entries);
        int32_t curstack = p->diff - 1;
 
        nodelist nl;
        nodelist visited;
        nl.push_back(p);
 
        uint32_t bound = 0;
 
        while (true) {
 
                while (curstack >= 0 && TAILQ_EMPTY(&q[curstack])) curstack--;
 
                if (curstack < int32_t(bound)) {
                        break;
                }
 
                node *u = TAILQ_FIRST(&q[curstack]);
                TAILQ_REMOVE(&q[curstack], u, entries);
 
 
 
                u->newrank = u->rank + u->diff;
                visited.push_back(u);
                u->diff = 0; // diff = 0 means that u is no longer in the stack
 
                if (u == s) break;
 
                graph::node *n = m_dag.getnode(u->id);
 
                TAILQ_FOREACH(e, &n->out, from) {
                        node *v = getnode(e->child->id);
                        assert(u->rank < v->rank);
                        if (v->newrank <= u->newrank) {
                                uint32_t t = u->newrank + 1 - v->newrank;
                                assert(t - 1 <= curstack);
                                if (v == s) bound = std::max(bound, t);
                                if (t > v->diff) {
                                        if (v->diff > 0) TAILQ_REMOVE(&q[v->diff - 1], v, entries);
                                        else nl.push_back(v);
                                        v->diff = t;
                                        // add v to queue
                                        TAILQ_INSERT_TAIL(&q[v->diff - 1], v, entries);
                                        v->parent = u;
                                        v->paredge = e->id;
                                }
                        }
                }
 
                n = m_euler.getnode(u->id);
                TAILQ_FOREACH(e, &n->in, to) {
                        node *v = getnode(e->parent->id);
                        if (newslack(v, u) > slack(v, u)) {
                                uint32_t t = newslack(v, u) - slack(v, u);
                                assert(t - 1 <= curstack);
                                if (v == s) bound = std::max(bound, t);
                                if (t > v->diff) {
                                        if (v->diff > 0) TAILQ_REMOVE(&q[v->diff - 1], v, entries);
                                        else nl.push_back(v);
                                        v->diff = t;
                                        // add v to queue
                                        TAILQ_INSERT_TAIL(&q[v->diff - 1], v, entries);
                                        v->parent = u;
                                        v->paredge = e->id;
                                }
                        }
                }
 
        }
 
        if (curstack >= 0) shiftrank(visited, curstack + 1);
 
        updaterelief(nl);
        if (slack(p, s)) extractcycle(edge);
 
}
 
void
agony::updaterelief(nodelist & nl)
{
        for (nodelist::iterator it = nl.begin(); it != nl.end(); ++it) {
                node *n = *it;
                n->rank = n->newrank;
                n->diff = 0;
        }
 
        for (nodelist::iterator it = nl.begin(); it != nl.end(); ++it) {
                node *u = *it;
                graph::edge *e;
                graph::node *n = m_euler.getnode(u->id);
                TAILQ_FOREACH(e, &n->out, from) {
                        node *v = to(e->id);
                        edge *f = getedge(e->id);
                        if (slack(u, v) != f->slack) {
                                deleteslack(e->id);
                                addslack(e->id);
                        }
                }
        }
}
 
void
agony::resetrelief(nodelist & nl)
{
        for (nodelist::iterator it = nl.begin(); it != nl.end(); ++it) {
                node *n = *it;
                n->newrank = n->rank;
                n->diff = 0;
        }
}
 
void
agony::shiftrank(nodelist & nl, uint32_t shift)
{
        for (nodelist::iterator it = nl.begin(); it != nl.end(); ++it) {
                node *n = *it;
                n->newrank -= shift;
        }
}
 
void
agony::extractcycle(uint32_t eid)
{
        graph::edge *e = m_euler.getedge(eid);
        node *p = getnode(e->parent->id);
        node *s = getnode(e->child->id);
 
        for (node *u = s; u != p; u = u->parent) {
 
                edge *f =  getedge(u->paredge);
 
                if (f->eulerian) {
                        f->eulerian = false;
                        m_euler.unbind(m_euler.getedge(u->paredge));
                        assert(u->rank < u->parent->rank);
                        m_dag.bind(u->paredge, u->id, u->parent->id);
                        deleteslack(u->paredge);
                        m_dual--;
                        m_primal--;
                }
                else {
                        f->eulerian = true;
                        m_dag.unbind(m_dag.getedge(u->paredge));
                        m_euler.bind(u->paredge, u->parent->id, u->id);
                        addslack(u->paredge);
                        m_dual++;
                        m_primal++;
                }
        }
 
        edge *g = getedge(eid);
 
        g->eulerian = false;
        m_euler.unbind(e);
        m_dag.bind(eid, p->id, s->id);
        m_dual--;
        m_primal--;
        deleteslack(eid);
}
 
void
agony::deleteslack(uint32_t eid)
{
        uint32_t t = getedge(eid)->slack;
        if (t > 0) TAILQ_REMOVE(&m_slacks[t - 1], getedge(eid), entries);
        m_primal -= t;
}
 
void
agony::addslack(uint32_t eid)
{
        uint32_t t = slack(eid);
        edge *e = getedge(eid);
        e->slack = t;
        if (t > 0) TAILQ_INSERT_TAIL(&m_slacks[t - 1], getedge(eid), entries);
        m_primal += t;
}

Browse

Tools

Subversion Repositories an-fpga-implementation-of-low-latency-noc-based-mpsoc

[/] [an-fpga-implementation-of-low-latency-noc-based-mpsoc/] [trunk/] [mpsoc/] [remove_cycle/] [agony/] [graph.cpp] - Blame information for rev 48

Line No.	Rev	Author	Line
1	48	alirezamon	`#include "graph.h"`
2			`#include <assert.h>`
3
4			`void`
5			`graph::reset(uint32_t n, uint32_t m)`
6			`{`
7			`m_nodes.resize(n);`
8			`m_edges.resize(m);`
9
10			`for (uint32_t i = 0; i < n; i++) {`
11			`TAILQ_INIT(&m_nodes[i].out);`
12			`TAILQ_INIT(&m_nodes[i].in);`
13			`m_nodes[i].id = i;`
14			`m_nodes[i].ind = m_nodes[i].outd = 0;`
15			`}`
16
17			`for (uint32_t i = 0; i < m_edges.size(); i++) {`
18			`m_edges[i].id = i;`
19			`m_edges[i].bound = false;`
20			`}`
21			`}`
22
23
24			`graph::graph(const graph & g) {copy(g);}`
25
26			`void`
27			`graph::copy(const graph & g)`
28			`{`
29			`reset(g.m_nodes.size(), g.m_edges.size());`
30
31			`for (uint32_t i = 0; i < m_edges.size(); i++) {`
32			`if (g.m_edges[i].bound)`
33			`bind(i, g.m_edges[i].parent->id, g.m_edges[i].child->id);`
34			`}`
35
36			`}`
37
38			`uint32_t`
39			`agony::cost()`
40			`{`
41			`uint32_t t = 0;`
42
43			`for (uint32_t i = 0; i < m_edges.size(); i++) {`
44			`node *n = from(i);`
45			`node *m = to(i);`
46			`if (m->rank <= n->rank) t += n->rank - m->rank + 1;`
47
48			`}`
49
50			`return t;`
51			`}`
52
53
54			`void`
55			`agony::cycledfs()`
56			`{`
57			`graph dfs(m_graph);`
58
59
60			`nodehead active;`
61			`TAILQ_INIT(&active);`
62
63			`for (uint32_t i = 0; i < size(); i++) TAILQ_INSERT_TAIL(&active, &m_nodes[i], entries);`
64
65			`while (!TAILQ_EMPTY(&active)) {`
66			`node *seed = TAILQ_FIRST(&active);`
67			`node *u = seed;`
68
69			`u->parent = 0;`
70
71			`while (u) {`
72
73			`graph::node *n = dfs.getnode(u->id);`
74			`if (TAILQ_EMPTY(&n->out)) {`
75			`TAILQ_REMOVE(&active, u, entries);`
76			`dfs.unbind(n);`
77			`u = u->parent;`
78			`}`
79			`else {`
80			`graph::edge *e = TAILQ_FIRST(&n->out);`
81			`graph::node *m = e->child;`
82			`node *v = getnode(m->id);`
83
84			`if (v->parent == 0 && v != seed) {`
85			`v->parent = u;`
86			`v->paredge = e->id;`
87			`u = v;`
88			`}`
89			`else {`
90			`for (node *w = u; w != v; w = w->parent) {`
91			`getedge(w->paredge)->eulerian = true;`
92			`dfs.unbind(dfs.getedge(w->paredge));`
93			`}`
94
95			`getedge(e->id)->eulerian = true;`
96			`dfs.unbind(e);`
97
98			`for (node w = u, wnext; w != v; w = wnext) {`
99			`wnext = w->parent;`
100			`w->parent = 0;`
101			`}`
102
103			`u = v;`
104			`}`
105			`}`
106			`}`
107			`}`
108			`}`
109
110			`void`
111			`agony::initagony()`
112			`{`
113			`m_dag.copy(m_graph);`
114			`m_euler.copy(m_graph);`
115
116			`for (uint32_t i = 0; i < m_edges.size(); i++) {`
117			`if (getedge(i)->eulerian) {`
118			`m_dag.unbind(m_dag.getedge(i));`
119			`m_dual++;`
120			`}`
121			`else {`
122			`m_euler.unbind(m_euler.getedge(i));`
123			`}`
124			`}`
125
126			`m_primal = m_dual;`
127			`}`
128
129			`void`
130			`agony::initrank()`
131			`{`
132			`nodelist sources;`
133
134			`for (uint32_t i = 0; i < size(); i++) {`
135			`node *n = getnode(i);`
136			`n->count = m_dag.getnode(i)->ind;`
137			`if (n->count == 0) {`
138			`n->newrank = n->rank = 0;`
139			`sources.push_back(n);`
140			`}`
141			`}`
142
143			`while (!sources.empty()) {`
144			`node *n = sources.front();`
145			`sources.pop_front();`
146
147			`graph::node *u = m_dag.getnode(n->id);`
148			`graph::edge *e;`
149			`TAILQ_FOREACH(e, &u->out, from) {`
150			`node *m = getnode(e->child->id);`
151			`m->count--;`
152			`m->newrank = m->rank = std::max(m->rank, n->rank + 1);`
153			`if (m->count == 0) sources.push_back(m);`
154			`}`
155			`}`
156
157			`m_slacks.resize(size());`
158			`for (uint32_t i = 0; i < size(); i++) {`
159			`TAILQ_INIT(&m_slacks[i]);`
160			`}`
161
162			`m_curslack = -1;`
163			`for (uint32_t i = 0; i < m_edges.size(); i++) {`
164			`if (getedge(i)->eulerian) addslack(i);`
165			`m_curslack = std::max(int32_t(slack(i)), m_curslack);`
166			`}`
167			`}`
168
169			`void`
170			`agony::minagony()`
171			`{`
172			`for (uint32_t i = 0; i < size(); i++) {`
173			`graph::node *n = m_dag.getnode(i);`
174			`graph::edge *e;`
175
176			`TAILQ_FOREACH(e, &n->out, from) {`
177			`assert(from(e->id)->rank < to(e->id)->rank);`
178			`}`
179			`}`
180
181			`while(true) {`
182			`while (m_curslack >= 0 && TAILQ_EMPTY(&m_slacks[m_curslack])) m_curslack--;`
183			`if (m_curslack < 0) break;`
184
185			`edge *e = TAILQ_FIRST(&m_slacks[m_curslack]);`
186
187			`relief(e->id);`
188			`printf("%d %d\n", primal(), dual());`
189			`}`
190			`}`
191
192
193			`void`
194			`agony::relief(uint32_t edge)`
195			`{`
196			`graph::edge *e = m_euler.getedge(edge);`
197			`node *p = getnode(e->parent->id);`
198			`node *s = getnode(e->child->id);`
199
200			`p->parent = 0;`
201			`p->diff = slack(p, s);`
202			`assert(p->diff > 0);`
203
204			`// Add and init queue`
205			`nodequeue q(p->diff);`
206			`for (uint32_t i = 0; i < q.size(); i++)`
207			`TAILQ_INIT(&q[i]);`
208			`TAILQ_INSERT_TAIL(&q[p->diff - 1], p, entries);`
209			`int32_t curstack = p->diff - 1;`
210
211			`nodelist nl;`
212			`nodelist visited;`
213			`nl.push_back(p);`
214
215			`uint32_t bound = 0;`
216
217			`while (true) {`
218
219			`while (curstack >= 0 && TAILQ_EMPTY(&q[curstack])) curstack--;`
220
221			`if (curstack < int32_t(bound)) {`
222			`break;`
223			`}`
224
225			`node *u = TAILQ_FIRST(&q[curstack]);`
226			`TAILQ_REMOVE(&q[curstack], u, entries);`
227
228
229
230			`u->newrank = u->rank + u->diff;`
231			`visited.push_back(u);`
232			`u->diff = 0; // diff = 0 means that u is no longer in the stack`
233
234			`if (u == s) break;`
235
236			`graph::node *n = m_dag.getnode(u->id);`
237
238			`TAILQ_FOREACH(e, &n->out, from) {`
239			`node *v = getnode(e->child->id);`
240			`assert(u->rank < v->rank);`
241			`if (v->newrank <= u->newrank) {`
242			`uint32_t t = u->newrank + 1 - v->newrank;`
243			`assert(t - 1 <= curstack);`
244			`if (v == s) bound = std::max(bound, t);`
245			`if (t > v->diff) {`
246			`if (v->diff > 0) TAILQ_REMOVE(&q[v->diff - 1], v, entries);`
247			`else nl.push_back(v);`
248			`v->diff = t;`
249			`// add v to queue`
250			`TAILQ_INSERT_TAIL(&q[v->diff - 1], v, entries);`
251			`v->parent = u;`
252			`v->paredge = e->id;`
253			`}`
254			`}`
255			`}`
256
257			`n = m_euler.getnode(u->id);`
258			`TAILQ_FOREACH(e, &n->in, to) {`
259			`node *v = getnode(e->parent->id);`
260			`if (newslack(v, u) > slack(v, u)) {`
261			`uint32_t t = newslack(v, u) - slack(v, u);`
262			`assert(t - 1 <= curstack);`
263			`if (v == s) bound = std::max(bound, t);`
264			`if (t > v->diff) {`
265			`if (v->diff > 0) TAILQ_REMOVE(&q[v->diff - 1], v, entries);`
266			`else nl.push_back(v);`
267			`v->diff = t;`
268			`// add v to queue`
269			`TAILQ_INSERT_TAIL(&q[v->diff - 1], v, entries);`
270			`v->parent = u;`
271			`v->paredge = e->id;`
272			`}`
273			`}`
274			`}`
275
276			`}`
277
278			`if (curstack >= 0) shiftrank(visited, curstack + 1);`
279
280			`updaterelief(nl);`
281			`if (slack(p, s)) extractcycle(edge);`
282
283			`}`
284
285			`void`
286			`agony::updaterelief(nodelist & nl)`
287			`{`
288			`for (nodelist::iterator it = nl.begin(); it != nl.end(); ++it) {`
289			`node n = it;`
290			`n->rank = n->newrank;`
291			`n->diff = 0;`
292			`}`
293
294			`for (nodelist::iterator it = nl.begin(); it != nl.end(); ++it) {`
295			`node u = it;`
296			`graph::edge *e;`
297			`graph::node *n = m_euler.getnode(u->id);`
298			`TAILQ_FOREACH(e, &n->out, from) {`
299			`node *v = to(e->id);`
300			`edge *f = getedge(e->id);`
301			`if (slack(u, v) != f->slack) {`
302			`deleteslack(e->id);`
303			`addslack(e->id);`
304			`}`
305			`}`
306			`}`
307			`}`
308
309			`void`
310			`agony::resetrelief(nodelist & nl)`
311			`{`
312			`for (nodelist::iterator it = nl.begin(); it != nl.end(); ++it) {`
313			`node n = it;`
314			`n->newrank = n->rank;`
315			`n->diff = 0;`
316			`}`
317			`}`
318
319			`void`
320			`agony::shiftrank(nodelist & nl, uint32_t shift)`
321			`{`
322			`for (nodelist::iterator it = nl.begin(); it != nl.end(); ++it) {`
323			`node n = it;`
324			`n->newrank -= shift;`
325			`}`
326			`}`
327
328			`void`
329			`agony::extractcycle(uint32_t eid)`
330			`{`
331			`graph::edge *e = m_euler.getedge(eid);`
332			`node *p = getnode(e->parent->id);`
333			`node *s = getnode(e->child->id);`
334
335			`for (node *u = s; u != p; u = u->parent) {`
336
337			`edge *f = getedge(u->paredge);`
338
339			`if (f->eulerian) {`
340			`f->eulerian = false;`
341			`m_euler.unbind(m_euler.getedge(u->paredge));`
342			`assert(u->rank < u->parent->rank);`
343			`m_dag.bind(u->paredge, u->id, u->parent->id);`
344			`deleteslack(u->paredge);`
345			`m_dual--;`
346			`m_primal--;`
347			`}`
348			`else {`
349			`f->eulerian = true;`
350			`m_dag.unbind(m_dag.getedge(u->paredge));`
351			`m_euler.bind(u->paredge, u->parent->id, u->id);`
352			`addslack(u->paredge);`
353			`m_dual++;`
354			`m_primal++;`
355			`}`
356			`}`
357
358			`edge *g = getedge(eid);`
359
360			`g->eulerian = false;`
361			`m_euler.unbind(e);`
362			`m_dag.bind(eid, p->id, s->id);`
363			`m_dual--;`
364			`m_primal--;`
365			`deleteslack(eid);`
366			`}`
367
368			`void`
369			`agony::deleteslack(uint32_t eid)`
370			`{`
371			`uint32_t t = getedge(eid)->slack;`
372			`if (t > 0) TAILQ_REMOVE(&m_slacks[t - 1], getedge(eid), entries);`
373			`m_primal -= t;`
374			`}`
375
376			`void`
377			`agony::addslack(uint32_t eid)`
378			`{`
379			`uint32_t t = slack(eid);`
380			`edge *e = getedge(eid);`
381			`e->slack = t;`
382			`if (t > 0) TAILQ_INSERT_TAIL(&m_slacks[t - 1], getedge(eid), entries);`
383			`m_primal += t;`
384			`}`