CGRA-ME
general_mapper_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/ConfigStore.h>
12 #include <CGRA/Mapper.h>
13 #include <CGRA/Module.h>
14 #include <CGRA/MRRG.h>
15 #include <CGRA/OpGraph.h>
16 #include <CGRA/user-inc/UserArchs.h>
17 
18 #include "testutils/OpGraphsForTesting.hpp"
19 
20 #include <catch2/catch.hpp>
21 
22 namespace {
23 
24 Module god_module("top", ""); // used for tests in this file
25 
26 MRRG makeMRRG_Simple(int II, ConfigStore options);
27 MRRG makeMRRG_SimpleFlow(int II, ConfigStore options);
28 
29 [[nodiscard]]
30 MRRG removeUselessRoutingNodes(MRRG mrrg, ConfigStore options);
31 
32 struct MapperTest {
33  bool connectivity_available; // false => all mappers should fail
34  bool possible_to_balance_latency; // false => mappers that balance should fail
35  bool requires_recomputation; // true => mappers that cannot do re-computation should fail
36  std::string cgra_description;
37  std::string opgraph_description;
38  std::function<MRRG()> mrrg_generator;
39  std::function<OpGraph()> opgraph_generator;
40 };
41 
42 struct MappingApproch {
43  std::string description;
44  std::string mapper_id;
45  bool balance_latency;
46  bool recomputation_enabled;
47 };
48 
49 MRRG makeMRRG_112x21DAG(int latency_of_d1) {
50  MRRG mrrg(1);
51  const auto a = mrrg.insert( MRRGNode::make_function(&god_module, 32, 0, "a", 0, {OpCode::ADD})).first;
52  const auto b = mrrg.insert(a, MRRGNode::make_routing (&god_module, 32, 0, "b", 0)).first;
53  const auto c1 = mrrg.insert(b, MRRGNode::make_routing (&god_module, 32, 0, "c1", 0)).first;
54  const auto c2 = mrrg.insert(b, MRRGNode::make_routing (&god_module, 32, 0, "c2", 0)).first;
55  const auto d1 = mrrg.insertMultiFanin({c1,c2}, MRRGNode::make_operand_pin(&god_module, 32, 0, "d1", {Operands::BINARY_LHS}, latency_of_d1)).first;
56  const auto d2 = mrrg.insertMultiFanin({c1,c2}, MRRGNode::make_operand_pin(&god_module, 32, 0, "d2", {Operands::BINARY_RHS}, 0)).first;
57  const auto f = mrrg.insertMultiFanin({d1,d2}, MRRGNode::make_function (&god_module, 32, 0, "f", 0, {OpCode::ADD})).first;
58  mrrg.insert(f, MRRGNode::make_routing(&god_module, 32, 0, "f_dummy_fanout_for_ILPMapper", 0));
59 
60  verifyAndPrintReport(mrrg, std::cout, true, true);
61  return mrrg;
62 }
63 
64 MRRG makeMRRG_221DAG(int mrrg_ii, int latency_of_c1) {
65  MRRG mrrg(mrrg_ii);
66  const int cyc2 = latency_of_c1 % mrrg_ii;
67  const auto a1 = mrrg.insert( MRRGNode::make_function(&god_module, 32, 0, "a1", 0, {OpCode::ADD})).first;
68  const auto a2 = mrrg.insert( MRRGNode::make_function(&god_module, 32, cyc2, "a2", 0, {OpCode::ADD})).first;
69  const auto c1 = mrrg.insert(a1, MRRGNode::make_routing (&god_module, 32, 0, "c1", latency_of_c1)).first;
70  const auto c2 = mrrg.insert(a2, MRRGNode::make_routing (&god_module, 32, cyc2, "c2", 0)).first;
71  const auto d1 = mrrg.insert(c1, MRRGNode::make_operand_pin(&god_module, 32, cyc2, "d1", {Operands::BINARY_LHS}, 0)).first;
72  const auto d2 = mrrg.insert(c2, MRRGNode::make_operand_pin(&god_module, 32, cyc2, "d2", {Operands::BINARY_RHS}, 0)).first;
73  const auto f = mrrg.insertMultiFanin({d1,d2}, MRRGNode::make_function(&god_module, 32, cyc2, "f", 0, {OpCode::ADD})).first;
74  mrrg.insert(f, MRRGNode::make_routing(&god_module, 32, cyc2, "f_dummy_fanout_for_ILPMapper", 0));
75 
76  verifyAndPrintReport(mrrg, std::cout, true, true);
77  return mrrg;
78 }
79 
80 MRRG makeMRRG_222DAG(int mrrg_ii, int latency_of_c1) {
81  MRRG mrrg(mrrg_ii);
82  const int cyc2 = latency_of_c1 % mrrg_ii;
83  const auto a1 = mrrg.insertMultiFanin({}, MRRGNode::make_function( &god_module, 32, 0, "a1", 0, {OpCode::ADD})).first;
84  const auto a2 = mrrg.insertMultiFanin({}, MRRGNode::make_function( &god_module, 32, 0, "a2", 0, {OpCode::ADD})).first;
85  const auto c1 = mrrg.insertMultiFanin({a1}, MRRGNode::make_routing( &god_module, 32, 0, "c1", latency_of_c1)).first;
86  const auto c2 = mrrg.insertMultiFanin({a2}, MRRGNode::make_routing( &god_module, 32, 0, "c2", 0)).first;
87  const auto d1 = mrrg.insertMultiFanin({c1}, MRRGNode::make_operand_pin(&god_module, 32, cyc2, "d1", {Operands::BINARY_LHS, Operands::BINARY_ANY}, 0)).first;
88  const auto d2 = mrrg.insertMultiFanin({c2}, MRRGNode::make_operand_pin(&god_module, 32, 0, "d2", {Operands::BINARY_RHS, Operands::BINARY_ANY}, 0)).first;
89  const auto f1 = mrrg.insertMultiFanin({d1}, MRRGNode::make_function( &god_module, 32, cyc2, "f1", 0, {OpCode::ADD})).first;
90  const auto f2 = mrrg.insertMultiFanin({d2}, MRRGNode::make_function( &god_module, 32, 0, "f2", 0, {OpCode::ADD})).first;
91  mrrg.insert(f1, MRRGNode::make_routing(&god_module, 32, cyc2, "f1_dummy_fanout_for_ILPMapper", 0));
92  mrrg.insert(f2, MRRGNode::make_routing(&god_module, 32, 0, "f2_dummy_fanout_for_ILPMapper", 0));
93 
94  verifyAndPrintReport(mrrg, std::cout, true, true);
95  return mrrg;
96 }
97 
98 MRRG makeMRRG_131DAG(int mrrg_ii, int latency_of_c1) {
99  MRRG mrrg(mrrg_ii);
100  const auto a1 = mrrg.insertMultiFanin({}, MRRGNode::make_function(&god_module, 32, 0, "a1", 0, {OpCode::ADD})).first;
101  const auto b1 = mrrg.insertMultiFanin({a1}, MRRGNode::make_routing( &god_module, 32, 0, "b1", 0)).first;
102  const auto c1 = mrrg.insertMultiFanin({b1}, MRRGNode::make_routing( &god_module, 32, 0, "c1", latency_of_c1)).first;
103  const auto c2 = mrrg.insertMultiFanin({b1}, MRRGNode::make_routing( &god_module, 32, 0, "c2", 0)).first;
104  const auto c3 = mrrg.insertMultiFanin({b1}, MRRGNode::make_routing( &god_module, 32, 0, "c3", 0)).first;
105  const auto d1 = mrrg.insertMultiFanin({c1}, MRRGNode::make_routing( &god_module, 32, 0, "d1", 0)).first;
106  const auto d2 = mrrg.insertMultiFanin({c2}, MRRGNode::make_routing( &god_module, 32, 0, "d2", 0)).first;
107  const auto d3 = mrrg.insertMultiFanin({c3}, MRRGNode::make_routing( &god_module, 32, 0, "d3", 0)).first;
108  const auto f1 = mrrg.insertMultiFanin({d1,d2,d3}, MRRGNode::make_function(&god_module, 32, 0, "f1", 0, {OpCode::ADD})).first;
109  mrrg.insert(f1, MRRGNode::make_routing(&god_module, 32, 0, "f1_dummy_fanout_for_ILPMapper", 0));
110 
111  verifyAndPrintReport(mrrg, std::cout, true, true);
112  return mrrg;
113 }
114 
115 MRRG makeMRRG_121DAG(int mrrg_ii, int latency_of_c1) {
116  MRRG mrrg(mrrg_ii);
117  const auto a1 = mrrg.insertMultiFanin({}, MRRGNode::make_function(&god_module, 32, 0, "a1", 0, {OpCode::ADD})).first;
118  const auto b1 = mrrg.insertMultiFanin({a1}, MRRGNode::make_routing( &god_module, 32, 0, "b1", 0)).first;
119  const auto c1 = mrrg.insertMultiFanin({b1}, MRRGNode::make_routing( &god_module, 32, 0, "c1", latency_of_c1)).first;
120  const auto c2 = mrrg.insertMultiFanin({b1}, MRRGNode::make_routing( &god_module, 32, 0, "c2", 0)).first;
121  const auto d1 = mrrg.insertMultiFanin({c1}, MRRGNode::make_routing( &god_module, 32, 0, "d1", 0)).first;
122  const auto d2 = mrrg.insertMultiFanin({c2}, MRRGNode::make_routing( &god_module, 32, 0, "d2", 0)).first;
123  const auto f1 = mrrg.insertMultiFanin({d1,d2}, MRRGNode::make_function(&god_module, 32, 0, "f1", 0, {OpCode::ADD})).first;
124  mrrg.insert(f1, MRRGNode::make_routing(&god_module, 32, 0, "f1_dummy_fanout_for_ILPMapper", 0));
125 
126  verifyAndPrintReport(mrrg, std::cout, true, true);
127  return mrrg;
128 }
129 
130 MRRG makeMRRG_231DAG(int mrrg_ii, int latency_of_c1) {
131  MRRG mrrg(mrrg_ii);
132  const int cyc2 = latency_of_c1 % mrrg_ii;
133  const auto a1 = mrrg.insertMultiFanin({}, MRRGNode::make_function( &god_module, 32, 0, "a1", 0, {OpCode::ADD})).first;
134  const auto a2 = mrrg.insertMultiFanin({}, MRRGNode::make_function( &god_module, 32, cyc2, "a2", 0, {OpCode::ADD})).first;
135  const auto b1 = mrrg.insertMultiFanin({a1}, MRRGNode::make_routing( &god_module, 32, 0, "b1", 0)).first;
136  const auto b2 = mrrg.insertMultiFanin({a2}, MRRGNode::make_routing( &god_module, 32, cyc2, "b2", 0)).first;
137  const auto c1 = mrrg.insertMultiFanin({b1}, MRRGNode::make_routing( &god_module, 32, 0, "c1", latency_of_c1)).first;
138  const auto c2 = mrrg.insertMultiFanin({b2}, MRRGNode::make_routing( &god_module, 32, cyc2, "c2", 0)).first;
139  const auto c3 = mrrg.insertMultiFanin({b2}, MRRGNode::make_routing( &god_module, 32, cyc2, "c3", 0)).first;
140  const auto d1 = mrrg.insertMultiFanin({c1}, MRRGNode::make_operand_pin(&god_module, 32, cyc2, "d1", {Operands::BINARY_LHS, Operands::BINARY_ANY}, 0)).first;
141  const auto d2 = mrrg.insertMultiFanin({c2,c3}, MRRGNode::make_operand_pin(&god_module, 32, cyc2, "d2", {Operands::BINARY_RHS, Operands::BINARY_ANY}, 0)).first;
142  const auto f1 = mrrg.insertMultiFanin({d1,d2}, MRRGNode::make_function( &god_module, 32, cyc2, "f1", 0, {OpCode::ADD})).first;
143  mrrg.insertMultiFanin({f1}, MRRGNode::make_routing(&god_module, 32, cyc2, "f1_dummy_fanout_for_ILPMapper", 0));
144 
145  verifyAndPrintReport(mrrg, std::cout, true, true);
146  return mrrg;
147 }
148 
149 } // end anon namespace
150 
155 SCENARIO("General Mapper Tests -- Tiny MRRGs", "") {
156  const auto mapper_registry = AutoRegisterMapper::getDefaultRegistry();
157 
159  // Test listings
161 
162  const auto& test = GENERATE_REF(values<MapperTest>({
163  { true, true, false, "3x1t1 ortho", "linear 3-node",
164  []{return makeMRRG_Simple(1, {{"width",1},{"height",3}});},
165  []{return makeDFG_Linear3Node();},
166  },
167  { true, true, false, "1x3t1 ortho", "linear 3-node",
168  []{return makeMRRG_Simple(1, {{"width",3},{"height",1}});},
169  []{return makeDFG_Linear3Node();},
170  },
171  // Not enough FU nodes
172  { false, false, false, "1x2t1 ortho", "linear 3-node",
173  []{return makeMRRG_Simple(1, {{"width",2},{"height",1}});},
174  []{return makeDFG_Linear3Node();},
175  },
176  // No support for loops in MRRG, but opgraph needs it
177  { false, false, false, "1x1t1 ortho without self-feedback", "1 node self-loop",
178  []{return makeMRRG_Simple(1, {{"width",1},{"height",1},{"fu_self_feedback",false}});},
179  []{return makeDFG_SelfLoop1Node();},
180  },
181  // MRRG could support loops, but there's no latency on the FU, so we can't use it
182  { true, false, false, "1x1t1 ortho with self-feedback, but no FU latency", "1 node self-loop",
183  []{return makeMRRG_Simple(1, {{"width",1},{"height",1}});},
184  []{return makeDFG_SelfLoop1Node();},
185  },
186  // Same as above, but with latency, so self-feedback is useful
187  { true, true, false, "1x1t1 ortho with self-feedback and FU latency of 1", "1 node self-loop",
188  []{return makeMRRG_Simple(1, {{"width",1},{"height",1},{"fu_latency",1}});},
189  []{return makeDFG_SelfLoop1Node();},
190  },
191  // Passing version of the one below
192  { true, true, false, "2x2t1 flow ortho with self-feedback and FU latency of 1", "Converging 121",
193  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",2},{"fu_latency",1}});},
194  []{return makeDFG_Converging121();},
195  },
196  // Forced latency imbalance by having one FU with longer latency. Flow connections force mapping to use it.
197  { true, false, false, "2x2t1 flow ortho with self-feedback and FU latency of 1 except for FU 01", "Converging 121",
198  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",2},{"fu_latency",1},{xyName("fu_latency",{0,1}),0}});},
199  []{return makeDFG_Converging121();},
200  },
201  // Only possible to map with re-computation; duplicating root of the 'tree' DFG
202  { true, true, true, "2x1t2 flow ortho without self-feedback", "Tree 12",
203  []{return makeMRRG_SimpleFlow(2, {{"width",2},{"height",1},{"fu_self_feedback",false}});},
204  []{return makeDFG_Tree12();},
205  },
206  // Passing version of the one below
207  { true, true, false, "2x2t1 flow ortho supporting only commutative ops", "Converging 21 with only commutative operands",
208  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",2},{"operand_tags","only_commutative"}});},
209  []{return makeDFG_Converging21({{"operands","commutative"}});},
210  },
211  // DFG needs LHS & RHS tags, but MRRG only has any2inputs
212  { false, true, false, "2x2t1 flow ortho supporting only commutative ops", "Converging 21 with only non-commutative operands",
213  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",2},{"operand_tags","only_commutative"}});},
214  []{return makeDFG_Converging21({{"operands","non-commutative"}});},
215  },
216  // Passing version of the one above
217  { true, true, false, "2x2t1 flow ortho", "Converging 21 with only non-commutative operands",
218  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",2}});},
219  []{return makeDFG_Converging21({{"operands","non-commutative"}});},
220  },
221  // Another passing version of the one above
222  { true, true, false, "3x3t1 flow ortho", "Converging 21 with only untagged operands",
223  []{return makeMRRG_SimpleFlow(1, {{"width",3},{"height",3}});},
224  []{return makeDFG_Converging21({{"operands","untagged"}});},
225  },
226  // Test routing directionality
227  { false, false, false, "1x2t1 flow ortho, op support backwards", "Linear 2-node, hetero ops",
228  []{return makeMRRG_SimpleFlow(1, {
229  {"width",1},{"height",2},{"fu_arity",1},{"fu_self_feedback",false},{xyName("fu_ops",{0,0}),"add"},{xyName("fu_ops",{0,1}),"mul"}});},
230  []{return makeDFG_Linear2Node({{"ops", "mul,add"}});},
231  },
232  // multi-edge DFG tests, with operands
233  { true, true, false, "2x1t1 flow ortho", "Multi-edge 11, no operand tags",
234  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1}});},
235  []{return makeDFG_MultiEdge11({{"operands","untagged"}});},
236  },
237  { true, true, false, "2x1t1 flow ortho", "Multi-edge 11, non-commutative",
238  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1}});},
239  []{return makeDFG_MultiEdge11({{"operands","non-commutative"}});},
240  },
241  { true, true, false, "2x1t1 flow ortho", "Multi-edge 11, commutative",
242  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1}});},
243  []{return makeDFG_MultiEdge11({{"operands","commutative"}});},
244  },
245  { true, true, false, "2x1t1 flow ortho", "Multi-edge 11, mixed_lhs",
246  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1}});},
247  []{return makeDFG_MultiEdge11({{"operands","mixed_lhs"}});},
248  },
249  { true, true, false, "2x1t1 flow ortho", "Multi-edge 11, mixed_any",
250  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1}});},
251  []{return makeDFG_MultiEdge11({{"operands","mixed_any"}});},
252  },
253  // Untagged val-edge can use the LHS-tagged routing, and any2input-tagged val-edge can use the untagged routing
254  { true, true, false, "2x1t1 flow ortho only_one_any operands", "Multi-edge 11, mixed_lhs",
255  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1},{"operand_tags","only_one_any"}});},
256  []{return makeDFG_MultiEdge11({{"operands","mixed_lhs"}});},
257  },
258  { false, false, false, "2x1t1 flow ortho only_commutative operands", "Multi-edge 11, mixed_lhs",
259  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1},{"operand_tags","only_commutative"}});},
260  []{return makeDFG_MultiEdge11({{"operands","mixed_lhs"}});},
261  },
262  { true, true, false, "2x1t1 flow ortho only_one_any operands", "Multi-edge 11, mixed_any",
263  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1},{"operand_tags","only_one_any"}});},
264  []{return makeDFG_MultiEdge11({{"operands","mixed_any"}});},
265  },
266 
267  // Some tests to make sure that the mappers route to enough inputs.
268  // It's electrically OK for signals from the same source to share rotuing,
269  // but the data needs to show up at the right number of inputs!
270  // 1-input FU -- no tags
271  { false, false, false, "2x1t1 flow ortho, fu_arity 1", "Multi-edge 11, no operands",
272  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1},{"fu_arity",1},{"operand_tags","none"},{"fu_self_feedback",false}});},
273  []{return makeDFG_MultiEdge11({{"operands","untagged"}});},
274  },
275  // 1-input FU test with an operand tag on the MRRG
276  { false, false, false, "2x1t1 flow ortho, fu_arity 1, all_lhs", "Multi-edge 11, no operands",
277  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1},{"fu_arity",1},{"operand_tags","all_lhs"},{"fu_self_feedback",false}});},
278  []{return makeDFG_MultiEdge11({{"operands","untagged"}});},
279  },
280  // 1-input FU test with one DFG edge being tagged
281  { false, false, false, "2x1t1 flow ortho, fu_arity 1, all_lhs", "Multi-edge 11, one-lhs-one-untagged",
282  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1},{"fu_arity",1},{"operand_tags","none"},{"fu_self_feedback",false}});},
283  []{return makeDFG_MultiEdge11({{"operands","mixed_lhs"}});},
284  },
285  // 1-input FU test with both MRRG and DFG operand tags
286  { false, false, false, "2x1t1 flow ortho, fu_arity 1, all_lhs", "Multi-edge 11, one-lhs-one-untagged",
287  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1},{"fu_arity",1},{"operand_tags","all_lhs"},{"fu_self_feedback",false}});},
288  []{return makeDFG_MultiEdge11({{"operands","mixed_lhs"}});},
289  },
290  // both DFG edges are tagged the same, and so could use the same input
291  { false, false, false, "2x1t1 flow ortho, fu_arity 2", "Multi-edge 11, all lhs",
292  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1},{"fu_arity",2},{"operand_tags","all"},{"fu_self_feedback",false}});},
293  []{return makeDFG_MultiEdge11({{"operands","all_lhs"}});},
294  },
295  // passing version of the above
296  { true, true, false, "2x1t1 flow ortho, fu_arity 2 all_lhs", "Multi-edge 11, all lhs",
297  []{return makeMRRG_SimpleFlow(1, {{"width",2},{"height",1},{"fu_arity",2},{"operand_tags","all_lhs"},{"fu_self_feedback",false}});},
298  []{return makeDFG_MultiEdge11({{"operands","all_lhs"}});},
299  },
300  // It's not enough that there are 2 paths to one usable FU input
301  { false, false, false, "112x21DAG: fu_arity 2, crossbar at input, lhs-rhs", "Multi-edge 11, all_lhs",
302  []{return makeMRRG_112x21DAG(0);},
303  []{return makeDFG_MultiEdge11({{"operands","all_lhs"}});},
304  },
305  // passing version of the above
306  { true, true, false, "112x21DAG: fu_arity 2, crossbar at input, lhs-rhs", "Multi-edge 11 lhs-rhs",
307  []{return makeMRRG_112x21DAG(0);},
308  []{return makeDFG_MultiEdge11({{"operands","non-commutative"}});},
309  },
310  // not possible to balance latency -- no tag constraints
311  { true, false, false, "112x21DAG: fu_arity 2, crossbar at input, lhs-rhs, d1 latency 1", "Multi-edge 11 untagged",
312  []{return makeMRRG_112x21DAG(1);},
313  []{return makeDFG_MultiEdge11({{"operands","untagged"}});},
314  },
315  // not possible to balance latency -- tag constrained
316  { true, false, false, "112x21DAG: fu_arity 2, crossbar at input, lhs-rhs, d1 latency 1", "Multi-edge 11 lhs-rhs",
317  []{return makeMRRG_112x21DAG(1);},
318  []{return makeDFG_MultiEdge11({{"operands","non-commutative"}});},
319  },
320  // test re-computation over a mult-edge -- fails due to operand tags
321  { false, false, false, "221DAG: II=2, c1 latenecy 0, lhs-rhs", "Multi-edge 11 all_lhs",
322  []{return makeMRRG_221DAG(2, 0);},
323  []{return makeDFG_MultiEdge11({{"operands","all_lhs"}});},
324  },
325  // passing version of above
326  { true, true, true, "221DAG: II=2, c1 latenecy 0, lhs-rhs", "Multi-edge 11 lhs-rhs",
327  []{return makeMRRG_221DAG(2, 0);},
328  []{return makeDFG_MultiEdge11({{"operands","non-commutative"}});},
329  },
330  // test re-computation and latency over a mult-edge -- fails due to operand tags
331  { false, false, false, "221DAG: II=2, c1 latenecy 1, lhs-rhs", "Multi-edge 11 all_lhs",
332  []{return makeMRRG_221DAG(2, 1);},
333  []{return makeDFG_MultiEdge11({{"operands","all_lhs"}});},
334  },
335  // passing version of above
336  { true, true, true, "221DAG: II=2, c1 latenecy 1, lhs-rhs", "Multi-edge 11 lhs-rhs",
337  []{return makeMRRG_221DAG(2, 1);},
338  []{return makeDFG_MultiEdge11({{"operands","non-commutative"}});},
339  },
340  // same as above but exit context II-1 twice
341  { true, true, true, "221DAG: II=2, c1 latenecy 3, lhs-rhs", "Multi-edge 11 lhs-rhs",
342  []{return makeMRRG_221DAG(2, 3);},
343  []{return makeDFG_MultiEdge11({{"operands","non-commutative"}});},
344  },
345  // both operands must go to the same op node, but that's impossible
346  { false, false, false, "222DAG: II=1, c1 latenecy 0", "Multi-edge 11 lhs-rhs",
347  []{return makeMRRG_222DAG(1, 0);},
348  []{return makeDFG_MultiEdge11({{"operands","non-commutative"}});},
349  },
350  // same MRRG as above, but with a compatible DFG
351  { true, true, false, "222DAG: II=1, c1 latenecy 0", "Parallel 11-11",
352  []{return makeMRRG_222DAG(1, 0);},
353  []{return makeDFG_Parallel11_11();},
354  },
355  // 2 paths to one input -- might confuse mapper
356  { true, true, true, "231DAG: II=1, c1 latenecy 0", "Multi-edge 11 commutative",
357  []{return makeMRRG_231DAG(1, 0);},
358  []{return makeDFG_MultiEdge11({{"operands","commutative"}});},
359  },
360  // Triple DFG edge, double path MRRG
361  { false, false, false, "121DAG: II=1, c1 latenecy 0", "Triple-edge 11",
362  []{return makeMRRG_121DAG(1, 0);},
363  []{return makeDFG_MultiEdge11({{"num_edges", 3}});},
364  },
365  // Triple DFG edge, triple path MRRG
366  { true, true, false, "131DAG: II=1, c1 latenecy 0", "Triple-edge 11",
367  []{return makeMRRG_131DAG(1, 0);},
368  []{return makeDFG_MultiEdge11({{"num_edges", 3}});},
369  },
370  }));
371 
372  const auto approach = GENERATE_REF(values<MappingApproch>({
373  {"Exact ILP with partial latency balancing", "ILPMapper", true, false},
374  {"Exact ILP with latency balancing", "ILPMapper", true, false},
375  {"Heuristic ILP with latency balancing", "ILPHeuristicMapper", true, false},
376  {"Heuristic ILP without latency balancing", "ILPHeuristicMapper", false, false},
377  {"Heuristic ILP with re-computation and latency balancing", "ILPHeuristicMapper", true, true},
378  {"Heuristic ILP with re-computation but without latency balancing", "ILPHeuristicMapper", false, true},
379  }));
380 
382  // Interpret configuration
384 
385  // common settings
386  auto args = mapper_registry.getAllRegisteredArgDefaults();
387 
388  // generic settings
389  if (not approach.balance_latency && approach.mapper_id == "ILPHeuristicMapper") {
390  args.setBool(approach.mapper_id + ".allow_unbalanced_latency", true);
391  }
392  if (approach.description == "Exact ILP with latency balancing") {
393  args.setBool(approach.mapper_id + ".enable_topological_order_mode", true);
394  }
395  if (approach.recomputation_enabled) {
396  args.setBool(approach.mapper_id + ".allow_recomputation", true);
397  }
398 
399  const bool expect_to_map = test.connectivity_available
400  && (not approach.balance_latency || test.possible_to_balance_latency)
401  && (approach.recomputation_enabled || not test.requires_recomputation);
402 
404  // Run the test
406 
407  GIVEN("A '" << test.cgra_description << "' CGRA") {
408  ConfigStore remove_useless_routing_nodes_config;
409  if (approach.mapper_id == "ILPMapper") {
410  remove_useless_routing_nodes_config.setBool("fus_must_have_fanout", true);
411  }
412  const auto& mrrg = removeUselessRoutingNodes(test.mrrg_generator(), remove_useless_routing_nodes_config);
413  const auto II = mrrg.initiationInterval();
414  auto cgra = std::make_shared<CGRA>();
415 
416  GIVEN("A '" << test.opgraph_description << "' DFG") {
417  const auto opgraph = std::make_shared<OpGraph>(test.opgraph_generator());
418 
419  WHEN ("Mapped with a '" << approach.description << "' Mapper") {
420  std::unordered_map<std::string, std::string> fix_port;
421  const auto mapping = mapper_registry.createMapper(approach.mapper_id, cgra, 60, args)->mapOpGraph(opgraph, II, mrrg, fix_port);
422 
423  THEN ("Mapping should " << (expect_to_map ? "succeed" : "fail")) {
424  CHECKED_ELSE(mapping.getStatus() == (expect_to_map ? MappingStatus::success : MappingStatus::failure)) {
425  mrrg.printDot(std::cout);
426  opgraph->serialize(std::cout);
427  if (mapping.isMapped()) { mapping.outputMapping(std::cout); }
428 
429  // do it again, but with output
430  const auto args_with_v = set_all(ConfigStore(args), {
431  {approach.mapper_id + ".verbosity", "3"},
432  // {approach.mapper_id + ".model_dump_filename","model.lp"},
433  });
434  AutoRegisterMapper::getDefaultRegistry().createMapper(approach.mapper_id, cgra, 60, args_with_v)->mapOpGraph(opgraph, II, mrrg, fix_port);
435  } else if (mapping.isMapped()) {
436  AND_WHEN("Making a MappingGraph") {
437 
438  auto cmg_result = createMappingGraph(mrrg, mapping);
439  THEN("Latency should " << (test.possible_to_balance_latency ? "" : "not ") << "be balanced") {
440 
441  const auto latency_check_result = latencyCheck(cmg_result.mg, mrrg, cmg_result.toMRRG);
442  CHECKED_ELSE(latency_check_result.first == test.possible_to_balance_latency) {
443  mrrg.printDot(std::cout);
444  opgraph->serialize(std::cout);
445  mapping.outputMapping(std::cout);
446  cmg_result.mg.printDot(std::cout, mrrg, *opgraph, cmg_result.toMRRG, ConfigStore());
447  INFO("The previous check failed, and it dumped its inputs");
448  }
449  }
450  }
451  }
452  }
453  }
454  }
455  }
456 }
457 
458 TEST_CASE("ILPMapper checks for FU fanouts", "") {
459  auto mrrg = MRRG(1);
460  auto fu0 = mrrg.insert(MRRGNode::make_function(&god_module, 32, 0, "fu0", 0, {OpCode::ADD})).first;
461  auto fu0_out = mrrg.insert(fu0, MRRGNode::make_routing(&god_module, 32, 0, "fu0_out", 0)).first;
462  auto fu1 = mrrg.insert(fu0_out, MRRGNode::make_function(&god_module, 32, 0, "fu1", 0, {OpCode::ADD})).first;
463 
464  auto cgra = std::make_shared<CGRA>();
465  const auto opgraph = std::make_shared<OpGraph>(makeDFG_Linear2Node());
466  const auto mapper_registry = AutoRegisterMapper::getDefaultRegistry();
467  const auto args = mapper_registry.getAllRegisteredArgDefaults();
468  const auto mapper = mapper_registry.createMapper("ILPMapper", cgra, 60, args);
469  std::unordered_map<std::string, std::string> fix_port;
470  REQUIRE_THROWS_WITH(mapper->mapOpGraph(opgraph, mrrg.initiationInterval(), mrrg, fix_port), Catch::Matchers::Contains("FU does not have exactly one fanout"));
471 }
472 
473 namespace {
474 
475 MRRG makeMRRG_Simple(int II, ConfigStore options = {}) {
476  if (options.getIntOr("fu_arity", 0) == 1) {
477  options.addString("operand_tags", "none");
478  }
479  add_all(options, {
480  // {"width", "?"}, // must specify
481  // {"height", "?"}, // must specify
482  {"fu_self_feedback", true},
483  {"ortho_connections", true}, // allow N,S,E,W
484  {"diag_connections", false}, // allow NE, SE, SW, NW
485  {"flow_conections_only", false}, // disallow N, W, NE, NW, SW
486  {"fu_latency", 0}, // default latency
487  // {xyName("fu_latency",{x,y}), "?"} // override the default latency
488  {"fu_ops", "add,sub"}, // default ops
489  // {xyName("fu_ops",{x,y}), "?"} // override the default supported ops
490  {"fu_arity", 2}, // num FU inputs
491  {"operand_tags", "all"},
492  });
493  const auto inter_cluster_offsets = [&](){
494  auto result = std::vector<XY>{};
495  if (options.getBool("ortho_connections")) {
496  if (not options.getBool("flow_conections_only")) {
497  result.emplace_back(-1, 0);
498  result.emplace_back( 0,-1);
499  }
500  result.emplace_back( 1, 0);
501  result.emplace_back( 0, 1);
502  }
503 
504  if (options.getBool("diag_connections")) {
505  if (not options.getBool("flow_conections_only")) {
506  result.emplace_back(-1,-1);
507  result.emplace_back(-1, 1);
508  result.emplace_back( 1,-1);
509  }
510  result.emplace_back( 1, 1);
511  }
512 
513  if (options.getBool("fu_self_feedback")) {
514  result.emplace_back( 0, 0);
515  }
516 
517  return result;
518  }();
519 
520  const auto wrap_logic = [&](XY local_xy, XY offset) -> XY {
521  return {
522  local_xy.first + offset.first,
523  local_xy.second + offset.second,
524  };
525  };
526 
527  auto mrrg = MRRG{II};
528 
529  struct PEData {
530  MRRG::NodeDescriptor fu;
531  MRRG::NodeDescriptor output;
532  std::vector<MRRG::NodeDescriptor> inputs;
533  };
534 
535  std::map<int, std::map<XY,PEData>> pe_data;
536 
537  // make PEs
538  for (int ii = 0; ii < II; ++ii) {
539  for (int x = 0; x < options.getInt("width"); ++x) {
540  for (int y = 0; y < options.getInt("height"); ++y) {
541  const auto xy = XY{x,y};
542  const auto fu_name = xyName("fu", xy);
543  const auto fu_latency = options.getIntOr(xyName("fu_latency",xy), options.getInt("fu_latency"));
544 
545  const auto fu_op_csv = options.getStringOr(xyName("fu_ops",xy), options.getString("fu_ops"));
546  std::vector<OpCode> fu_ops;
547  for (std::size_t next_pos = 0, pos = 0; next_pos != fu_op_csv.size(); pos = next_pos + 1) {
548  next_pos = std::min(fu_op_csv.find_first_of(',', pos), fu_op_csv.size());
549  fu_ops.push_back(opcode_from_string(fu_op_csv.substr(pos, next_pos - pos)));
550  }
551 
552  auto& pe = pe_data[ii].insert({ xy, {
553  mrrg.insert(
554  MRRGNode::make_function(&god_module, 32, ii, fu_name, fu_latency, fu_ops)
555  ).first,
556  mrrg.insert(
557  MRRGNode::make_routing(&god_module, 32, (ii + fu_latency) % II, xyName("fu_out", xy)
558  )).first,
559  {}
560  }}).first->second;
561  mrrg.link(pe.fu, pe.output);
562 
563  const auto& operand_option = options.getString("operand_tags");
564  const auto fu_arity = options.getInt("fu_arity");
565 
566  std::vector<MRRGNode::SupportedOpTags> operand_tags(fu_arity);
567  if (operand_option == "all") {
568  if (fu_arity == 2) {
569  operand_tags.at(0) = {Operands::BINARY_LHS, Operands::BINARY_ANY};
570  operand_tags.at(1) = {Operands::BINARY_RHS, Operands::BINARY_ANY};
571  } else throw std::runtime_error("unsupported arity");
572  } else if (operand_option == "none") {
573  // nothing to do
574  } else if (operand_option == "only_lhs") {
575  if (fu_arity == 2) {
576  operand_tags.at(0) = {Operands::BINARY_LHS};
577  operand_tags.at(1) = {};
578  } else throw std::runtime_error("unsupported arity");
579  } else if (operand_option == "all_lhs") {
580  for (auto& tag_list : operand_tags) {
581  tag_list = {Operands::BINARY_LHS};
582  }
583  } else if (operand_option == "only_one_any") {
584  if (fu_arity == 2) {
585  operand_tags.at(0) = {};
586  operand_tags.at(1) = {Operands::BINARY_ANY};
587  } else throw std::runtime_error("unsupported arity");
588  } else if (operand_option == "only_commutative") {
589  if (fu_arity == 2) {
590  operand_tags.at(0) = {Operands::BINARY_ANY};
591  operand_tags.at(1) = {Operands::BINARY_ANY};
592  } else if (fu_arity == 3) {
593  operand_tags.at(0) = {Operands::TERNARY_ANY};
594  operand_tags.at(1) = {Operands::TERNARY_ANY};
595  operand_tags.at(2) = {Operands::TERNARY_ANY};
596  } else throw std::runtime_error("unsupported arity");
597  } else {
598  throw std::runtime_error("unsupported operand_tags option: " + operand_option);
599  }
600 
601  for (int i = 0; i < fu_arity; ++i) {
602  pe.inputs.push_back(mrrg.insert(MRRGNode::make_operand_pin(
603  &god_module, 32, ii, xyidName("pe_in", xy, i), operand_tags.at(i))).first);
604  mrrg.link(pe.inputs.back(), pe.fu);
605  }
606  }
607  }
608  }
609 
610  // connect PEs together
611  for (int ii = 0; ii < II; ++ii) {
612  for (int x = 0; x < options.getInt("width"); ++x) {
613  for (int y = 0; y < options.getInt("height"); ++y) {
614  const auto xy = XY{x,y};
615  const auto& pe = pe_data.at(ii).at(xy);
616  for (const auto offset : inter_cluster_offsets) {
617  const auto remote_xy = wrap_logic(xy, offset);
618  const auto find_results = pe_data.at(ii).find(remote_xy);
619  if (find_results == pe_data.at(ii).end()) { continue; }
620  for (const auto& remote_input : find_results->second.inputs) {
621  // intermediate node is to satisfy mux-ex invariant.
622  // remove it when it is added automatically.
623  const auto intermediate = mrrg.insert(MRRGNode::make_routing(&god_module, 32, ii,
624  mrrg.getNodeRef(pe.output).getHierarchyQualifiedName()
625  + "-to-" + mrrg.getNodeRef(remote_input).getHierarchyQualifiedName()
626  )).first;
627  mrrg.link(pe.output, intermediate);
628  mrrg.link(intermediate, remote_input);
629  }
630  }
631  }
632  }
633  }
634 
635  verifyAndPrintReport(mrrg, std::cout, true, true);
636  return mrrg;
637 }
638 
639 MRRG makeMRRG_SimpleFlow(int II, ConfigStore options) {
640  add_all(options, {
641  {"flow_conections_only", "yes"}
642  });
643  return makeMRRG_Simple(II, options);
644 }
645 
646 MRRG removeUselessRoutingNodes(MRRG mrrg, ConfigStore options) {
647  add_all(options, {
648  {"fus_must_have_fanout", false}, // Ensure all FU nodes have fanout. Required for ILPMapper correctness.
649  });
650 
651  // remove any [fanout-0 or fanin-0] routing nodes.
652  for (bool made_changes = true; made_changes;) {
653  made_changes = false;
654  for (int ii = 0; ii < mrrg.initiationInterval() && not made_changes; ++ii) {
655  for (const auto& name_and_ptr : mrrg.allNodesByCycle().at(ii)) {
656  const auto& node = name_and_ptr.second.get(); // gross...
657  const auto& node_ref = mrrg.getNodeRef(node);
658  if (node_ref.type != MRRGNode_Type::MRRG_NODE_ROUTING) continue; // only operate on routing nodes
659  bool driven_by_fu = false;
660  for (const auto fanin : mrrg.fanin(node)) {
661  driven_by_fu = mrrg.getNodeRef(fanin).type == MRRGNode_Type::MRRG_NODE_FUNCTION;
662  if (driven_by_fu) break;
663  }
664  if (options.getBool("fus_must_have_fanout") && driven_by_fu) continue;
665  if (mrrg.fanin(node).empty() || mrrg.fanout(node).empty()) {
666  made_changes = true;
667  mrrg.erase(node);
668  break;
669  }
670  }
671  }
672  }
673 
674  verifyAndPrintReport(mrrg, std::cout, true, true);
675  return mrrg;
676 }
677 
678 } // end anon namespace
TEST_CASE
TEST_CASE("ILPMapper checks for FU fanouts", "")
Definition: general_mapper_tests.cpp:458
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
OpGraph.h
MRRG::allNodesByCycle
const auto & allNodesByCycle() const
Definition: MRRG.h:357
MRRG
Definition: MRRG.h:216
xyidName
std::string xyidName(const std::string &prefix, XY xy, int id)
Definition: UserArchs.h:190
MRRGNode::type
MRRGNode_Type type
Definition: MRRG.h:107
Operands::BINARY_LHS
static constexpr auto & BINARY_LHS
Definition: OpGraph.h:89
Module.h
makeDFG_Converging121
OpGraph makeDFG_Converging121()
Definition: OpGraphsForTesting.cpp:151
ConfigStore.h
UserArchs.h
MRRG::erase
void erase(MRRG::NodeDescriptor n)
Definition: MRRG.cpp:109
ConfigStore
Definition: ConfigStore.h:76
OpCode::ADD
@ ADD
latencyCheck
std::pair< bool, MappingGraphCycleAssignment > latencyCheck(const MappingGraph &mapping, const MRRG &mrrg, const CreateMappingGraphResult::ToMRRG &toMRRG)
Definition: Mapping.cpp:582
makeDFG_Linear3Node
OpGraph makeDFG_Linear3Node()
Definition: OpGraphsForTesting.cpp:50
Operands::BINARY_RHS
static constexpr auto & BINARY_RHS
Definition: OpGraph.h:90
MRRG::fanout
auto & fanout(NodeDescriptor ndesc) const
Definition: MRRG.h:288
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
MRRGNode::make_operand_pin
static MRRGNode make_operand_pin(Module *parent, int bitwidth, int cycle, STR &&name, SupportedOpTags operand_tags, int latency=0, int max_cap=1)
Definition: MRRG.h:164
MappingStatus::failure
@ failure
ConfigStore::setBool
void setBool(std::string key, bool value)
Definition: ConfigStore.h:131
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
MRRG_NODE_FUNCTION
@ MRRG_NODE_FUNCTION
Definition: MRRG.h:46
OpGraphsForTesting.hpp
makeDFG_MultiEdge11
OpGraph makeDFG_MultiEdge11(ConfigStore options)
Definition: OpGraphsForTesting.cpp:203
Module
Definition: Module.h:163
MRRG::fanin
auto & fanin(NodeDescriptor ndesc) const
Definition: MRRG.h:293
MRRG_NODE_ROUTING
@ MRRG_NODE_ROUTING
Definition: MRRG.h:45
makeDFG_Linear2Node
OpGraph makeDFG_Linear2Node(ConfigStore options)
a--> b
Definition: OpGraphsForTesting.cpp:34
AutoRegisterMapper::getDefaultRegistry
static const MapperRegistry & getDefaultRegistry()
Public read-only access to the mapper registry that this class automatically adds mappers to.
Definition: Mapper.h:214
set_all
ConfigStore & set_all(ConfigStore &into, const ConfigStore &from)
Definition: ConfigStore.h:252
xyName
std::string xyName(const std::string &prefix, XY xy)
Definition: UserArchs.h:184
MRRGNode
Definition: MRRG.h:60
makeDFG_Tree12
OpGraph makeDFG_Tree12()
Definition: OpGraphsForTesting.cpp:128
makeDFG_Converging21
OpGraph makeDFG_Converging21(ConfigStore options)
Definition: OpGraphsForTesting.cpp:163
MappingStatus::success
@ success
MRRG::initiationInterval
int initiationInterval() const
Definition: MRRG.h:346
Mapper.h
opcode_from_string
OpGraphOpCode opcode_from_string(const std::string &str)
Definition: OpGraph.cpp:113
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
SCENARIO
SCENARIO("General Mapper Tests -- Tiny MRRGs", "")
Definition: general_mapper_tests.cpp:155
MapperRegistry::createMapper
std::unique_ptr< Mapper > createMapper(const std::string &mapper_id, std::shared_ptr< CGRA > cgra, int timelimit, const ConfigStore &args) const
Given a mapper_id, create an instance of that mapper with the given arguments.
Definition: Mapper.cpp:36
MRRG.h
OpGraph
Definition: OpGraph.h:215
XY
Definition: UserArchs.h:178
makeDFG_Parallel11_11
OpGraph makeDFG_Parallel11_11()
Definition: OpGraphsForTesting.cpp:176
ConfigStore::getBool
bool getBool(const std::string &key) const
Definition: ConfigStore.h:166
Operands::TERNARY_ANY
static constexpr auto & TERNARY_ANY
Definition: OpGraph.h:92
Generated on Fri Nov 17 2023 12:26:44 for CGRA-ME by   doxygen 1.8.17