From f98d21a244c384c5942e4b261d168f65ecc8a797 Mon Sep 17 00:00:00 2001 From: David Beck Date: Fri, 26 Oct 2018 16:03:03 +0100 Subject: IVGCVSW-1896 : SubGraph selector Change-Id: Iae9a76b10d84d7ba80136b54355f8d37d2df475d --- Android.mk | 3 + CMakeLists.txt | 83 +++--- src/armnn/SubGraph.cpp | 72 +++++ src/armnn/SubGraph.hpp | 53 ++++ src/armnn/SubGraphSelector.cpp | 182 ++++++++++++ src/armnn/SubGraphSelector.hpp | 40 +++ src/armnn/test/SubGraphTests.cpp | 587 +++++++++++++++++++++++++++++++++++++++ 7 files changed, 982 insertions(+), 38 deletions(-) create mode 100644 src/armnn/SubGraph.cpp create mode 100644 src/armnn/SubGraph.hpp create mode 100644 src/armnn/SubGraphSelector.cpp create mode 100644 src/armnn/SubGraphSelector.hpp create mode 100644 src/armnn/test/SubGraphTests.cpp diff --git a/Android.mk b/Android.mk index a2299a14d4..fc126ac649 100644 --- a/Android.mk +++ b/Android.mk @@ -110,6 +110,8 @@ LOCAL_SRC_FILES := \ src/armnn/Optimizer.cpp \ src/armnn/Runtime.cpp \ src/armnn/SerializeLayerParameters.cpp \ + src/armnn/SubGraph.cpp \ + src/armnn/SubGraphSelector.cpp \ src/armnn/InternalTypes.cpp \ src/armnn/Layer.cpp \ src/armnn/LoadedNetwork.cpp \ @@ -196,6 +198,7 @@ LOCAL_SRC_FILES := \ src/armnn/test/UtilsTests.cpp \ src/armnn/test/GraphTests.cpp \ src/armnn/test/RuntimeTests.cpp \ + src/armnn/test/SubGraphTests.cpp \ src/armnn/test/TensorTest.cpp \ src/armnn/test/NetworkTests.cpp \ src/armnn/test/InstrumentTests.cpp \ diff --git a/CMakeLists.txt b/CMakeLists.txt index dcd097c705..9ae6e972f1 100644 --- a/CMakeLists.txt +++ b/CMakeLists.txt @@ -228,38 +228,49 @@ list(APPEND armnn_sources src/armnn/layers/SplitterLayer.cpp src/armnn/layers/SubtractionLayer.cpp src/armnn/layers/SubtractionLayer.hpp - src/armnn/InternalTypes.hpp + src/armnn/Descriptors.cpp + src/armnn/DeviceSpec.hpp + src/armnn/Exceptions.cpp + src/armnn/Graph.cpp + src/armnn/Graph.hpp + src/armnn/IGraphObservable.hpp + src/armnn/Instrument.hpp src/armnn/InternalTypes.cpp - src/armnn/JsonPrinter.hpp + src/armnn/InternalTypes.hpp src/armnn/JsonPrinter.cpp + src/armnn/JsonPrinter.hpp + src/armnn/Layer.cpp src/armnn/LayerFwd.hpp src/armnn/Layer.hpp - src/armnn/Layer.cpp src/armnn/LayersFwd.hpp - src/armnn/Runtime.hpp - src/armnn/Runtime.cpp - src/armnn/SerializeLayerParameters.cpp - src/armnn/SerializeLayerParameters.hpp - src/armnn/Descriptors.cpp - src/armnn/DeviceSpec.hpp - src/armnn/LoadedNetwork.hpp + src/armnn/LayerSupportCommon.hpp + src/armnn/LayerSupport.cpp src/armnn/LoadedNetwork.cpp - src/armnn/Exceptions.cpp - src/armnn/Graph.hpp - src/armnn/Graph.cpp - src/armnn/Network.hpp + src/armnn/LoadedNetwork.hpp src/armnn/Network.cpp + src/armnn/Network.hpp src/armnn/NetworkUtils.hpp + src/armnn/Observable.cpp + src/armnn/Observable.hpp + src/armnn/Optimizer.cpp + src/armnn/Optimizer.hpp + src/armnn/Profiling.cpp src/armnn/ProfilingEvent.cpp src/armnn/ProfilingEvent.hpp - src/armnn/Profiling.cpp - src/armnn/Instrument.hpp - src/armnn/WallClockTimer.hpp - src/armnn/WallClockTimer.cpp + src/armnn/Profiling.hpp + src/armnn/Runtime.cpp + src/armnn/Runtime.hpp + src/armnn/SerializeLayerParameters.cpp + src/armnn/SerializeLayerParameters.hpp + src/armnn/SubGraph.cpp + src/armnn/SubGraph.hpp + src/armnn/SubGraphSelector.cpp + src/armnn/SubGraphSelector.hpp src/armnn/Tensor.cpp + src/armnn/TypeUtils.hpp src/armnn/Utils.cpp - src/armnn/LayerSupport.cpp - src/armnn/LayerSupportCommon.hpp + src/armnn/WallClockTimer.cpp + src/armnn/WallClockTimer.hpp src/armnn/optimizations/All.hpp src/armnn/optimizations/ConvertConstants.hpp src/armnn/optimizations/MovePermuteUp.hpp @@ -270,12 +281,7 @@ list(APPEND armnn_sources src/armnn/optimizations/SquashEqualSiblings.hpp src/armnn/optimizations/OptimizeInverseConversions.hpp src/armnn/optimizations/ConvertFp32NetworkToFp16.hpp - src/armnn/Optimizer.hpp - src/armnn/Optimizer.cpp third-party/half/half.hpp - src/armnn/IGraphObservable.hpp - src/armnn/Observable.hpp - src/armnn/Observable.cpp ) # Files used for Streamline-based profiling backend @@ -334,26 +340,27 @@ endif() if(BUILD_UNIT_TESTS) set(unittest_sources) list(APPEND unittest_sources - src/armnn/test/UnitTests.cpp - src/armnn/test/UnitTests.hpp + src/armnn/test/CreateWorkload.hpp + src/armnn/test/CsvReaderTest.cpp src/armnn/test/EndToEndTest.cpp - src/armnn/test/UtilsTests.cpp + src/armnn/test/FloatingPointConverterTest.cpp src/armnn/test/GraphTests.cpp + src/armnn/test/GraphUtils.hpp + src/armnn/test/InstrumentTests.cpp + src/armnn/test/NetworkTests.cpp + src/armnn/test/ObservableTest.cpp src/armnn/test/OptimizerTests.cpp + src/armnn/test/OptionalTest.cpp src/armnn/test/ProfilerTests.cpp + src/armnn/test/ProfilingEventTest.cpp src/armnn/test/RuntimeTests.cpp src/armnn/test/RuntimeTests.hpp - src/armnn/test/CreateWorkload.hpp - src/armnn/test/TensorTest.cpp + src/armnn/test/SubGraphTests.cpp src/armnn/test/TensorHelpers.hpp - src/armnn/test/CsvReaderTest.cpp - src/armnn/test/NetworkTests.cpp - src/armnn/test/FloatingPointConverterTest.cpp - src/armnn/test/ProfilingEventTest.cpp - src/armnn/test/GraphUtils.hpp - src/armnn/test/InstrumentTests.cpp - src/armnn/test/ObservableTest.cpp - src/armnn/test/OptionalTest.cpp) + src/armnn/test/TensorTest.cpp + src/armnn/test/UnitTests.cpp + src/armnn/test/UnitTests.hpp + src/armnn/test/UtilsTests.cpp) if(BUILD_TF_PARSER) list(APPEND unittest_sources diff --git a/src/armnn/SubGraph.cpp b/src/armnn/SubGraph.cpp new file mode 100644 index 0000000000..5d41f32932 --- /dev/null +++ b/src/armnn/SubGraph.cpp @@ -0,0 +1,72 @@ +// +// Copyright © 2017 Arm Ltd. All rights reserved. +// SPDX-License-Identifier: MIT +// + +#include "Layer.hpp" +#include "SubGraph.hpp" + +#include + +namespace armnn +{ + +SubGraph::SubGraph() +{ +} + +SubGraph::SubGraph(InputSlots && inputs, + OutputSlots && outputs, + Layers && layers) +: m_InputSlots{inputs} +, m_OutputSlots{outputs} +, m_Layers{layers} +{ +} + +const SubGraph::InputSlots & SubGraph::GetInputSlots() const +{ + return m_InputSlots; +} + +const SubGraph::OutputSlots & SubGraph::GetOutputSlots() const +{ + return m_OutputSlots; +} + +const InputSlot* SubGraph::GetInputSlot(unsigned int index) const +{ + return m_InputSlots.at(index); +} + +InputSlot* SubGraph::GetInputSlot(unsigned int index) +{ + return m_InputSlots.at(index); +} + +const OutputSlot* SubGraph::GetOutputSlot(unsigned int index) const +{ + return m_OutputSlots.at(index); +} + +OutputSlot* SubGraph::GetOutputSlot(unsigned int index) +{ + return m_OutputSlots.at(index); +} + +unsigned int SubGraph::GetNumInputSlots() const +{ + return boost::numeric_cast(m_InputSlots.size()); +} + +unsigned int SubGraph::GetNumOutputSlots() const +{ + return boost::numeric_cast(m_OutputSlots.size()); +} + +const SubGraph::Layers & SubGraph::GetLayers() const +{ + return m_Layers; +} + +} // namespace armnn diff --git a/src/armnn/SubGraph.hpp b/src/armnn/SubGraph.hpp new file mode 100644 index 0000000000..312bb115eb --- /dev/null +++ b/src/armnn/SubGraph.hpp @@ -0,0 +1,53 @@ +// +// Copyright © 2017 Arm Ltd. All rights reserved. +// SPDX-License-Identifier: MIT +// + +#pragma once + +#include "Layer.hpp" + +#include +#include + +namespace armnn +{ + +/// +/// The SubGraph class represents a subgraph of a Graph. +/// The data it holds, points to data held by layers of the Graph, so the +/// the contents of the SubGraph becomes invalid when the Layers are destroyed +/// or changed. +/// +class SubGraph final +{ +public: + using InputSlots = std::vector; + using OutputSlots = std::vector; + using Layers = std::unordered_set; + + SubGraph(); + SubGraph(InputSlots && inputs, + OutputSlots && outputs, + Layers && layers); + + const InputSlots & GetInputSlots() const; + const OutputSlots & GetOutputSlots() const; + const Layers & GetLayers() const; + + const InputSlot* GetInputSlot(unsigned int index) const; + InputSlot* GetInputSlot(unsigned int index); + + const OutputSlot* GetOutputSlot(unsigned int index) const; + OutputSlot* GetOutputSlot(unsigned int index); + + unsigned int GetNumInputSlots() const; + unsigned int GetNumOutputSlots() const; + +private: + InputSlots m_InputSlots; + OutputSlots m_OutputSlots; + Layers m_Layers; +}; + +} // namespace armnn diff --git a/src/armnn/SubGraphSelector.cpp b/src/armnn/SubGraphSelector.cpp new file mode 100644 index 0000000000..b87e2b73b1 --- /dev/null +++ b/src/armnn/SubGraphSelector.cpp @@ -0,0 +1,182 @@ +// +// Copyright © 2017 Arm Ltd. All rights reserved. +// SPDX-License-Identifier: MIT +// + +#include "SubGraphSelector.hpp" +#include "Graph.hpp" +#include +#include +#include + +namespace armnn +{ + +namespace +{ + +struct LayerSelectionInfo +{ + using LayerInfoContainer = std::unordered_map; + static constexpr uint32_t InitialSplitId() { return 1; } + + LayerSelectionInfo(Layer* layer, const SubGraphSelector::LayerSelectorFunction& selector) + : m_Layer{layer} + , m_SplitId{0} + , m_IsSelected{selector(*layer)} + { + // fill topology information by storing direct children + for (auto&& slot = m_Layer->BeginOutputSlots(); slot != m_Layer->EndOutputSlots(); ++slot) + { + for (InputSlot* childLayerInputSlot : slot->GetConnections()) + { + Layer& childLayer = childLayerInputSlot->GetOwningLayer(); + m_DirectChildren.push_back(&childLayer); + } + } + } + + void MarkChildrenSplits(LayerInfoContainer& network, + uint32_t splitId, + bool prevSelected) + { + if (m_SplitId < splitId) + { + m_SplitId = splitId; + } + + // introduce a new split point at all non-selected points, but only if the + // previous point was selected. this prevents creating a new subgraph at + // every non-selected layer + if (!m_IsSelected && prevSelected) + { + ++m_SplitId; + } + + for (auto& layer : m_DirectChildren) + { + auto it = network.find(layer); + BOOST_ASSERT_MSG(it != network.end(), "All layers must be part of the topology."); + if (it != network.end()) + { + it->second.MarkChildrenSplits(network, m_SplitId, m_IsSelected); + } + } + } + + bool IsInputLayer() const + { + return m_Layer->GetType() == armnn::LayerType::Input; + } + + void CollectNonSelectedInputs(SubGraph::InputSlots& slots, + const SubGraphSelector::LayerSelectorFunction& selector) + { + for (auto&& slot = m_Layer->BeginInputSlots(); slot != m_Layer->EndInputSlots(); ++slot) + { + OutputSlot* parentLayerOutputSlot = slot->GetConnectedOutputSlot(); + BOOST_ASSERT_MSG(parentLayerOutputSlot != nullptr, "The slots must be connected here."); + if (parentLayerOutputSlot) + { + Layer& parentLayer = parentLayerOutputSlot->GetOwningLayer(); + if (selector(parentLayer) == false) + { + slots.push_back(&(*slot)); + } + } + } + } + + void CollectNonSelectedOutputSlots(SubGraph::OutputSlots& slots, + const SubGraphSelector::LayerSelectorFunction& selector) + { + for (auto&& slot = m_Layer->BeginOutputSlots(); slot != m_Layer->EndOutputSlots(); ++slot) + { + for (InputSlot* childLayerInputSlot : slot->GetConnections()) + { + Layer& childLayer = childLayerInputSlot->GetOwningLayer(); + if (selector(childLayer) == false) + { + slots.push_back(&(*slot)); + } + } + } + } + + std::vector m_DirectChildren; + Layer* m_Layer; + uint32_t m_SplitId; + bool m_IsSelected; +}; + +} // namespace + +SubGraphSelector::SubGraphs +SubGraphSelector::SelectSubGraphs(Graph& graph, + const LayerSelectorFunction& selector) +{ + LayerSelectionInfo::LayerInfoContainer layerInfo; + + for (auto& layer : graph) + { + layerInfo.emplace(layer, LayerSelectionInfo{layer, selector}); + } + + uint32_t splitNo = LayerSelectionInfo::InitialSplitId(); + for (auto& info : layerInfo) + { + if (info.second.IsInputLayer()) + { + // for each input layer we mark the graph where subgraph + // splits need to happen because of the dependency between + // the selected and non-selected nodes + info.second.MarkChildrenSplits(layerInfo, splitNo, false); + } + } + + // Collect all selected layers keyed by split id into a map + using SelectionInfoPtrs = std::vector; + std::unordered_map splitMap; + for (auto& info : layerInfo) + { + if (info.second.m_IsSelected) + { + auto it = splitMap.find(info.second.m_SplitId); + if (it == splitMap.end()) + { + splitMap.insert(std::make_pair(info.second.m_SplitId, SelectionInfoPtrs{&info.second})); + } + else + { + it->second.push_back(&info.second); + } + } + } + + // Now each non-empty split id represents a subgraph + SubGraphs result; + for (auto& splitGraph : splitMap) + { + if (splitGraph.second.empty() == false) + { + SubGraph::OutputSlots outputs; + SubGraph::InputSlots inputs; + SubGraph::Layers layers; + for (auto&& infoPtr : splitGraph.second) + { + infoPtr->CollectNonSelectedOutputSlots(outputs, selector); + infoPtr->CollectNonSelectedInputs(inputs, selector); + layers.insert(infoPtr->m_Layer); + } + result.emplace_back( + std::make_unique( + std::move(inputs), + std::move(outputs), + std::move(layers))); + } + } + + return result; +} + +} // namespace armnn diff --git a/src/armnn/SubGraphSelector.hpp b/src/armnn/SubGraphSelector.hpp new file mode 100644 index 0000000000..f96b986a2e --- /dev/null +++ b/src/armnn/SubGraphSelector.hpp @@ -0,0 +1,40 @@ +// +// Copyright © 2017 Arm Ltd. All rights reserved. +// SPDX-License-Identifier: MIT +// +#pragma once + +#include "SubGraph.hpp" +#include +#include + +namespace armnn +{ + +class Layer; +class Graph; + +class SubGraphSelector final +{ +public: + using SubGraphPtr = std::unique_ptr; + using SubGraphs = std::vector; + using LayerSelectorFunction = std::function; + + /// Selects subgraphs of a graph based on the selector function + /// and the algorithm. Since the SubGraphs returns modifiable pointers + /// the input and output slots of the graph: + /// 1) the graph cannot be const + /// 2) the caller need to make sure that the SubGraphs lifetime is + /// shorter than the graph's + static SubGraphs SelectSubGraphs(Graph& graph, + const LayerSelectorFunction& selector); + +private: + // this is a utility class, don't construct or copy + SubGraphSelector() = delete; + SubGraphSelector(const SubGraphSelector&) = delete; + SubGraphSelector & operator=(const SubGraphSelector&) = delete; +}; + +} // namespace armnn diff --git a/src/armnn/test/SubGraphTests.cpp b/src/armnn/test/SubGraphTests.cpp new file mode 100644 index 0000000000..4f8b0a920c --- /dev/null +++ b/src/armnn/test/SubGraphTests.cpp @@ -0,0 +1,587 @@ +// +// Copyright © 2017 Arm Ltd. All rights reserved. +// SPDX-License-Identifier: MIT +// +#include + +#include + +#include +#include +#include + +#include + +using namespace armnn; + +namespace +{ + +// +// this helper only works if all layers where the inputs connect to are not selected +// +SubGraph::InputSlots CreateInputsFrom(const std::vector & layers) +{ + SubGraph::InputSlots result; + for (auto&& layer : layers) + { + for (auto&& it = layer->BeginInputSlots(); it != layer->EndInputSlots(); ++it) + { + result.push_back(&(*it)); + } + } + return result; +} + +// +// this helper only works if all layers where the outputs connect to are not selected +// +SubGraph::OutputSlots CreateOutputsFrom(const std::vector & layers) +{ + SubGraph::OutputSlots result; + for (auto && layer : layers) + { + for (auto&& it = layer->BeginOutputSlots(); it != layer->EndOutputSlots(); ++it) + { + result.push_back(&(*it)); + } + } + return result; +} + +// +// this takes the inputs, outputs and layers as a copy and the move these copies into the +// resulting subgraph, so the pass bay value is intentional +// +SubGraphSelector::SubGraphPtr CreateSubGraphFrom(SubGraph::InputSlots inputs, + SubGraph::OutputSlots outputs, + SubGraph::Layers layers) +{ + return std::make_unique(std::move(inputs), std::move(outputs), std::move(layers)); +} + +template +std::vector ToSortedArray(Iterator begin, Iterator end) +{ + std::vector result(begin, end); + std::sort(result.begin(), result.end()); + return result; +} + +template +void CompareVectors(const std::vector & result, const std::vector & expected) +{ + BOOST_CHECK_EQUAL_COLLECTIONS(result.begin(), result.end(), expected.begin(), expected.end()); +} + +void CompareSubGraphs(SubGraphSelector::SubGraphPtr & result, + SubGraphSelector::SubGraphPtr & expected) +{ + // expect both to be valid subgraphs + BOOST_TEST((result.get() != nullptr)); + BOOST_TEST((expected.get() != nullptr)); + + if (result.get() != nullptr && expected.get() != nullptr) + { + // try to detect all other obvious errors too, mainly because here + // we can get a nicer error message from boost, the collection test + // also report error for these + BOOST_TEST(result->GetInputSlots().size() == expected->GetInputSlots().size()); + BOOST_TEST(result->GetOutputSlots().size() == expected->GetOutputSlots().size()); + BOOST_TEST(result->GetLayers().size() == expected->GetLayers().size()); + + auto resultLayers = ToSortedArray(result->GetLayers().begin(), + result->GetLayers().end()); + auto expectedLayers = ToSortedArray(expected->GetLayers().begin(), + expected->GetLayers().end()); + CompareVectors(resultLayers, expectedLayers); + + auto resultInputs = ToSortedArray(result->GetInputSlots().begin(), + result->GetInputSlots().end()); + auto expectedInputs = ToSortedArray(expected->GetInputSlots().begin(), + expected->GetInputSlots().end()); + CompareVectors(resultInputs, expectedInputs); + + auto resultOutputs = ToSortedArray(result->GetOutputSlots().begin(), + result->GetOutputSlots().end()); + auto expectedOutputs = ToSortedArray(expected->GetOutputSlots().begin(), + expected->GetOutputSlots().end()); + CompareVectors(resultOutputs, expectedOutputs); + } +} + +} // namespace + +BOOST_AUTO_TEST_SUITE(SubGraphSelection) + +BOOST_AUTO_TEST_CASE(NoSubGraphsForNoMatch) +{ + Graph graph; + + auto output = graph.AddLayer(0, "output"); + graph.InsertNewLayer(output->GetInputSlot(0), 0, "input"); + + SubGraphSelector::SubGraphs subGraphs = + SubGraphSelector::SelectSubGraphs(graph, [](const Layer &) { return false; }); + + BOOST_TEST(subGraphs.empty()); +} + +BOOST_AUTO_TEST_CASE(OneSubGraphsSelectedASingleMatch) +{ + Graph graph; + + auto output = graph.AddLayer(0, "output"); + graph.InsertNewLayer(output->GetInputSlot(0), 0, "input"); + + SubGraphSelector::SubGraphs subGraphs = + SubGraphSelector::SelectSubGraphs( + graph, + // select the output layer only + [](const Layer & l) + { + bool isOutput = l.GetNameStr().compare("output") == 0; + return isOutput; + }); + + BOOST_TEST(subGraphs.size() == 1); + if (subGraphs.size() == 1) + { + auto expected = CreateSubGraphFrom(CreateInputsFrom({output}), + // outputs of 'output' will be empty + CreateOutputsFrom({output}), + {output}); + + CompareSubGraphs(subGraphs[0], expected); + } +} + +BOOST_AUTO_TEST_CASE(MultipleLayersSelectedInTheMiddle) +{ + Graph graph; + + auto output = graph.AddLayer(0, "output"); + auto mid0 = graph.InsertNewLayer(output->GetInputSlot(0), + ActivationDescriptor{}, + "mid0"); + auto mid1 = graph.InsertNewLayer(mid0->GetInputSlot(0), + ActivationDescriptor{}, + "mid1"); + graph.InsertNewLayer(mid1->GetInputSlot(0), 0, "input"); + + SubGraphSelector::SubGraphs subGraphs = + SubGraphSelector::SelectSubGraphs( + graph, + // select the middle layers only + [](const Layer & l) + { + bool toSelect = (l.GetType() == LayerType::Activation); + return toSelect; + }); + + BOOST_TEST(subGraphs.size() == 1); + if (subGraphs.size() == 1) + { + auto expected = CreateSubGraphFrom(CreateInputsFrom({mid1}), + CreateOutputsFrom({mid0}), + {mid1, mid0}); + + CompareSubGraphs(subGraphs[0], expected); + } +} + +BOOST_AUTO_TEST_CASE(IslandInTheMiddle) +{ + // This case represent the scenario when a non-selected X1 node placed in the middle + // of the selected M* nodes: + // + // X0 -> M1 -> M2 -> M3 -> X2 + // X0 -> M4 -> X1 -> M5 -> X2 + // + /* + X0 + / \ + M1 M4 + | | + M2 X1 < the island in the middle ! + | | + M3 M5 + \ / + X2 + */ + // The expected result for this is that M1,M2,M3,M4 will be part of one subgraph and + // M5 will be part of another subgraph and the input and output slots in the subgraphs + // will be set accordingly. + // + Graph graph; + + OriginsDescriptor mergerDescriptor(2); + auto x2 = graph.AddLayer(mergerDescriptor, "x2"); + auto m3 = graph.InsertNewLayer(x2->GetInputSlot(0), + ActivationDescriptor{}, + "m3"); + auto m2 = graph.InsertNewLayer(m3->GetInputSlot(0), + ActivationDescriptor{}, + "m2"); + auto m1 = graph.InsertNewLayer(m2->GetInputSlot(0), + ActivationDescriptor{}, + "m1"); + auto x0 = graph.InsertNewLayer(m1->GetInputSlot(0), 0, "x0"); + + auto m5 = graph.InsertNewLayer(x2->GetInputSlot(1), + ActivationDescriptor{}, + "m5"); + auto x1 = graph.InsertNewLayer(m5->GetInputSlot(0), + Convolution2dDescriptor{}, + "x1"); + auto m4 = graph.InsertNewLayer(x1->GetInputSlot(0), + ActivationDescriptor{}, + "m4"); + + // Connect the other branch to the input layer + x0->GetOutputSlot(0).Connect(m4->GetInputSlot(0)); + + // All selected 'M*' layers will be of Activation type + SubGraphSelector::SubGraphs subGraphs = + SubGraphSelector::SelectSubGraphs( + graph, + // select the middle layers only + [](const Layer & l) + { + bool toSelect = (l.GetType() == LayerType::Activation); + return toSelect; + }); + + // expected results to test against + auto largerSubGraph = CreateSubGraphFrom(CreateInputsFrom({m1, m4}), + CreateOutputsFrom({m3, m4}), + {m1, m4, m2, m3}); + + auto smallerSubGraph = CreateSubGraphFrom(CreateInputsFrom({m5}), + CreateOutputsFrom({m5}), + {m5}); + + BOOST_TEST(subGraphs.size() == 2); + if (subGraphs.size() == 2) + { + // we need to have valid subgraph pointers here + BOOST_TEST((subGraphs[0] != nullptr)); + BOOST_TEST((subGraphs[1] != nullptr)); + + if (subGraphs[0].get() != nullptr && subGraphs[1].get() != nullptr) + { + // sort the subgraphs by layer size, so it is simpler to test + std::sort(subGraphs.begin(), subGraphs.end(), + [](SubGraphSelector::SubGraphPtr & lhs, SubGraphSelector::SubGraphPtr & rhs) + { + return (lhs->GetLayers().size() < rhs->GetLayers().size()); + } + ); + + // one subgraph needs to be size=1 and the other one is 4 + BOOST_TEST(subGraphs[0]->GetLayers().size() == 1); + BOOST_TEST(subGraphs[1]->GetLayers().size() == 4); + + CompareSubGraphs(subGraphs[0], smallerSubGraph); + CompareSubGraphs(subGraphs[1], largerSubGraph); + } + } +} + +BOOST_AUTO_TEST_CASE(MultipleSimpleSubGraphs) +{ + // This test case represents the scenario when we have two distinct subgraphs + // in a simple linear network. The selected nodes are the M* and the + // non-selected ones are the X* + // + // X1 -> M1 -> M2 -> X2 -> M3 -> X3 + // + // The expected results is two subgraphs, one with {M1, M2} and another one + // with {M3} + // + Graph graph; + + // the graph is constructed in reverse order + auto x3 = graph.AddLayer(0, "output"); + auto m3 = graph.InsertNewLayer(x3->GetInputSlot(0), + ActivationDescriptor{}, + "m3"); + auto x2 = graph.InsertNewLayer(m3->GetInputSlot(0), + Convolution2dDescriptor{}, + "x2"); + auto m2 = graph.InsertNewLayer(x2->GetInputSlot(0), + ActivationDescriptor{}, + "m2"); + auto m1 = graph.InsertNewLayer(m2->GetInputSlot(0), + ActivationDescriptor{}, + "m1"); + graph.InsertNewLayer(m1->GetInputSlot(0), 0, "x1"); + + // All selected 'M*' layers will be of Activation type + SubGraphSelector::SubGraphs subGraphs = + SubGraphSelector::SelectSubGraphs( + graph, + // select the middle layers only + [](const Layer & l) + { + bool toSelect = (l.GetType() == LayerType::Activation); + return toSelect; + }); + + // expected results to test against + auto largerSubGraph = CreateSubGraphFrom(CreateInputsFrom({m1}), + CreateOutputsFrom({m2}), + {m1, m2}); + + auto smallerSubGraph = CreateSubGraphFrom(CreateInputsFrom({m3}), + CreateOutputsFrom({m3}), + {m3}); + + BOOST_TEST(subGraphs.size() == 2); + if (subGraphs.size() == 2) + { + // we need to have valid subgraph pointers here + BOOST_TEST((subGraphs[0] != nullptr)); + BOOST_TEST((subGraphs[1] != nullptr)); + + if (subGraphs[0].get() != nullptr && subGraphs[1].get() != nullptr) + { + // sort the subgraphs by layer size, so it is simpler to test + std::sort(subGraphs.begin(), subGraphs.end(), + [](SubGraphSelector::SubGraphPtr & lhs, SubGraphSelector::SubGraphPtr & rhs) + { + return (lhs->GetLayers().size() < rhs->GetLayers().size()); + } + ); + + BOOST_TEST(subGraphs[0]->GetLayers().size() == 1); + BOOST_TEST(subGraphs[1]->GetLayers().size() == 2); + + CompareSubGraphs(subGraphs[0], smallerSubGraph); + CompareSubGraphs(subGraphs[1], largerSubGraph); + } + } +} + +BOOST_AUTO_TEST_CASE(SimpleLinearTest) +{ + //X1 -> M1 -> M2 -> X2 + //Where the input slots of M1 and the output slots of M2 are to be the sub graph boundaries. + Graph graph; + + ActivationDescriptor activationDefaults; + + auto layerX1 = graph.AddLayer(0, "layerX1"); + auto layerX2 = graph.AddLayer(0, "layerX2"); + auto layerM1 = graph.AddLayer(activationDefaults, "layerM1"); + auto layerM2 = graph.AddLayer(activationDefaults, "layerM2"); + + // X1 + // | + // M1 + // | + // M2 + // | + // X2 + + layerX1->GetOutputSlot(0).Connect(layerM1->GetInputSlot(0)); + layerM1->GetOutputSlot(0).Connect(layerM2->GetInputSlot(0)); + layerM2->GetOutputSlot(0).Connect(layerX2->GetInputSlot(0)); + + SubGraphSelector::SubGraphs subGraphs = + SubGraphSelector::SelectSubGraphs( + graph, + // select the activation layers M1 and M2 + [](const Layer & l) + { + bool toSelect = (l.GetType() == LayerType::Activation); + return toSelect; + }); + + BOOST_CHECK(subGraphs.size() == 1); + if(subGraphs.size() == 1) + { + auto expected = CreateSubGraphFrom(CreateInputsFrom({layerM1}), + CreateOutputsFrom({layerM2}), + {layerM1, layerM2}); + + CompareSubGraphs(subGraphs[0], expected); + } +} + +BOOST_AUTO_TEST_CASE(MultiInputSingleOutput) +{ + //X1 -> M1 -> M3 -> X3 + //X2 -> M2 -> M3 -> X3 + //Where the input slots of {M1, M2} and the output slots of M3 are to be the subgraph boundaries. + Graph graph; + + ActivationDescriptor activationDefaults; + + auto layerX1 = graph.AddLayer(0, "layerX1"); + auto layerX2 = graph.AddLayer(1, "layerX2"); + auto layerM1 = graph.AddLayer(activationDefaults, "layerM1"); + auto layerM2 = graph.AddLayer(activationDefaults, "layerM2"); + auto layerM3 = graph.AddLayer("layerM3"); + auto layerX3 = graph.AddLayer(0, "layerX3"); + + // X1 X2 + // | | + // M1 M2 + // \ | + // \ | + // \| + // M3 + // | + // | + // X3 + + layerX1->GetOutputSlot(0).Connect(layerM1->GetInputSlot(0)); + layerX2->GetOutputSlot(0).Connect(layerM2->GetInputSlot(0)); + layerM1->GetOutputSlot(0).Connect(layerM3->GetInputSlot(0)); + layerM2->GetOutputSlot(0).Connect(layerM3->GetInputSlot(1)); + layerM3->GetOutputSlot(0).Connect(layerX3->GetInputSlot(0)); + + SubGraphSelector::SubGraphs subGraphs = + SubGraphSelector::SelectSubGraphs( + graph, + // select Activation and Addition Layers M1, M2 and M3 + [](const Layer & l) + { + bool toSelect = (l.GetType() == LayerType::Activation + || l.GetType() == LayerType::Addition); + return toSelect; + }); + + BOOST_CHECK(subGraphs.size() == 1); + if (subGraphs.size() == 1) + { + auto expected = CreateSubGraphFrom(CreateInputsFrom({layerM1, layerM2}), + CreateOutputsFrom({layerM3}), + {layerM1, layerM2, layerM3}); + + CompareSubGraphs(subGraphs[0], expected); + } +} + +BOOST_AUTO_TEST_CASE(SingleInputMultiOutput) +{ + //X1 -> M1 -> M2 -> X2 + //X1 -> M1 -> M3 -> X3 + //Where the input slots of M1 and the output slots of {M2, M3} are to be the subgraph boundaries. + Graph graph; + + ActivationDescriptor activationDefaults; + ViewsDescriptor viewDefaults(2,4); + + Layer* layerX1 = graph.AddLayer(0, "layerX1"); + Layer* layerM1 = graph.AddLayer(viewDefaults, "layerM1"); + Layer* layerM2 = graph.AddLayer(activationDefaults, "layerM2"); + Layer* layerM3 = graph.AddLayer(activationDefaults, "layerM3"); + Layer* layerX2 = graph.AddLayer(0, "layerX2"); + Layer* layerX3 = graph.AddLayer(1, "layerX3"); + + // X2 + // | + // M1 + // /| + // / | + // / | + // M2 M3 + // | | + // | | + // X2 X3 + + layerX1->GetOutputSlot(0).Connect(layerM1->GetInputSlot(0)); + layerM1->GetOutputSlot(0).Connect(layerM2->GetInputSlot(0)); + layerM1->GetOutputSlot(1).Connect(layerM3->GetInputSlot(0)); + layerM2->GetOutputSlot(0).Connect(layerX2->GetInputSlot(0)); + layerM3->GetOutputSlot(0).Connect(layerX3->GetInputSlot(0)); + + SubGraphSelector::SubGraphs subGraphs = + SubGraphSelector::SelectSubGraphs( + graph, + // select Activation and Splitter Layers M1, M2 and M3 + [](const Layer & l) + { + bool toSelect = (l.GetType() == LayerType::Activation + || l.GetType() == LayerType::Splitter); + return toSelect; + }); + + BOOST_CHECK(subGraphs.size() == 1); + if(subGraphs.size() == 1) + { + auto expected = CreateSubGraphFrom(CreateInputsFrom({layerM1}), + CreateOutputsFrom({layerM2, layerM3}), + {layerM1, layerM2, layerM3}); + + CompareSubGraphs(subGraphs[0], expected); + } +} + +BOOST_AUTO_TEST_CASE(MultiInputMultiOutput) +{ + // This case represents the scenario with multiple inputs and multiple outputs + // + // X1 -> M1 -> M3 -> M4 -> X3 + // X2 -> M2 -> M3 -> M5 -> X4 + // + // Where the input slots of {M1, M2} and the output slots of {M4, M5} are to be the subgraph + // boundaries. + + Graph graph; + + ActivationDescriptor activationDefaults; + OriginsDescriptor mergerDescriptor(2); + + auto x1 = graph.AddLayer(0, "x1"); + auto x2 = graph.AddLayer(1, "x2"); + + auto m1 = graph.AddLayer(activationDefaults, "m1"); + auto m2 = graph.AddLayer(activationDefaults, "m2"); + auto m3 = graph.AddLayer(mergerDescriptor, "m3"); + + auto m4 = graph.AddLayer(activationDefaults, "m4"); + auto m5 = graph.AddLayer(activationDefaults, "m5"); + + auto x3 = graph.AddLayer(0, "x3"); + auto x4 = graph.AddLayer(1, "x4"); + + x1->GetOutputSlot(0).Connect(m1->GetInputSlot(0)); + x2->GetOutputSlot(0).Connect(m2->GetInputSlot(0)); + + m1->GetOutputSlot(0).Connect(m3->GetInputSlot(0)); + m2->GetOutputSlot(0).Connect(m3->GetInputSlot(1)); + + m3->GetOutputSlot(0).Connect(m4->GetInputSlot(0)); + m3->GetOutputSlot(0).Connect(m5->GetInputSlot(0)); + + m4->GetOutputSlot(0).Connect(x3->GetInputSlot(0)); + m5->GetOutputSlot(0).Connect(x4->GetInputSlot(0)); + + + SubGraphSelector::SubGraphs subGraphs = + SubGraphSelector::SelectSubGraphs( + graph, + // select Activation and Merger Layers M1, M2, M3, M4, M5 + [](const Layer & l) + { + bool toSelect = (l.GetType() == LayerType::Activation + || l.GetType() == LayerType::Merger); + return toSelect; + }); + + + BOOST_CHECK(subGraphs.size() == 1); + if (subGraphs.size() == 1) + { + auto expected = CreateSubGraphFrom(CreateInputsFrom({m1, m2}), + CreateOutputsFrom({m4, m5}), + {m1, m2, m3, m4, m5}); + + CompareSubGraphs(subGraphs[0], expected); + } +} + +BOOST_AUTO_TEST_SUITE_END() -- cgit v1.2.1