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	SubgraphViewPtr = std::unique_ptr< SubgraphView >
using	Subgraphs = std::vector< 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 26 of file SubgraphViewSelector.hpp.

Subgraphs

using Subgraphs = std::vector<SubgraphViewPtr>

Definition at line 25 of file SubgraphViewSelector.hpp.

SubgraphViewPtr

using SubgraphViewPtr = std::unique_ptr<SubgraphView>

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.

Referenced by armnn::ApplyBackendOptimizations(), MockBackend::OptimizeSubgraphView(), and TEST_SUITE().

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

SelectSubgraphs() [2/2]

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

static

Definition at line 389 of file SubgraphViewSelector.cpp.

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

{
    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)));
    }

    return result;
}

---

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

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