CGRA-ME
MappingGraphTests.cpp
Go to the documentation of this file.
1 /*******************************************************************************
2  * The software programs comprising "CGRA-ME" and the documentation provided
3  * with them are copyright by its authors and the University of Toronto. Only
4  * non-commercial, not-for-profit use of this software is permitted without ex-
5  * plicit permission. This software is provided "as is" with no warranties or
6  * guarantees of support. See the LICENCE for more details. You should have re-
7  * ceived a copy of the full licence along with this software. If not, see
8  * <http://cgra-me.ece.utoronto.ca/license/>.
9  ******************************************************************************/
10 
11 #include <CGRA/Mapping.h>
12 #include <CGRA/Module.h>
13 #include <CGRA/user-inc/UserArchs.h>
14 
15 #include "testutils/OpGraphsForTesting.hpp"
16 
17 #include <iostream>
18 
19 #include <catch2/catch.hpp>
20 
21 namespace {
22 
23 Module god_module("top", ""); // used for tests in this file
24 
25 MRRG makeMRRG_Simple(int II, ConfigStore options);
26 MRRG makeMRRG_SimpleFlow(int II, ConfigStore options);
27 
28 } // end anon namespace
29 
30 
31 SCENARIO("Mapping Graph Tests") {
32  GIVEN("an empty graph") {
33  auto mg = MappingGraph();
34 
35  WHEN("inserting 1 node") {
36  mg.insert(MappingGraphNode{nullptr});
37 
38  THEN("Size should be 1") {
39  CHECK(mg.size() == 1);
40  }
41  }
42 
43  WHEN("inserting 2 nodes and linking them") {
44  OpGraphNode op1 = OpGraphNode("Add1");
45  OpGraphNode op2 = OpGraphNode("Add2");
46 
47  auto firstNode = mg.insert(MappingGraphNode{&op1}).first;
48  auto secondNode = mg.insert(MappingGraphNode{static_cast<OpGraph::NodeDescriptor> (&op2)}).first;
49  mg.link(firstNode, secondNode);
50 
51  THEN("first node should fan into second node and second node should fan out from first node") {
52  CHECK(mg.fanout(firstNode)[0] == secondNode);
53  CHECK(mg.fanin(secondNode)[0] == firstNode);
54 
55  AND_THEN("should be able to get references for nodes") {
56  CHECK(mg.getNodeRef(firstNode).op_node_desc == &op1);
57  CHECK(mg.getNodeRef(secondNode).op_node_desc == &op2);
58  }
59  }
60 
61  AND_WHEN("unlinking the two nodes") {
62  mg.unlink(firstNode, secondNode);
63  auto driverFanout = mg.fanout(firstNode);
64  auto fanoutFanin = mg.fanin(secondNode);
65 
66  CHECK(std::find(driverFanout.begin(), driverFanout.end(), secondNode) == driverFanout.end());
67  CHECK(std::find(fanoutFanin.begin(), fanoutFanin.end(), firstNode) == fanoutFanin.end());
68 
69  CHECK(mg.fanout(firstNode).size() == 0);
70  CHECK(mg.fanin(secondNode).size() == 0);
71  }
72  }
73  }
74 
75  GIVEN("a graph with a bunch of nodes") {
76  auto mg = MappingGraph();
77  OpGraphNode op1 = OpGraphNode("Val1");
78  OpGraphNode op2 = OpGraphNode("Val2");
79  OpGraphNode op3 = OpGraphNode("Add1");
80  OpGraphNode op4 = OpGraphNode("Val3");
81  OpGraphNode op5 = OpGraphNode("Val4");
82  OpGraphNode op6 = OpGraphNode("Add2");
83  OpGraphNode op7 = OpGraphNode("Val5");
84 
85  auto m1 = mg.insert(MappingGraphNode{&op1}).first;
86  auto m2 = mg.insert(MappingGraphNode{&op2}).first;
87  auto m3 = mg.insert(MappingGraphNode{&op3}).first;
88  auto m4 = mg.insert(MappingGraphNode{&op4}).first;
89  auto m5 = mg.insert(MappingGraphNode{&op5}).first;
90  auto m6 = mg.insert(MappingGraphNode{&op6}).first;
91  auto m7 = mg.insert(MappingGraphNode{&op7}).first;
92 
93  mg.link(m1, m3);
94  mg.link(m2, m3);
95  mg.link(m3, m4);
96  mg.link(m4, m6);
97  mg.link(m5, m6);
98  mg.link(m6, m7);
99 
100  WHEN("erasing 1 node (Add1)") {
101  mg.erase(m3);
102  THEN("no nodes should have op_desc_node of Add1") {
103  // Check the fanins and fanouts of the nodes we linked
104  auto m1Fanout = mg.fanout(m1);
105  auto m2Fanout = mg.fanout(m2);
106  auto m4Fanin = mg.fanin(m4);
107 
108  CHECK(std::find(m1Fanout.begin(), m1Fanout.end(), m3) == m1Fanout.end());
109  CHECK(std::find(m2Fanout.begin(), m2Fanout.end(), m3) == m2Fanout.end());
110  CHECK(std::find(m4Fanin.begin(), m4Fanin.end(), m3) == m4Fanin.end());
111  }
112  }
113 
114  WHEN("erasing multiple nodes") {
115  mg.erase(m2);
116  mg.erase(m4);
117  mg.erase(m5);
118 
119  THEN("no segfaults should occur") {
120  auto m3Fanin = mg.fanin(m3);
121  auto m3Fanout = mg.fanout(m3);
122  auto m6Fanin = mg.fanin(m6);
123 
124  CHECK(!mg.contains(m2));
125  CHECK(!mg.contains(m4));
126  CHECK(mg.contains(m7));
127 
128  CHECK(std::find(m3Fanin.begin(), m3Fanin.end(), m2) == m3Fanin.end());
129  CHECK(std::find(m3Fanout.begin(), m3Fanout.end(), m4) == m3Fanout.end());
130  CHECK(std::find(m6Fanin.begin(), m6Fanin.end(), m4) == m6Fanin.end());
131  CHECK(std::find(m6Fanin.begin(), m6Fanin.end(), m5) == m6Fanin.end());
132 
133  }
134  }
135  }
136 
137  GIVEN("a self-loop mapping") {
138  // auto opGraph = makeDFG_Large();
139  auto og = makeDFG_SelfLoop3Node();
140 
141  Mapping m = Mapping(nullptr, 3, nullptr);
142  MRRG mrrg(3);
143 
144  Module fillerMod("Mod", "");
145  auto m1 = mrrg.insert(MRRGNode::make_function(&fillerMod, 32, 0, "m1", 1, {})).first;
146  auto m2 = mrrg.insert(MRRGNode::make_function(&fillerMod, 32, 0, "m2", 1, {})).first;
147  auto m3 = mrrg.insert(MRRGNode::make_function(&fillerMod, 32, 0, "m3", 1, {})).first;
148  auto m4 = mrrg.insert(MRRGNode::make_function(&fillerMod, 32, 0, "m4", 1, {})).first;
149  auto m5 = mrrg.insert(MRRGNode::make_function(&fillerMod, 32, 0, "m5", 1, {})).first;
150 
151  mrrg.link(m1, m2);
152  mrrg.link(m2, m3);
153  mrrg.link(m3, m4);
154  mrrg.link(m4, m3);
155  mrrg.link(m4, m5);
156 
157  m.mapMRRGNode(og.opNodes()[0], m1);
158  m.mapMRRGNode(og.valNodes()[0], m2);
159  m.mapMRRGNode(og.opNodes()[1], m3);
160  m.mapMRRGNode(og.valNodes()[1], m4);
161  m.mapMRRGNode(og.opNodes()[2], m5);
162 
163  WHEN("transforming the mapping to a graph") {
164  auto cgmr = createMappingGraph(mrrg, m);
165  SUCCEED();
166  }
167  }
168 
169  GIVEN("a mapping with multiple branches") {
170  auto og = makeDFG_Large(false);
171  Mapping m = Mapping(nullptr, 3, nullptr);
172  MRRG mrrg(3);
173  std::vector<MRRG::NodeDescriptor> mrrgNodes;
174 
175  std::vector<Module> modules;
176  modules.emplace_back("module_1", "");
177  modules.emplace_back("module_2", "");
178  modules.emplace_back("module_3", "");
179 
180 
181  for (auto i = 0; i < (std::ptrdiff_t)og.opNodes().size() + (std::ptrdiff_t)og.valNodes().size(); i++) {
182  std::string name = "m" + std::to_string(i);
183  if (i < (std::ptrdiff_t)og.opNodes().size()) {
184  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&modules[i%3], 32, 0, name, 1, {})).first);
185  }
186  else {
187  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&modules[i%3], 32, 0, name, 1)).first);
188 
189  }
190  }
191 
192  mrrg.link(mrrgNodes[0], mrrgNodes[17]); // add0->add0_out
193  mrrg.link(mrrgNodes[1], mrrgNodes[24]); // const1->const1_out
194  mrrg.link(mrrgNodes[2], mrrgNodes[26]); // mul2->mul2_out
195  mrrg.link(mrrgNodes[3], mrrgNodes[25]); // const3->const3_out
196  mrrg.link(mrrgNodes[4], mrrgNodes[18]); // load4->load4_out
197  mrrg.link(mrrgNodes[5], mrrgNodes[19]); // add5->add5_out
198  mrrg.link(mrrgNodes[6], mrrgNodes[27]); // const6->const6_out
199  mrrg.link(mrrgNodes[7], mrrgNodes[29]); // mul7->mul7_out
200  mrrg.link(mrrgNodes[8], mrrgNodes[28]); // const8->const8_out
201  mrrg.link(mrrgNodes[10], mrrgNodes[20]); // add10->add10_out
202  mrrg.link(mrrgNodes[11], mrrgNodes[31]); // mul11->mul11_out
203  mrrg.link(mrrgNodes[12], mrrgNodes[30]); // const12->const12_out
204  mrrg.link(mrrgNodes[13], mrrgNodes[21]); // load13->load13_out
205  mrrg.link(mrrgNodes[14], mrrgNodes[22]); // mul14->mul14_out
206  mrrg.link(mrrgNodes[16], mrrgNodes[23]); // add16->add16_out
207 
208  mrrg.link(mrrgNodes[17], mrrgNodes[2]); // add0->mul2
209  mrrg.link(mrrgNodes[17], mrrgNodes[5]); // add0->add5
210  mrrg.link(mrrgNodes[17], mrrgNodes[11]); // add0->mul1
211  mrrg.link(mrrgNodes[17], mrrgNodes[0]); // add0->add0
212  mrrg.link(mrrgNodes[24], mrrgNodes[0]); // const1->add0
213  mrrg.link(mrrgNodes[26], mrrgNodes[4]); // mul2->load4
214  mrrg.link(mrrgNodes[25], mrrgNodes[2]); // const3->mul2
215  mrrg.link(mrrgNodes[18], mrrgNodes[10]); // load4->add10
216  mrrg.link(mrrgNodes[19], mrrgNodes[7]); // add5->mul7
217  mrrg.link(mrrgNodes[27], mrrgNodes[5]); // const6->add5
218  mrrg.link(mrrgNodes[29], mrrgNodes[9]); // mul7->load9
219  mrrg.link(mrrgNodes[28], mrrgNodes[7]); // const8->mul7
220  mrrg.link(mrrgNodes[20], mrrgNodes[14]); // add10->mul14
221  mrrg.link(mrrgNodes[31], mrrgNodes[13]); // mul11->load13
222  mrrg.link(mrrgNodes[31], mrrgNodes[15]); // mul11->load15
223  mrrg.link(mrrgNodes[30], mrrgNodes[11]); // const12->mul11
224  mrrg.link(mrrgNodes[21], mrrgNodes[4]); // load13->mul14
225  mrrg.link(mrrgNodes[22], mrrgNodes[15]); // mull14->store5
226  mrrg.link(mrrgNodes[22], mrrgNodes[16]); // mul14->add16
227  mrrg.link(mrrgNodes[23], mrrgNodes[16]); // add16->add16
228 
229 
230  int mrrgNodeNum = 0;
231  for (auto & op : og.opNodes()) {
232  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum]);
233  mrrgNodeNum++;
234  }
235  for (auto & val : og.valNodes()) {
236  m.mapMRRGNode(val, mrrgNodes[mrrgNodeNum]);
237  mrrgNodeNum++;
238  }
239 
240  WHEN("transforming the mapping to a graph") {
241  auto cgmr = createMappingGraph(mrrg, m);
242  SUCCEED();
243  }
244 
245  }
246 
247  GIVEN("a graph with isolated routing loops") {
248  auto og = makeDFG_Large(false);
249 
250  Mapping m = Mapping(nullptr, 3, nullptr);
251  MRRG mrrg(3);
252  std::vector<MRRG::NodeDescriptor> mrrgNodes;
253 
254  std::vector<Module> modules;
255  modules.emplace_back("module_1", "");
256  modules.emplace_back("module_2", "");
257  modules.emplace_back("module_3", "");
258 
259  int nodesToIsolate = 7;
260  for (size_t i = 0; i < og.opNodes().size() + og.valNodes().size() + nodesToIsolate; i++) {
261  std::string name = "m" + std::to_string(i);
262  if (i < og.opNodes().size()) {
263  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&modules[i%3], 32, 0, name, 0, {})).first);
264  }
265  else {
266  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&modules[i%3], 32, 0, name, 0)).first);
267  }
268  }
269 
270 
271  mrrg.link(mrrgNodes[0], mrrgNodes[17]); // add0->add0_out
272  mrrg.link(mrrgNodes[1], mrrgNodes[24]); // const1->const1_out
273  mrrg.link(mrrgNodes[2], mrrgNodes[26]); // mul2->mul2_out
274  mrrg.link(mrrgNodes[3], mrrgNodes[25]); // const3->const3_out
275  mrrg.link(mrrgNodes[4], mrrgNodes[18]); // load4->load4_out
276  mrrg.link(mrrgNodes[5], mrrgNodes[19]); // add5->add5_out
277  mrrg.link(mrrgNodes[6], mrrgNodes[27]); // const6->const6_out
278  mrrg.link(mrrgNodes[7], mrrgNodes[29]); // mul7->mul7_out
279  mrrg.link(mrrgNodes[8], mrrgNodes[28]); // const8->const8_out
280  mrrg.link(mrrgNodes[10], mrrgNodes[20]); // add10->add10_out
281  mrrg.link(mrrgNodes[11], mrrgNodes[31]); // mul11->mul11_out
282  mrrg.link(mrrgNodes[12], mrrgNodes[30]); // const12->const12_out
283  mrrg.link(mrrgNodes[13], mrrgNodes[21]); // load13->load13_out
284  mrrg.link(mrrgNodes[14], mrrgNodes[22]); // mul14->mul14_out
285  mrrg.link(mrrgNodes[16], mrrgNodes[23]); // add16->add16_out
286 
287  mrrg.link(mrrgNodes[17], mrrgNodes[2]); // add0->mul2
288  mrrg.link(mrrgNodes[17], mrrgNodes[5]); // add0->add5
289  mrrg.link(mrrgNodes[17], mrrgNodes[11]); // add0->mul1
290  mrrg.link(mrrgNodes[17], mrrgNodes[0]); // add0->add0
291  mrrg.link(mrrgNodes[24], mrrgNodes[0]); // const1->add0
292  mrrg.link(mrrgNodes[26], mrrgNodes[4]); // mul2->load4
293  mrrg.link(mrrgNodes[25], mrrgNodes[2]); // const3->mul2
294  mrrg.link(mrrgNodes[18], mrrgNodes[10]); // load4->add10
295  mrrg.link(mrrgNodes[19], mrrgNodes[7]); // add5->mul7
296  mrrg.link(mrrgNodes[27], mrrgNodes[5]); // const6->add5
297  mrrg.link(mrrgNodes[29], mrrgNodes[9]); // mul7->load9
298  mrrg.link(mrrgNodes[28], mrrgNodes[7]); // const8->mul7
299  mrrg.link(mrrgNodes[20], mrrgNodes[14]); // add10->mul14
300  mrrg.link(mrrgNodes[31], mrrgNodes[13]); // mul11->load13
301  mrrg.link(mrrgNodes[31], mrrgNodes[15]); // mul11->load15
302  mrrg.link(mrrgNodes[30], mrrgNodes[11]); // const12->mul11
303  mrrg.link(mrrgNodes[21], mrrgNodes[4]); // load13->mul14
304  mrrg.link(mrrgNodes[22], mrrgNodes[15]); // mull14->store5
305  mrrg.link(mrrgNodes[22], mrrgNodes[16]); // mul14->add16
306  mrrg.link(mrrgNodes[23], mrrgNodes[16]); // add16->add16
307 
308  // Loops
309  mrrg.link(mrrgNodes[32], mrrgNodes[33]);
310  mrrg.link(mrrgNodes[33], mrrgNodes[34]);
311  mrrg.link(mrrgNodes[34], mrrgNodes[35]);
312  mrrg.link(mrrgNodes[35], mrrgNodes[33]);
313  mrrg.link(mrrgNodes[36], mrrgNodes[37]);
314  mrrg.link(mrrgNodes[37], mrrgNodes[36]);
315 
316  int mrrgNodeNum = 0;
317  for (auto & op : og.opNodes()) {
318  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum]);
319  mrrgNodeNum++;
320  }
321  for (auto & val : og.valNodes()) {
322  m.mapMRRGNode(val, mrrgNodes[mrrgNodeNum]);
323  mrrgNodeNum++;
324  }
325  for (int i = 0; i < nodesToIsolate; i++) {
326  m.mapMRRGNode(og.valNodes()[0], mrrgNodes[og.opNodes().size()+og.valNodes().size()+i]);
327  }
328 
329  auto cgmr = createMappingGraph(mrrg, m);
330 
331  // Manual testing
332  WHEN("removing isolated loops") {
333  auto fixedGraph = removeIsolatedRoutingNodes(cgmr.mg, mrrg, cgmr.toMRRG);
334 
335  CHECK(fixedGraph.size() == 32);
336  }
337  }
338 
339  GIVEN("a graph with a diamond shape") {
340  auto og = makeDFG_Converging121();
341  MRRG mrrg(1);
342  std::vector<MRRG::NodeDescriptor> mrrgNodes;
343  Mapping m(nullptr, 1, nullptr);
344  Module mod("1", "");
345  WHEN("graph has unbalanced latencies") {
346  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_in", 0)).first);
347  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "a", 0, {})).first);
348  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_out", 0)).first);
349  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b_in", 0)).first);
350  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "b", 1, {})).first);
351  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b_out", 0)).first);
352  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b2_in", 0)).first);
353  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "b2", 0, {})).first);
354  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b2_out", 0)).first);
355  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "c_in", 0)).first);
356  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "c", 0, {})).first);
357  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "c_out", 0)).first);
358 
359  mrrg.link(mrrgNodes[0], mrrgNodes[1]);
360  mrrg.link(mrrgNodes[1], mrrgNodes[2]);
361  mrrg.link(mrrgNodes[2], mrrgNodes[3]);
362  mrrg.link(mrrgNodes[3], mrrgNodes[4]);
363  mrrg.link(mrrgNodes[4], mrrgNodes[5]);
364  mrrg.link(mrrgNodes[2], mrrgNodes[6]);
365  mrrg.link(mrrgNodes[6], mrrgNodes[7]);
366  mrrg.link(mrrgNodes[7], mrrgNodes[8]);
367  mrrg.link(mrrgNodes[8], mrrgNodes[9]);
368  mrrg.link(mrrgNodes[5], mrrgNodes[9]);
369  mrrg.link(mrrgNodes[9], mrrgNodes[10]);
370  mrrg.link(mrrgNodes[10], mrrgNodes[11]);
371 
372  int mrrgNodeNum = 0;
373  for (auto & val : og.valNodes()) {
374  m.mapMRRGNode(val, mrrgNodes[mrrgNodeNum*3+2]);
375  mrrgNodeNum++;
376  }
377 
378  mrrgNodeNum = 0;
379  for (auto & op : og.opNodes()) {
380  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*3]);
381  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*3+1]);
382  mrrgNodeNum++;
383  }
384 
385  auto cgmr = createMappingGraph(mrrg, m);
386 
387  THEN("checking for unbalanced graph") {
388  CHECK(!latencyCheck(cgmr.mg, mrrg, cgmr.toMRRG).first);
389  }
390  }
391 
392  WHEN("graph has balanced latencies") {
393  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_in", 1)).first);
394  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "a", 1, {})).first);
395  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_out", 1)).first);
396  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b_in", 2)).first);
397  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "b", 2, {})).first);
398  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b_out", 1)).first);
399  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b2_in", 1)).first);
400  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "b2", 2, {})).first);
401  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b2_out", 2)).first);
402  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "c_in", 1)).first);
403  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "c", 1, {})).first);
404  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "c_out", 1)).first);
405 
406  mrrg.link(mrrgNodes[0], mrrgNodes[1]);
407  mrrg.link(mrrgNodes[1], mrrgNodes[2]);
408  mrrg.link(mrrgNodes[2], mrrgNodes[3]);
409  mrrg.link(mrrgNodes[3], mrrgNodes[4]);
410  mrrg.link(mrrgNodes[4], mrrgNodes[5]);
411  mrrg.link(mrrgNodes[2], mrrgNodes[6]);
412  mrrg.link(mrrgNodes[6], mrrgNodes[7]);
413  mrrg.link(mrrgNodes[7], mrrgNodes[8]);
414  mrrg.link(mrrgNodes[8], mrrgNodes[9]);
415  mrrg.link(mrrgNodes[5], mrrgNodes[9]);
416  mrrg.link(mrrgNodes[9], mrrgNodes[10]);
417  mrrg.link(mrrgNodes[10], mrrgNodes[11]);
418 
419  int mrrgNodeNum = 0;
420  for (auto & val : og.valNodes()) {
421  m.mapMRRGNode(val, mrrgNodes[mrrgNodeNum*3+2]);
422  mrrgNodeNum++;
423  }
424 
425  mrrgNodeNum = 0;
426  for (auto & op : og.opNodes()) {
427  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*3]);
428  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*3+1]);
429  mrrgNodeNum++;
430  }
431 
432  auto cgmr = createMappingGraph(mrrg, m);
433 
434  THEN("checking for balanced graph") {
435  CHECK(latencyCheck(cgmr.mg, mrrg, cgmr.toMRRG).first);
436  }
437  }
438  }
439 
440  GIVEN("a graph with a loop") {
441  auto og = makeDFG_2NodeLoop4Node();
442  MRRG mrrg(2);
443  std::vector<MRRG::NodeDescriptor> mrrgNodes;
444  Mapping m(nullptr, 2, nullptr);
445  Module mod("1", "");
446  WHEN("graph has unbalanced latencies") {
447  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_in", 0)).first);
448  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "a", 0, {})).first);
449  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_out", 0)).first);
450  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "l_in", 0)).first);
451  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "l", 1, {})).first);
452  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "l_out", 0)).first);
453  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "m_in", 0)).first);
454  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod,32, 0, "m", 0, {})).first);
455  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "m_out", 0)).first);
456  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "d_in", 0)).first);
457  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "d", 0, {})).first);
458  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "d_out", 0)).first);
459 
460  mrrg.link(mrrgNodes[0], mrrgNodes[1]);
461  mrrg.link(mrrgNodes[1], mrrgNodes[2]);
462  mrrg.link(mrrgNodes[2], mrrgNodes[3]);
463  mrrg.link(mrrgNodes[3], mrrgNodes[4]);
464  mrrg.link(mrrgNodes[4], mrrgNodes[5]);
465  mrrg.link(mrrgNodes[5], mrrgNodes[6]);
466  mrrg.link(mrrgNodes[6], mrrgNodes[7]);
467  mrrg.link(mrrgNodes[7], mrrgNodes[8]);
468  mrrg.link(mrrgNodes[8], mrrgNodes[9]);
469  mrrg.link(mrrgNodes[9], mrrgNodes[10]);
470  mrrg.link(mrrgNodes[10], mrrgNodes[11]);
471  // Loop
472  mrrg.link(mrrgNodes[8], mrrgNodes[3]);
473 
474 
475  int mrrgNodeNum = 0;
476  for (auto & val : og.valNodes()) {
477  m.mapMRRGNode(val, mrrgNodes[mrrgNodeNum*3+2]);
478  mrrgNodeNum++;
479  }
480 
481  mrrgNodeNum = 0;
482  for (auto & op : og.opNodes()) {
483  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*3]);
484  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*3+1]);
485  mrrgNodeNum++;
486  }
487 
488  auto cgmr = createMappingGraph(mrrg, m);
489 
490 
491  THEN("checking for unbalanced graph") {
492  CHECK(!latencyCheck(cgmr.mg, mrrg, cgmr.toMRRG).first);
493  }
494  }
495 
496  WHEN("graph has balanced latencies") {
497  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_in", 0)).first);
498  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "a", 0, {})).first);
499  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_out", 0)).first);
500  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "l_in", 0)).first);
501  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "l", 0, {})).first);
502  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "l_out", 0)).first);
503  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "m_in", 0)).first);
504  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod,32, 0, "m", 2, {})).first); // Latency
505  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "m_out", 0)).first); // Latency
506  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "d_in", 0)).first);
507  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "d", 0, {})).first);
508  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "d_out", 0)).first);
509 
510  mrrg.link(mrrgNodes[0], mrrgNodes[1]);
511  mrrg.link(mrrgNodes[1], mrrgNodes[2]);
512  mrrg.link(mrrgNodes[2], mrrgNodes[3]);
513  mrrg.link(mrrgNodes[3], mrrgNodes[4]);
514  mrrg.link(mrrgNodes[4], mrrgNodes[5]);
515  mrrg.link(mrrgNodes[5], mrrgNodes[6]);
516  mrrg.link(mrrgNodes[6], mrrgNodes[7]);
517  mrrg.link(mrrgNodes[7], mrrgNodes[8]);
518  mrrg.link(mrrgNodes[8], mrrgNodes[9]);
519  mrrg.link(mrrgNodes[9], mrrgNodes[10]);
520  mrrg.link(mrrgNodes[10], mrrgNodes[11]);
521  // Loop
522  mrrg.link(mrrgNodes[8], mrrgNodes[3]);
523 
524 
525  int mrrgNodeNum = 0;
526  for (auto & val : og.valNodes()) {
527  m.mapMRRGNode(val, mrrgNodes[mrrgNodeNum*3+2]);
528  mrrgNodeNum++;
529  }
530 
531  mrrgNodeNum = 0;
532  for (auto & op : og.opNodes()) {
533  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*3]);
534  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*3+1]);
535  mrrgNodeNum++;
536  }
537 
538  auto cgmr = createMappingGraph(mrrg, m);
539 
540  THEN("checking for balanced graph") {
541  CHECK(latencyCheck(cgmr.mg, mrrg, cgmr.toMRRG).first);
542  }
543  }
544  }
545 }
546 
547 SCENARIO("Complex Latency Tests") {
548  GIVEN ("graph with a loop that contains a diamond") {
549  // std::cout << "\ngraph with a loop that contains a diamond\n";
555  OpGraph opgraph;
556  const auto op_a = opgraph.insert( OpGraphOp("op_a", 32, OpCode::ADD));
557  const auto op_l = opgraph.insert(op_a, OpGraphOp("op_l", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
558  const auto op_m = opgraph.insert(op_l, OpGraphOp("op_m", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
559  const auto op_n = opgraph.insert(op_m, OpGraphOp("op_n", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
560  const auto op_o = opgraph.insert(op_m, OpGraphOp("op_o", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
561  const auto op_d = opgraph.insert(op_m, OpGraphOp("op_d", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
562  (void)op_d;
563 
564  opgraph.link(op_o, op_l, Operands::BINARY_ANY);
565  opgraph.link(op_n, op_l, Operands::BINARY_ANY);
566 
567  OpGraph og = finalFixup(std::move(opgraph));
568 
569  MRRG mrrg(2);
570  std::vector<MRRG::NodeDescriptor> mrrgNodes;
571  Mapping m(nullptr, 2, nullptr);
572  Module mod("1", "");
573 
574  WHEN("graph has unbalanced latencies") {
575  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod,32, 0, "a", 0, {})).first);
576  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_out", 0)).first);
577  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "l", 0, {})).first);
578  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "l_out", 0)).first);
579  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "m", 1, {})).first); // Latency
580  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "m_out", 1)).first); // Latency
581  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "n", 2, {})).first);
582  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "n_out", 0)).first);
583  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "o", 2, {})).first); // Latency
584  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "o_out", 0)).first);
585  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "d", 0, {})).first);
586  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "d_out", 0)).first);
587 
588  mrrg.link(mrrgNodes[0], mrrgNodes[1]);
589  mrrg.link(mrrgNodes[1], mrrgNodes[2]);
590  mrrg.link(mrrgNodes[2], mrrgNodes[3]);
591  mrrg.link(mrrgNodes[3], mrrgNodes[4]);
592  mrrg.link(mrrgNodes[4], mrrgNodes[5]);
593  mrrg.link(mrrgNodes[5], mrrgNodes[6]);
594  mrrg.link(mrrgNodes[6], mrrgNodes[7]);
595  mrrg.link(mrrgNodes[5], mrrgNodes[8]);
596  mrrg.link(mrrgNodes[8], mrrgNodes[9]);
597  mrrg.link(mrrgNodes[5], mrrgNodes[10]);
598  mrrg.link(mrrgNodes[9], mrrgNodes[2]);
599  mrrg.link(mrrgNodes[7], mrrgNodes[2]);
600 
601  int mrrgNodeNum = 0;
602  for (auto & val : og.valNodes()) {
603  m.mapMRRGNode(val, mrrgNodes[mrrgNodeNum*2+1]);
604  mrrgNodeNum++;
605  }
606 
607  mrrgNodeNum = 0;
608  for (auto & op : og.opNodes()) {
609  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*2]);
610  mrrgNodeNum++;
611  }
612 
613  auto cgmr = createMappingGraph(mrrg, m);
614 
615  THEN("checking for unbalanced graph") {
616  // std::cout << "\nunbalanced graph\n";
617  CHECK(!latencyCheck(cgmr.mg, mrrg, cgmr.toMRRG).first);
618  }
619  }
620 
621  WHEN("graph has balanced latencies") {
622  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "a", 0, {})).first);
623  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_out", 0)).first);
624  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "l", 0, {})).first);
625  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "l_out", 0)).first);
626  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "m", 1, {})).first); // Latency
627  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "m_out", 0)).first);
628  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "n", 1, {})).first); // Latency
629  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "n_out", 0)).first);
630  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "o", 1, {})).first); // Latency
631  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "o_out", 0)).first);
632  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "d", 0, {})).first);
633  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "d_out", 0)).first);
634 
635  mrrg.link(mrrgNodes[0], mrrgNodes[1]);
636  mrrg.link(mrrgNodes[1], mrrgNodes[2]);
637  mrrg.link(mrrgNodes[2], mrrgNodes[3]);
638  mrrg.link(mrrgNodes[3], mrrgNodes[4]);
639  mrrg.link(mrrgNodes[4], mrrgNodes[5]);
640  mrrg.link(mrrgNodes[5], mrrgNodes[6]);
641  mrrg.link(mrrgNodes[6], mrrgNodes[7]);
642  mrrg.link(mrrgNodes[5], mrrgNodes[8]);
643  mrrg.link(mrrgNodes[8], mrrgNodes[9]);
644  mrrg.link(mrrgNodes[5], mrrgNodes[10]);
645  mrrg.link(mrrgNodes[9], mrrgNodes[2]);
646  mrrg.link(mrrgNodes[7], mrrgNodes[2]);
647 
648  int mrrgNodeNum = 0;
649  for (auto & val : og.valNodes()) {
650  m.mapMRRGNode(val, mrrgNodes[mrrgNodeNum*2+1]);
651  mrrgNodeNum++;
652  }
653 
654  mrrgNodeNum = 0;
655  for (auto & op : og.opNodes()) {
656  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*2]);
657  mrrgNodeNum++;
658  }
659 
660  auto cgmr = createMappingGraph(mrrg, m);
661  // std::cout << "Graph with a loop that contains a diamond\n";
662 
663  THEN("checking for balanced graph") {
664  // std::cout << "\nbalanced graph\n";
665  CHECK(latencyCheck(cgmr.mg, mrrg, cgmr.toMRRG).first);
666  }
667  }
668  }
669  GIVEN ("a graph with a diamond that contains a loop") {
670  // std::cout << "\na graph with a diamond that contains a loop\n";
678  OpGraph opgraph;
679  const auto op_a = opgraph.insert( OpGraphOp("op_a", 32, OpCode::ADD));
680  const auto op_b = opgraph.insert(op_a, OpGraphOp("op_b", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
681  const auto op_b2 = opgraph.insert(op_a, OpGraphOp("op_b2", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
682  const auto op_c = opgraph.insert(op_b2, OpGraphOp("op_c", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
683  const auto op_d = opgraph.insert(op_b, OpGraphOp("op_d", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
684 
685  opgraph.link(op_b, op_c, Operands::BINARY_ANY);
686  opgraph.link(op_d, op_b, Operands::BINARY_ANY); // Loop
687  OpGraph og = finalFixup(std::move(opgraph));
688 
689  MRRG mrrg(2);
690  std::vector<MRRG::NodeDescriptor> mrrgNodes;
691  Mapping m(nullptr, 2, nullptr);
692  Module mod("1", "");
693 
694  WHEN("graph has unbalanced latencies") {
695  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "a", 0, {})).first);
696  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_out", 0)).first);
697  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "b", 0, {})).first);
698  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b2_out", 2)).first);
699  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "b2", 0, {})).first);
700  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b_out", 2)).first);
701  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "c", 0, {})).first);
702  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "d_out", 0)).first); // Has latency
703  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "d", 1, {})).first); // Has latency
704 
705  mrrg.link(mrrgNodes[0], mrrgNodes[1]);
706  mrrg.link(mrrgNodes[1], mrrgNodes[2]);
707  mrrg.link(mrrgNodes[2], mrrgNodes[5]);
708  mrrg.link(mrrgNodes[1], mrrgNodes[4]);
709  mrrg.link(mrrgNodes[4], mrrgNodes[3]);
710  mrrg.link(mrrgNodes[3], mrrgNodes[6]);
711  mrrg.link(mrrgNodes[5], mrrgNodes[6]);
712  mrrg.link(mrrgNodes[5], mrrgNodes[8]);
713  mrrg.link(mrrgNodes[8], mrrgNodes[7]);
714  mrrg.link(mrrgNodes[7], mrrgNodes[2]);
715 
716  int mrrgNodeNum = 0;
717  for (auto & val : og.valNodes()) {
718  m.mapMRRGNode(val, mrrgNodes[mrrgNodeNum*2+1]);
719  mrrgNodeNum++;
720  }
721 
722  mrrgNodeNum = 0;
723  for (auto & op : og.opNodes()) {
724  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*2]);
725  mrrgNodeNum++;
726  }
727 
728  auto cgmr = createMappingGraph(mrrg, m);
729 
730  THEN("checking for unbalanced graph") {
731  // std::cout << "\nunbalanced graph\n";
732  CHECK(!latencyCheck(cgmr.mg, mrrg, cgmr.toMRRG).first);
733  }
734  }
735 
744  WHEN("graph has balanced latencies") {
745  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "a", 0, {})).first);
746  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_out", 0)).first);
747  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "b", 0, {})).first);
748  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b2_out", 0)).first);
749  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "b2", 0, {})).first);
750  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b_out", 0)).first);
751  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "c", 0, {})).first);
752  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "d_out", 1)).first); // Has latency
753  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "d", 1, {})).first); // Has latency
754 
755  mrrg.link(mrrgNodes[0], mrrgNodes[1]);
756  mrrg.link(mrrgNodes[1], mrrgNodes[2]);
757  mrrg.link(mrrgNodes[2], mrrgNodes[5]);
758  mrrg.link(mrrgNodes[1], mrrgNodes[4]);
759  mrrg.link(mrrgNodes[4], mrrgNodes[3]);
760  mrrg.link(mrrgNodes[3], mrrgNodes[6]);
761  mrrg.link(mrrgNodes[5], mrrgNodes[6]);
762  mrrg.link(mrrgNodes[5], mrrgNodes[8]);
763  mrrg.link(mrrgNodes[8], mrrgNodes[7]);
764  mrrg.link(mrrgNodes[7], mrrgNodes[2]);
765 
766  int mrrgNodeNum = 0;
767  for (auto & val : og.valNodes()) {
768  m.mapMRRGNode(val, mrrgNodes[mrrgNodeNum*2+1]);
769  mrrgNodeNum++;
770  }
771 
772  mrrgNodeNum = 0;
773  for (auto & op : og.opNodes()) {
774  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*2]);
775  mrrgNodeNum++;
776  }
777 
778  auto cgmr = createMappingGraph(mrrg, m);
779  // std::cout << "Graph with a diamond that contains a loop\n";
780 
781  THEN("checking for balanced graph") {
782  // std::cout << "\nunbalanced graph\n";
783  CHECK(latencyCheck(cgmr.mg, mrrg, cgmr.toMRRG).first);
784  }
785  }
786  }
787 
788  GIVEN("A cyclical graph containing a 0-latency graph") {
794  OpGraph opgraph;
795  const auto op_a = opgraph.insert( OpGraphOp("op_a", 32, OpCode::ADD));
796  const auto op_b = opgraph.insert(op_a, OpGraphOp("op_b", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
797  const auto op_c = opgraph.insert(op_b, OpGraphOp("op_c", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
798  const auto op_d = opgraph.insert(op_c, OpGraphOp("op_d", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
799  const auto op_e = opgraph.insert(op_d, OpGraphOp("op_e", 32, OpCode::ADD), Operands::BINARY_ANY).newOp;
800 
801  opgraph.link(op_e, op_a, Operands::BINARY_ANY);
802  opgraph.link(op_d, op_b, Operands::BINARY_ANY);
803 
804  OpGraph og = finalFixup(std::move(opgraph));
805  MRRG mrrg(2);
806  std::vector<MRRG::NodeDescriptor> mrrgNodes;
807  Mapping m(nullptr, 2, nullptr);
808  Module mod("1", "");
809 
810  WHEN("graph has unbalanced latencies") {
811  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "a", 0, {})).first);
812  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "a_out", 0)).first);
813  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "b", 0, {})).first);
814  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "b_out", 0)).first);
815  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "c", 0, {})).first);
816  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "c_out", 0)).first);
817  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "d", 0, {})).first);
818  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "d_out", 0)).first);
819  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_function(&mod, 32, 0, "e", 0, {})).first);
820  mrrgNodes.push_back(mrrg.insert(MRRGNode::make_routing(&mod, 32, 0, "e_out", 0)).first);
821 
822  mrrg.link(mrrgNodes[0], mrrgNodes[1]);
823  mrrg.link(mrrgNodes[1], mrrgNodes[2]);
824  mrrg.link(mrrgNodes[2], mrrgNodes[3]);
825  mrrg.link(mrrgNodes[3], mrrgNodes[4]);
826  mrrg.link(mrrgNodes[4], mrrgNodes[5]);
827  mrrg.link(mrrgNodes[5], mrrgNodes[6]);
828  mrrg.link(mrrgNodes[6], mrrgNodes[7]);
829  mrrg.link(mrrgNodes[7], mrrgNodes[8]);
830  mrrg.link(mrrgNodes[8], mrrgNodes[9]);
831  mrrg.link(mrrgNodes[9], mrrgNodes[0]);
832  mrrg.link(mrrgNodes[7], mrrgNodes[2]);
833 
834  int mrrgNodeNum = 0;
835  for (auto & op : og.opNodes()) {
836  m.mapMRRGNode(op, mrrgNodes[mrrgNodeNum*2]);
837  mrrgNodeNum++;
838  }
839 
840  mrrgNodeNum = 0;
841  for (auto & val : og.valNodes()) {
842  m.mapMRRGNode(val, mrrgNodes[mrrgNodeNum*2+1]);
843  mrrgNodeNum++;
844  }
845 
846  auto cgmr = createMappingGraph(mrrg, m);
847 
848  THEN("checking for unbalanced graph") {
849  CHECK(!latencyCheck(cgmr.mg, mrrg, cgmr.toMRRG).first);
850  }
851  }
852  }
853 }
854 
855 namespace {
856 
857 struct LatencyBalanceTest {
858  bool expcted_latency_balance_result;
859  std::string mapping_description;
860  std::string mrrg_description;
861  std::string opgraph_description;
862 
863  using MGGenRetVal = std::pair<MappingGraph,MappingGraph::ToMRRGVertexMap>;
864  std::function<MGGenRetVal(const MRRG&,const OpGraph&)> mapping_graph_generator;
865  std::function<MRRG()> mrrg_generator;
866  std::function<OpGraph()> opgraph_generator;
867 };
868 
869 struct MGSimpleArchBuilder {
870  const MRRG* mrrg;
871  const OpGraph* opgraph;
872  MappingGraph mg = {};
873  MappingGraph::ToMRRGVertexMap toMRRG = {};
874 
875  struct MapOpResult { MappingGraph::NodeDescriptor fu; XY pos; std::string name; };
876  MapOpResult map_op(const std::string& op_name, XY pos) {
877  const auto fu = mg.insert({opgraph->getOp(op_name)}).first;
878  toMRRG[fu] = mrrg->getNode(0, xyName("fu",pos));
879  return { fu, pos, std::move(op_name) };
880  };
881 
882  auto link_ops(const MapOpResult& src, const MapOpResult& sink, int dest_in) {
883  const auto out = mg.insert(src.fu, {opgraph->getVal(src.name + "_out")}).first;
884  const auto inter = mg.insert(out, {opgraph->getVal(src.name + "_out")}).first;
885  const auto in = mg.insert(inter, {opgraph->getVal(src.name + "_out")}).first;
886  mg.link(in, sink.fu);
887  toMRRG[out] = mrrg->getNode(0, xyName("fu_out", src.pos));
888  toMRRG[inter] = mrrg->getNode(0, xyName("fu_out", src.pos) + "-to-" + xyidName("pe_in", sink.pos, dest_in));
889  toMRRG[in] = mrrg->getNode(0, xyidName("pe_in", sink.pos, dest_in));
890  struct Result { MappingGraph::NodeDescriptor out, inter, in; };
891  return Result { out, inter, in };
892  };
893 
894  LatencyBalanceTest::MGGenRetVal consume() && {
895  return {std::move(mg), std::move(toMRRG)};
896  }
897 };
898 
899 LatencyBalanceTest::MGGenRetVal makeMG_loop_around_fu_00(const MRRG& mrrg, const OpGraph& og) {
900  auto builder = MGSimpleArchBuilder{&mrrg, &og};
901  const auto op_l = builder.map_op("op_l", {0,0});
902  builder.link_ops(op_l, op_l, 0);
903  return std::move(builder).consume();
904 }
905 
906 LatencyBalanceTest::MGGenRetVal makeMG_reconvergence_121_00_to_11(const MRRG& mrrg, const OpGraph& og) {
907  auto builder = MGSimpleArchBuilder{&mrrg, &og};
908  const auto op_a = builder.map_op("op_a", {0,0});
909  const auto op_b = builder.map_op("op_b", {0,1});
910  const auto op_b2 = builder.map_op("op_b2", {1,0});
911  const auto op_c = builder.map_op("op_c", {1,1});
912  builder.link_ops(op_a, op_b, 0);
913  builder.link_ops(op_a, op_b2, 0);
914  builder.link_ops(op_b, op_c, 0);
915  builder.link_ops(op_b2, op_c, 0);
916  return std::move(builder).consume();
917 }
918 
919 } // end anon namespace
920 
921 TEST_CASE("Latency Balancing -- small graphs") {
922  const auto test = GENERATE(values<LatencyBalanceTest>({
923  { false, "latency=0 cycle", "1x1t1 ortho with self-feedback, but no FU latency", "1 node self-loop",
924  makeMG_loop_around_fu_00,
925  []{ return makeMRRG_Simple(1, {{"width","1"},{"height","1"}}); },
926  []{ return makeDFG_SelfLoop1Node(); },
927  },
928  { true, "latency=1 cycle", "1x1t1 ortho with self-feedback, FU latency=1", "1 node self-loop",
929  makeMG_loop_around_fu_00,
930  []{ return makeMRRG_Simple(1, {{"width","1"},{"height","1"},{"fu_latency","1"}}); },
931  []{ return makeDFG_SelfLoop1Node(); },
932  },
933  { false, "unbalanced re-convergence", "2x2t1 flow ortho with self-feedback and FU latency of 1 except for FU 01", "Converging 121",
934  makeMG_reconvergence_121_00_to_11,
935  []{return makeMRRG_SimpleFlow(1, {{"width","2"},{"height","2"},{"fu_latency","1"},{xyName("fu_latency",{0,1}),"0"}});},
936  []{return makeDFG_Converging121();},
937  },
938  { true, "balanced re-convergence", "2x2t1 flow ortho with self-feedback and FU latency of 1", "Converging 121",
939  makeMG_reconvergence_121_00_to_11,
940  []{return makeMRRG_SimpleFlow(1, {{"width","2"},{"height","2"},{"fu_latency","1"}});},
941  []{return makeDFG_Converging121();},
942  },
943  }));
944 
945  GIVEN("A '" << test.mrrg_description << "' MRRG") {
946  const auto mrrg = test.mrrg_generator();
947  GIVEN("A '" << test.opgraph_description << "' DFG") {
948  const auto opgraph = test.opgraph_generator();
949  GIVEN("A '" << test.mapping_description << "' mapping graph") {
950  const auto mg_and_tomrrg = test.mapping_graph_generator(mrrg, opgraph);
951  THEN("The latency check should " << (test.expcted_latency_balance_result ? "pass" : "fail")) {
952  const auto latency_check_result = latencyCheck(mg_and_tomrrg.first, mrrg, mg_and_tomrrg.second);
953  CHECKED_ELSE(latency_check_result.first == test.expcted_latency_balance_result) {
954  std::cout << "Test Failed. Dumping inputs...";
955  std::cout << "\nMRRG:\n"; mrrg.printDot(std::cout);
956  std::cout << "\nOpGraph:\n"; opgraph.print_dot(std::cout);
957  std::cout << "\nMappingGraph:\n"; mg_and_tomrrg.first.printDot(std::cout, mrrg, opgraph, mg_and_tomrrg.second, ConfigStore());
958  };
959  }
960  }
961  }
962  }
963 }
964 
965 namespace {
966 
967 MRRG makeMRRG_Simple(int II, ConfigStore options) {
968  add_all(options, {
969  // {"width", "?"}, // must specify
970  // {"height", "?"}, // must specify
971  {"fu_self_feedback", "yes"},
972  {"ortho_connections","yes"}, // allow N,S,E,W
973  {"diag_connections","no"}, // allow NE, SE, SW, NW
974  {"flow_conections_only", "no"}, // disallow N, W, NE, NW, SW
975  {"fu_latency", "0"}, // default latency
976  // {xyName("fu_latency",{x,y}), "?"} // override the default
977  {"fu_arity", "2"}, // num FU inputs
978  });
979  const auto inter_cluster_offsets = [&](){
980  auto result = std::vector<XY>{};
981  if (options.getBool("ortho_connections")) {
982  if (not options.getBool("flow_conections_only")) {
983  result.emplace_back(-1, 0);
984  result.emplace_back( 0,-1);
985  }
986  result.emplace_back( 1, 0);
987  result.emplace_back( 0, 1);
988  }
989 
990  if (options.getBool("diag_connections")) {
991  if (not options.getBool("flow_conections_only")) {
992  result.emplace_back(-1,-1);
993  result.emplace_back(-1, 1);
994  result.emplace_back( 1,-1);
995  }
996  result.emplace_back( 1, 1);
997  }
998 
999  if (options.getBool("fu_self_feedback")) {
1000  result.emplace_back( 0, 0);
1001  }
1002 
1003  return result;
1004  }();
1005 
1006  const auto wrap_logic = [&](XY local_xy, XY offset) -> XY {
1007  return {
1008  local_xy.first + offset.first,
1009  local_xy.second + offset.second,
1010  };
1011  };
1012 
1013  auto mrrg = MRRG{II};
1014 
1015  struct PEData {
1016  MRRG::NodeDescriptor fu;
1017  MRRG::NodeDescriptor output;
1018  std::vector<MRRG::NodeDescriptor> inputs;
1019  };
1020 
1021  std::map<int, std::map<XY,PEData>> pe_data;
1022 
1023  // make PEs
1024  for (int ii = 0; ii < II; ++ii) {
1025  for (int x = 0; x < options.getInt("width"); ++x) {
1026  for (int y = 0; y < options.getInt("height"); ++y) {
1027  const auto xy = XY{x,y};
1028  const auto fu_name = xyName("fu", xy);
1029  const auto fu_latency = options.getIntOr(xyName("fu_latency",xy), options.getInt("fu_latency"));
1030  auto& pe = pe_data[ii].insert({ xy, {
1031  mrrg.insert(MRRGNode::make_function(&god_module, 32, ii,
1032  fu_name,
1033  fu_latency,
1034  { OpCode::ADD }
1035  )).first,
1036  mrrg.insert(
1037  MRRGNode::make_routing(&god_module, 32, (ii + fu_latency) % II, xyName("fu_out", xy)
1038  )).first,
1039  {}
1040  }}).first->second;
1041  mrrg.link(pe.fu, pe.output);
1042 
1043  for (int i = 0; i < options.getInt("fu_arity"); ++i) {
1044  pe.inputs.push_back(mrrg.insert(MRRGNode::make_routing(&god_module, 32, ii,
1045  xyidName("pe_in", xy, i)
1046  )).first);
1047  mrrg.link(pe.inputs.back(), pe.fu);
1048  }
1049  }
1050  }
1051  }
1052 
1053  // connect PEs together
1054  for (int ii = 0; ii < II; ++ii) {
1055  for (int x = 0; x < options.getInt("width"); ++x) {
1056  for (int y = 0; y < options.getInt("height"); ++y) {
1057  const auto xy = XY{x,y};
1058  const auto& pe = pe_data.at(ii).at(xy);
1059  for (const auto offset : inter_cluster_offsets) {
1060  const auto remote_xy = wrap_logic(xy, offset);
1061  const auto find_results = pe_data.at(ii).find(remote_xy);
1062  if (find_results == pe_data.at(ii).end()) { continue; }
1063  for (const auto& remote_input : find_results->second.inputs) {
1064  // intermediate node is to satisfy mux-ex invariant.
1065  // remove it when it is added automatically.
1066  const auto intermediate = mrrg.insert(MRRGNode::make_routing(&god_module, 32, ii,
1067  mrrg.getNodeRef(pe.output).getHierarchyQualifiedName()
1068  + "-to-" + mrrg.getNodeRef(remote_input).getHierarchyQualifiedName()
1069  )).first;
1070  mrrg.link(pe.output, intermediate);
1071  mrrg.link(intermediate, remote_input);
1072  }
1073  }
1074  }
1075  }
1076  }
1077 
1078  verifyAndPrintReport(mrrg, std::cout, true, true);
1079  return mrrg;
1080 }
1081 
1082 MRRG makeMRRG_SimpleFlow(int II, ConfigStore options) {
1083  add_all(options, {
1084  {"flow_conections_only", "yes"}
1085  });
1086  return makeMRRG_Simple(II, options);
1087 }
1088 
1089 } // end anon namespace
removeIsolatedRoutingNodes
MappingGraph removeIsolatedRoutingNodes(const MappingGraph &mapping, const MRRG &mrrg, const MappingGraph::ToMRRGVertexMap &toMRRG)
Definition: Mapping.cpp:504
MRRG::link
void link(MRRG::NodeDescriptor driver, MRRG::NodeDescriptor fanout)
Definition: MRRG.cpp:849
makeDFG_SelfLoop1Node
OpGraph makeDFG_SelfLoop1Node()
Definition: OpGraphsForTesting.cpp:60
verifyAndPrintReport
bool verifyAndPrintReport(const MRRG &mrrg, std::ostream &os, bool silent_on_no_errors, bool throw_if_errors, const ConfigStore &extra_opts)
Definition: MRRG.cpp:473
MRRG
Definition: MRRG.h:216
xyidName
std::string xyidName(const std::string &prefix, XY xy, int id)
Definition: UserArchs.h:190
Module.h
makeDFG_Converging121
OpGraph makeDFG_Converging121()
Definition: OpGraphsForTesting.cpp:151
OpGraph::getOp
OpDescriptor getOp(const std::string &name) const
Definition: OpGraph.h:386
SCENARIO
SCENARIO("Mapping Graph Tests")
Definition: MappingGraphTests.cpp:31
OpGraph::valNodes
auto & valNodes() const
Definition: OpGraph.h:314
UserArchs.h
ConfigStore
Definition: ConfigStore.h:76
OpCode::ADD
@ ADD
OpGraph::print_dot
void print_dot(std::ostream &s) const
Definition: OpGraph.cpp:1040
latencyCheck
std::pair< bool, MappingGraphCycleAssignment > latencyCheck(const MappingGraph &mapping, const MRRG &mrrg, const CreateMappingGraphResult::ToMRRG &toMRRG)
Definition: Mapping.cpp:582
MappingGraph
Definition: Mapping.h:129
to_string
const std::string & to_string(const OpGraphOpCode &opcode)
Definition: OpGraph.cpp:111
Mapping::mapMRRGNode
void mapMRRGNode(OpGraph::NodeDescriptor, MRRG::NodeDescriptor node)
Definition: Mapping.cpp:58
MRRG::printDot
void printDot(std::ostream &os, Module *, const ConfigStore &archAttrs) const
Definition: MRRG.cpp:151
MRRG::insert
std::pair< NodeDescriptor, bool > insert(MRRGNode node)
Definition: MRRG.cpp:91
MappingGraphNode
Definition: Mapping.h:125
makeDFG_SelfLoop3Node
OpGraph makeDFG_SelfLoop3Node()
Definition: OpGraphsForTesting.cpp:80
Mapping
Definition: Mapping.h:31
MappingGraph::NodeDescriptor
Definition: Mapping.h:131
add_all
ConfigStore & add_all(ConfigStore &into, const ConfigStore &from)
Add (or set) all keys from from in into.
Definition: ConfigStore.h:251
MRRG::getNodeRef
MRRGNode & getNodeRef(NodeDescriptor ndesc)
Definition: MRRG.h:273
OpGraph::link
ValDescriptor link(OpDescriptor driver, OpDescriptor fanout, std::string operand_group, int bitwidth=32, int dist=0, EdgeKind kind=EdgeKind::kDataFlow, bool predicate=false)
Definition: OpGraph.cpp:364
OpGraph::opNodes
auto & opNodes() const
Definition: OpGraph.h:313
MRRGNode::make_function
static MRRGNode make_function(Module *parent, int bitwidth, int cycle, STR &&name, int latency, SupportedOps supported_ops, int max_cap=1, bool is_const_unit=false)
Definition: MRRG.h:191
OpGraphsForTesting.hpp
Module
Definition: Module.h:163
OpGraphNode
Definition: OpGraph.h:113
finalFixup
OpGraph finalFixup(OpGraph opgraph)
Definition: OpGraphsForTesting.cpp:5
TEST_CASE
TEST_CASE("Latency Balancing -- small graphs")
Definition: MappingGraphTests.cpp:921
MappingGraph::ToMRRGVertexMap
std::unordered_map< NodeDescriptor, MRRG::NodeDescriptor, NodeDescriptorHash > ToMRRGVertexMap
Definition: Mapping.h:146
MRRGNode::getHierarchyQualifiedName
const std::string & getHierarchyQualifiedName() const
Definition: MRRG.h:122
ConfigStore::getIntOr
long long getIntOr(const std::string &key, long long otherwise) const
Definition: ConfigStore.h:191
xyName
std::string xyName(const std::string &prefix, XY xy)
Definition: UserArchs.h:184
OpGraphOp
Definition: OpGraph.h:131
MRRGNode
Definition: MRRG.h:60
makeDFG_2NodeLoop4Node
OpGraph makeDFG_2NodeLoop4Node()
Definition: OpGraphsForTesting.cpp:115
MRRG::getNode
NodeDescriptor getNode(int cycle, const std::string &name) const
Definition: MRRG.cpp:142
Mapping.h
MappingGraph::link
void link(MappingGraph::NodeDescriptor driver, MappingGraph::NodeDescriptor fanout)
Definition: Mapping.cpp:317
OpGraph::insert
OpDescriptor insert(OpGraphOp op)
Definition: OpGraph.cpp:338
MappingGraph::insert
std::pair< NodeDescriptor, bool > insert(MappingGraphNode node)
Definition: Mapping.cpp:303
OpGraph::getVal
ValDescriptor getVal(const std::string &name) const
Definition: OpGraph.h:387
MRRGNode::make_routing
static MRRGNode make_routing(Module *parent, int bitwidth, int cycle, STR &&name, int latency=0, int max_cap=1)
Definition: MRRG.h:151
Operands::BINARY_ANY
static constexpr auto & BINARY_ANY
Definition: OpGraph.h:91
createMappingGraph
CreateMappingGraphResult createMappingGraph(const MRRG &mrrg, const Mapping &m)
Definition: Mapping.cpp:468
ConfigStore::getInt
long long getInt(const std::string &key) const
Definition: ConfigStore.h:146
OpGraph
Definition: OpGraph.h:215
makeDFG_Large
OpGraph makeDFG_Large(bool require_non_NN_FUs)
Definition: OpGraphsForTesting.cpp:288
XY
Definition: UserArchs.h:178
ConfigStore::getBool
bool getBool(const std::string &key) const
Definition: ConfigStore.h:166
Generated on Fri Nov 17 2023 12:26:44 for CGRA-ME by   doxygen 1.8.17