CGRA-ME
computeTrailsToBalance_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/OpGraphProcedures.h>
13 
15 #include <catch2/catch.hpp>
16 
17 namespace {
18 
19 struct ComputeTrailsToBalanceTestDescription {
20  int expected_number_of_noncyclic_trail_pairs;
21  int expected_number_of_cycle_paths;
22  std::string dfg_description;
23  std::function<OpGraph()> opgraph_generator;
24  auto getExpectedNumberOfNoncyclicTrailPairs() const { return expected_number_of_noncyclic_trail_pairs; }
25  auto getExpectedNumberOfCyclePaths() const { return expected_number_of_cycle_paths; }
26 };
27 
28 struct ComputeTrailsToBalanceTestDescriptionWithExpectedResult {
29  using EdgeSpec = std::pair<std::string, int>;
30  using Trail = std::vector<EdgeSpec>;
31  using TrailPair = std::pair<Trail,Trail>;
32  struct UnresolvedBalanceTrails {
33  std::vector<TrailPair> noncyclic_trail_pairs;
34  std::vector<Trail> cyclic_trails;
35  bool operator<(const UnresolvedBalanceTrails& rhs) const {
36  return std::tie(this->noncyclic_trail_pairs, this->cyclic_trails)
37  < std::tie( rhs.noncyclic_trail_pairs, rhs.cyclic_trails);
38  }
39  };
40 
41  std::string dfg_description;
42  std::function<OpGraph()> opgraph_generator;
62  std::set<UnresolvedBalanceTrails> expected_balance_trails;
63  auto getExpectedNumberOfNoncyclicTrailPairs() const { return expected_balance_trails.begin()->noncyclic_trail_pairs.size(); }
64  auto getExpectedNumberOfCyclePaths() const { return expected_balance_trails.begin()->cyclic_trails.size(); }
65 };
66 
67 template<typename TestDesc, typename Continuation = DoNothing>
68 void runComputeTrailsToBalanceTest(const TestDesc& test, Continuation&& continuation = {}) {
69  GIVEN("A " << test.dfg_description << " DFG") {
70  const auto opgraph = test.opgraph_generator();
71  WHEN("Computing paths to balance") {
72  const auto trails_to_balance = computeTrailsToBalance(opgraph);
73  if (false
74  // || test.dfg_description == "???" // eg. "tree 112"
75  ) {
76  opgraph.serialize(std::cout);
77  std::cout << '\n' << trails_to_balance << '\n';
78  }
79  THEN("There may be some paths to balance") {
80  // The total should never change -- the return value essentially describes a set
81  // of equalities, and it is expected to be a minimal set. However, row reductions
82  // can change re-convergence constraints into cycle constraints (or visa-versa), producing
83  // an equally correct output with different individual counts.
84  CHECK(test.getExpectedNumberOfNoncyclicTrailPairs() == (std::ptrdiff_t)trails_to_balance.noncyclic_trail_pairs.size());
85  CHECK(test.getExpectedNumberOfCyclePaths() == (std::ptrdiff_t)trails_to_balance.cyclic_trails.size());
86  CHECK(test.getExpectedNumberOfNoncyclicTrailPairs() + test.getExpectedNumberOfCyclePaths()
87  == (std::ptrdiff_t)trails_to_balance.noncyclic_trail_pairs.size() + (std::ptrdiff_t)trails_to_balance.cyclic_trails.size());
88 
89  continuation(test, opgraph, trails_to_balance);
90  }
91  }
92  }
93 }
94 
95 template<typename TestDesc>
96 void runComputeTrailsToBalanceTestWithExpectedResult(const TestDesc& test) {
97  runComputeTrailsToBalanceTest(test, [](const auto& test, const auto& opgraph, const auto& trails_to_balance) {
98  const auto resolve_names_into = [&](const auto& val_name_and_out_indices, auto& dest) {
99  for (const auto& val_name_and_oindex : val_name_and_out_indices) {
100  try {
101  const auto val = opgraph.getVal(val_name_and_oindex.first);
102  dest.push_back(OpGraph::EdgeDescriptor{val, val_name_and_oindex.second});
103  } catch (const std::exception& e) {
104  std::throw_with_nested(make_from_stream<std::logic_error>([&](auto&& s) {
105  s << "problem while resolving val name " << val_name_and_oindex.first
106  << " does it exist in the OpGraph?";
107  }));
108  }
109  }
110  };
111 
112  AND_THEN("The paths to balance should match") {
113  std::vector<TrailsToBalance> expected_trails_to_balance;
114 
115  for (const auto & expected : test.expected_balance_trails) {
116  expected_trails_to_balance.emplace_back();
117  for (const auto& val_name_and_oindex_trail_pair : expected.noncyclic_trail_pairs) {
118  TrailsToBalance::TrailPair trail_pair;
119  resolve_names_into(val_name_and_oindex_trail_pair.first, trail_pair.first);
120  resolve_names_into(val_name_and_oindex_trail_pair.second, trail_pair.second);
121  expected_trails_to_balance.back().noncyclic_trail_pairs.insert(std::move(trail_pair));
122  }
123  for (const auto& val_name_and_oindexs : expected.cyclic_trails) {
125  resolve_names_into(val_name_and_oindexs,cycle);
126  expected_trails_to_balance.back().cyclic_trails.insert(std::move(cycle));
127  }
128  }
129 
130  using Catch::Matchers::VectorContains;
131  CHECK_THAT(expected_trails_to_balance, VectorContains(trails_to_balance));
132  }
133  });
134 }
135 
136 } // end anon namespace
137 
138 SCENARIO ("Computing Trails To Balance -- Single Solution, Small", "") {
139  const auto& test = GENERATE(values<ComputeTrailsToBalanceTestDescriptionWithExpectedResult>({
140  { "linear 3-node", []{ return makeDFG_Linear3Node(); },
141  { { {}, // no re-convergences
142  {} } } }, // no cycles
143  { "1-node with self loop", []{ return makeDFG_SelfLoop1Node(); },
144  { { {}, // no re-convergences
145  { { {"op_l_out",0} } } } } },
146  { "3-node linear with self loop", []{ return makeDFG_SelfLoop3Node(); },
147  { { {}, // no re-convergences
148  { { {"op_l_out",1} } } } } },
149  { "2-node loop", []{ return makeDFG_Loop2Node(); },
150  { { {}, // no re-convergences
151  { { {"op_a_out",0}, {"op_b_out",0} } } } } },
152  { "3-node loop", []{ return makeDFG_Loop3Node(); },
153  { { {}, // no re-convergences
154  { { {"op_a_out",0}, {"op_b_out",0}, {"op_c_out",0} } } } } },
155  { "4-node with 2-node loop", []{ return makeDFG_2NodeLoop4Node(); },
156  { { {}, // no re-convergences
157  { { {"op_l_out",0}, {"op_m_out",1} } } } } },
158  { "tree 112", []{ return makeDFG_Tree112(); },
159  { { {}, // no re-convergences
160  {} } } }, // no cycles
161  { "re-converging 121", []{ return makeDFG_Converging121(); },
162  { { { { { {"op_a_out",0}, {"op_b_out", 0} }, { {"op_a_out",1}, {"op_b2_out",0} } } },
163  {} } } }, // no cycles
164  { "multi-input re-converging 2121", []{ return makeDFG_MultiInputReconverging2121(); },
165  { { { { { {"op_b_out",0}, {"op_c1_out",0} }, { {"op_b_out",1}, {"op_c2_out",0} } } },
166  {} } } }, // no cycles
167  { "Multi Edge 11", []{ return makeDFG_MultiEdge11(); },
168  { { { { { {"op_a_out",0}, }, { {"op_a_out",1} } } },
169  {} } } }, // no cycles
170  }));
171 
172  runComputeTrailsToBalanceTestWithExpectedResult(test);
173 }
174 
175 SCENARIO ("Computing Trails To Balance -- Single Solution, Large", "") {
176  const auto& test = GENERATE(values<ComputeTrailsToBalanceTestDescriptionWithExpectedResult>({
177  { "large requiring only NN FUs", []{ return makeDFG_Large(false); },
178  { { { { { {"add0_out",0}, {"mul2_out",0}, {"load4_out",0}, {"add10_out",0} }, { {"add0_out",2}, {"mul11_out",0}, {"load13_out",0} } } },
179  { { {"add0_out", 3} },
180  { {"add16_out",0} } } } } },
181  }));
182 
183  runComputeTrailsToBalanceTestWithExpectedResult(test);
184 }
185 
186 SCENARIO ("Computing Trails To Balance -- Non-Unique Solution, Small", "") {
187  const auto& test = GENERATE(values<ComputeTrailsToBalanceTestDescriptionWithExpectedResult>({
188  { "TriangeWithAntiparellelDoubledBottomEdge",[]{ return makeDFG_TriangeWithAntiparellelDoubledBottomEdge(); },
189  // produces either solution; depends on pointer comparisons
190  { {
191  { { { {"op_i_out",0} }, { {"op_i_out",1}, {"op_b_out",0} } } },
192  { { {"op_a_out",0}, {"op_b_out",0} } }
193  }, {
194  { { { {"op_i_out",0}, {"op_a_out",0} }, { {"op_i_out",1} } } },
195  { { {"op_a_out",0}, {"op_b_out",0} } }
196  } }
197  },
198  { "MultiInputReconverging3x2Grid" ,[]{ return makeDFG_MultiInputReconverging3x2Grid(); },
199  { { { { { {"op_i1_out",0}, {"op_a1_out",0} }, { {"op_i1_out",1}, {"op_a2_out",1} } },
200  { { {"op_i1_out",0}, {"op_a1_out",0}, {"op_b1_out",0} }, { {"op_i1_out",1}, {"op_a2_out",0}, {"op_b2_out",0} } } },
201  {} } } }, // no cycles
202  }));
203 
204  runComputeTrailsToBalanceTestWithExpectedResult(test);
205 }
206 
207 SCENARIO ("Computing Trails To Balance -- Non-Unique Solutions, Large", "") {
208  // changes to the algorithm may result in different results, though the total should always be the same
209  const auto& test = GENERATE(values<ComputeTrailsToBalanceTestDescription>({
210  { 3, 2, "large requiring non NN FUs", []{ return makeDFG_Large(true); } },
211  { 5, 0, "DeviceFiller 3c2x2 -- no loops", []{ return makeDFG_DeviceFiller({{{"width", "2"}, {"height","2"}, {"num_contexts", "3"}}});; } },
212  { 5, 4, "DeviceFiller 3c2x2 -- loops", []{ return makeDFG_DeviceFiller({{{"width", "2"}, {"height","2"}, {"num_contexts", "3"}, {"self_loop_via_regfile", "yes"}}});; } },
213  { 5, 4, "DeviceFiller 3c2x2 -- loops & consts", []{ return makeDFG_DeviceFiller({{{"width", "2"}, {"height","2"}, {"num_contexts", "3"}, {"self_loop_via_regfile", "yes"}, {"num_consts_in_pe", "2"}}});; } },
214  { 3, 2, "larger", []{ return makeDFG_Larger(); } },
215  {103, 43, "huge", []{ return makeDFG_Huge(); } },
216  }));
217 
218  runComputeTrailsToBalanceTest(test);
219 }
computeTrailsToBalance
TrailsToBalance computeTrailsToBalance(const OpGraph &opgraph)
Definition: OpGraphProcedures.cpp:40
makeDFG_Loop2Node
OpGraph makeDFG_Loop2Node()
Definition: OpGraphsForTesting.cpp:92
makeDFG_SelfLoop1Node
OpGraph makeDFG_SelfLoop1Node()
Definition: OpGraphsForTesting.cpp:60
makeDFG_Loop3Node
OpGraph makeDFG_Loop3Node()
Definition: OpGraphsForTesting.cpp:103
OpGraphProcedures.h
makeDFG_MultiInputReconverging2121
OpGraph makeDFG_MultiInputReconverging2121()
Definition: OpGraphsForTesting.cpp:188
makeDFG_Converging121
OpGraph makeDFG_Converging121()
Definition: OpGraphsForTesting.cpp:151
makeDFG_SelfLoop3Node
OpGraph makeDFG_SelfLoop3Node()
Definition: OpGraphsForTesting.cpp:80
makeDFG_Linear3Node
OpGraph makeDFG_Linear3Node()
Definition: OpGraphsForTesting.cpp:50
makeDFG_DeviceFiller
OpGraph makeDFG_DeviceFiller(const ConfigStore &options)
Definition: OpGraphsForTesting.cpp:1086
TrailsToBalance::TrailPair
std::pair< Trail, Trail > TrailPair
Definition: OpGraphProcedures.h:70
Functional.h
operator<
bool operator<(const OpGraph::EdgeDescriptor &lhs, const OpGraph::EdgeDescriptor &rhs)
Definition: OpGraph.h:533
makeDFG_TriangeWithAntiparellelDoubledBottomEdge
OpGraph makeDFG_TriangeWithAntiparellelDoubledBottomEdge()
Definition: OpGraphsForTesting.cpp:222
OpGraphsForTesting.hpp
makeDFG_MultiEdge11
OpGraph makeDFG_MultiEdge11(ConfigStore options)
Definition: OpGraphsForTesting.cpp:203
makeDFG_Huge
OpGraph makeDFG_Huge(const std::vector< int > &allowed_ids, ConfigStore options)
Definition: OpGraphsForTesting.cpp:408
makeDFG_Larger
OpGraph makeDFG_Larger()
Definition: OpGraphsForTesting.cpp:335
makeDFG_Tree112
OpGraph makeDFG_Tree112()
Definition: OpGraphsForTesting.cpp:139
makeDFG_2NodeLoop4Node
OpGraph makeDFG_2NodeLoop4Node()
Definition: OpGraphsForTesting.cpp:115
OpGraph::EdgeDescriptor
Definition: OpGraph.h:224
makeDFG_MultiInputReconverging3x2Grid
OpGraph makeDFG_MultiInputReconverging3x2Grid()
Definition: OpGraphsForTesting.cpp:234
TrailsToBalance::Trail
OpGraph::Walk Trail
Definition: OpGraphProcedures.h:69
OpGraph
Definition: OpGraph.h:215
makeDFG_Large
OpGraph makeDFG_Large(bool require_non_NN_FUs)
Definition: OpGraphsForTesting.cpp:288
SCENARIO
SCENARIO("Computing Trails To Balance -- Single Solution, Small", "")
Definition: computeTrailsToBalance_tests.cpp:138