From 30db8ad8b15e5d0e94ae2ff64c246350885c4b6b Mon Sep 17 00:00:00 2001 From: Rob Hughes Date: Fri, 8 Nov 2019 15:50:10 +0000 Subject: NNXSW-1853 Change SubgraphViewSelector algorithm The current algorithm in SubgraphViewSelector has a bug that can lead to it producing subgraphs which have a dependency cycle (see the newly added test case 'ValidMerge' for a repro). It also fails to merge subgraphs in some cases where it could, which leads to smaller subgraphs. In the case of FSRCNN, the NPU cannot support these smaller subgraphs and so this is blocking us from supporting that network. This commit changes the algorithm to fix the dependency bug and also make it so that subgraphs are merged in the cases that were missed before. It also adds some unit tests to cover cases that were problematic before, and to extend coverage for the new algorithm. The new algorithm has two downsides compared to the previous one: 1. Disjoint subgraphs are not merged. This can never lead to a failed compilation by the NPU and so I believe this is less of an issue than the previous algorithm's "missed merges". This could however lead to a runtime performance loss in some cases as the NPU will be unable to parallelise as many operations. There are some unit tests that cover this which I have disabled. 2. The performance is worse. I have spent some time analysing this and for a graph with ~1000 layers the new algorithm takes 20ms vs. the old algorithm's 4ms (on my desktop PC). I believe the performance is still within acceptable limits. I also compared inception V3 (which was the network which caused performance issues with the original version of the splitting algorithm) and this new algorithm has not regressed there (200-300us in both cases). Change-Id: I1dd64a779f272723621e04d203b5a2752a6af2ef Signed-off-by: Robert Hughes --- .../test/OptimizeSubgraphViewTests.cpp | 75 ++++++++++++---------- 1 file changed, 40 insertions(+), 35 deletions(-) (limited to 'src/backends/backendsCommon/test/OptimizeSubgraphViewTests.cpp') diff --git a/src/backends/backendsCommon/test/OptimizeSubgraphViewTests.cpp b/src/backends/backendsCommon/test/OptimizeSubgraphViewTests.cpp index 7cb5ded773..ca3c563757 100644 --- a/src/backends/backendsCommon/test/OptimizeSubgraphViewTests.cpp +++ b/src/backends/backendsCommon/test/OptimizeSubgraphViewTests.cpp @@ -877,8 +877,13 @@ void PartiallySupportedSubgraphTestImpl() // Check the substitutions // ----------------------- - const OptimizationViews::Substitutions& substitutions = optimizationViews.GetSubstitutions(); + OptimizationViews::Substitutions substitutions = optimizationViews.GetSubstitutions(); BOOST_TEST(substitutions.size() == 2); + // Sort into a consistent order + std::sort(substitutions.begin(), substitutions.end(), [](auto s1, auto s2) { + return strcmp(s1.m_SubstitutableSubgraph.GetLayers().front()->GetName(), + s2.m_SubstitutableSubgraph.GetLayers().front()->GetName()) < 0; + }); std::vector expectedSubstitutableSubgraphSizes{ { 1, 1, 1 }, { 1, 1, 1 } }; @@ -914,8 +919,12 @@ void PartiallySupportedSubgraphTestImpl() // Check the failed subgraphs // -------------------------- - const OptimizationViews::Subgraphs& failedSubgraphs = optimizationViews.GetFailedSubgraphs(); + OptimizationViews::Subgraphs failedSubgraphs = optimizationViews.GetFailedSubgraphs(); BOOST_TEST(failedSubgraphs.size() == 2); + // Sort into a consistent order + std::sort(failedSubgraphs.begin(), failedSubgraphs.end(), [](auto s1, auto s2) { + return strcmp(s1.GetLayers().front()->GetName(), s2.GetLayers().front()->GetName()) < 0; + }); std::vector expectedFailedSubgraphSizes{ { 1, 1, 2 }, { 1, 1, 1 } }; @@ -1060,8 +1069,12 @@ void PartiallyOptimizableSubgraphTestImpl1() // Check the substitutions // ----------------------- - const OptimizationViews::Substitutions& substitutions = optimizationViews.GetSubstitutions(); + OptimizationViews::Substitutions substitutions = optimizationViews.GetSubstitutions(); BOOST_TEST(substitutions.size() == 3); + // Sort into a consistent order + std::sort(substitutions.begin(), substitutions.end(), + [](auto s1, auto s2) { return strcmp(s1.m_SubstitutableSubgraph.GetLayers().front()->GetName(), + s2.m_SubstitutableSubgraph.GetLayers().front()->GetName()) < 0; }); std::vector expectedSubstitutableSubgraphSizes{ { 1, 1, 1 }, { 1, 1, 1 }, @@ -1108,8 +1121,12 @@ void PartiallyOptimizableSubgraphTestImpl1() // Check the untouched subgraphs // ----------------------------- - const OptimizationViews::Subgraphs& untouchedSubgraphs = optimizationViews.GetUntouchedSubgraphs(); + OptimizationViews::Subgraphs untouchedSubgraphs = optimizationViews.GetUntouchedSubgraphs(); BOOST_TEST(untouchedSubgraphs.size() == 2); + // Sort into a consistent order + std::sort(untouchedSubgraphs.begin(), untouchedSubgraphs.end(), [](auto s1, auto s2) { + return strcmp(s1.GetLayers().front()->GetName(), s2.GetLayers().front()->GetName()) < 0; + }); std::vector expectedUntouchedSubgraphSizes{ { 1, 1, 1 }, { 1, 1, 1 } }; @@ -1146,7 +1163,7 @@ void PartiallyOptimizableSubgraphTestImpl2() Graph graph; LayerNameToLayerMap layersInGraph; - // Create a fully optimizable subgraph + // Create a partially optimizable subgraph SubgraphViewSelector::SubgraphViewPtr subgraphPtr = BuildPartiallyOptimizableSubgraph2(graph, layersInGraph); BOOST_TEST((subgraphPtr != nullptr)); @@ -1185,44 +1202,32 @@ void PartiallyOptimizableSubgraphTestImpl2() // ----------------------- const OptimizationViews::Substitutions& substitutions = optimizationViews.GetSubstitutions(); - BOOST_TEST(substitutions.size() == 2); - - std::vector expectedSubstitutableSubgraphSizes{ { 1, 1, 1 }, - { 2, 1, 2 } }; - std::vector expectedReplacementSubgraphSizes{ { 1, 1, 1 }, - { 2, 1, 1 } }; + BOOST_TEST(substitutions.size() == 1); - SubgraphView::InputSlots expectedSubstitutableSubgraph2InputSlots = - ConvertReferenceTypeToPointerType(layersInGraph.at("conv3 layer")->GetInputSlots()); - expectedSubstitutableSubgraph2InputSlots.push_back( - ConvertReferenceTypeToPointerType(layersInGraph.at("add layer")->GetInputSlot(0))); + ExpectedSubgraphSize expectedSubstitutableSubgraphSizes{ 2, 1, 3 }; + ExpectedSubgraphSize expectedReplacementSubgraphSizes{ 2, 1, 1 }; - std::vector expectedSubstitutableInputSlots - { - ConvertReferenceTypeToPointerType(layersInGraph.at("conv1 layer")->GetInputSlots()), - expectedSubstitutableSubgraph2InputSlots + SubgraphView::InputSlots expectedSubstitutableInputSlots = { + ConvertReferenceTypeToPointerType(layersInGraph.at("conv1 layer")->GetInputSlots()[0]), + ConvertReferenceTypeToPointerType(layersInGraph.at("conv3 layer")->GetInputSlots()[0]) }; - std::vector expectedSubstitutableOutputSlots + SubgraphView::OutputSlots expectedSubstitutableOutputSlots = { - ConvertReferenceTypeToPointerType(layersInGraph.at("conv1 layer")->GetOutputSlots()), - ConvertReferenceTypeToPointerType(layersInGraph.at("add layer")->GetOutputSlots()) + ConvertReferenceTypeToPointerType(layersInGraph.at("add layer")->GetOutputSlots()[0]) }; - std::vector expectedSubstitutableLayers + SubgraphView::Layers expectedSubstitutableLayers { - { layersInGraph.at("conv1 layer") }, - { layersInGraph.at("conv3 layer"), - layersInGraph.at("add layer") } + layersInGraph.at("conv1 layer"), + layersInGraph.at("conv3 layer"), + layersInGraph.at("add layer") }; - for (size_t substitutionIndex = 0; substitutionIndex < substitutions.size(); substitutionIndex++) - { - CheckSubstitution(substitutions.at(substitutionIndex), - expectedSubstitutableSubgraphSizes.at(substitutionIndex), - expectedReplacementSubgraphSizes.at(substitutionIndex), - expectedSubstitutableInputSlots.at(substitutionIndex), - expectedSubstitutableOutputSlots.at(substitutionIndex), - expectedSubstitutableLayers.at(substitutionIndex)); - } + CheckSubstitution(substitutions[0], + expectedSubstitutableSubgraphSizes, + expectedReplacementSubgraphSizes, + expectedSubstitutableInputSlots, + expectedSubstitutableOutputSlots, + expectedSubstitutableLayers); // -------------------------- // Check the failed subgraphs -- cgit v1.2.1