ArmNN
 24.08
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 269 of file SubgraphViewSelector.cpp.

270 {
271  SubgraphView subgraph(graph);
272  return SubgraphViewSelector::SelectSubgraphs(subgraph, selector);
273 }

Referenced by armnn::ApplyBackendOptimizations().

◆ SelectSubgraphs() [2/2]

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

Definition at line 402 of file SubgraphViewSelector.cpp.

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

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:322
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:269
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:387
armnn::ForEachLayerOutput
void ForEachLayerOutput(LayerSelectionInfo::LayerInfoContainer &layerInfos, LayerSelectionInfo &layerInfo, Delegate function)
Definition: SubgraphViewSelector.cpp:301
armnn::SubgraphViewSelector::Subgraphs
std::vector< SubgraphView::SubgraphViewPtr > Subgraphs
Definition: SubgraphViewSelector.hpp:24