Compute Library
 22.11
DependencyGraph.cpp
Go to the documentation of this file.
1 /*
2  * Copyright (c) 2022 Arm Limited.
3  *
4  * SPDX-License-Identifier: MIT
5  *
6  * Permission is hereby granted, free of charge, to any person obtaining a copy
7  * of this software and associated documentation files (the "Software"), to
8  * deal in the Software without restriction, including without limitation the
9  * rights to use, copy, modify, merge, publish, distribute, sublicense, and/or
10  * sell copies of the Software, and to permit persons to whom the Software is
11  * furnished to do so, subject to the following conditions:
12  *
13  * The above copyright notice and this permission notice shall be included in all
14  * copies or substantial portions of the Software.
15  *
16  * THE SOFTWARE IS PROVIDED "AS IS", WITHOUT WARRANTY OF ANY KIND, EXPRESS OR
17  * IMPLIED, INCLUDING BUT NOT LIMITED TO THE WARRANTIES OF MERCHANTABILITY,
18  * FITNESS FOR A PARTICULAR PURPOSE AND NONINFRINGEMENT. IN NO EVENT SHALL THE
19  * AUTHORS OR COPYRIGHT HOLDERS BE LIABLE FOR ANY CLAIM, DAMAGES OR OTHER
20  * LIABILITY, WHETHER IN AN ACTION OF CONTRACT, TORT OR OTHERWISE, ARISING FROM,
21  * OUT OF OR IN CONNECTION WITH THE SOFTWARE OR THE USE OR OTHER DEALINGS IN THE
22  * SOFTWARE.
23  */
24 #ifdef ENABLE_EXPERIMENTAL_DYNAMIC_FUSION
26 
28 #include "tests/framework/Macros.h"
29 
31 
32 namespace arm_compute
33 {
34 namespace test
35 {
36 namespace validation
37 {
38 TEST_SUITE(CL)
39 
40 TEST_SUITE(UNIT)
41 TEST_SUITE(DYNAMIC_FUSION)
43 
44 TEST_CASE(Correct_Graph_Creation_Should_Pass, framework::DatasetMode::ALL)
45 {
46  DependencyGraph graph{};
47  const auto t0 = graph.add_tensor();
48  const auto t1 = graph.add_tensor();
49  const auto t2 = graph.add_tensor();
50  const auto t3 = graph.add_tensor();
51  const auto t4 = graph.add_tensor();
52 
53  const auto o0 = graph.add_operator({ t0, t1 }, { t2 }).second;
54  const auto o1 = graph.add_operator({ t3, t2 }, { t4 }).second;
55 
56  ARM_COMPUTE_EXPECT_EQUAL(graph.number_of_ops(), 2U, framework::LogLevel::ERRORS);
57  ARM_COMPUTE_EXPECT_EQUAL(graph.number_of_tensors(), 5U, framework::LogLevel::ERRORS);
58 
59  const DependencyGraph ref_graph
60  {
61  {
62  // src_tensors
63  { o0, { t0, t1 } },
64  { o1, { t3, t2 } },
65  },
66  {
67  // dst_tensors
68  { o0, { t2 } },
69  { o1, { t4 } },
70  },
71  {
72  // src_ops
73  { t0, {} },
74  { t1, {} },
75  { t2, { o0 } },
76  { t3, {} },
77  { t4, { o1 } },
78  },
79  {
80  // dst_ops
81  { t0, { o0 } },
82  { t1, { o0 } },
83  { t2, { o1 } },
84  { t3, { o1 } },
85  { t4, {} },
86  }
87 
88  };
89  ARM_COMPUTE_EXPECT(graph == ref_graph, framework::LogLevel::ERRORS);
90 }
91 
92 TEST_CASE(Correct_Merge_Points_Should_Enable_Graph_Expansion, framework::DatasetMode::ALL)
93 {
94  // Merge points are a simple way to collapse "graph of graphs" into a single graph
95  // Suppose we have a top-level graph g0
96  DependencyGraph g0{};
97  const auto g0_t0 = g0.add_tensor();
98  const auto g0_t1 = g0.add_tensor();
99  const auto g0_t2 = g0.add_tensor();
100  const auto g0_t3 = g0.add_tensor();
101  const auto g0_t4 = g0.add_tensor();
102  g0.add_operator({ g0_t0, g0_t1 }, { g0_t2 }); // g0_o0
103  g0.add_operator({ g0_t3, g0_t2 }, { g0_t4 }); // g0_o1
104 
105  // Then g0 expands into g1, with additional nodes added in-between "merge point tensors"
106  // Note that the expansion logic may be local to each operator node
107  DependencyGraph g1{};
108  // g0_o0 expands into g1_o0, g1_o1, g1_o2
109  const auto g1_t0 = g1.add_tensor(g0_t0);
110  const auto g1_t1 = g1.add_tensor(g0_t1);
111  const auto g1_t2 = g1.add_tensor();
112  const auto g1_t3 = g1.add_tensor();
113  const auto g1_t4 = g1.add_tensor(g0_t2);
114  const auto g1_o0 = g1.add_operator({ g1_t0 }, { g1_t2 }).second;
115  const auto g1_o1 = g1.add_operator({ g1_t1 }, { g1_t3 }).second;
116  const auto g1_o2 = g1.add_operator({ g1_t2, g1_t3 }, { g1_t4 }).second;
117 
118  // g0_o1 expands into g1_o3
119  const auto g1_t5 = g1.add_tensor(g0_t3);
120  const auto g1_t6 = g1.add_tensor(g0_t2);
121  const auto g1_t7 = g1.add_tensor(g0_t4);
122  ARM_COMPUTE_EXPECT_EQUAL(g1_t4, g1_t6, framework::LogLevel::ERRORS); // both associate with the same merge point g0_t2, thus they should point to the same tensor in g1
123  const auto g1_o3 = g1.add_operator({ g1_t5, g1_t6 }, { g1_t7 }).second;
124 
125  const DependencyGraph ref_graph
126  {
127  {
128  // src_tensors
129  { g1_o0, { g1_t0 } },
130  { g1_o1, { g1_t1 } },
131  { g1_o2, { g1_t2, g1_t3 } },
132  { g1_o3, { g1_t5, g1_t4 } },
133  },
134  {
135  // dst_tensors
136  { g1_o0, { g1_t2 } },
137  { g1_o1, { g1_t3 } },
138  { g1_o2, { g1_t4 } },
139  { g1_o3, { g1_t7 } },
140  },
141  {
142  // src_ops
143  { g1_t0, {} },
144  { g1_t1, {} },
145  { g1_t2, { g1_o0 } },
146  { g1_t3, { g1_o1 } },
147  { g1_t4, { g1_o2 } },
148  { g1_t5, {} },
149  { g1_t7, { g1_o3 } },
150  },
151  {
152  // dst_ops
153  { g1_t0, { g1_o0 } },
154  { g1_t1, { g1_o1 } },
155  { g1_t2, { g1_o2 } },
156  { g1_t3, { g1_o2 } },
157  { g1_t4, { g1_o3 } },
158  { g1_t5, { g1_o3 } },
159  { g1_t7, {} },
160  },
161  {
162  // merge points
163  { g0_t0, g1_t0 },
164  { g0_t1, g1_t1 },
165  { g0_t2, g1_t4 },
166  { g0_t3, g1_t5 },
167  { g0_t4, g1_t7 },
168  }
169  };
170  ARM_COMPUTE_EXPECT(g1 == ref_graph, framework::LogLevel::ERRORS);
171 }
172 
173 TEST_CASE(Path_Existence_Check_0, framework::DatasetMode::ALL)
174 {
175  DependencyGraph graph{};
176  const auto t0 = graph.add_tensor();
177  const auto t1 = graph.add_tensor();
178  const auto t2 = graph.add_tensor();
179  const auto t3 = graph.add_tensor();
180  const auto t4 = graph.add_tensor();
181  const auto t5 = graph.add_tensor();
182  const auto t6 = graph.add_tensor();
183  const auto t7 = graph.add_tensor();
184  const auto o0 = graph.add_operator({ t1 }, { t3, t4 }).second;
185  const auto o1 = graph.add_operator({ t3 }, { t5 }).second;
186  const auto o2 = graph.add_operator({ t5, t6 }, { t7 }).second;
187  const auto o3 = graph.add_operator({ t4 }, { t6 }).second;
188  const auto o4 = graph.add_operator({ t0, t5 }, { t2 }).second;
189 
190  ARM_COMPUTE_UNUSED(o1, o3);
191 
192  ARM_COMPUTE_EXPECT((graph.path_exists_from_tensor_to_op(t3, o2)), framework::LogLevel::ERRORS);
193  ARM_COMPUTE_EXPECT((graph.path_exists_from_tensor_to_op(t1, o4)), framework::LogLevel::ERRORS);
194  ARM_COMPUTE_EXPECT(!(graph.path_exists_from_tensor_to_op(t2, o4)), framework::LogLevel::ERRORS);
195  ARM_COMPUTE_EXPECT(!(graph.path_exists_from_tensor_to_op(t0, o2)), framework::LogLevel::ERRORS);
196 
197  ARM_COMPUTE_EXPECT((graph.path_exists_from_op_to_op(o0, o2)), framework::LogLevel::ERRORS);
198  ARM_COMPUTE_EXPECT(!(graph.path_exists_from_op_to_op(o2, o0)), framework::LogLevel::ERRORS);
199 
200  ARM_COMPUTE_EXPECT(!(graph.path_exists_from_op_to_op(o2, o4)), framework::LogLevel::ERRORS);
201 }
202 
203 TEST_CASE(Correct_Topological_Sort_Should_Pass, framework::DatasetMode::ALL)
204 {
205  DependencyGraph graph{};
206  const auto t0 = graph.add_tensor();
207  const auto t1 = graph.add_tensor();
208  const auto t2 = graph.add_tensor();
209  const auto t3 = graph.add_tensor();
210  const auto t4 = graph.add_tensor();
211  const auto t5 = graph.add_tensor();
212  const auto t6 = graph.add_tensor();
213  const auto t7 = graph.add_tensor();
214  const auto o0 = graph.add_operator({ t1 }, { t3, t4 }).second;
215  const auto o1 = graph.add_operator({ t3 }, { t5 }).second;
216  const auto o2 = graph.add_operator({ t5, t6 }, { t7 }).second;
217  const auto o3 = graph.add_operator({ t4 }, { t6 }).second;
218  const auto o4 = graph.add_operator({ t0, t5 }, { t2 }).second;
219 
220  const auto res = graph.topological_sort();
221  ARM_COMPUTE_EXPECT(bool(res.first), framework::LogLevel::ERRORS);
222  std::vector<DependencyGraph::OpPack> ref_sorted_op_packs
223  {
224  { o0, { t1 }, { t3, t4 } },
225  { o1, { t3 }, { t5 } },
226  { o3, { t4 }, { t6 } },
227  { o4, { t0, t5 }, { t2 } },
228  { o2, { t5, t6 }, { t7 } },
229 
230  };
231  ARM_COMPUTE_EXPECT((res.second == ref_sorted_op_packs), framework::LogLevel::ERRORS);
232 }
233 
234 TEST_CASE(Cycles_Should_Fail, framework::DatasetMode::ALL)
235 {
236  DependencyGraph graph{};
237  const auto t0 = graph.add_tensor();
238  const auto t1 = graph.add_tensor();
239  const auto t2 = graph.add_tensor();
240  const auto t3 = graph.add_tensor();
241 
242  graph.add_operator({ t0, t1 }, { t2 });
243  graph.add_operator({ t2 }, { t1, t3 }); // Ideally error should occur here
244 
245  const auto res = graph.topological_sort();
246  ARM_COMPUTE_EXPECT(!bool(res.first), framework::LogLevel::ERRORS);
247 }
248 TEST_CASE(Loops_Should_Fail, framework::DatasetMode::ALL)
249 {
250  DependencyGraph graph{};
251  const auto t0 = graph.add_tensor();
252  const auto t1 = graph.add_tensor();
253  const auto t2 = graph.add_tensor();
254 
255  ARM_COMPUTE_EXPECT_THROW(graph.add_operator({ t0, t2 }, { t1, t2 }).first, framework::LogLevel::ERRORS);
256  ARM_COMPUTE_UNUSED(t0, t1, t2);
257 }
258 TEST_SUITE_END() // DependencyGraph
259 TEST_SUITE_END() // DYNAMIC_FUSION
260 TEST_SUITE_END() // UNIT
261 
262 TEST_SUITE_END() // CL
263 } // namespace validation
264 } // namespace test
265 } // namespace arm_compute
266 #endif /* ENABLE_EXPERIMENTAL_DYNAMIC_FUSION */
The dependency graph of a workload, where the nodes are of 2 types: Tensor or Operator Represented as...
Id add_tensor(Id merge_tensor=empty_id())
Add a new tensor.
#define ARM_COMPUTE_EXPECT_THROW(X, LEVEL)
Definition: Asserts.h:187
#define ARM_COMPUTE_EXPECT_EQUAL(X, Y, LEVEL)
Definition: Asserts.h:111
Copyright (c) 2017-2022 Arm Limited.
#define TEST_SUITE(SUITE_NAME)
Definition: Macros.h:34
#define TEST_CASE(TEST_NAME, MODE)
Definition: Macros.h:180
DatasetMode
Possible dataset modes.
Definition: DatasetModes.h:40
#define ARM_COMPUTE_UNUSED(...)
To avoid unused variables warnings.
Definition: Error.h:152
#define ARM_COMPUTE_EXPECT(X, LEVEL)
Definition: Asserts.h:131
#define TEST_SUITE_END()
Definition: Macros.h:39