Compute Library
 22.08
DependencyGraph Class Reference

The dependency graph of a workload, where the nodes are of 2 types: Tensor or Operator Represented as a doubly-linked adjacency list with the differentiation between source and destination. More...

#include <DependencyGraph.h>

Data Structures

struct  OpPack
 A pack of operator including its input and output tensors, used by traversing through the graph in topological order. More...
 
class  SerialIdAllocator
 A serial Id allocator. More...
 

Public Types

using Id = SerialIdAllocator::Id
 
using AdjList = std::map< Id, std::vector< Id > >
 Adjacency list. More...
 

Public Member Functions

 DependencyGraph ()=default
 
 DependencyGraph (const std::vector< Id > &imported_tensors)
 
 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={})
 
Id add_tensor (Id merge_tensor=empty_id())
 Add a new tensor. More...
 
void remove_tensor (Id tensor)
 
std::pair< Status, DependencyGraph::Idadd_operator (const std::vector< Id > &inputs, const std::vector< Id > &outputs)
 Add a new operator. More...
 
void remove_operator (Id op)
 
std::pair< Status, std::vector< OpPack > > topological_sort () const
 Sort the graph in a topological order. More...
 
std::vector< Idsrc_ops (Id op) const
 
std::vector< Iddst_ops (Id op) const
 
std::vector< Idsrc_ops_from_tensor (Id tensor) const
 
std::vector< Iddst_ops_from_tensor (Id tensor) const
 
std::map< Id, Idget_merge_points () const
 Get the merge points object. More...
 
std::vector< Idget_root_ops () const
 Get all root ops. More...
 
std::vector< Idget_dst_ops () const
 Get all dst ops of the whole graph. More...
 
std::vector< Idsrc_tensors (Id op) const
 Get source tensors to an operator. More...
 
std::vector< Iddst_tensors (Id op) const
 Get destination tensors to an operator. More...
 
std::vector< Idsrc_tensors () const
 Get source tensors of the whole graph. More...
 
std::vector< Iddst_tensors () const
 Get destination tensors of the whole graph. More...
 
std::vector< Idall_ops () const
 Get all operators. More...
 
std::vector< Idall_tensors () const
 Get all tensors. More...
 
unsigned int number_of_ops () const
 Number of operators. More...
 
unsigned int number_of_tensors () const
 Number of tensors. More...
 
Status update_merge_point (Id t_id, Id merge_point)
 Update merge_point to point to t_id. More...
 
void link_input (Id op, Id in_tensor)
 
void link_output (Id op, Id out_tensor)
 
bool path_exists_from_tensor_to_op (Id src_tensor, Id dst_op) const
 Check if there's a path from src_tensor to dst_op. More...
 
bool path_exists_from_op_to_op (Id src_op, Id dst_op) const
 Check if there's a path from src_op to dst_op. More...
 
bool is_src_tensor (Id tensor) const
 Check if tensor is the src tensor of the entire graph. More...
 
bool is_dst_tensor (Id tensor) const
 Check if tensor is the dst tensor of the entire graph. More...
 

Static Public Member Functions

static constexpr Id empty_id ()
 

Friends

bool operator== (const DependencyGraph &g0, const DependencyGraph &g1)
 Strict equality comparison (all internal ids and order of insertion matter). More...
 

Detailed Description

The dependency graph of a workload, where the nodes are of 2 types: Tensor or Operator Represented as a doubly-linked adjacency list with the differentiation between source and destination.

A "Merge Tensor" is an external tensor associated with the tensor within the graph, and serve as a merge point

Definition at line 51 of file DependencyGraph.h.

Member Typedef Documentation

◆ AdjList

using AdjList = std::map<Id, std::vector<Id> >

Adjacency list.

Definition at line 77 of file DependencyGraph.h.

◆ Id

Definition at line 73 of file DependencyGraph.h.

Constructor & Destructor Documentation

◆ DependencyGraph() [1/3]

DependencyGraph ( )
default

◆ DependencyGraph() [2/3]

DependencyGraph ( const std::vector< Id > &  imported_tensors)
explicit

Definition at line 41 of file DependencyGraph.cpp.

References tf_frozen_model_extractor::t.

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 }

◆ DependencyGraph() [3/3]

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 = {} 
)

Definition at line 37 of file DependencyGraph.cpp.

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 }

Member Function Documentation

◆ add_operator()

std::pair< Status, DependencyGraph::Id > add_operator ( const std::vector< Id > &  inputs,
const std::vector< Id > &  outputs 
)

Add a new operator.

Parameters
inputsInput tensors to the operator
outputsOutput tensors to the operator
Returns
std::pair<Status, DependencyGraph::Id> where id is the newly allocated operator

Definition at line 103 of file DependencyGraph.cpp.

References DependencyGraph::link_input(), DependencyGraph::link_output(), and DependencyGraph::topological_sort().

Referenced by ClKernelFusionGroup::add_fused_kernel(), arm_compute::experimental::dynamic_fusion::add_op_conv2d(), arm_compute::experimental::dynamic_fusion::add_op_elementwise_op(), arm_compute::experimental::dynamic_fusion::add_op_floor(), and DependencyGraph::empty_id().

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 }
std::pair< Status, std::vector< OpPack > > topological_sort() const
Sort the graph in a topological order.

◆ add_tensor()

DependencyGraph::Id add_tensor ( Id  merge_tensor = empty_id())

Add a new tensor.

Parameters
merge_tensorThe external merge point associated with the tensor. Leave empty if not needed.
Returns
Id The newly allocated tensor, or a previously added tensor associated with merge_tensor

Definition at line 61 of file DependencyGraph.cpp.

References DependencyGraph::empty_id().

Referenced by ClKernelFusionGroup::add_fused_kernel(), arm_compute::experimental::dynamic_fusion::add_tensor(), DependencyGraph::empty_id(), and arm_compute::test::validation::TEST_CASE().

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 }

◆ all_ops()

std::vector< DependencyGraph::Id > all_ops ( ) const

Get all operators.

Returns
std::vector<Id>

Definition at line 218 of file DependencyGraph.cpp.

References arm_compute::mlgo::parser::end().

Referenced by DependencyGraph::empty_id(), DependencyGraph::get_dst_ops(), DependencyGraph::get_root_ops(), and DependencyGraph::topological_sort().

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 }
void end(TokenStream &in, bool &valid)
Definition: MLGOParser.cpp:290

◆ all_tensors()

std::vector< DependencyGraph::Id > all_tensors ( ) const

Get all tensors.

Returns
std::vector<Id>

Definition at line 260 of file DependencyGraph.cpp.

References arm_compute::mlgo::parser::end().

Referenced by DependencyGraph::empty_id().

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 }
void end(TokenStream &in, bool &valid)
Definition: MLGOParser.cpp:290

◆ dst_ops()

std::vector< DependencyGraph::Id > dst_ops ( Id  op) const

Definition at line 369 of file DependencyGraph.cpp.

References ARM_COMPUTE_ERROR_ON, and arm_compute::mlgo::parser::end().

Referenced by DependencyGraph::empty_id(), DependencyGraph::get_dst_ops(), DependencyGraph::remove_operator(), and DependencyGraph::topological_sort().

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 }
#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
void end(TokenStream &in, bool &valid)
Definition: MLGOParser.cpp:290

◆ dst_ops_from_tensor()

std::vector< DependencyGraph::Id > dst_ops_from_tensor ( Id  tensor) const

Definition at line 213 of file DependencyGraph.cpp.

Referenced by DependencyGraph::empty_id(), and DependencyGraph::path_exists_from_tensor_to_op().

214 {
215  return _adj_dst_ops.at(tensor);
216 }

◆ dst_tensors() [1/2]

std::vector< DependencyGraph::Id > dst_tensors ( Id  op) const

Get destination tensors to an operator.

Parameters
op
Returns
std::vector<Id>

Definition at line 181 of file DependencyGraph.cpp.

References ARM_COMPUTE_ERROR_ON.

Referenced by arm_compute::experimental::dynamic_fusion::build(), arm_compute::experimental::dynamic_fusion::generate(), arm_compute::experimental::dynamic_fusion::generate_store(), and ClKernelFusionGroup::get_dst_tensors().

182 {
183  ARM_COMPUTE_ERROR_ON(!operator_exists(op));
184  return _adj_dst_tensors.at(op);
185 }
#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

◆ dst_tensors() [2/2]

std::vector< DependencyGraph::Id > dst_tensors ( ) const

Get destination tensors of the whole graph.

Returns
std::vector<Id>

Definition at line 198 of file DependencyGraph.cpp.

Referenced by DependencyGraph::empty_id(), DependencyGraph::is_dst_tensor(), DependencyGraph::path_exists_from_op_to_op(), DependencyGraph::remove_tensor(), and DependencyGraph::topological_sort().

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 }

◆ empty_id()

◆ get_dst_ops()

std::vector< DependencyGraph::Id > get_dst_ops ( ) const

Get all dst ops of the whole graph.

Returns
std::vector<Id>

Definition at line 160 of file DependencyGraph.cpp.

References DependencyGraph::all_ops(), and DependencyGraph::dst_ops().

Referenced by DependencyGraph::empty_id(), and DependencyGraph::path_exists_from_op_to_op().

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 }
std::vector< Id > all_ops() const
Get all operators.

◆ get_merge_points()

std::map< DependencyGraph::Id, DependencyGraph::Id > get_merge_points ( ) const

Get the merge points object.

Returns
std::map<Id, Id>

Definition at line 140 of file DependencyGraph.cpp.

Referenced by arm_compute::experimental::dynamic_fusion::build(), and DependencyGraph::empty_id().

141 {
142  return _merge_to_internal;
143 }

◆ get_root_ops()

std::vector< DependencyGraph::Id > get_root_ops ( ) const

Get all root ops.

Root ops can also be referred to as "src ops" of the whole graph

Returns
std::vector<Id>

Definition at line 145 of file DependencyGraph.cpp.

References DependencyGraph::all_ops(), and DependencyGraph::src_ops().

Referenced by arm_compute::experimental::dynamic_fusion::add_op_conv2d(), DependencyGraph::empty_id(), ClKernelBlueprint::Implementation::get_graph(), and ClKernelFusionGroup::get_root_kernel().

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 }
std::vector< Id > all_ops() const
Get all operators.

◆ is_dst_tensor()

bool is_dst_tensor ( Id  tensor) const

Check if tensor is the dst tensor of the entire graph.

Parameters
tensor
Returns
true
false

Definition at line 328 of file DependencyGraph.cpp.

References DependencyGraph::dst_tensors(), and DependencyGraph::src_tensors().

329 {
330  if(!tensor_exists(tensor))
331  {
332  return false;
333  }
334  return _adj_dst_ops.at(tensor).empty();
335 }

◆ is_src_tensor()

bool is_src_tensor ( Id  tensor) const

Check if tensor is the src tensor of the entire graph.

Parameters
tensor
Returns
true
false

Definition at line 319 of file DependencyGraph.cpp.

320 {
321  if(!tensor_exists(tensor))
322  {
323  return false;
324  }
325  return _adj_src_ops.at(tensor).empty();
326 }

◆ link_input()

void link_input ( Id  op,
Id  in_tensor 
)

Definition at line 294 of file DependencyGraph.cpp.

References ARM_COMPUTE_ERROR_ON.

Referenced by DependencyGraph::add_operator().

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 }
#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

◆ link_output()

void link_output ( Id  op,
Id  out_tensor 
)

Definition at line 302 of file DependencyGraph.cpp.

References ARM_COMPUTE_ERROR_ON.

Referenced by DependencyGraph::add_operator().

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 }
#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

◆ number_of_ops()

unsigned int number_of_ops ( ) const

Number of operators.

Returns
unsigned int

Definition at line 270 of file DependencyGraph.cpp.

Referenced by DependencyGraph::empty_id(), and DependencyGraph::topological_sort().

271 {
272  return _adj_src_tensors.size();
273 }

◆ number_of_tensors()

unsigned int number_of_tensors ( ) const

Number of tensors.

Returns
unsigned int

Definition at line 275 of file DependencyGraph.cpp.

References DependencyGraph::SerialIdAllocator::alloc().

Referenced by DependencyGraph::empty_id().

276 {
277  return _adj_src_ops.size();
278 }

◆ path_exists_from_op_to_op()

bool path_exists_from_op_to_op ( Id  src_op,
Id  dst_op 
) const

Check if there's a path from src_op to dst_op.

Parameters
src_op
dst_op
Returns
true
false

Definition at line 240 of file DependencyGraph.cpp.

References DependencyGraph::dst_tensors(), DependencyGraph::get_dst_ops(), arm_compute::experimental::dynamic_fusion::is_in(), and DependencyGraph::path_exists_from_tensor_to_op().

Referenced by DependencyGraph::path_exists_from_tensor_to_op().

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 }
bool is_in(const T &v, const std::vector< T > &vec)
std::vector< Id > dst_tensors() const
Get destination tensors of the whole graph.
std::vector< Id > get_dst_ops() const
Get all dst ops of the whole graph.
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.

◆ path_exists_from_tensor_to_op()

bool path_exists_from_tensor_to_op ( Id  src_tensor,
Id  dst_op 
) const

Check if there's a path from src_tensor to dst_op.

Parameters
src_tensor
dst_op
Returns
true
false

Definition at line 228 of file DependencyGraph.cpp.

References DependencyGraph::dst_ops_from_tensor(), and DependencyGraph::path_exists_from_op_to_op().

Referenced by DependencyGraph::path_exists_from_op_to_op().

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 }
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.

◆ remove_operator()

void remove_operator ( Id  op)

Definition at line 120 of file DependencyGraph.cpp.

References DependencyGraph::dst_ops(), arm_compute::mlgo::parser::end(), and DependencyGraph::src_ops().

Referenced by DependencyGraph::empty_id().

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 }
void end(TokenStream &in, bool &valid)
Definition: MLGOParser.cpp:290

◆ remove_tensor()

void remove_tensor ( Id  tensor)

Definition at line 83 of file DependencyGraph.cpp.

References DependencyGraph::dst_tensors(), arm_compute::mlgo::parser::end(), and DependencyGraph::src_tensors().

Referenced by DependencyGraph::empty_id().

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 }
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.
void end(TokenStream &in, bool &valid)
Definition: MLGOParser.cpp:290

◆ src_ops()

std::vector< DependencyGraph::Id > src_ops ( Id  op) const

Definition at line 358 of file DependencyGraph.cpp.

References ARM_COMPUTE_ERROR_ON, arm_compute::mlgo::parser::end(), and DependencyGraph::src_tensors().

Referenced by DependencyGraph::empty_id(), DependencyGraph::get_root_ops(), DependencyGraph::remove_operator(), and DependencyGraph::topological_sort().

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 }
#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
std::vector< Id > src_tensors() const
Get source tensors of the whole graph.
void end(TokenStream &in, bool &valid)
Definition: MLGOParser.cpp:290

◆ src_ops_from_tensor()

std::vector< DependencyGraph::Id > src_ops_from_tensor ( Id  tensor) const

Definition at line 209 of file DependencyGraph.cpp.

Referenced by DependencyGraph::empty_id().

210 {
211  return _adj_src_ops.at(tensor);
212 }

◆ src_tensors() [1/2]

std::vector< DependencyGraph::Id > src_tensors ( Id  op) const

Get source tensors to an operator.

Parameters
op
Returns
std::vector<Id>

Definition at line 175 of file DependencyGraph.cpp.

References ARM_COMPUTE_ERROR_ON.

Referenced by arm_compute::experimental::dynamic_fusion::build(), arm_compute::experimental::dynamic_fusion::generate(), and ClKernelFusionGroup::get_src_tensors().

176 {
177  ARM_COMPUTE_ERROR_ON(!operator_exists(op));
178  return _adj_src_tensors.at(op);
179 }
#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

◆ src_tensors() [2/2]

std::vector< DependencyGraph::Id > src_tensors ( ) const

Get source tensors of the whole graph.

Returns
std::vector<Id>

Definition at line 187 of file DependencyGraph.cpp.

Referenced by DependencyGraph::empty_id(), DependencyGraph::is_dst_tensor(), DependencyGraph::remove_tensor(), DependencyGraph::src_ops(), and DependencyGraph::topological_sort().

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 }

◆ topological_sort()

std::pair< Status, std::vector< DependencyGraph::OpPack > > topological_sort ( ) const

Sort the graph in a topological order.

Returns
std::pair<Status, std::vector<OpPack>>

Definition at line 380 of file DependencyGraph.cpp.

References DependencyGraph::all_ops(), DependencyGraph::dst_ops(), DependencyGraph::dst_tensors(), DependencyGraph::number_of_ops(), arm_compute::RUNTIME_ERROR, DependencyGraph::src_ops(), and DependencyGraph::src_tensors().

Referenced by DependencyGraph::add_operator(), ClCompositeOperator::configure(), DependencyGraph::empty_id(), and arm_compute::experimental::dynamic_fusion::traverse().

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 }
unsigned int number_of_ops() const
Number of operators.
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.

◆ update_merge_point()

Status update_merge_point ( Id  t_id,
Id  merge_point 
)

Update merge_point to point to t_id.

Parameters
t_id
merge_point

Definition at line 51 of file DependencyGraph.cpp.

References arm_compute::RUNTIME_ERROR.

Referenced by DependencyGraph::empty_id().

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 }

Friends And Related Function Documentation

◆ operator==

bool operator== ( const DependencyGraph g0,
const DependencyGraph g1 
)
friend

Strict equality comparison (all internal ids and order of insertion matter).

In the future this may be replaced with a topological comparison, allowing equivalent graphs with different internal ids to be equal

Parameters
g0
g1
Returns
true
false

Definition at line 212 of file DependencyGraph.h.

213  {
214  // Do not compare id allocators
215  return std::make_tuple(
216  g0._adj_src_tensors, g0._adj_dst_tensors, g0._adj_src_ops, g0._adj_dst_ops, g0._merge_to_internal)
217  == std::make_tuple(
218  g1._adj_src_tensors, g1._adj_dst_tensors, g1._adj_src_ops, g1._adj_dst_ops, g1._merge_to_internal);
219  }

The documentation for this class was generated from the following files: