Compute Library
 22.08
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 
27 #include <algorithm>
28 #include <deque>
29 #include <set>
30 
31 namespace arm_compute
32 {
33 namespace experimental
34 {
35 namespace dynamic_fusion
36 {
37 DependencyGraph::DependencyGraph(const AdjList &adj_src_tensors, const AdjList &adj_dst_tensors, const AdjList &adj_src_ops, const AdjList &adj_dst_ops, std::map<Id, Id> merge_points)
38  : _adj_src_tensors{ adj_src_tensors }, _adj_dst_tensors{ adj_dst_tensors }, _adj_src_ops{ adj_src_ops }, _adj_dst_ops{ adj_dst_ops }, _merge_to_internal{ merge_points }, _operator_id{}, _tensor_id{}
39 {
40 }
41 DependencyGraph::DependencyGraph(const std::vector<Id> &imported_tensors)
42  : _adj_src_tensors{}, _adj_dst_tensors{}, _adj_src_ops{}, _adj_dst_ops{}, _merge_to_internal{}, _operator_id{}, _tensor_id{}
43 {
44  for(auto t : imported_tensors)
45  {
46  _adj_src_ops[t] = {};
47  _adj_dst_ops[t] = {};
48  }
49 }
50 
52 {
53  if(_merge_to_internal.find(merge_point) == _merge_to_internal.end())
54  {
55  return Status{ ErrorCode::RUNTIME_ERROR, "Merge point does not exist" };
56  }
57  _merge_to_internal[merge_point] = t_id;
58  return Status{};
59 }
60 
62 {
63  Id new_tensor{ empty_id() };
64  if(merge_tensor != empty_id())
65  {
66  if(_merge_to_internal.find(merge_tensor) != _merge_to_internal.end())
67  {
68  new_tensor = _merge_to_internal[merge_tensor];
69  }
70  else
71  {
72  new_tensor = insert_new_tensor();
73  _merge_to_internal[merge_tensor] = new_tensor;
74  }
75  }
76  else
77  {
78  new_tensor = insert_new_tensor();
79  }
80  return new_tensor;
81 }
82 
84 {
85  for(auto src_op : _adj_src_ops.at(tensor))
86  {
87  auto &dst_tensors = _adj_dst_tensors.at(src_op);
88  dst_tensors.erase(
89  std::remove(std::begin(dst_tensors), std::end(dst_tensors), tensor),
91  }
92  for(auto dst_op : _adj_dst_ops.at(tensor))
93  {
94  auto &src_tensors = _adj_src_tensors.at(dst_op);
95  src_tensors.erase(
96  std::remove(std::begin(src_tensors), std::end(src_tensors), tensor),
98  }
99  _adj_src_ops.erase(tensor);
100  _adj_dst_ops.erase(tensor);
101 }
102 
103 std::pair<Status, DependencyGraph::Id> DependencyGraph::add_operator(const std::vector<Id> &inputs, const std::vector<Id> &outputs)
104 {
105  Id new_op = insert_new_op();
106  for(Id tensor : inputs)
107  {
108  link_input(new_op, tensor);
109  }
110  for(Id tensor : outputs)
111  {
112  link_output(new_op, tensor);
113  }
114 
115  // Use topological sort in order to detect possible loops / cycles.
116  // NOTE: This is unscalable. We'll need to have a better way of detecting loops or relax this invariant during operation, and add a validate method instead
117  return std::pair<Status, DependencyGraph::Id>(topological_sort().first, new_op);
118 }
119 
121 {
122  for(auto src_tensor : _adj_src_tensors.at(op))
123  {
124  auto &dst_ops = _adj_dst_ops.at(src_tensor);
125  dst_ops.erase(
126  std::remove(std::begin(dst_ops), std::end(dst_ops), op),
127  std::end(dst_ops));
128  }
129  for(auto dst_tensor : _adj_dst_tensors.at(op))
130  {
131  auto &src_ops = _adj_src_ops.at(dst_tensor);
132  src_ops.erase(
133  std::remove(std::begin(src_ops), std::end(src_ops), op),
134  std::end(src_ops));
135  }
136  _adj_src_tensors.erase(op);
137  _adj_dst_tensors.erase(op);
138 }
139 
140 std::map<DependencyGraph::Id, DependencyGraph::Id> DependencyGraph::get_merge_points() const
141 {
142  return _merge_to_internal;
143 }
144 
145 std::vector<DependencyGraph::Id> DependencyGraph::get_root_ops() const
146 {
147  std::vector<Id> ops{};
148  const auto op_list = all_ops();
149 
150  for(auto op : op_list)
151  {
152  if(src_ops(op).empty())
153  {
154  ops.emplace_back(op);
155  }
156  }
157  return ops;
158 }
159 
160 std::vector<DependencyGraph::Id> DependencyGraph::get_dst_ops() const
161 {
162  std::vector<Id> ops{};
163  const auto op_list = all_ops();
164 
165  for(auto op : op_list)
166  {
167  if(dst_ops(op).empty())
168  {
169  ops.emplace_back(op);
170  }
171  }
172  return ops;
173 }
174 
175 std::vector<DependencyGraph::Id> DependencyGraph::src_tensors(Id op) const
176 {
177  ARM_COMPUTE_ERROR_ON(!operator_exists(op));
178  return _adj_src_tensors.at(op);
179 }
180 
181 std::vector<DependencyGraph::Id> DependencyGraph::dst_tensors(Id op) const
182 {
183  ARM_COMPUTE_ERROR_ON(!operator_exists(op));
184  return _adj_dst_tensors.at(op);
185 }
186 
187 std::vector<DependencyGraph::Id> DependencyGraph::src_tensors() const
188 {
189  std::vector<Id> tensors;
190  for(auto tensor_src_ops : _adj_src_ops)
191  {
192  if(tensor_src_ops.second.empty())
193  tensors.push_back(tensor_src_ops.first);
194  }
195  return tensors;
196 }
197 
198 std::vector<DependencyGraph::Id> DependencyGraph::dst_tensors() const
199 {
200  std::vector<Id> tensors;
201  for(auto tensor_dst_ops : _adj_dst_ops)
202  {
203  if(tensor_dst_ops.second.empty())
204  tensors.push_back(tensor_dst_ops.first);
205  }
206  return tensors;
207 }
208 
209 std::vector<DependencyGraph::Id> DependencyGraph::src_ops_from_tensor(Id tensor) const
210 {
211  return _adj_src_ops.at(tensor);
212 }
213 std::vector<DependencyGraph::Id> DependencyGraph::dst_ops_from_tensor(Id tensor) const
214 {
215  return _adj_dst_ops.at(tensor);
216 }
217 
218 std::vector<DependencyGraph::Id> DependencyGraph::all_ops() const
219 {
220  std::vector<Id> ops{};
221  std::transform(std::begin(_adj_src_tensors), std::end(_adj_src_tensors), std::back_inserter(ops), [](const auto & it)
222  {
223  return it.first;
224  });
225  return ops;
226 }
227 
229 {
230  for(auto child_op : dst_ops_from_tensor(src_tensor))
231  {
232  if(path_exists_from_op_to_op(child_op, dst_op))
233  {
234  return true;
235  }
236  }
237  return false;
238 }
239 
241 {
242  if(src_op == dst_op)
243  {
244  return true;
245  }
246  if(is_in(src_op, get_dst_ops()))
247  {
248  return false;
249  }
250  for(auto child_tensor : dst_tensors(src_op))
251  {
252  if(path_exists_from_tensor_to_op(child_tensor, dst_op))
253  {
254  return true;
255  }
256  }
257  return false;
258 }
259 
260 std::vector<DependencyGraph::Id> DependencyGraph::all_tensors() const
261 {
262  std::vector<Id> tensors{};
263  std::transform(std::begin(_adj_src_ops), std::end(_adj_src_ops), std::back_inserter(tensors), [](const auto & it)
264  {
265  return it.first;
266  });
267  return tensors;
268 }
269 
270 unsigned int DependencyGraph::number_of_ops() const
271 {
272  return _adj_src_tensors.size();
273 }
274 
276 {
277  return _adj_src_ops.size();
278 }
279 
280 DependencyGraph::Id DependencyGraph::insert_new_tensor()
281 {
282  Id new_tensor = _tensor_id.alloc();
283  _adj_src_ops[new_tensor] = {};
284  _adj_dst_ops[new_tensor] = {};
285  return new_tensor;
286 }
287 DependencyGraph::Id DependencyGraph::insert_new_op()
288 {
289  Id new_op = _operator_id.alloc();
290  _adj_src_tensors[new_op] = {};
291  _adj_dst_tensors[new_op] = {};
292  return new_op;
293 }
294 void DependencyGraph::link_input(Id op, Id in_tensor)
295 {
296  ARM_COMPUTE_ERROR_ON(!operator_exists(op));
297  ARM_COMPUTE_ERROR_ON(!tensor_exists(in_tensor));
298  ARM_COMPUTE_ERROR_ON(are_connected(op, in_tensor));
299  _adj_src_tensors[op].push_back(in_tensor);
300  _adj_dst_ops[in_tensor].push_back(op);
301 }
302 void DependencyGraph::link_output(Id op, Id out_tensor)
303 {
304  ARM_COMPUTE_ERROR_ON(!operator_exists(op));
305  ARM_COMPUTE_ERROR_ON(!tensor_exists(out_tensor));
306  ARM_COMPUTE_ERROR_ON(are_connected(op, out_tensor));
307  _adj_dst_tensors[op].push_back(out_tensor);
308  _adj_src_ops[out_tensor].push_back(op);
309 }
310 bool DependencyGraph::tensor_exists(Id tensor) const
311 {
312  return _adj_src_ops.find(tensor) != _adj_src_ops.end() && _adj_dst_ops.find(tensor) != _adj_dst_ops.end();
313 }
314 bool DependencyGraph::operator_exists(Id op) const
315 {
316  return _adj_src_tensors.find(op) != _adj_src_tensors.end() && _adj_dst_tensors.find(op) != _adj_dst_tensors.end();
317 }
318 
320 {
321  if(!tensor_exists(tensor))
322  {
323  return false;
324  }
325  return _adj_src_ops.at(tensor).empty();
326 }
327 
329 {
330  if(!tensor_exists(tensor))
331  {
332  return false;
333  }
334  return _adj_dst_ops.at(tensor).empty();
335 }
336 bool DependencyGraph::is_src_tensor_of(Id op, Id tensor) const
337 {
338  if(!operator_exists(op) || !tensor_exists(tensor))
339  {
340  return false;
341  }
342  const auto op_inputs = src_tensors(op);
343  return std::find(op_inputs.begin(), op_inputs.end(), tensor) != op_inputs.end();
344 }
345 bool DependencyGraph::is_dst_tensor_of(Id op, Id tensor) const
346 {
347  if(!operator_exists(op) || !tensor_exists(tensor))
348  {
349  return false;
350  }
351  const auto op_outputs = dst_tensors(op);
352  return std::find(op_outputs.begin(), op_outputs.end(), tensor) != op_outputs.end();
353 }
354 bool DependencyGraph::are_connected(Id op, Id tensor) const
355 {
356  return is_src_tensor_of(op, tensor) || is_dst_tensor_of(op, tensor);
357 }
358 std::vector<DependencyGraph::Id> DependencyGraph::src_ops(Id op) const
359 {
360  ARM_COMPUTE_ERROR_ON(!operator_exists(op));
361  std::vector<Id> ops{};
362  for(Id src_tensor : src_tensors(op))
363  {
364  ops.insert(ops.end(), std::begin(_adj_src_ops.at(src_tensor)), std::end(_adj_src_ops.at(src_tensor)));
365  }
366  return ops;
367 }
368 
369 std::vector<DependencyGraph::Id> DependencyGraph::dst_ops(Id op) const
370 {
371  ARM_COMPUTE_ERROR_ON(!operator_exists(op));
372  std::vector<Id> ops{};
373  for(Id dst_tensor : _adj_dst_tensors.at(op))
374  {
375  ops.insert(ops.end(), std::begin(_adj_dst_ops.at(dst_tensor)), std::end(_adj_dst_ops.at(dst_tensor)));
376  }
377  return ops;
378 }
379 
380 std::pair<Status, std::vector<DependencyGraph::OpPack>> DependencyGraph::topological_sort() const
381 {
382  // Incident degree (number of source operators to an op)
383  std::map<Id, unsigned int> in_degree{};
384  std::set<Id> visited_ops{};
385  std::deque<Id> zero_in_degree_ops{};
386  std::vector<OpPack> sorted_op_packs{};
387  for(auto op : all_ops())
388  {
389  const auto degree = src_ops(op).size();
390  in_degree[op] = degree;
391  if(degree == 0)
392  {
393  zero_in_degree_ops.push_back(op);
394  visited_ops.insert(op);
395  }
396  }
397 
398  while(!zero_in_degree_ops.empty())
399  {
400  const Id op = zero_in_degree_ops.front();
401  zero_in_degree_ops.pop_front();
402  sorted_op_packs.push_back(OpPack{ op, src_tensors(op), dst_tensors(op) });
403 
404  for(const auto next_op : dst_ops(op))
405  {
406  if(in_degree[next_op] > 0)
407  {
408  in_degree[next_op]--;
409  }
410  if(in_degree[next_op] == 0 && visited_ops.find(next_op) == visited_ops.end())
411  {
412  zero_in_degree_ops.push_back(next_op);
413  visited_ops.insert(op);
414  }
415  }
416  }
417 
418  // If there are remaining ops with in_degree > 0, then it's indication that there are cycles in the graph
419  Status st{};
420  if(sorted_op_packs.size() != number_of_ops())
421  {
422  st = Status{ ErrorCode::RUNTIME_ERROR, "Cycles or loops are not allowed in a DependencyGraph" };
423  }
424  return std::make_pair(st, sorted_op_packs);
425 }
426 
427 } // namespace dynamic_fusion
428 } // namespace experimental
429 } // namespace arm_compute
430 #endif /* ENABLE_EXPERIMENTAL_DYNAMIC_FUSION */
unsigned int number_of_ops() const
Number of operators.
bool is_dst_tensor(Id tensor) const
Check if tensor is the dst tensor of the entire graph.
Id add_tensor(Id merge_tensor=empty_id())
Add a new tensor.
std::vector< Id > get_root_ops() const
Get all root ops.
std::map< Id, Id > get_merge_points() const
Get the merge points object.
A pack of operator including its input and output tensors, used by traversing through the graph in to...
#define ARM_COMPUTE_ERROR_ON(cond)
If the condition is true then an error message is printed and an exception thrown.
Definition: Error.h:466
Status class.
Definition: Error.h:52
std::pair< Status, std::vector< OpPack > > topological_sort() const
Sort the graph in a topological order.
bool is_src_tensor(Id tensor) const
Check if tensor is the src tensor of the entire graph.
Copyright (c) 2017-2022 Arm Limited.
bool is_in(const T &v, const std::vector< T > &vec)
std::vector< Id > src_tensors() const
Get source tensors of the whole graph.
std::vector< Id > dst_tensors() const
Get destination tensors of the whole graph.
std::vector< Id > all_ops() const
Get all operators.
void end(TokenStream &in, bool &valid)
Definition: MLGOParser.cpp:290
std::vector< Id > all_tensors() const
Get all tensors.
std::vector< Id > get_dst_ops() const
Get all dst ops of the whole graph.
bool path_exists_from_op_to_op(Id src_op, Id dst_op) const
Check if there&#39;s a path from src_op to dst_op.
std::pair< Status, DependencyGraph::Id > add_operator(const std::vector< Id > &inputs, const std::vector< Id > &outputs)
Add a new operator.
std::map< Id, std::vector< Id > > AdjList
Adjacency list.
bool path_exists_from_tensor_to_op(Id src_tensor, Id dst_op) const
Check if there&#39;s a path from src_tensor to dst_op.
Status update_merge_point(Id t_id, Id merge_point)
Update merge_point to point to t_id.
unsigned int number_of_tensors() const
Number of tensors.