ArmNN
 24.02
SubgraphViewSelector Class Referencefinal

Algorithm that splits a Graph into Subgraphs based on a filtering of layers (e.g. More...

#include <SubgraphViewSelector.hpp>

Public Types

using Subgraphs = std::vector< SubgraphView::SubgraphViewPtr >
 
using LayerSelectorFunction = std::function< bool(const Layer &)>
 

Static Public Member Functions

static Subgraphs SelectSubgraphs (Graph &graph, const LayerSelectorFunction &selector)
 Selects subgraphs from a graph based on the selector function and the algorithm. More...
 
static Subgraphs SelectSubgraphs (SubgraphView &subgraph, const LayerSelectorFunction &selector)
 

Detailed Description

Algorithm that splits a Graph into Subgraphs based on a filtering of layers (e.g.

which layers are appropriate for a certain backend). The resulting subgraphs are guaranteed to be form a DAG (i.e. there are no dependency loops).

The algorithm aims to produce as few subgraphs as possible.

Definition at line 21 of file SubgraphViewSelector.hpp.

Member Typedef Documentation

◆ LayerSelectorFunction

using LayerSelectorFunction = std::function<bool(const Layer&)>

Definition at line 25 of file SubgraphViewSelector.hpp.

◆ Subgraphs

Definition at line 24 of file SubgraphViewSelector.hpp.

Member Function Documentation

◆ SelectSubgraphs() [1/2]

SubgraphViewSelector::Subgraphs SelectSubgraphs ( Graph graph,
const LayerSelectorFunction selector 
)
static

Selects subgraphs from a graph based on the selector function and the algorithm.

Since the Subgraphs object returns modifiable pointers to the input and output slots of the graph: 1) the graph/sub-graph cannot be const 2) the caller needs to make sure that the Subgraphs lifetime is shorter than the parent graph's

Definition at line 259 of file SubgraphViewSelector.cpp.

260 {
261  SubgraphView subgraph(graph);
262  return SubgraphViewSelector::SelectSubgraphs(subgraph, selector);
263 }

Referenced by armnn::ApplyBackendOptimizations().

◆ SelectSubgraphs() [2/2]

SubgraphViewSelector::Subgraphs SelectSubgraphs ( SubgraphView subgraph,
const LayerSelectorFunction selector 
)
static

Definition at line 389 of file SubgraphViewSelector.cpp.

390 {
391  LayerSelectionInfo::LayerInfoContainer layerInfos;
392 
393  LayerSelectionInfo::LayerInfoQueue processQueue;
394  const SubgraphView::IConnectableLayers& subgraphLayers = subgraph.GetIConnectableLayers();
395  for (auto& layer : subgraphLayers)
396  {
397 
398  auto emplaced = layerInfos.emplace(layer, LayerSelectionInfo{PolymorphicDowncast<Layer*>(layer), selector});
399  LayerSelectionInfo& layerInfo = emplaced.first->second;
400 
401  // Start with Input type layers
402  if (layerInfo.IsInputLayer())
403  {
404  processQueue.push(&layerInfo);
405  }
406  }
407 
408  const SubgraphView::IInputSlots& subgraphInputSlots = subgraph.GetIInputSlots();
409  for (auto& inputSlot : subgraphInputSlots)
410  {
411  Layer& layer = PolymorphicDowncast<InputSlot*>(inputSlot)->GetOwningLayer();
412  auto emplaced = layerInfos.emplace(&layer, LayerSelectionInfo{&layer, selector});
413  LayerSelectionInfo& layerInfo = emplaced.first->second;
414 
415  processQueue.push(&layerInfo);
416  }
417 
418  while (!processQueue.empty())
419  {
420  LayerSelectionInfo& layerInfo = *processQueue.front();
421  processQueue.pop(); // remove front from queue
422 
423  // This layerInfo may have been added to the queue multiple times, so skip if we have already processed it
424  if (!layerInfo.m_IsProcessed)
425  {
426  // Only process this layerInfo if all inputs have been processed
427  if (!IsReadyForSplitAssignment(layerInfos, layerInfo))
428  {
429  // Put back of the process queue if we can't process it just yet
430  processQueue.push(&layerInfo);
431  continue; // Skip to next iteration
432  }
433 
434  // Now we do the processing
435  AssignSplitId(layerInfos, layerInfo);
436 
437  // Queue any child nodes for processing
438  ForEachLayerOutput(layerInfos, layerInfo, [&processQueue](LayerSelectionInfo& childInfo)
439  {
440  processQueue.push(&childInfo);
441  });
442 
443  // We don't need to process this node again
444  layerInfo.m_IsProcessed = true;
445  }
446  }
447 
448  // Collect all selected layers keyed by subgraph representative into a map
449  using SelectionInfoPtrs = std::vector<LayerSelectionInfo*>;
450  std::map<PartialSubgraph*, SelectionInfoPtrs> splitMap;
451  for (auto& info : layerInfos)
452  {
453  if (info.second.m_IsSelected)
454  {
455  auto it = splitMap.find(info.second.m_Subgraph->GetRepresentative());
456  if (it == splitMap.end())
457  {
458  splitMap.insert(
459  std::make_pair(info.second.m_Subgraph->GetRepresentative(), SelectionInfoPtrs{&info.second}));
460  }
461  else
462  {
463  it->second.push_back(&info.second);
464  }
465  }
466  }
467 
468  // Now each entry in splitMap represents a subgraph
469  Subgraphs result;
470  for (auto& splitGraph : splitMap)
471  {
475  for (auto&& infoPtr : splitGraph.second)
476  {
477  infoPtr->CollectNonSelectedInputs(layerInfos, inputs);
478  infoPtr->CollectNonSelectedOutputSlots(layerInfos, outputs);
479  layers.push_back(infoPtr->m_Layer);
480  }
481 
482  // Sort lists into deterministic order, not relying on pointer values which may be different on each execution.
483  // This makes debugging the optimised graph much easier as subsequent stages can also be deterministic.
484  std::sort(inputs.begin(), inputs.end(), [](const IInputSlot* a, const IInputSlot* b)
485  {
486  auto* castA = PolymorphicDowncast<const InputSlot*>(a);
487  auto* castB = PolymorphicDowncast<const InputSlot*>(b);
488  const LayerGuid guidA = castA->GetOwningLayer().GetGuid();
489  const LayerGuid guidB = castB->GetOwningLayer().GetGuid();
490  if (guidA < guidB)
491  {
492  return true;
493  }
494  else if (guidA == guidB)
495  {
496  return (castA->GetSlotIndex() < castB->GetSlotIndex());
497  }
498  return false;
499  });
500  std::sort(outputs.begin(), outputs.end(), [](const IOutputSlot* a, const IOutputSlot* b)
501  {
502  auto* castA = PolymorphicDowncast<const OutputSlot*>(a);
503  auto* castB = PolymorphicDowncast<const OutputSlot*>(b);
504  const LayerGuid guidA = castA->GetOwningLayer().GetGuid();
505  const LayerGuid guidB = castB->GetOwningLayer().GetGuid();
506  if (guidA < guidB)
507  {
508  return true;
509  }
510  else if (guidA == guidB)
511  {
512  return (a->CalculateIndexOnOwner() < b->CalculateIndexOnOwner());
513  }
514  return false;
515  });
516  layers.sort([](const IConnectableLayer* a, const IConnectableLayer* b) { return a->GetGuid() < b->GetGuid(); });
517 
518  // Create a new sub-graph with the new lists of input/output slots and layer
519  result.emplace_back(std::make_unique<SubgraphView>(std::move(layers),
520  std::move(inputs),
521  std::move(outputs)));
522  }
523 
524  // Sort subgraphs list into deterministic order, not relying on pointer values which may be different on each
525  // execution. This makes debugging the optimised graph much easier as subsequent stages can also be
526  // deterministic.
527  std::sort(result.begin(), result.end(), [](const SubgraphView::SubgraphViewPtr& a,
529  {
530  return a->GetIConnectableLayers().front()->GetGuid() < b->GetIConnectableLayers().front()->GetGuid();
531  });
532 
533  return result;
534 }

References armnn::AssignSplitId(), IOutputSlot::CalculateIndexOnOwner(), armnn::ForEachLayerOutput(), SubgraphView::GetIConnectableLayers(), SubgraphView::GetIInputSlots(), armnn::info, and armnn::IsReadyForSplitAssignment().


The documentation for this class was generated from the following files:
armnn::SubgraphView::IOutputSlots
std::vector< IOutputSlot * > IOutputSlots
Definition: SubgraphView.hpp:60
armnn::AssignSplitId
void AssignSplitId(LayerSelectionInfo::LayerInfoContainer &layerInfos, LayerSelectionInfo &layerInfo)
Definition: SubgraphViewSelector.cpp:309
armnn::SubgraphView::IConnectableLayers
std::list< IConnectableLayer * > IConnectableLayers
Definition: SubgraphView.hpp:62
armnn::SubgraphViewSelector::SelectSubgraphs
static Subgraphs SelectSubgraphs(Graph &graph, const LayerSelectorFunction &selector)
Selects subgraphs from a graph based on the selector function and the algorithm.
Definition: SubgraphViewSelector.cpp:259
armnn::SubgraphView::SubgraphViewPtr
std::shared_ptr< SubgraphView > SubgraphViewPtr
Definition: SubgraphView.hpp:56
armnn::SubgraphView::IInputSlots
std::vector< IInputSlot * > IInputSlots
Definition: SubgraphView.hpp:58
armnn::BoostLogSeverityMapping::info
@ info
armnn::IsReadyForSplitAssignment
bool IsReadyForSplitAssignment(LayerSelectionInfo::LayerInfoContainer &layerInfos, LayerSelectionInfo &layerInfo)
Definition: SubgraphViewSelector.cpp:374
armnn::ForEachLayerOutput
void ForEachLayerOutput(LayerSelectionInfo::LayerInfoContainer &layerInfos, LayerSelectionInfo &layerInfo, Delegate function)
Definition: SubgraphViewSelector.cpp:288
armnn::SubgraphViewSelector::Subgraphs
std::vector< SubgraphView::SubgraphViewPtr > Subgraphs
Definition: SubgraphViewSelector.hpp:24