A multi-input (tensors), multi-output (tensors) acyclic directed graph 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...

Public Types
using	Id = int32_t

using	TensorId = Id

using	OperatorId = Id

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

Public Member Functions
	DependencyGraph ()=default

bool	try_add_operator_as_linear (OperatorId op, const std::vector< TensorId > &inputs, const std::vector< TensorId > &outputs, bool is_output=false) const
	Try adding an operator (without actually adding it), while keeping the graph as a "linear sequence" / list. More...

void	add_operator_as_linear (OperatorId op, const std::vector< TensorId > &inputs, const std::vector< TensorId > &outputs, bool is_output=false)
	Add an operator, while keeping the graph as a "linear sequence". More...

bool	add_operator (OperatorId op, const std::vector< TensorId > &inputs, const std::vector< TensorId > &outputs, bool is_output=false)
	Add a new operator Return invalid if it violates the DAG invariant Invalid operation will not change the graph. More...

std::vector< OpPack >	build_operators_sequence () const
	Build a sequence of operators from the acyclic graph of operators. More...

std::vector< OperatorId >	src_ops_from_tensor (TensorId tensor) const

std::vector< OperatorId >	dst_ops_from_tensor (TensorId tensor) const

std::vector< TensorId >	all_tensors () const
	Get all tensors. More...

std::vector< TensorId >	global_src_tensors () const
	Get source tensors of the whole graph. More...

std::vector< TensorId >	global_dst_tensors () const
	Get destination tensors of the whole graph. More...

std::vector< TensorId >	intermediate_tensors () const
	Get intermediate tensors of the whole graph. More...

std::vector< OperatorId >	get_root_ops () const
	Get all root ops. More...

Friends
std::ostream &	operator<< (std::ostream &os, const DependencyGraph &)

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

Detailed Description

A multi-input (tensors), multi-output (tensors) acyclic directed graph Represented as a doubly-linked adjacency list with the differentiation between source and destination.

Definition at line 52 of file DependencyGraph.h.

Member Typedef Documentation

◆ AdjList

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

Adjacency list.

Definition at line 61 of file DependencyGraph.h.

◆ Id

using Id = int32_t

Definition at line 55 of file DependencyGraph.h.

◆ OperatorId

using OperatorId = Id

Definition at line 57 of file DependencyGraph.h.

◆ TensorId

using TensorId = Id

Definition at line 56 of file DependencyGraph.h.

Constructor & Destructor Documentation

◆ DependencyGraph()

DependencyGraph ( )

default

Member Function Documentation

◆ add_operator()

bool add_operator	(	OperatorId	op,
		const std::vector< TensorId > &	inputs,
		const std::vector< TensorId > &	outputs,
		bool	is_output = `false`
	)

inline

Add a new operator Return invalid if it violates the DAG invariant Invalid operation will not change the graph.

Parameters

[in]	op	Operator to add
[in]	inputs	Input tensors to the operator
[in]	outputs	Output tensors to the operator
[in]	is_output	Whether this is an output operator

Definition at line 186 of file DependencyGraph.h.

     {
         if(operator_exists(op))
         {
             return false;
         }
         _adj_src_tensors[op] = {};
         _adj_dst_tensors[op] = {};
         for(auto in_tensor : inputs)
         {
             // Linking input tensor to operator node will never create a cycle / loop because we guarantee
             // each op is newly created, so every <input, op> pair / edge is new
             link_input(op, in_tensor);
         }
         for(auto out_tensor : outputs)
         {
             // If there exists a back path from op's output tensor to op already, then linking the two will create a loop / cycle
             if(path_exists_from_tensor_to_op(out_tensor, op))
             {
                 remove_operator(op);
                 return false;
             }
             else
             {
                 link_output(op, out_tensor);
             }
         }
  
         if(!is_output)
         {
             _last_op_available = true;
             _last_op = op;
         }
  
         return true;
     }

Referenced by GpuKernelComponentGraph::add_new_component(), and DependencyGraph::add_operator_as_linear().

◆ add_operator_as_linear()

void add_operator_as_linear	(	OperatorId	op,
		const std::vector< TensorId > &	inputs,
		const std::vector< TensorId > &	outputs,
		bool	is_output = `false`
	)

inline

Add an operator, while keeping the graph as a "linear sequence".

PRECONDITION: The current graph is already linear INVARIANT: The list can only grow from head to tail INVARIANT: POSTCONDITION: The graph is linear

Definition at line 171 of file DependencyGraph.h.

     {
         const auto success = add_operator(op, inputs, outputs, is_output);
         ARM_COMPUTE_UNUSED(success);
         ARM_COMPUTE_ERROR_ON(!success);
     }

References DependencyGraph::add_operator(), ARM_COMPUTE_ERROR_ON, and ARM_COMPUTE_UNUSED.

Referenced by GpuOperatorGroup::add_operator().

◆ all_tensors()

std::vector<TensorId> all_tensors ( ) const

inline

Get all tensors.

Returns: std::vector<TensorId>

Definition at line 280 of file DependencyGraph.h.

     {
         std::vector<TensorId> tensors{};
         std::transform(std::begin(_adj_src_ops), std::end(_adj_src_ops), std::back_inserter(tensors), [](const auto & it)
         {
             return it.first;
         });
         return tensors;
     }

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

◆ build_operators_sequence()

std::vector<OpPack> build_operators_sequence ( ) const

inline

Build a sequence of operators from the acyclic graph of operators.

The graph will be visited in depth-first strategy. The operator can only be added to the sequence when all operators that supply the input tensors have been added. Otherwise, the operator will be ignored and later visited again. In other words, the dependency between operators will be preserved in the sequence.

Definition at line 230 of file DependencyGraph.h.

     {
         std::vector<OpPack> ops_seq;
         std::set<Id> done_ops;
         std::set<Id> done_tensors;
  
         const auto input_tensors = global_src_tensors();
  
         for(auto tensor : input_tensors)
         {
             done_tensors.insert(tensor);
  
             for(auto op : _adj_dst_ops.at(tensor))
             {
                 build_operators_sequence_from_op(op, ops_seq, done_ops, done_tensors);
             }
         }
  
         return ops_seq;
     }

References DependencyGraph::global_src_tensors(), and tensor.

Referenced by GpuKernelComponentGraph::fuse().

◆ dst_ops_from_tensor()

std::vector<OperatorId> dst_ops_from_tensor ( TensorId tensor ) const

inline

Definition at line 272 of file DependencyGraph.h.

     {
         return _adj_dst_ops.at(tensor);
     }

References tensor.

◆ get_root_ops()

std::vector<OperatorId> get_root_ops ( ) const

inline

Get all root ops.

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

Returns: std::vector<OperatorId>

Definition at line 352 of file DependencyGraph.h.

     {
         std::vector<OperatorId> ops{};
         const auto              op_list = all_ops();
  
         for(auto op : op_list)
         {
             if(src_ops(op).empty())
             {
                 ops.emplace_back(op);
             }
         }
         return ops;
     }

Referenced by GpuOperatorGroup::get_root_operator().

◆ global_dst_tensors()

std::vector<TensorId> global_dst_tensors ( ) const

inline

Get destination tensors of the whole graph.

Returns: std::vector<TensorId>

Definition at line 309 of file DependencyGraph.h.

     {
         std::vector<TensorId> tensors;
         for(auto tensor_dst_ops : _adj_dst_ops)
         {
             if(tensor_dst_ops.second.empty())
             {
                 tensors.push_back(tensor_dst_ops.first);
             }
         }
         return tensors;
     }

◆ global_src_tensors()

std::vector<TensorId> global_src_tensors ( ) const

inline

Get source tensors of the whole graph.

Returns: std::vector<TensorId>

Definition at line 293 of file DependencyGraph.h.

     {
         std::vector<TensorId> tensors;
         for(auto tensor_src_ops : _adj_src_ops)
         {
             if(tensor_src_ops.second.empty())
             {
                 tensors.push_back(tensor_src_ops.first);
             }
         }
         return tensors;
     }

Referenced by DependencyGraph::build_operators_sequence().

◆ intermediate_tensors()

std::vector<TensorId> intermediate_tensors ( ) const

inline

Get intermediate tensors of the whole graph.

Returns: std::vector<TensorId>

Definition at line 325 of file DependencyGraph.h.

     {
         std::vector<TensorId> tensors;
  
         // If a tensor is used to connect the input of an operator and the output of another operator,
         // it is not allocated in the memory. The tensor exists as a temporary variable only.
         for(auto src_tensor : _adj_src_ops)
         {
             if(!src_tensor.second.empty())
             {
                 const auto dst_tensor = _adj_dst_ops.find(src_tensor.first);
                 if(dst_tensor != _adj_dst_ops.end())
                 {
                     if(!dst_tensor->second.empty())
                     {
                         tensors.push_back(src_tensor.first);
                     }
                 }
             }
         }
  
         return tensors;
     }

◆ src_ops_from_tensor()

std::vector<OperatorId> src_ops_from_tensor ( TensorId tensor ) const

inline

Definition at line 268 of file DependencyGraph.h.

     {
         return _adj_src_ops.at(tensor);
     }

References tensor.

◆ try_add_operator_as_linear()

bool try_add_operator_as_linear	(	OperatorId	op,
		const std::vector< TensorId > &	inputs,
		const std::vector< TensorId > &	outputs,
		bool	is_output = `false`
	)		const

inline

Try adding an operator (without actually adding it), while keeping the graph as a "linear sequence" / list.

Rule: If the new operator is not the first operator, at least one input tensor must be the output tensor of the last non-output operator. All other input tensors must be the global input of the graph (i.e. not the output of any operator).

Rule: The output tensor of the new operator must not be the input tensor of any previously added operator.

PRECONDITION: The current graph is already linear

Returns: true If the operator can be added while keeping the graph as a linear sequence; false Otherwise

Definition at line 98 of file DependencyGraph.h.

     {
         ARM_COMPUTE_UNUSED(op, is_output);
         if(all_ops().empty())
         {
             return true;
         }
  
         // If the new operator is not the first operator, at least one input tensor must be
         // the output tensor of the last non-output operator. All other input tensors must be
         // the global input of the graph (i.e. not the output of any operator).
         if(_last_op_available)
         {
             auto use_input_from_last_op = false;
  
             for(auto src_tensor : inputs)
             {
                 const auto src_ops = _adj_src_ops.find(src_tensor);
  
                 if(src_ops != _adj_src_ops.end())
                 {
                     ARM_COMPUTE_ERROR_ON(src_ops->second.size() > 1);
  
                     if(!src_ops->second.empty())
                     {
                         const auto src_op = src_ops->second[0];
  
                         if(src_op == _last_op)
                         {
                             if(use_input_from_last_op)
                             {
                                 // To be safe, we also forbid using the output tensor
                                 // of the last operator twice.
                                 return false;
                             }
  
                             use_input_from_last_op = true;
                         }
                         else
                         {
                             // The input tensor of this operator must not be the output tensor
                             // of any other operator except the last non-output operator.
                             return false;
                         }
                     }
                 }
             }
  
             if(!use_input_from_last_op)
             {
                 // At least one input tensor must be the output tensor of the last non-output operator.
                 return false;
             }
         }
  
         // The output tensor of the new operator must not be the input tensor of any previously
         // added operator.
         for(auto dst_tensor : outputs)
         {
             if(_adj_dst_ops.find(dst_tensor) != _adj_dst_ops.end())
             {
                 return false;
             }
         }
  
         return true;
     }

References ARM_COMPUTE_ERROR_ON, and ARM_COMPUTE_UNUSED.

Referenced by GpuOperatorGroup::try_add_operator().

Friends And Related Function Documentation

◆ operator<<

std::ostream& operator<<	(	std::ostream &	os,
		const DependencyGraph &
	)

friend

◆ 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

[in]	g0
[in]	g1

Returns: true If the same; false Otherwise

Definition at line 260 of file DependencyGraph.h.

     {
         // Do not compare id allocators
         return std::make_tuple(
                    g0._adj_src_tensors, g0._adj_dst_tensors, g0._adj_src_ops, g0._adj_dst_ops)
                == std::make_tuple(
                    g1._adj_src_tensors, g1._adj_dst_tensors, g1._adj_src_ops, g1._adj_dst_ops);
     }

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

src/dynamic_fusion/sketch/utils/DependencyGraph.h

Data Structures

Public Types

Public Member Functions

Friends

Detailed Description

Member Typedef Documentation

◆ AdjList

◆ Id

◆ OperatorId

◆ TensorId

Constructor & Destructor Documentation

◆ DependencyGraph()

Member Function Documentation

◆ add_operator()

◆ add_operator_as_linear()

◆ all_tensors()

◆ build_operators_sequence()

◆ dst_ops_from_tensor()

◆ get_root_ops()

◆ global_dst_tensors()

◆ global_src_tensors()

◆ intermediate_tensors()

◆ src_ops_from_tensor()

◆ try_add_operator_as_linear()

Friends And Related Function Documentation

◆ operator<<

◆ operator==