CGRA-ME
HeuristicMappers_tests.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/dotparse.h>
12 #include <CGRA/HeuristicMappers.h>
13 #include <CGRA/MRRGProcedures.h>
14 #include <CGRA/OpGraphProcedures.h>
15 #include <CGRA/user-inc/UserArchs.h>
16 #include <CGRA/utility/CodeProfiling.h>
17 #include <CGRA/Visual.h>
18 
19 #include "testutils/OpGraphsForTesting.hpp"
20 
21 #include <chrono>
22 #include <cstdlib>
23 #include <fstream>
24 #include <numeric>
25 
26 #include <catch2/catch.hpp>
27 
28 namespace {
29 
30 Module god_module("god",""); // used by MRRGs in this file
31 
32 auto makeCGRA_otho(int w, int h, ConfigStore options = {}) {
33  return UserArchs().getGenerator("simple-ortho")(add_all(options, ConfigStore{{
34  {"rows", std::to_string(w)},
35  {"cols", std::to_string(h)},
36  {"homogeneous_fu", "1"},
37  {"fu_latency", "0"},
38  {"fu_II", "1"},
39  }}));
40 }
41 
42 std::unique_ptr<CGRA> makeCGRA_diag(int w, int h, ConfigStore options = {}) {
43  return UserArchs().getGenerator("simple-diag")(add_all(options, ConfigStore{{
44  {"rows", std::to_string(w)},
45  {"cols", std::to_string(h)},
46  {"homogeneous_fu", "1"},
47  {"fu_latency", "0"},
48  {"fu_II", "1"},
49  }}));
50 }
51 
52 std::unique_ptr<CGRA> makeCGRA_hycube(int w, int h, ConfigStore options = {}) {
53  return UserArchs().getGenerator("hycube")(add_all(options, ConfigStore{{
54  {"rows", std::to_string(w)},
55  {"cols", std::to_string(h)},
56  {"pred", "0"},
57  {"fu_II", "1"},
58  {"fu_latency", "0"},
59  {"pe_conn", "15"},
60  {"num_const_addresses", "1"}, // need this for AES at the moment
61  }}));
62 }
63 
64 std::unique_ptr<CGRA> makeCGRA_clustered(int w, int h, ConfigStore options = {}) {
65  return UserArchs().getGenerator("clustered")(add_all(options, ConfigStore{{
66  {"rows", std::to_string(w)},
67  {"cols", std::to_string(h)},
68  // {"pe0_fu_II", "1"},
69  // {"pe0_fu_latency", "1"},
70  {"num_const_addresses", "1"}, // need this for AES at the moment
71  }}));
72 }
73 
74 std::unique_ptr<CGRA> makeCGRA_adres(int w, int h, ConfigStore options = {}) {
75  return UserArchs().getGenerator("adres")(add_all(options, ConfigStore{{
76  {"rows", std::to_string(w)},
77  {"cols", std::to_string(h)},
78  {"num_const_addresses", "1"}, // need this for AES at the moment
79  }}));
80 }
81 
82 std::unordered_map<std::string, std::function<std::unique_ptr<CGRA>(int,int,ConfigStore)>> cgra_makers {
83  { "makeCGRA_otho", makeCGRA_otho },
84  { "makeCGRA_diag", makeCGRA_diag },
85  { "makeCGRA_hycube", makeCGRA_hycube },
86  { "makeCGRA_clustered", makeCGRA_clustered },
87  { "makeCGRA_adres", makeCGRA_adres },
88 };
89 
90 MRRG makeMRRG_112221DAG(int II, int latency_of_a, int latency_of_c) {
91  const int cycle_after_a = (0 + latency_of_a) % II;
92  const int cycle_after_c = (cycle_after_a + latency_of_c) % II;
93  MRRG mrrg(II);
94  const auto a = mrrg.insert( MRRGNode::make_function(&god_module, 32, 0, "a", latency_of_a, {OpCode::ADD})).first;
95  const auto b = mrrg.insert(a, MRRGNode::make_routing(&god_module, 32, cycle_after_a, "b", 0 )).first;
96  const auto c1 = mrrg.insert(b, MRRGNode::make_routing(&god_module, 32, cycle_after_a, "c1", latency_of_c)).first;
97  const auto c2 = mrrg.insert(b, MRRGNode::make_routing(&god_module, 32, cycle_after_a, "c2", latency_of_c)).first;
98  const auto d1 = mrrg.insert(c1, MRRGNode::make_routing(&god_module, 32, cycle_after_c, "d1", 0 )).first;
99  const auto d2 = mrrg.insert(c2, MRRGNode::make_routing(&god_module, 32, cycle_after_c, "d2", 0 )).first;
100  const auto e1 = mrrg.insert(d1, MRRGNode::make_routing(&god_module, 32, cycle_after_c, "e1", 0 )).first;
101  const auto e2 = mrrg.insert(d2, MRRGNode::make_routing(&god_module, 32, cycle_after_c, "e2", 0 )).first;
102  const auto f = mrrg.insertMultiFanin({e1,e2}, MRRGNode::make_function(&god_module, 32, latency_of_c, "f", 0, {OpCode::ADD})).first;
103  (void)f;
104 
105  verifyAndPrintReport(mrrg, std::cout, true, true);
106  return mrrg;
107 }
108 
109 MRRG makeMRRG_1212DAG(int II, int latency_of_a, int latency_of_b, int extra_trip_counts_on_b2) {
110  const int cycle_after_a = (0 + latency_of_a) % II;
111  const int cycle_after_b = (cycle_after_a + latency_of_b) % II;
112  const auto latency_of_b1 = latency_of_b;
113  const auto latency_of_b2 = latency_of_b + II*extra_trip_counts_on_b2;
114  MRRG mrrg(II);
115  const auto a = mrrg.insert( MRRGNode::make_function(&god_module, 32, 0, "a", latency_of_a, {OpCode::ADD})).first;
116  const auto b1 = mrrg.insert(a, MRRGNode::make_routing (&god_module, 32, cycle_after_a, "b1", latency_of_b1)).first;
117  const auto b2 = mrrg.insert(a, MRRGNode::make_routing (&god_module, 32, cycle_after_a, "b2", latency_of_b2)).first;
118  const auto c = mrrg.insertMultiFanin({b1,b2}, MRRGNode::make_routing(&god_module, 32, cycle_after_b, "c", 0)).first;
119  const auto z1 = mrrg.insert(c, MRRGNode::make_function(&god_module, 32, cycle_after_b, "z1", 0, {OpCode::ADD})).first;
120  const auto z2 = mrrg.insert(c, MRRGNode::make_function(&god_module, 32, cycle_after_b, "z2", 0, {OpCode::ADD})).first;
121  (void)z1;
122  (void)z2;
123 
124  verifyAndPrintReport(mrrg, std::cout, true, true);
125  return mrrg;
126 }
127 
128 MRRG makeMRRG_1112DAG(int II, int latency_of_a, int latency_of_b) {
129  const int cycle_after_a = (0 + latency_of_a) % II;
130  const int cycle_after_b = (cycle_after_a + latency_of_b) % II;
131  MRRG mrrg(II);
132  const auto a = mrrg.insert( MRRGNode::make_function(&god_module, 32, 0, "a", latency_of_a, {OpCode::ADD})).first;
133  const auto b = mrrg.insert(a, MRRGNode::make_routing (&god_module, 32, cycle_after_a, "b", latency_of_b)).first;
134  const auto c = mrrg.insert(b, MRRGNode::make_routing (&god_module, 32, cycle_after_b, "c", 0)).first;
135  const auto z1 = mrrg.insert(c, MRRGNode::make_function(&god_module, 32, cycle_after_b, "z1", 0, {OpCode::ADD})).first;
136  const auto z2 = mrrg.insert(c, MRRGNode::make_function(&god_module, 32, cycle_after_b, "z2", 0, {OpCode::ADD})).first;
137  (void)z1;
138  (void)z2;
139 
140  verifyAndPrintReport(mrrg, std::cout, true, true);
141  return mrrg;
142 }
143 
153 MRRG makeMRRG_Loop3NodeMaybeExtraFU(int II, bool has_extra_fu, int num_shared_nodes, int latency_of_a, int latency_of_b) {
154  const int cycle_after_a = (0 + latency_of_a) % II;
155  const int cycle_after_b = (cycle_after_a + latency_of_b) % II;
156  MRRG mrrg(II);
157  const auto a = mrrg.insert( MRRGNode::make_function(&god_module, 32, 0, "a", latency_of_a, {OpCode::ADD})).first;
158  const auto b = mrrg.insert(a, MRRGNode::make_routing (&god_module, 32, cycle_after_a, "b", latency_of_b)).first;
159  const auto c = mrrg.insert(b, MRRGNode::make_routing (&god_module, 32, cycle_after_b, "c", 0)).first;
160  mrrg.link(c,a);
161 
162  if (has_extra_fu) {
163  const auto fanin = [&,fname=__func__]() { // (immediately invoked)
164  if (num_shared_nodes == 0) { return mrrg.insert(a, MRRGNode::make_routing(&god_module, 32, 0, "b2", 0)).first; }
165  if (num_shared_nodes == 1) { return b; }
166  if (num_shared_nodes == 2) { return c; }
167  throw std::logic_error(fname + (": trying to share too many nodes: " + std::to_string(num_shared_nodes)));
168  }();
169  const auto z = mrrg.insert(fanin, MRRGNode::make_function(&god_module, 32, cycle_after_b, "z", 0, {OpCode::ADD})).first;
170  }
171 
172  verifyAndPrintReport(mrrg, std::cout, true, true);
173  return mrrg;
174 }
175 
176 std::unordered_map<std::string, EdgeCoster> edgeCosters {
177  { "min-path-length",
178  [](
179  const FunctionalUnitNeighbours& fu_neighbours,
180  const OpGraphOp& src_op, const MRRG::NodeDescriptor& src_node,
181  const OpGraphOp& sink_op, const MRRG::NodeDescriptor& sink_node
182  ) -> double {
183  (void)src_op; (void)sink_op;
184  return fu_neighbours.getInfoFor(src_node, sink_node).distance + 1;
185  },
186  },
187  { "no-cost", {} },
188  { "all-zero", [](auto&, auto&, auto&, auto&, auto&) -> double { return 0; } },
189 };
190 
191 struct MapOpsJustByConnectivityTestDescription {
192  bool expect_to_map;
193  std::string cgra_description;
194  std::pair<int,int> cgra_II_min_max;
195  std::string opgraph_description;
196  std::string neighbour_finder_description;
197  std::function<std::unique_ptr<CGRA>()> cgra_generator;
198  std::function<OpGraph()> opgraph_generator;
199  NeighbourFinder neighbour_finder;
200 };
201 
202 }
203 
204 SCENARIO ("mapOpsJustByConnectivity Tests", "") {
205  const auto& simpO2x2 = "simple 2-by-2 grid";
206  const auto& make_simpO2x2 = []{return makeCGRA_otho(2,2);};
207  const auto& simpO3x3 = "simple 3-by-3 grid";
208  const auto& make_simpO3x3 = []{return makeCGRA_otho(3,3);};
209  std::unordered_map<std::string, std::string> fix_port;
210  const auto& test = GENERATE_REF(values<MapOpsJustByConnectivityTestDescription>({
211  { true, simpO2x2, {1,3}, "linear 3-node", "1 NN", make_simpO2x2, []{return makeDFG_Linear3Node();}, makeNClosestNeighbourFinder(1) },
212  { false, simpO2x2, {1,1}, "tree 112", "1 NN", make_simpO2x2, []{return makeDFG_Tree112();}, makeNClosestNeighbourFinder(1) },
213  { true, simpO2x2, {2,3}, "tree 112", "1 NN", make_simpO2x2, []{return makeDFG_Tree112();}, makeNClosestNeighbourFinder(1) },
214  { true, simpO2x2, {1,3}, "converging 121", "1 NN", make_simpO2x2, []{return makeDFG_Converging121();}, makeNClosestNeighbourFinder(1) },
215  { true, simpO2x2, {1,3}, "multiEdge 11", "1 NN", make_simpO2x2, []{return makeDFG_MultiEdge11();}, makeNClosestNeighbourFinder(1) },
216  { true, simpO2x2, {1,3}, "1-node with self loop", "1 NN", make_simpO2x2, []{return makeDFG_SelfLoop1Node();}, makeNClosestNeighbourFinder(1) },
217  { true, simpO2x2, {1,3}, "3-node linear with self loop", "1 NN", make_simpO2x2, []{return makeDFG_SelfLoop3Node();}, makeNClosestNeighbourFinder(1) },
218  { true, simpO2x2, {1,3}, "2-node loop", "1 NN", make_simpO2x2, []{return makeDFG_Loop2Node();}, makeNClosestNeighbourFinder(1) },
219  { false, simpO2x2, {1,2}, "3-node loop", "1 NN", make_simpO2x2, []{return makeDFG_Loop3Node();}, makeNClosestNeighbourFinder(1) },
220  { true, simpO2x2, {3,3}, "3-node loop", "1 NN", make_simpO2x2, []{return makeDFG_Loop3Node();}, makeNClosestNeighbourFinder(1) },
221  { true, simpO2x2, {1,3}, "4-node with 2-node loop", "1 NN", make_simpO2x2, []{return makeDFG_2NodeLoop4Node();}, makeNClosestNeighbourFinder(1) },
222  { false, simpO2x2, {2,2}, "2-input re-converging 2121", "1 NN", make_simpO2x2, []{return makeDFG_MultiInputReconverging2121();}, makeNClosestNeighbourFinder(1) },
223  { true, simpO2x2, {3,3}, "2-input re-converging 2121", "1 NN", make_simpO2x2, []{return makeDFG_MultiInputReconverging2121();}, makeNClosestNeighbourFinder(1) },
224  { true, simpO3x3, {2,3}, "Converging 121", "1 NN", make_simpO3x3, []{return makeDFG_Converging121();}, makeNClosestNeighbourFinder(1) },
225  { true, simpO3x3, {2,3}, "Large only requiring NN FUs", "7 NN", make_simpO3x3, []{return makeDFG_Large(false);}, makeNClosestNeighbourFinder(7) },
226  { false, simpO3x3, {2,3}, "Large requiring non NN FUs", "1 NN", make_simpO3x3, []{return makeDFG_Large(true);}, makeNClosestNeighbourFinder(1) },
227  }));
228 
229  GIVEN("A " << test.cgra_description << " CGRA") {
230  const auto cgra = test.cgra_generator();
231  const auto cgra_II = GENERATE_REF(range(test.cgra_II_min_max.first, test.cgra_II_min_max.second+1));
232  GIVEN ("A CGRA II of " << cgra_II) {
233  const auto& mrrg = cgra->getMRRG(cgra_II);
234 
235  GIVEN("A " << test.opgraph_description << " DFG") {
236  const auto opgraph = test.opgraph_generator();
237 
238  WHEN ("Placed with a " << test.neighbour_finder_description << " neighbour finder") {
239  const auto mapping = mapOpsJustByConnectivity(fix_port, opgraph, mrrg,
240  MapOpsJustByConnectivityOptions{
241  test.neighbour_finder,
242  acceptTheFirstSolution,
243  noEdgeCosting, {
244  // { "model_IIS_dump_filename", test.cgra_description + ("-II" + std::to_string(cgra_II)) + "-" + test.opgraph_description + "-placement"},
245  }
246  }
247  );
248 
249  THEN ("Placement will " << (test.expect_to_map ? "succeed" : "fail")) {
250  CHECK(test.expect_to_map == mapping.isMapped());
251  }
252  }
253  }
254  }
255  }
256 }
257 
258 template<typename PLACEMENTS>
259 void then_placement_should_fail_after_n_placements(
260  const std::size_t nplace,
261  const PLACEMENTS& placements,
262  const Mapping& final_mapping
263 ) {
264  THEN ("Placement should fail after " << nplace << " placements") {
265  CHECK(final_mapping.isMapped() == false);
266  CHECK(placements.size() == nplace);
267  }
268 }
269 
270 template<typename NFINDER, typename EDGE_COSTER>
271 void when_mapped_then_placement_should_fail_after_n_placements(
272  const std::size_t nplace,
273  const OpGraph& opgraph, const MRRG& mrrg,
274  const NFINDER& neighbour_finder, const EDGE_COSTER& edge_coster,
275  ConfigStore options = {}
276 ) {
277  std::vector<Mapping> placements;
278  std::unordered_map<std::string, std::string> fix_port;
279  const auto placement_recorder = [&](const Mapping& m) -> Mapping {
280  placements.push_back(m);
281  placements.back().setStatus(MappingStatus::failure);
282  // placements.back().outputMapping(opgraph, std::cout);
283  // std::cout << "-+-+-+-+-\n";
284  return placements.back();
285  };
286 
287  WHEN ("Mapped") {
288  const auto final_mapping = mapOpsJustByConnectivity(fix_port, opgraph, mrrg, MapOpsJustByConnectivityOptions{neighbour_finder, placement_recorder, edge_coster, options});
289 
290  then_placement_should_fail_after_n_placements(nplace, placements, final_mapping);
291  }
292 }
293 
294 SCENARIO ("is mapOpsJustByConnectivity exact?") {
295  const int rotational_symmetry = 4;
296 
297  {const int w = 2; const int h = 2;
298  GIVEN("A simple " << w << "-by-" << h << " grid CGRA") {
299  const auto cgra = makeCGRA_otho(w,h);
300 
301  const int num_contexts = 1;
302  GIVEN ("A CGRA II of " << num_contexts) {
303  const auto mrrg = cgra->getMRRG(num_contexts);
304 
305  GIVEN("A linear 3-node DFG") {
306  const auto opgraph = makeDFG_Linear3Node();
307 
308  when_mapped_then_placement_should_fail_after_n_placements(
309  8,
310  opgraph, mrrg, makeNClosestNeighbourFinder(1), noEdgeCosting
311  );
312  }
313 
314  GIVEN("A Converging 121 DFG") {
315  const auto opgraph = makeDFG_Converging121();
316  const int dfg_symmetry = 2;
317 
318  when_mapped_then_placement_should_fail_after_n_placements(
319  (1)*num_contexts*rotational_symmetry*dfg_symmetry,
320  opgraph, mrrg, makeNClosestNeighbourFinder(1), noEdgeCosting
321  );
322  }
323 
324  GIVEN("A Self Loop 3 Node DFG") {
325  const auto opgraph = makeDFG_SelfLoop3Node();
326  const int dfg_symmetry = 2;
327 
328  when_mapped_then_placement_should_fail_after_n_placements(
329  (1)*num_contexts*rotational_symmetry*dfg_symmetry,
330  opgraph, mrrg, makeNClosestNeighbourFinder(1), noEdgeCosting
331  );
332  }
333 
334  GIVEN("A Loop 4 Node DFG") {
335  const auto opgraph = makeDFG_2NodeLoop4Node();
336  const int dfg_symmetry = 2;
337 
338  when_mapped_then_placement_should_fail_after_n_placements(
339  (1)*num_contexts*rotational_symmetry*dfg_symmetry,
340  opgraph, mrrg, makeNClosestNeighbourFinder(1), noEdgeCosting
341  );
342  }
343  }
344  }}
345 
346  {const int w = 2; const int h = 2; const int fu_lat = 1;
347  GIVEN("A simple " << w << "-by-" << h << " with FU latency " << fu_lat << " grid CGRA") {
348  const auto cgra = makeCGRA_otho(w,h,{ {"fu_latency", std::to_string(fu_lat)} });
349 
350  const int num_contexts = 2;
351  GIVEN ("A CGRA II of " << num_contexts) {
352  const auto mrrg = cgra->getMRRG(num_contexts);
353 
354  GIVEN("A linear 3-node DFG") {
355  const auto opgraph = makeDFG_Linear3Node();
356 
357  when_mapped_then_placement_should_fail_after_n_placements(
358  6*num_contexts*rotational_symmetry,
359  opgraph, mrrg, makeNClosestNeighbourFinder(3), noEdgeCosting
360  );
361  }
362 
363  GIVEN("A Converging 121 DFG") {
364  const auto opgraph = makeDFG_Converging121();
365  const int dfg_symmetry = 2;
366 
367  when_mapped_then_placement_should_fail_after_n_placements(
368  3*num_contexts*rotational_symmetry*dfg_symmetry,
369  opgraph, mrrg, makeNClosestNeighbourFinder(3), noEdgeCosting
370  );
371  }
372 
373  GIVEN("A Self Loop 3 Node DFG") {
374  const auto opgraph = makeDFG_SelfLoop3Node();
375  const int dfg_symmetry = 2;
376 
377  when_mapped_then_placement_should_fail_after_n_placements(
378  3*num_contexts*rotational_symmetry*dfg_symmetry,
379  opgraph, mrrg, makeNClosestNeighbourFinder(3), noEdgeCosting
380  );
381  }
382 
383  GIVEN("A Loop 4 Node DFG") {
384  const auto opgraph = makeDFG_2NodeLoop4Node();
385  const int dfg_symmetry = 2;
386 
387  when_mapped_then_placement_should_fail_after_n_placements(
388  6*num_contexts*rotational_symmetry*dfg_symmetry,
389  opgraph, mrrg, makeNClosestNeighbourFinder(3), noEdgeCosting
390  );
391  }
392  }
393  }}
394 
395  {const int w = 3; const int h = 3;
396  GIVEN("A simple " << w << "-by-" << h << " grid CGRA") {
397  const auto cgra = makeCGRA_otho(w,h);
398 
399  const int num_contexts = 2;
400  GIVEN ("A CGRA II of " << num_contexts) {
401  const auto mrrg = cgra->getMRRG(num_contexts);
402 
403  GIVEN("A Converging 121 DFG") {
404  const auto opgraph = makeDFG_Converging121();
405  const int dfg_symmetry = 2;
406 
407  when_mapped_then_placement_should_fail_after_n_placements(
408  (3 + 5 + 2)*num_contexts*rotational_symmetry*dfg_symmetry,
409  opgraph, mrrg, makeNClosestNeighbourFinder(1), noEdgeCosting
410  );
411  }
412 
413  GIVEN("A Large DFG only requiring NN FUs") {
414  const auto opgraph = makeDFG_Large(false);
415 
416  when_mapped_then_placement_should_fail_after_n_placements(
417  num_contexts*rotational_symmetry*135, // determined empirically...
418  opgraph, mrrg, makeNClosestNeighbourFinder(1), noEdgeCosting
419  );
420  }
421 
422 
423  GIVEN("A Tree 112 DFG") {
424  const auto opgraph = makeDFG_Tree112();
425  const int dfg_symmetry = 2;
426 
427  when_mapped_then_placement_should_fail_after_n_placements(
428  // +2 is for the T shaped mapping rooted at (1,1) that go ++context
429  ((7 + 11 + 4)*rotational_symmetry + 2)*num_contexts*dfg_symmetry,
430  opgraph, mrrg, makeNClosestNeighbourFinder(1), noEdgeCosting
431  );
432  }
433  }
434  }}
435 }
436 
437 SCENARIO ("routeOpMappingByChoosingPaths Tests", "") {
438  std::unordered_map<std::string, std::string> fix_port;
439  GIVEN("A simple 2-by-2 grid CGRA") {
440  const auto cgra = makeCGRA_otho(2,2);
441 
442  auto cgra_II = GENERATE(1,2);
443  GIVEN ("A CGRA II of " << cgra_II) {
444  const auto mrrg = cgra->getMRRG(cgra_II);
445 
446  GIVEN("A linear 3-node DFG") {
447  const auto opgraph = makeDFG_Linear3Node();
448 
449  GIVEN("An op mapping that should work") {
450  Mapping op_mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
451  op_mapping.mapMRRGNode(opgraph.getOp("op_a"), mrrg.getNode(0,"b_c1_r1.func.fu"));
452  op_mapping.mapMRRGNode(opgraph.getOp("op_b"), mrrg.getNode(0,"b_c1_r0.func.fu"));
453  op_mapping.mapMRRGNode(opgraph.getOp("op_c"), mrrg.getNode(0,"b_c0_r0.func.fu"));
454 
455  WHEN ("Mapped") {
456  const auto mapping = routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg);
457 
458  THEN ("Mapping should map") {
459  CHECK(mapping.isMapped());
460  }
461  }
462  }
463  }
464 
465  GIVEN("A Converging 121 DFG") {
466  const auto opgraph = makeDFG_Converging121();
467 
468  GIVEN("An op mapping that should work") {
469  Mapping op_mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
470  op_mapping.mapMRRGNode(opgraph.getOp("op_a"), mrrg.getNode(0,"b_c1_r1.func.fu"));
471  op_mapping.mapMRRGNode(opgraph.getOp("op_b"), mrrg.getNode(0,"b_c0_r1.func.fu"));
472  op_mapping.mapMRRGNode(opgraph.getOp("op_b2"), mrrg.getNode(0,"b_c1_r0.func.fu"));
473  op_mapping.mapMRRGNode(opgraph.getOp("op_c"), mrrg.getNode(0,"b_c0_r0.func.fu"));
474 
475  WHEN ("Mapped") {
476  const auto mapping = routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg);
477 
478  THEN ("Mapping should map") {
479  CHECK(mapping.isMapped());
480  }
481  }
482  }
483  }
484 
485  GIVEN("A Self Loop 3 Node DFG") {
486  const auto opgraph = makeDFG_SelfLoop3Node();
487 
488  WHEN ("Mapped") {
489  Mapping op_mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
490  op_mapping.mapMRRGNode(opgraph.getOp("op_a"), mrrg.getNode(0,"b_c0_r1.func.fu"));
491  op_mapping.mapMRRGNode(opgraph.getOp("op_l"), mrrg.getNode(0,"b_c1_r1.func.fu"));
492  op_mapping.mapMRRGNode(opgraph.getOp("op_c"), mrrg.getNode(0,"b_c1_r0.func.fu"));
493  const auto mapping = routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg);
494 
495  THEN ("Mapping should map") {
496  CHECK(mapping.isMapped());
497  }
498  }
499  }
500 
501  GIVEN("A Loop 4 Node DFG") {
502  const auto opgraph = makeDFG_2NodeLoop4Node();
503 
504  WHEN ("Mapped") {
505  Mapping op_mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
506  op_mapping.mapMRRGNode(opgraph.getOp("op_a"), mrrg.getNode(0,"b_c1_r0.func.fu"));
507  op_mapping.mapMRRGNode(opgraph.getOp("op_l"), mrrg.getNode(0,"b_c1_r1.func.fu"));
508  op_mapping.mapMRRGNode(opgraph.getOp("op_m"), mrrg.getNode(0,"b_c0_r1.func.fu"));
509  op_mapping.mapMRRGNode(opgraph.getOp("op_d"), mrrg.getNode(0,"b_c0_r0.func.fu"));
510  const auto mapping = routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg);
511 
512  THEN ("Mapping should map") {
513  CHECK(mapping.isMapped());
514  }
515  }
516  }
517 
518  GIVEN("A MultiEdge 11 DFG") {
519  const auto opgraph = makeDFG_MultiEdge11();
520 
521  WHEN ("Mapped") {
522  Mapping op_mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
523  op_mapping.mapMRRGNode(opgraph.getOp("op_a"), mrrg.getNode(0,"b_c1_r0.func.fu"));
524  op_mapping.mapMRRGNode(opgraph.getOp("op_b"), mrrg.getNode(0,"b_c1_r1.func.fu"));
525  const auto mapping = routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg);
526 
527  THEN ("Mapping should map") {
528  CHECK(mapping.isMapped());
529  }
530  }
531  }
532  }
533  }
534 
535  GIVEN("A simple 2-by-3 grid CGRA") {
536  const auto cgra = makeCGRA_otho(2,2);
537 
538  GIVEN ("A CGRA II of 3") {
539  const auto mrrg = cgra->getMRRG(3);
540 
541  GIVEN("A DeviceFiller DFG") {
542  const auto opgraph = makeDFG_DeviceFiller({{
543  {"width", "2"}, {"height","2"}, {"num_contexts", "3"}
544  }});
545 
546  GIVEN("An op mapping that should work") {
547  Mapping op_mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
548 
549  op_mapping.mapMRRGNode(opgraph.getOp("op_c0x0y0"), mrrg.getNode(0, "b_c0_r0.func.fu"));
550  op_mapping.mapMRRGNode(opgraph.getOp("op_c0x0y1"), mrrg.getNode(0, "b_c0_r1.func.fu"));
551  op_mapping.mapMRRGNode(opgraph.getOp("op_c0x1y0"), mrrg.getNode(0, "b_c1_r0.func.fu"));
552  op_mapping.mapMRRGNode(opgraph.getOp("op_c0x1y1"), mrrg.getNode(0, "b_c1_r1.func.fu"));
553  op_mapping.mapMRRGNode(opgraph.getOp("op_c1x0y0"), mrrg.getNode(1, "b_c0_r0.func.fu"));
554  op_mapping.mapMRRGNode(opgraph.getOp("op_c1x0y1"), mrrg.getNode(1, "b_c0_r1.func.fu"));
555  op_mapping.mapMRRGNode(opgraph.getOp("op_c1x1y0"), mrrg.getNode(1, "b_c1_r0.func.fu"));
556  op_mapping.mapMRRGNode(opgraph.getOp("op_c1x1y1"), mrrg.getNode(1, "b_c1_r1.func.fu"));
557  op_mapping.mapMRRGNode(opgraph.getOp("op_c2x0y0"), mrrg.getNode(2, "b_c0_r0.func.fu"));
558  op_mapping.mapMRRGNode(opgraph.getOp("op_c2x0y1"), mrrg.getNode(2, "b_c0_r1.func.fu"));
559  op_mapping.mapMRRGNode(opgraph.getOp("op_c2x1y0"), mrrg.getNode(2, "b_c1_r0.func.fu"));
560  op_mapping.mapMRRGNode(opgraph.getOp("op_c2x1y1"), mrrg.getNode(2, "b_c1_r1.func.fu"));
561 
562  WHEN ("Mapped") {
563  const auto mapping = routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg, { {}, acceptTheFirstSolution, {}, {
564  }});
565 
566  THEN ("Mapping should map") {
567  CHECK(mapping.isMapped());
568  }
569  }
570  }
571  }
572  }
573  }
574 }
575 
576 SCENARIO ("Try op mappings until one routes - Easy", "") {
577  std::unordered_map<std::string, std::string> fix_port;
578  GIVEN("A simple 2-by-2 grid CGRA") {
579  const auto cgra = makeCGRA_otho(2,2);
580 
581  GIVEN ("A CGRA II of 1") {
582  const auto mrrg = cgra->getMRRG(1);
583 
584  GIVEN("A linear 3-node DFG") {
585  const auto opgraph = makeDFG_Linear3Node();
586 
587  WHEN ("Mapped") {
588  const auto mapping = mapOpsJustByConnectivity(fix_port, opgraph, mrrg, MapOpsJustByConnectivityOptions{makeNClosestNeighbourFinder(1), [&](auto& op_mapping) {
589  return routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg);
590  }, noEdgeCosting});
591 
592  THEN ("Mapping should map") {
593  CHECK(mapping.isMapped());
594  }
595  }
596  }
597 
598  GIVEN("A Converging 121 DFG") {
599  const auto opgraph = makeDFG_Converging121();
600 
601  WHEN ("Mapped") {
602  const auto mapping = mapOpsJustByConnectivity(fix_port, opgraph, mrrg, MapOpsJustByConnectivityOptions{makeNClosestNeighbourFinder(1), [&](auto& op_mapping) {
603  return routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg);
604  }, noEdgeCosting});
605 
606  THEN ("Mapping should map") {
607  CHECK(mapping.isMapped());
608  }
609  }
610  }
611  }
612  }
613 
614  GIVEN("A simple 2-by-2 grid CGRA") {
615  const auto cgra = makeCGRA_otho(2,2);
616 
617  {const int num_contexts = GENERATE(1,2,3);
618  GIVEN ("A CGRA II of " << num_contexts) {
619  const auto mrrg = cgra->getMRRG(num_contexts);
620 
621  GIVEN("A DeviceFiller DFG") {
622  const auto opgraph = makeDFG_DeviceFiller({{
623  {"width", "2"}, {"height","2"}, {"num_contexts", std::to_string(num_contexts)}
624  }});
625 
626  WHEN ("Mapped") {
627  const int nneigh = 1;
628  const auto mapping = mapOpsJustByConnectivity(fix_port, opgraph, mrrg, MapOpsJustByConnectivityOptions{makeNClosestNeighbourFinder(nneigh), [&](auto& op_mapping) {
629  return routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg);
630  }, noEdgeCosting});
631 
632  THEN ("Mapping should map") {
633  CHECK(mapping.isMapped());
634  }
635  }
636  }
637  }}
638  }
639 }
640 
644 SCENARIO ("Try op mappings until one routes - Sometimes hard", "[!hide]") {
645  std::unordered_map<std::string, std::string> fix_port;
646  GIVEN("A simple 2-by-3 grid CGRA") {
647  const auto cgra = makeCGRA_otho(2,3);
648 
649  GIVEN ("A CGRA II of 3") {
650  const auto mrrg = cgra->getMRRG(3);
651 
652  GIVEN("A Large DFG") {
653  const auto opgraph = makeDFG_Large(true);
654 
655  WHEN ("Mapped") {
656  Mapping mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
657 
658  int nneigh = 0;
659  while (nneigh < 16 && not mapping.isMapped()) {
660  ++nneigh;
661  mapping = mapOpsJustByConnectivity(fix_port, opgraph, mrrg, MapOpsJustByConnectivityOptions{makeNClosestNeighbourFinder(nneigh), [&](auto& op_mapping) {
662  return routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg);
663  }, noEdgeCosting});
664  }
665 
666  THEN ("Mapping should map with 8 NNs") {
667  CHECK(mapping.isMapped());
668  CHECK(nneigh == 8);
669  }
670  }
671  }
672  }
673  }
674 
675  // GIVEN("A simple 6-by-6 grid+diag CGRA") {
676  // const auto cgra = makeCGRA_diag(6,6);
677 
678  // GIVEN ("A CGRA II of 8") {
679  // const auto mrrg = cgra->getMRRG(10);
680 
681  // GIVEN("A Huge DFG") {
682  // const auto opgraph = makeDFG_Huge();
683 
684  // WHEN ("Mapped") {
685  // Mapping mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
686 
687  // int nneigh = 24;
688  // while (nneigh < 75 && not mapping.isMapped()) {
689  // ++nneigh;
690  // mapping = mapOpsJustByConnectivity(opgraph, mrrg, MapOpsJustByConnectivityOptions{makeNClosestNeighbourFinder(nneigh), [&](auto& op_mapping) {
691  // return routeOpMappingByChoosingPaths(op_mapping, opgraph, mrrg);
692  // }, noEdgeCosting});
693  // }
694 
695  // THEN ("Mapping should map with ??? NNs") {
696  // CHECK(mapping.isMapped());
697  // CHECK(nneigh == 0);
698  // }
699  // }
700  // }
701  // }
702  // }
703 
704  GIVEN("A simple 4-by-4 grid+diag CGRA") {
705  const auto cgra = makeCGRA_diag(4,4);
706 
707  GIVEN ("A CGRA II of 2") {
708  const auto mrrg = cgra->getMRRG(2);
709 
710  GIVEN("A Larger DFG") {
711  const auto opgraph = makeDFG_Larger();
712 
713  WHEN ("Mapped") {
714  Mapping mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
715 
716  int nneigh = 4;
717  while (nneigh < 10 && not mapping.isMapped()) {
718  ++nneigh;
719  mapping = mapOpsJustByConnectivity(fix_port, opgraph, mrrg, MapOpsJustByConnectivityOptions{makeNClosestNeighbourFinder(nneigh), [&](auto& op_mapping) {
720  return routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg);
721  }, noEdgeCosting});
722  }
723 
724  THEN ("Mapping should map with 6 NNs") {
725  CHECK(mapping.isMapped());
726  CHECK(nneigh == 6);
727  }
728  }
729  }
730  }
731  }
732 }
733 
734 namespace {
735 
736 struct PathMergingTest {
737  std::string description, mrrg_description, dfg_description;
738  MRRG mrrg;
739  OpGraph opgraph;
740 
741  // for *all* mappings
742  std::map<std::string,int> expected_op_output_val_mapping_sizes;
743  // to make sure all interesting cases are covered
744  int expected_number_of_mappings;
745  // customize behaviour of the mapper
746  ConfigStore custom_mapping_options;
747 };
748 
749 } // end anon namespace
750 
751 TEST_CASE("Heurmpr: path merging") {
752  std::unordered_map<std::string, std::string> fix_port;
753  const PathMergingTest tests[] { // OpGraph is move-only...
754  { "No choices", "1112", "Tree12",makeMRRG_1112DAG(1,0,0), makeDFG_Tree12(),
755  {{"op_a",2}}, 2, {},
756  },
757  { "No choices -- latency on b", "1112", "Tree12",makeMRRG_1112DAG(1,0,1), makeDFG_Tree12(),
758  {{"op_a",2}}, 2, {},
759  },
760  { "Two choices", "1212", "Tree12",makeMRRG_1212DAG(1,0,0,0), makeDFG_Tree12(),
761  {{"op_a",2}}, 8, {},
762  },
763  { "Two choices -- only one path", "1212", "Tree12",makeMRRG_1212DAG(1,0,0,0), makeDFG_Tree12(),
764  {{"op_a",2}}, 2, {{"max_num_paths_between_FUs", "1"}},
765  },
766  { "Two choices -- matched latency", "1212", "Tree12",makeMRRG_1212DAG(1,0,1,0), makeDFG_Tree12(),
767  {{"op_a",2}}, 8, {},
768  },
769  { "Two choices -- mismatched latency", "1212", "Tree12",makeMRRG_1212DAG(1,0,1,1), makeDFG_Tree12(),
770  {{"op_a",2}}, 4, {{"path_exclusivity_constraints_are_pairwise", "yes"}}, // no solutions otherwise...
771  },
772  { "Loop", "3NodeLoop", "self-loop", makeMRRG_Loop3NodeMaybeExtraFU(1,false,0,1,0), makeDFG_SelfLoop1Node(),
773  {{"op_l",2}}, 1, {},
774  },
775  { "Loop with leg, sharing", "3NodeLoop-extra-FU", "self-loop", makeMRRG_Loop3NodeMaybeExtraFU(1,true,0,1,0), makeDFG_SelfLoop1Node(),
776  {{"op_l",2}}, 1, {},
777  },
778  { "Loop with leg, no sharing", "3NodeLoop-extra-FU", "self-loop with extra fanout", makeMRRG_Loop3NodeMaybeExtraFU(1,true,0,1,0), makeDFG_SelfLoop1NodeWith1ExtraFanout(),
779  {{"op_l",3}}, 1, {},
780  },
781  };
782 
783  const auto name_and_mapper_config = GENERATE(values<std::pair<std::string,ConfigStore>>({
784  {"pairwise pathex", {{"path_exclusivity_constraints_are_pairwise", "yes"}}},
785  {"non-pairwise pathex", {{"path_exclusivity_constraints_are_pairwise", "no"}}},
786  }));
787 
788  const auto& test = tests[GENERATE_REF(range<std::ptrdiff_t>(0, std::distance(std::begin(tests), std::end(tests))))];
789 
790  const auto& opgraph = test.opgraph;
791 
792  DYNAMIC_SECTION("A '" << test.description << "' test") {
793  GIVEN("A '" << name_and_mapper_config.first << "' mapper configuration") {
794  GIVEN("A '" << test.dfg_description << "' DFG") {
795  GIVEN("A '" << test.mrrg_description << "' MRRG") {
796  const auto mapping_options = set_all(set_all(ConfigStore {
797  {"model_IIS_dump_filename", "non-pairwise-no-solution"},
798  }, name_and_mapper_config.second), test.custom_mapping_options);
799 
800  const auto initial_mapping = Mapping{nullptr, test.mrrg.initiationInterval(), nullptr};
801  int num_mappings = 0;
802  const auto mapping = mapViaConnectivityAndPathChoosing(fix_port, opgraph, test.mrrg, initial_mapping,
803  ILPHeuristicMapperOptions{
804  makeNClosestNeighbourFinder(2),
805  [&](Mapping m) {
806  num_mappings += 1;
807  for (const auto& op_name_and_expected_val_size : test.expected_op_output_val_mapping_sizes) {
808  const auto& op = opgraph.getOp(op_name_and_expected_val_size.first);
809  const auto& op_output_val_mapping = m.getMappingList(opgraph.outputVal(op));
810  INFO( // as an INFO to reduce re-runs
811  "for mapping #" << num_mappings << ", the output val of "
812  << opgraph.getNodeRef(op).getName() << " should map to the expected number of MRRG nodes"
813  );
814  CHECK(op_output_val_mapping.size() == op_name_and_expected_val_size.second);
815  }
816  m.setStatus(MappingStatus::failure); // reject all mappings so we look at every one
817  return m;
818  },
819  noEdgeCosting, mapping_options,
820  }
821  );
822 
823  THEN("The number of mappings should be as expected, to make sure no cases were missed") {
824  // also, to make sure there are no unexpected mappings
825  CHECK(num_mappings == test.expected_number_of_mappings);
826  }
827  }}}}
828 }
829 
830 SCENARIO("hycube AES test", "[!hide]") {
831  const auto test_options = ConfigStore({
832  {"partition_method", "0"},
833  {"print_DFG", "no"},
834  {"dump_DFG", "no"},
835  {"filter_consts", "no"},
836  {"do_test_placement", "no"},
837  });
838 
839  const auto possibly_print_and_dump_dfg = [](const OpGraph& opgraph, auto&& name, const ConfigStore& options) {
840  if (options.getBool("dump_DFG")) {
841  std::ofstream dfg_ofstream {string_from_stream([&](auto&&s) { s << name << "-DFG.dot"; })};
842  opgraph.serialize(dfg_ofstream);
843  dfg_ofstream.flush();
844  }
845  if (options.getBool("print_DFG")) { opgraph.serialize(std::cout); }
846  };
847 
848 
849  GIVEN("A 4-by-4 HyCUBE CGRA") {
850  const auto cgra = makeCGRA_hycube(4,4);
851 
852  SECTION("loopAllOpMappings test") {
853 
854  int i = 64;
855  for (int numc = 16; numc <= 16; numc += 4) {
856  bool mapping_worked = true;
857  const auto mrrg = cgra->getMRRG(numc);
858  ILPHeuristicMapperCaches ilphm_caches;
859  MRRGProcedureCacheHandle mrrg_cache;
860  ilphm_caches.mrrg_proc_cache = &mrrg_cache;
861  std::unordered_map<std::string, std::string> fix_port;
862  for (; i <= 269 && mapping_worked; i += 1) {
863  std::vector<int> ops_wanted(i + 1); // + 1 for 0 indexing of nodes // = {64,65,30,31,66,143,144,67,68,220,221};
864  std::iota(ops_wanted.begin(), ops_wanted.end(), 0);
865 
866  // GIVEN (string_from_stream([&](auto&&s) { s << "A CGRA II of " << numc; })) {
867 
868  // GIVEN(string_from_stream([&](auto&&s) { s << "A Huge DFG, with nodes "; print_container(s, ops_wanted); })) {
869  const auto opgraph = makeDFG_Huge(ops_wanted, test_options);
870  possibly_print_and_dump_dfg(opgraph, "P0", test_options);
871 
872  const auto test_placement_options = ConfigStore({
873  {"path_exclusivity_modelling", "off"},
874  {"print_solve_progress", "yes"},
875  {"max_threads", "1"},
876  });
877 
878  const auto outer_options = ConfigStore({
879  {"path_exclusivity_modelling", "on"},
880  {"max_num_paths_between_FUs", "3"},
881  {"allowable_routing_usage_multiplier", "2"},
882 
883  {"print_configuration_and_statistics", "yes"},
884  {"print_solve_progress", "yes"},
885  {"max_threads", "1"},
886  });
887 
888  const auto inner_options = ConfigStore({
889  {"max_threads", "1"},
890  });
891 
892  const auto edge_coster_name = "no-cost";
893  const EdgeCoster edgeCoster = edgeCosters.at(edge_coster_name);
894 
895  std::cout << "trying to place & route ops 0-" << i << " with coster " << edge_coster_name << '\n';
896  print_container(std::cout, ops_wanted);
897  std::cout << "\nA CGRA II of " << numc << '\n';
898  std::cout << "with outer options " << outer_options << '\n';
899 
900  // WHEN ("Mapped") {
901  Mapping mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
902  const Mapping empty_mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
903 
904  const int nneigh_step = 1;
905  int nneigh = 18 - nneigh_step;
906  while (nneigh < 20 && not mapping.isMapped()) {
907  nneigh += nneigh_step;
908  std::cout << "trying to place & route with NN = " << nneigh << '\n';
909  if (test_options.getInt("partition_method") == 0) {
910  if (test_options.getBool("do_test_placement")) {
911  const auto test_placement = mapOpsJustByConnectivity(fix_port, opgraph, mrrg,
912  MapOpsJustByConnectivityOptions{
913  makeNClosestNeighbourFinder(nneigh), acceptTheFirstSolution, noEdgeCosting, test_placement_options
914  },
915  ilphm_caches
916  );
917  if (not test_placement.isMapped()) {
918  continue;
919  }
920  }
921  mapping = mapOpsJustByConnectivity(fix_port, opgraph, mrrg, MapOpsJustByConnectivityOptions{makeNClosestNeighbourFinder(nneigh), [&](auto& op_mapping) {
922  return routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg, { {}, acceptTheFirstSolution, {} }, ilphm_caches);
923  // (void)op_mapping;
924  // return true;
925  }, edgeCoster, outer_options}, ilphm_caches);
926  } else if (test_options.getInt("partition_method") == 1) {
927  const int num_partitions = 2;
928 
929  const auto map_partitions = [&](
930  const int level,
931  auto&& map_rest,
932  const auto& mapping_so_far
933  ) {
934  const auto level_string = 'P' + std::to_string(level);
935  if (level > num_partitions) {
936  auto local_inner_options = inner_options;
937  local_inner_options.setString("solve_approach_name", "Final Route");
938  return routeOpMappingByChoosingPaths(
939  fix_port,
940  mapping_so_far,
941  opgraph,
942  mrrg,
943  { {}, acceptTheFirstSolution, {}, local_inner_options }
944  );
945  } else {
946  const auto input_nodes = filter_collection(opgraph.opNodes(), [&](const auto& op) { return opgraph.inputVals(op).empty(); });
947  const auto ops_to_use = findNDownstreamOps(opgraph, input_nodes, opgraph.opNodes().size() * level / num_partitions);
948  const auto opgraph_filter_result = filter(opgraph, ops_to_use);
949  const auto mapping_so_far_for_filtered_opgraph = withRemappedOps(mapping_so_far, opgraph_filter_result.forward_mappings);
950 
951  auto local_outer_options = outer_options;
952  local_outer_options.setString("solve_approach_name", "Place Partition " + level_string);
953  if (local_outer_options.getStringOr("model_IIS_dump_filename","") != "") { local_outer_options.setString("model_IIS_dump_filename", level_string + '-' + local_outer_options.getString("model_IIS_dump_filename")); }
954  if (local_outer_options.getStringOr("model_dump_filename","") != "") { local_outer_options.setString("model_dump_filename", level_string + '-' + local_outer_options.getString("model_dump_filename")); }
955 
956  if (level > 1) {
957  local_outer_options.setInt("max_solutions", 10);
958  }
959 
960  possibly_print_and_dump_dfg(opgraph, level_string, test_options);
961 
962  return mapViaConnectivityAndPathChoosing(
963  fix_port,
964  opgraph_filter_result.transform_result,
965  mrrg,
966  mapping_so_far_for_filtered_opgraph,
967  MapOpsJustByConnectivityOptions{
968  makeNClosestNeighbourFinder(nneigh + 10*(level-1)),
969  [&](auto& proposed_mapping) {
970  const auto proposed_mapping_for_original_opgraph = withRemappedOps(proposed_mapping, opgraph_filter_result.reverse_mappings);
971  return map_rest(level+1, map_rest, proposed_mapping_for_original_opgraph);
972  },
973  edgeCoster,
974  local_outer_options,
975  },
976  ilphm_caches
977  );
978  }
979  };
980 
981  mapping = map_partitions(1, map_partitions, empty_mapping);
982  }
983  }
984 
985  mapping_worked = mapping.isMapped();
986  if (mapping.isMapped()) {
987  std::cout << ": PASSED: with NN " << nneigh << "\n";
988  } else {
989  std::cout << ": FAILED: with NN " << nneigh << "\n";
990  break;
991  }
992 
993  // THEN (string_from_stream([&](auto&&s) { s << "Mapping should map with " << nneigh << " NNs"; })) {
994  // REQUIRE(mapping.isMapped());
995  // throw cgrame_error("!!! found_a_solution !!!");
996  // CHECK(nneigh == 12);
997  // }
998  // }
999  // }
1000  // }
1001  }
1002  }
1003  }
1004 
1005  // for (int numc = 8; numc <= 32; numc += 4) {
1006  // GIVEN (string_from_stream([&](auto&&s) { s << "A CGRA II of " << numc; })) {
1007  // const auto mrrg = cgra->getMRRG(numc);
1008 
1009  // GIVEN("A Huge DFG") {
1010  // const auto opgraph = makeDFG_Huge();
1011 
1012  // WHEN ("Mapped") {
1013  // Mapping mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
1014 
1015  // int nneigh = 32-8;
1016  // while (nneigh < 64 && not mapping.isMapped()) {
1017  // nneigh += 8;
1018  // mapping = mapOpsJustByConnectivity(opgraph, mrrg, MapOpsJustByConnectivityOptions{makeNClosestNeighbourFinder(nneigh), [&](auto& op_mapping) {
1019  // return routeOpMappingByChoosingPaths(op_mapping, opgraph, mrrg);
1020  // }});
1021  // }
1022 
1023  // THEN (string_from_stream([&](auto&&s) { s << "Mapping should map with " << nneigh << " NNs"; })) {
1024  // REQUIRE(mapping.isMapped());
1025  // // CHECK(nneigh == 12);
1026  // }
1027  // }
1028  // }
1029  // }
1030  // }
1031  }
1032 }
1033 
1034 SCENARIO("Demo", "[!hide]") {
1035  const auto test_options = ConfigStore({
1036  {"do_cache_warmups", "yes"},
1037  });
1038 
1039  const std::string demo_path_prefix = std::getenv("CGRA_ME_BENCHMARKDIR");
1040  const std::string demo_path_suffix = "/graph_loop.dot";
1041 
1042  const std::vector<std::string> demo_names {
1043  "/microbench/accumulate",
1044  // "/mibench/aes",
1045  "/microbench/cap",
1046  "/microbench/conv2",
1047  "/microbench/conv3",
1048  "/mibench/FFT",
1049  "/microbench/mac",
1050  "/microbench/mac2",
1051  "/microbench/matrixmultiply",
1052  "/microbench/mults1",
1053  "/microbench/mults2",
1054  "/microbench/nomem1",
1055  "/microbench/simple",
1056  "/microbench/simple2",
1057  "/microbench/sum",
1058  };
1059 
1060  const std::vector<std::pair<int,int>> cgra_sizes {
1061  {2,2},
1062  {4,4},
1063  {10,10},
1064  };
1065 
1066  const std::vector<int> context_counts {
1067  1,
1068  2,
1069  3,
1070  };
1071 
1072  struct DemoSettings {
1073  ConfigStore test_placement_options = {
1074  {"path_exclusivity_modelling", "off"},
1075  {"print_solve_progress", "yes"},
1076  };
1077  ConfigStore outer_options = {
1078  {"print_configuration_and_statistics", "yes"},
1079  {"path_exclusivity_modelling", "on"},
1080  {"max_num_paths_between_FUs", "3"},
1081  {"allowable_routing_usage_multiplier", "2"},
1082  {"print_solve_progress", "yes"},
1083  {"print_intermediate_mappings", "yes"},
1084  };
1085  std::string outer_edge_coster_name = "no-cost";
1086  ConfigStore inner_options = {};
1087  ConfigStore cgra_options = {{"num_const_addresses", "1"}};
1088  ConfigStore other_cgra_options = {
1089  {"cgra_maker", "makeCGRA_clustered"},
1090  };
1091  ConfigStore other_options = {
1092  // for clustered
1093  {"nneigh_start", "8"},
1094  {"nneigh_stop", "16"},
1095  {"nneigh_step", "1"},
1096  // for ADRES:
1097  // ideal sched: 12, 14, 18, 21;
1098  // cusp at: 17
1099  // {"nneigh_start", "12"},
1100  // {"nneigh_stop", "21"},
1101  // {"nneigh_step", "2"},
1102  // for ADRES:
1103  // ideal sched: 7, 9, 11, 16
1104  // cusp at: ??
1105  // {"nneigh_start", "2"},
1106  // {"nneigh_stop", "32"},
1107  // {"nneigh_step", "1"},
1108 
1109  {"do_test_placement", "yes"},
1110  };
1111  };
1112 
1113  std::vector<DemoSettings> demo_settings_storage;
1114  std::vector<DemoSettings> cache_warm_up_demo_settings;
1115 
1116  for (const auto& dims : cgra_sizes) {
1117  for (const auto num_contexts : context_counts) {
1118  for (const auto& name : demo_names) {
1119  DemoSettings settings;
1120  set_all(settings.cgra_options, ConfigStore{{
1121  {"cols", std::to_string(dims.first)},
1122  {"rows", std::to_string(dims.second)},
1123  }});
1124  set_all(settings.other_options, ConfigStore{{
1125  {"name", name},
1126  }});
1127  set_all(settings.other_cgra_options, ConfigStore{{
1128  {"num_contexts", std::to_string(num_contexts)},
1129  }});
1130  demo_settings_storage.push_back(std::move(settings));
1131  };
1132  cache_warm_up_demo_settings.push_back(demo_settings_storage.back()); // copy the typical settings
1133  auto& warm_up_settings = cache_warm_up_demo_settings.back();
1134  auto& warm_up_other_opts = warm_up_settings.other_options;
1135  warm_up_other_opts.setString("name", "/microbench/sum"); // representative
1136  warm_up_settings.outer_options.setInt("max_num_paths_between_FUs", 20); // enough for both phases
1137  warm_up_other_opts.setInt("nneigh_start", warm_up_other_opts.getInt("nneigh_stop")); // don't waste time
1138  }
1139  }
1140 
1141  if (not test_options.getBool("do_cache_warmups")) {
1142  cache_warm_up_demo_settings.clear();
1143  }
1144 
1145  const auto dfg_path_for = [&](const DemoSettings& ds) {
1146  return demo_path_prefix + ds.other_options.getString("name") + demo_path_suffix;
1147  };
1148 
1149  const auto mrrg_id_for = [&](const DemoSettings& ds) {
1150  return string_from_stream([&](auto&& s) {
1151  s << ds.cgra_options << ds.other_cgra_options;
1152  });
1153  };
1154 
1155  std::map<std::string, const MRRG> mrrgs;
1156  std::map<std::string, std::unique_ptr<MRRGProcedureCacheHandle>> mrrg_cache_handles;
1157  std::map<std::string, ILPHeuristicMapperCaches> ilphm_caches;
1158  std::map<std::string, OpGraph> opgraphs;
1159  std::unordered_map<std::string, std::string> fix_port;
1160  // create the MRRGs, DFGs and caches
1161  for (const auto& demo_settings : demo_settings_storage) {
1162  const auto& num_contexts = demo_settings.other_cgra_options.getInt("num_contexts");
1163  const auto& cgra = cgra_makers.at(demo_settings.other_cgra_options.getString("cgra_maker"))(-1,-1,demo_settings.cgra_options);
1164  const auto mrrg_id = mrrg_id_for(demo_settings);
1165  mrrgs.emplace(mrrg_id, cgra->getMRRG(num_contexts));
1166  mrrg_cache_handles.emplace(mrrg_id, std::make_unique<MRRGProcedureCacheHandle>());
1167  ilphm_caches.emplace(mrrg_id, ILPHeuristicMapperCaches{ mrrg_cache_handles[mrrg_id].get() });
1168  auto dfg_ifstream = std::ifstream(dfg_path_for(demo_settings));
1169  const auto parsed_dfg_dot = parseDot(dfg_ifstream, dfg_path_for(demo_settings));
1170  opgraphs.emplace(dfg_path_for(demo_settings), createOpGraphFromConfig(parsed_dfg_dot));
1171  }
1172 
1173  ConfigStore stats;
1174  stats.setInt("num mrrgs", mrrgs.size());
1175  stats.setInt("num mrrg_caches", mrrg_cache_handles.size());
1176  stats.setInt("num ilphm caches", ilphm_caches.size());
1177  stats.setInt("num opgraphs", opgraphs.size());
1178  std::cout << "Demo Stats = " << stats << '\n';
1179 
1180  for (const auto& demo_settings_list : {cache_warm_up_demo_settings, demo_settings_storage}) {
1181  for (const auto& demo_settings : demo_settings_list) {
1182  // WHEN ("Mapped " << i) {
1183  std::cout << "with other_options = " << demo_settings.other_options << '\n';
1184  std::cout << "with cgra_options = " << demo_settings.cgra_options << '\n';
1185  std::cout << "with other_cgra_options = " << demo_settings.other_cgra_options << '\n';
1186 
1187  PrintOnDestructionChronoSequence timing_seq("demo mapping", &std::cout);
1188  const auto mrrg_id = mrrg_id_for(demo_settings);
1189  const auto& mrrg = mrrgs.at(mrrg_id);
1190  const auto& caches = ilphm_caches.at(mrrg_id);
1191  const auto& opgraph = opgraphs.at(dfg_path_for(demo_settings));
1192 
1193  Mapping mapping(std::make_shared<CGRA>(), mrrg.initiationInterval(), std::make_shared<OpGraph>());
1194 
1195  timing_seq.tick("setup");
1196  const auto nneigh_step = demo_settings.other_options.getInt("nneigh_step");
1197  auto nneigh = demo_settings.other_options.getInt("nneigh_start") - nneigh_step;
1198  while (nneigh < demo_settings.other_options.getInt("nneigh_stop") && not mapping.isMapped()) {
1199  nneigh += nneigh_step;
1200  if (demo_settings.other_options.getBool("do_test_placement")) {
1201  // try once with to path exclusivity
1202  const auto test_placement = mapOpsJustByConnectivity(fix_port, opgraph, mrrg, MapOpsJustByConnectivityOptions{makeNClosestNeighbourFinder(nneigh), acceptTheFirstSolution, {}, demo_settings.test_placement_options}, caches);
1203  timing_seq.tick("test placement for NN = " + std::to_string(nneigh), 0.0, &std::cout);
1204  if (not test_placement.isMapped()) {
1205  continue;
1206  }
1207  }
1208  // then try with the full options
1209  mapping = mapOpsJustByConnectivity(fix_port, opgraph, mrrg, MapOpsJustByConnectivityOptions{makeNClosestNeighbourFinder(nneigh), [&](auto& op_mapping) {
1210  return routeOpMappingByChoosingPaths(fix_port, op_mapping, opgraph, mrrg, { {}, acceptTheFirstSolution, {} }, caches);
1211  }, edgeCosters.at(demo_settings.outer_edge_coster_name), demo_settings.outer_options}, caches);
1212  timing_seq.tick("tried NN = " + std::to_string(nneigh), 0.0, &std::cout);
1213  }
1214 
1215  CHECK(mapping.isMapped());
1216  }
1217  }
1218 }
makeNClosestNeighbourFinder
auto makeNClosestNeighbourFinder(int min_neighbours)
Definition: MRRGProcedures.h:109
then_placement_should_fail_after_n_placements
void then_placement_should_fail_after_n_placements(const std::size_t nplace, const PLACEMENTS &placements, const Mapping &final_mapping)
Definition: HeuristicMappers_tests.cpp:259
CodeProfiling.h
makeDFG_Loop2Node
OpGraph makeDFG_Loop2Node()
Definition: OpGraphsForTesting.cpp:92
Visual.h
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
makeDFG_Loop3Node
OpGraph makeDFG_Loop3Node()
Definition: OpGraphsForTesting.cpp:103
ConfigStore::setString
void setString(std::string key, std::string value)
Definition: ConfigStore.h:128
MRRG
Definition: MRRG.h:216
dotparse.h
makeDFG_SelfLoop1NodeWith1ExtraFanout
OpGraph makeDFG_SelfLoop1NodeWith1ExtraFanout()
Definition: OpGraphsForTesting.cpp:70
OpGraphProcedures.h
makeDFG_MultiInputReconverging2121
OpGraph makeDFG_MultiInputReconverging2121()
Definition: OpGraphsForTesting.cpp:188
begin
auto begin(const SingleItemImmutableSet< VertexID > &siis)
Definition: Collections.h:137
makeDFG_Converging121
OpGraph makeDFG_Converging121()
Definition: OpGraphsForTesting.cpp:151
OpGraph::getOp
OpDescriptor getOp(const std::string &name) const
Definition: OpGraph.h:386
ConfigStore::setInt
void setInt(std::string key, long long value)
Definition: ConfigStore.h:129
acceptTheFirstSolution
const SolutionSelector acceptTheFirstSolution
Definition: HeuristicMappers.h:41
UserArchs.h
ConfigStore
Definition: ConfigStore.h:76
OpCode::ADD
@ ADD
ILPHeuristicMapperOptions
Definition: HeuristicMappers.h:57
OpGraph::serialize
void serialize(std::ostream &s) const
Definition: OpGraph.cpp:1070
mapOpsJustByConnectivity
Mapping mapOpsJustByConnectivity(std::unordered_map< std::string, std::string > fix_port, const OpGraph &opgraph, const MRRG &mrrg, ILPHeuristicMapperOptions options, ILPHeuristicMapperCaches caches, Mapping initial_mapping)
Definition: HeuristicMappers.cpp:1707
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
SCENARIO
SCENARIO("mapOpsJustByConnectivity Tests", "")
Definition: HeuristicMappers_tests.cpp:204
TEST_CASE
TEST_CASE("Heurmpr: path merging")
Definition: HeuristicMappers_tests.cpp:751
makeDFG_SelfLoop3Node
OpGraph makeDFG_SelfLoop3Node()
Definition: OpGraphsForTesting.cpp:80
makeDFG_Linear3Node
OpGraph makeDFG_Linear3Node()
Definition: OpGraphsForTesting.cpp:50
Mapping
Definition: Mapping.h:31
makeDFG_DeviceFiller
OpGraph makeDFG_DeviceFiller(const ConfigStore &options)
Definition: OpGraphsForTesting.cpp:1086
ILPHeuristicMapperCaches
Definition: HeuristicMappers.h:130
NeighbourFinder
std::function< FunctionalUnitNeighbours(const MRRG &, const std::vector< MRRG::NodeDescriptor > &)> NeighbourFinder
Definition: HeuristicMappers.h:26
findNDownstreamOps
std::set< OpGraph::OpDescriptor > findNDownstreamOps(const OpGraph &opgraph, const std::vector< OpGraphOp * > &starting_points, const std::ptrdiff_t n_ops)
Definition: OpGraph.cpp:1246
add_all
ConfigStore & add_all(ConfigStore &into, const ConfigStore &from)
Add (or set) all keys from from in into.
Definition: ConfigStore.h:251
FunctionalUnitNeighbours::getInfoFor
const NodeInfo & getInfoFor(MRRG::NodeDescriptor src, MRRG::NodeDescriptor dest) const
Definition: MRRGProcedures.h:59
createOpGraphFromConfig
OpGraph createOpGraphFromConfig(const ConfigGraph &config)
Definition: OpGraphProcedures.cpp:187
MappingStatus::failure
@ failure
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
makeDFG_MultiEdge11
OpGraph makeDFG_MultiEdge11(ConfigStore options)
Definition: OpGraphsForTesting.cpp:203
Module
Definition: Module.h:163
makeDFG_Huge
OpGraph makeDFG_Huge(const std::vector< int > &allowed_ids, ConfigStore options)
Definition: OpGraphsForTesting.cpp:408
mapViaConnectivityAndPathChoosing
Mapping mapViaConnectivityAndPathChoosing(std::unordered_map< std::string, std::string > fix_port, const OpGraph &opgraph, const MRRG &mrrg, const Mapping &initial_mapping, ILPHeuristicMapperOptions options_, ILPHeuristicMapperCaches caches)
Definition: HeuristicMappers.cpp:347
string_from_stream
std::string string_from_stream(F &&f)
Definition: Exception.h:95
FunctionalUnitNeighbours
Definition: MRRGProcedures.h:48
PrintOnDestructionChronoSequence
Definition: CodeProfiling.h:121
parseDot
ConfigGraph parseDot(std::istream &input, std::string file_name)
makeDFG_Larger
OpGraph makeDFG_Larger()
Definition: OpGraphsForTesting.cpp:335
routeOpMappingByChoosingPaths
Mapping routeOpMappingByChoosingPaths(std::unordered_map< std::string, std::string > fix_port, const Mapping &op_mapping, const OpGraph &opgraph, const MRRG &mrrg, RouteOpMappingByChoosingPathsOptions options, ILPHeuristicMapperCaches caches)
Definition: HeuristicMappers.cpp:1718
withRemappedOps
Mapping withRemappedOps(const Mapping &src, const std::unordered_map< OpGraph::NodeDescriptor, OpGraph::NodeDescriptor > &forward_mappings)
Definition: Mapping.cpp:288
end
auto end(const SingleItemImmutableSet< VertexID > &siis)
Definition: Collections.h:138
set_all
ConfigStore & set_all(ConfigStore &into, const ConfigStore &from)
Definition: ConfigStore.h:252
OpGraphOp
Definition: OpGraph.h:131
HeuristicMappers.h
print_container
void print_container(OSTREAM &&os, const CONTAINER &c, const T1 &element_separator, const T2 &container_prefix, const T3 &container_suffix, PRINTER &&element_printer=PRINTER{})
Definition: Collections.h:435
MRRGNode
Definition: MRRG.h:60
makeDFG_Tree12
OpGraph makeDFG_Tree12()
Definition: OpGraphsForTesting.cpp:128
noEdgeCosting
const EdgeCoster noEdgeCosting
Definition: HeuristicMappers.h:42
UserArchs::getGenerator
const ArchitectureGenerator & getGenerator(const std::string &identifer) const
Definition: UserArchs.h:154
makeDFG_Tree112
OpGraph makeDFG_Tree112()
Definition: OpGraphsForTesting.cpp:139
makeDFG_2NodeLoop4Node
OpGraph makeDFG_2NodeLoop4Node()
Definition: OpGraphsForTesting.cpp:115
UserArchs
Definition: UserArchs.h:43
ILPHeuristicMapperCaches::mrrg_proc_cache
MRRGProcedureCacheHandle * mrrg_proc_cache
Definition: HeuristicMappers.h:131
MRRG::getNode
NodeDescriptor getNode(int cycle, const std::string &name) const
Definition: MRRG.cpp:142
MRRG::initiationInterval
int initiationInterval() const
Definition: MRRG.h:346
MRRGProcedures.h
MRRGProcedureCacheHandle
Definition: MRRGProcedureCache.h:20
Mapping::isMapped
bool isMapped() const
Definition: Mapping.h:37
when_mapped_then_placement_should_fail_after_n_placements
void when_mapped_then_placement_should_fail_after_n_placements(const std::size_t nplace, const OpGraph &opgraph, const MRRG &mrrg, const NFINDER &neighbour_finder, const EDGE_COSTER &edge_coster, ConfigStore options={})
Definition: HeuristicMappers_tests.cpp:271
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
FunctionalUnitNeighbours::NodeInfo::distance
int distance
Definition: MRRGProcedures.h:51
filter
OpGraphTransformResult filter(const OpGraph &src, const std::set< OpGraph::OpDescriptor > &allowed_ops)
Definition: OpGraph.cpp:1212
filter_collection
auto filter_collection(const COLLECTION &base_container, UNARY_PREDICATE &&filter)
Definition: Collections.h:317
OpGraph
Definition: OpGraph.h:215
makeDFG_Large
OpGraph makeDFG_Large(bool require_non_NN_FUs)
Definition: OpGraphsForTesting.cpp:288
Mapping::setStatus
void setStatus(MappingStatus new_status)
Definition: Mapping.h:40
EdgeCoster
std::function< double(const FunctionalUnitNeighbours &fu_neighbours, const OpGraphOp &src_op, const MRRG::NodeDescriptor &src_node, const OpGraphOp &sink_op, const MRRG::NodeDescriptor &sink_node)> EdgeCoster
Definition: HeuristicMappers.h:34
Generated on Fri Nov 17 2023 12:26:44 for CGRA-ME by   doxygen 1.8.17