Compute Library
 22.08
ClFusedKernelGraph Struct Reference

#include <ClFusedKernelGraph.h>

Collaboration diagram for ClFusedKernelGraph:
[legend]

Public Types

using Id = DependencyGraph::Id
 
using KernelFusionGroupMap = std::map< Id, utils::memory::deep_unique_ptr< ClKernelFusionGroup > >
 

Public Member Functions

 ClFusedKernelGraph ()=default
 
 ~ClFusedKernelGraph ()=default
 
 ClFusedKernelGraph (const ClFusedKernelGraph &graph)=default
 
ClFusedKernelGraphoperator= (const ClFusedKernelGraph &graph)=default
 
 ClFusedKernelGraph (ClFusedKernelGraph &&graph)=default
 
ClFusedKernelGraphoperator= (ClFusedKernelGraph &&graph)=default
 
Id add_fusion_group (const std::vector< const ClKernel *> &fused_kernels)
 
Status fuse (ClKernelFusionGroup &fg0, ClKernelFusionGroup &fg1)
 
Status can_fuse (const ClKernelFusionGroup &fg0, const ClKernelFusionGroup &fg1) const
 

Data Fields

const ClKernelGraphoriginal_graph {}
 
DependencyGraph fg_dependency {}
 
KernelFusionGroupMap fusion_groups {}
 

Friends

bool operator== (const ClFusedKernelGraph &graph0, const ClFusedKernelGraph &graph1)
 

Detailed Description

Definition at line 134 of file ClFusedKernelGraph.h.

Member Typedef Documentation

◆ Id

Definition at line 137 of file ClFusedKernelGraph.h.

◆ KernelFusionGroupMap

Constructor & Destructor Documentation

◆ ClFusedKernelGraph() [1/3]

ClFusedKernelGraph ( )
default

◆ ~ClFusedKernelGraph()

~ClFusedKernelGraph ( )
default

◆ ClFusedKernelGraph() [2/3]

ClFusedKernelGraph ( const ClFusedKernelGraph graph)
default

◆ ClFusedKernelGraph() [3/3]

ClFusedKernelGraph ( ClFusedKernelGraph &&  graph)
default

Member Function Documentation

◆ add_fusion_group()

Id add_fusion_group ( const std::vector< const ClKernel *> &  fused_kernels)
inline

Definition at line 156 of file ClFusedKernelGraph.h.

References arm_compute::mlgo::parser::end(), and arm_compute::test::validation::k.

157  {
158  auto fg = utils::memory::make_deep_unique<ClKernelFusionGroup, ClKernelFusionGroup>();
159  for(const auto k : fused_kernels)
160  {
161  fg->add_fused_kernel(k);
162  }
163  const auto src_tensors = fg->get_src_tensors();
164  const auto dst_tensors = fg->get_dst_tensors();
165  std::vector<Id> inputs{};
166  std::transform(std::begin(src_tensors), std::end(src_tensors), std::back_inserter(inputs), [this](auto kernel)
167  {
168  return fg_dependency.add_tensor(kernel->id);
169  });
170  std::vector<Id> outputs{};
171  std::transform(std::begin(dst_tensors), std::end(dst_tensors), std::back_inserter(outputs), [this](auto kernel)
172  {
173  return fg_dependency.add_tensor(kernel->id);
174  });
175  const auto id = fg_dependency.add_operator(inputs, outputs);
176  fg->set_id(id.second);
177  fusion_groups[id.second] = std::move(fg);
178  return id.second;
179  }
Id add_tensor(Id merge_tensor=empty_id())
Add a new tensor.
void end(TokenStream &in, bool &valid)
Definition: MLGOParser.cpp:290
std::pair< Status, DependencyGraph::Id > add_operator(const std::vector< Id > &inputs, const std::vector< Id > &outputs)
Add a new operator.

◆ can_fuse()

Status can_fuse ( const ClKernelFusionGroup fg0,
const ClKernelFusionGroup fg1 
) const
inline

ASSUMPTION0: All tensors have 0 or 1 incoming kernel ASSUMPTION1: All kernels have exactly 1 dst tensor (Temporary, can be lifted once we start supporting multi-dst kernels) Note that this does not apply to fusion groups ASSUMPTION2: Simple kernels' tile infos can be overriden (share with) that of the root kernel's ASSUMPTION3: Extension of ASSUMPTION0: All tensors have 0 or 1 incoming fusion group INV0: All Fusion groups have a single root INV1: All Fusion groups have no cycles or loops within themselves <- guaranteed by the underlying ClKernelGraph having no cycles or loops; enforced by DependencyGraph INV2: The ClKernelFusionGroup itself has no cycles or loops <- enforced by DependencyGraph INV3: All non-roots are Simple kernels INV4: All non roots' dst tensors have the same shape as that of the root kernel INV5: All kernels within a fusion group have the same UnitWorkloadStage

Definition at line 319 of file ClFusedKernelGraph.h.

References ARM_COMPUTE_ERROR_ON, arm_compute::detail::have_different_dimensions(), ClKernelFusionGroup::id, arm_compute::experimental::dynamic_fusion::is_in(), arm_compute::RUNTIME_ERROR, arm_compute::experimental::dynamic_fusion::Simple, and tf_frozen_model_extractor::t.

Referenced by arm_compute::experimental::dynamic_fusion::fuse().

320  {
321  /// ASSUMPTION0: All tensors have 0 or 1 incoming kernel
322  /// ASSUMPTION1: All kernels have exactly 1 dst tensor (Temporary, can be lifted once we start supporting multi-dst kernels)
323  /// Note that this does not apply to fusion groups
324  /// ASSUMPTION2: Simple kernels' tile infos can be overriden (share with) that of the root kernel's
325  /// ASSUMPTION3: Extension of ASSUMPTION0: All tensors have 0 or 1 incoming fusion group
326  /// INV0: All Fusion groups have a single root
327  /// INV1: All Fusion groups have no cycles or loops within themselves <- guaranteed by the underlying ClKernelGraph having no cycles or loops; enforced by DependencyGraph
328  /// INV2: The ClKernelFusionGroup itself has no cycles or loops <- enforced by DependencyGraph
329  /// INV3: All non-roots are Simple kernels
330  /// INV4: All non roots' dst tensors have the same shape as that of the root kernel
331  /// INV5: All kernels within a fusion group have the same UnitWorkloadStage
332  const ClKernelFusionGroup *fg_src {};
333  const ClKernelFusionGroup *fg_dst{};
334 
335  // Check 0: Ensure fg0 and fg1 are "directly connected": one of them is a direct parent of the other
336  // This guarantess INV0
337  // This also finds fg_src (parent / root) and fg_dst (child / non-root)
338  if(is_in(fg1.id, fg_dependency.dst_ops(fg0.id)))
339  {
340  fg_src = &fg0;
341  fg_dst = &fg1;
342  }
343  else if(is_in(fg0.id, fg_dependency.dst_ops(fg1.id)))
344  {
345  fg_src = &fg1;
346  fg_dst = &fg0;
347  }
348  else
349  {
350  return Status{ ErrorCode::RUNTIME_ERROR, "Invalid fusion: Not directly connected fusion groups cannot be fused together" };
351  }
352 
353  // Find unconnected tensors between fg_src and fg_dst
354  std::vector<Id> unconnected_tensors{};
355  for(const auto &t : fg_dependency.dst_tensors(fg_src->id))
356  {
357  if(!is_in(t, fg_dependency.src_tensors(fg_dst->id)))
358  {
359  unconnected_tensors.push_back(t);
360  }
361  }
362 
363  // Check 1: Any unconnected tensor cannot be an ancestor of fg_dst
364  // This guarantees INV2: That is, the fused graph does not have any cycles or loops between different fusion groups
365  for(const auto &t : unconnected_tensors)
366  {
368  {
369  return Status{ ErrorCode::RUNTIME_ERROR, "Invalid fusion: the fusion would result in cycles or loops" };
370  }
371  }
372 
373  // Check 2: All non-root fgs are simple. Ensure INV3
374  if(fg_dst->get_root_kernel()->complexity() != Complexity::Simple)
375  {
376  return Status{ ErrorCode::RUNTIME_ERROR, "Invalid fusion: only root kernel can be a complex kernel" };
377  }
378 
379  // Check 3: All non roots' dst tensors have the same shape as that of the root kernel. Ensure INV4
380  const auto root_kernel_dst_tensors = fg_dependency.dst_tensors(fg_src->id);
381  ARM_COMPUTE_ERROR_ON(root_kernel_dst_tensors.size() != 1); // (ASSUMPTION 1: All kernels have exactly 1 dst tensor)
382  const auto root_kernel_dst_tensor_info = original_graph->get_tensor(root_kernel_dst_tensors[0])->desc;
383 
384  for(const auto &t : fg_dependency.dst_tensors(fg_dst->id))
385  {
386  const auto t_info = original_graph->get_tensor(t)->desc;
387  if(detail::have_different_dimensions(root_kernel_dst_tensor_info->tensor_shape(), t_info->tensor_shape(), 0))
388  {
389  return Status{ ErrorCode::RUNTIME_ERROR, "Invalid fusion: all non roots' dst tensors should have the same shape as that of the root kernel" };
390  }
391  }
392 
393  // Check 4: All kernels within a fg have the same UnitWorkloadStage. Ensure INV5
394  if(!(fg_src->get_root_kernel()->config().stage == fg_dst->get_root_kernel()->config().stage))
395  {
396  return Status{ ErrorCode::RUNTIME_ERROR, "Invalid fusion: all kernels within a fusion group should have the same UnitWorkloadStage" };
397  }
398 
399  return Status{};
400  }
#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(Id op) const
Get source tensors to an operator.
bool is_in(const T &v, const std::vector< T > &vec)
bool have_different_dimensions(const Dimensions< T > &dim1, const Dimensions< T > &dim2, unsigned int upper_dim)
Definition: Validate.h:47
std::vector< Id > dst_tensors(Id op) const
Get destination tensors to an operator.
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.

◆ fuse()

Status fuse ( ClKernelFusionGroup fg0,
ClKernelFusionGroup fg1 
)
inline

PRE: Already checked by can_fuse, and thus all the INVs and ASSUMPTIONS still hold

Definition at line 181 of file ClFusedKernelGraph.h.

References ClKernelFusionGroup::id, arm_compute::experimental::dynamic_fusion::is_in(), arm_compute::RUNTIME_ERROR, tf_frozen_model_extractor::t, arm_compute::experimental::dynamic_fusion::traverse(), and arm_compute::utils::cast::U.

Referenced by arm_compute::experimental::dynamic_fusion::fuse().

182  {
183  /// PRE: Already checked by can_fuse, and thus all the INVs and ASSUMPTIONS still hold
184  ClKernelFusionGroup *fg_src{};
185  ClKernelFusionGroup *fg_dst{};
186  // Find fg_src (parent / root) and fg_dst (child / non-root)
187  if(is_in(fg1.id, fg_dependency.dst_ops(fg0.id)))
188  {
189  fg_src = &fg0;
190  fg_dst = &fg1;
191  }
192  else if(is_in(fg0.id, fg_dependency.dst_ops(fg1.id)))
193  {
194  fg_src = &fg1;
195  fg_dst = &fg0;
196  }
197  else
198  {
199  return Status{ ErrorCode::RUNTIME_ERROR, "Invalid fusion: Not directly connected fusion groups cannot be fused together" };
200  }
201 
202  for(const auto &t : fg_dependency.src_tensors(fg_dst->id))
203  {
204  if(!is_in(t, fg_dependency.dst_tensors(fg_src->id)))
205  {
206  // Link any incoming tensors of fg_dst, that ARE NOT in between fg_src and fg_dst, to fg_src
207 
208  // Before:
209  // fg_src
210  // |
211  // .. t1
212  // | |
213  // -> fg_dst <-
214  //
215  // After:
216  // fg_src <---t1
217  //
218  const auto st = link_src_tensors(fg_src->id, { t });
219  if(!bool(st))
220  {
221  return st;
222  }
223  }
224  else
225  {
226  const auto dst_fgs = fg_dependency.dst_ops_from_tensor(t);
227  if(dst_fgs.size() == 1U && dst_fgs.at(0) == fg_dst->id)
228  {
229  // Remove any incoming tensors of fg_dst, that ARE in between fg_src and fg_dst
230  // AND that are not connected to any other outgoing fgs (Note that they cannot connect to any other incoming fgs as all tensors can have at most 1 incoming fg (ASSUMPTION 3))
231 
232  // Before:
233  // fg_src
234  // |
235  // t0
236  // |
237  // -> fg_dst
238  //
239  // After:
240  // fg_src
241  //
242  const auto st = remove_fg_tensor(t);
243  if(!bool(st))
244  {
245  return st;
246  }
247  }
248  else
249  {
250  // If the tensors ARE in between fg_src and fg_dst
251  // BUT have any other outgoing fgs than fg_dst, then we leave it as a dst tensor to the fused fg_src
252 
253  // Before:
254  // fg_src
255  // |
256  // t0
257  // |
258  // |-----------
259  // | |
260  // -> fg_dst -> fg_other
261  //
262  // After:
263  // fg_src
264  // |
265  // t0
266  // |
267  // -> fg_other
268  //
269 
270  // Note that this may seem like a case we shouldn't fuse. But actually all it means is that t0 is an
271  // intermediate tensor between the fused fg_src and fg_dst, but only that we also STORE it to memory
272  // so that any unfused fg's (fg_other in this case) can read it.
273  // So all this means that we not only can STORE the tensors at the "end" of a fusion group,
274  // but also any other tensors that are not source tensors. And all tensors that are STORED (exported),
275  // can be termed "dst tensors" to a fusion group
276  void();
277  }
278  }
279  }
280 
281  for(const auto &t : fg_dependency.dst_tensors(fg_dst->id))
282  {
283  // Link any outgoing tensors of fg_dst to fg_src
284 
285  // Before:
286  // fg_src
287  // |
288  // ..
289  // |
290  // -> fg_dst
291  // |
292  // |--------
293  // | |
294  // |-> t0 |-> t1
295  //
296  // After:
297  // fg_src
298  // |
299  // |--------
300  // | |
301  // |-> t0 |-> t1
302  //
303  const auto st = link_dst_tensors(fg_src->id, { t });
304  if(!bool(st))
305  {
306  return st;
307  }
308  }
309 
310  // Merge fg_dst's graph into fg_src's graph
311  for(const auto kernel : traverse(*fg_dst))
312  {
313  fg_src->add_fused_kernel(kernel);
314  }
315 
316  const auto st = remove_fg(fg_dst->id);
317  return st;
318  }
std::vector< const ClKernel * > traverse(const ClKernelFusionGroup &group)
std::vector< Id > src_tensors(Id op) const
Get source tensors to an operator.
bool is_in(const T &v, const std::vector< T > &vec)
std::vector< Id > dst_tensors(Id op) const
Get destination tensors to an operator.

◆ operator=() [1/2]

ClFusedKernelGraph& operator= ( const ClFusedKernelGraph graph)
default

◆ operator=() [2/2]

ClFusedKernelGraph& operator= ( ClFusedKernelGraph &&  graph)
default

Friends And Related Function Documentation

◆ operator==

bool operator== ( const ClFusedKernelGraph graph0,
const ClFusedKernelGraph graph1 
)
friend

NOTE: fg_dependency may change based on the order of fusion, and thus is omitted in the comparison. The fusion groups can already guarantee the equivalence of fusion In the future we may want to enforce a stronger equivalence by implementing topological comparison between DependencyGraph s

Definition at line 148 of file ClFusedKernelGraph.h.

149  {
150  /// NOTE: fg_dependency may change based on the order of fusion, and thus is omitted in the comparison.
151  /// The fusion groups can already guarantee the equivalence of fusion
152  /// In the future we may want to enforce a stronger equivalence by implementing topological comparison between @ref DependencyGraph s
153  return graph0.original_graph == graph1.original_graph && graph0.fusion_groups == graph1.fusion_groups;
154  }

Field Documentation

◆ fg_dependency

◆ fusion_groups

KernelFusionGroupMap fusion_groups {}

◆ original_graph


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