SubgraphViewSelector Class Reference

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

using Subgraphs = std::vector<SubgraphView::SubgraphViewPtr>

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.

{
    SubgraphView subgraph(graph);
    return SubgraphViewSelector::SelectSubgraphs(subgraph, selector);
}

Referenced by armnn::ApplyBackendOptimizations().

SelectSubgraphs() [2/2]

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

static

Definition at line 389 of file SubgraphViewSelector.cpp.

{
    LayerSelectionInfo::LayerInfoContainer layerInfos;
 
    LayerSelectionInfo::LayerInfoQueue processQueue;
    const SubgraphView::IConnectableLayers& subgraphLayers = subgraph.GetIConnectableLayers();
    for (auto& layer : subgraphLayers)
    {
 
        auto emplaced = layerInfos.emplace(layer, LayerSelectionInfo{PolymorphicDowncast<Layer*>(layer), selector});
        LayerSelectionInfo& layerInfo = emplaced.first->second;
 
        // Start with Input type layers
        if (layerInfo.IsInputLayer())
        {
            processQueue.push(&layerInfo);
        }
    }
 
    const SubgraphView::IInputSlots& subgraphInputSlots = subgraph.GetIInputSlots();
    for (auto& inputSlot : subgraphInputSlots)
    {
        Layer& layer = PolymorphicDowncast<InputSlot*>(inputSlot)->GetOwningLayer();
        auto emplaced = layerInfos.emplace(&layer, LayerSelectionInfo{&layer, selector});
        LayerSelectionInfo& layerInfo = emplaced.first->second;
 
        processQueue.push(&layerInfo);
    }
 
    while (!processQueue.empty())
    {
        LayerSelectionInfo& layerInfo = *processQueue.front();
        processQueue.pop(); // remove front from queue
 
        // This layerInfo may have been added to the queue multiple times, so skip if we have already processed it
        if (!layerInfo.m_IsProcessed)
        {
            // Only process this layerInfo if all inputs have been processed
            if (!IsReadyForSplitAssignment(layerInfos, layerInfo))
            {
                // Put back of the process queue if we can't process it just yet
                processQueue.push(&layerInfo);
                continue; // Skip to next iteration
            }
 
            // Now we do the processing
            AssignSplitId(layerInfos, layerInfo);
 
            // Queue any child nodes for processing
            ForEachLayerOutput(layerInfos, layerInfo, [&processQueue](LayerSelectionInfo& childInfo)
                {
                    processQueue.push(&childInfo);
                });
 
            // We don't need to process this node again
            layerInfo.m_IsProcessed = true;
        }
    }
 
    // Collect all selected layers keyed by subgraph representative into a map
    using SelectionInfoPtrs = std::vector<LayerSelectionInfo*>;
    std::map<PartialSubgraph*, SelectionInfoPtrs> splitMap;
    for (auto& info : layerInfos)
    {
        if (info.second.m_IsSelected)
        {
            auto it = splitMap.find(info.second.m_Subgraph->GetRepresentative());
            if (it == splitMap.end())
            {
                splitMap.insert(
                    std::make_pair(info.second.m_Subgraph->GetRepresentative(), SelectionInfoPtrs{&info.second}));
            }
            else
            {
                it->second.push_back(&info.second);
            }
        }
    }
 
    // Now each entry in splitMap represents a subgraph
    Subgraphs result;
    for (auto& splitGraph : splitMap)
    {
        SubgraphView::IInputSlots inputs;
        SubgraphView::IOutputSlots outputs;
        SubgraphView::IConnectableLayers layers;
        for (auto&& infoPtr : splitGraph.second)
        {
            infoPtr->CollectNonSelectedInputs(layerInfos, inputs);
            infoPtr->CollectNonSelectedOutputSlots(layerInfos, outputs);
            layers.push_back(infoPtr->m_Layer);
        }
 
        // Sort lists into deterministic order, not relying on pointer values which may be different on each execution.
        // This makes debugging the optimised graph much easier as subsequent stages can also be deterministic.
        std::sort(inputs.begin(), inputs.end(), [](const IInputSlot* a, const IInputSlot* b)
        {
            auto* castA = PolymorphicDowncast<const InputSlot*>(a);
            auto* castB = PolymorphicDowncast<const InputSlot*>(b);
            const LayerGuid guidA = castA->GetOwningLayer().GetGuid();
            const LayerGuid guidB = castB->GetOwningLayer().GetGuid();
            if (guidA < guidB)
            {
                return true;
            }
            else if (guidA == guidB)
            {
                return (castA->GetSlotIndex() < castB->GetSlotIndex());
            }
            return false;
        });
        std::sort(outputs.begin(), outputs.end(), [](const IOutputSlot* a, const IOutputSlot* b)
        {
            auto* castA = PolymorphicDowncast<const OutputSlot*>(a);
            auto* castB = PolymorphicDowncast<const OutputSlot*>(b);
            const LayerGuid guidA = castA->GetOwningLayer().GetGuid();
            const LayerGuid guidB = castB->GetOwningLayer().GetGuid();
            if (guidA < guidB)
            {
                return true;
            }
            else if (guidA == guidB)
            {
                return (a->CalculateIndexOnOwner() < b->CalculateIndexOnOwner());
            }
            return false;
        });
        layers.sort([](const IConnectableLayer* a, const IConnectableLayer* b) { return a->GetGuid() < b->GetGuid(); });
 
        // Create a new sub-graph with the new lists of input/output slots and layer
        result.emplace_back(std::make_unique<SubgraphView>(std::move(layers),
                                                           std::move(inputs),
                                                           std::move(outputs)));
    }
 
    // Sort subgraphs list into deterministic order, not relying on pointer values which may be different on each 
    // execution. This makes debugging the optimised graph much easier as subsequent stages can also be 
    // deterministic.
    std::sort(result.begin(), result.end(), [](const SubgraphView::SubgraphViewPtr& a,
                                               const SubgraphView::SubgraphViewPtr& b)
    {
        return a->GetIConnectableLayers().front()->GetGuid() < b->GetIConnectableLayers().front()->GetGuid();
    });
 
    return result;
}

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:

• src/armnn/SubgraphViewSelector.hpp
• src/armnn/SubgraphViewSelector.cpp