From c2fe5fb3a070ce2c7daebf63d0def3d57cec09d3 Mon Sep 17 00:00:00 2001 From: Derek Lamberti Date: Wed, 8 May 2019 10:23:08 +0100 Subject: IVGCVSW-3031 Finer grained backend optimization API Change-Id: I9b93bc81b97f3d89fa046ba001854f732040e63a Signed-off-by: Derek Lamberti --- src/armnn/BackendSettings.hpp | 8 +++ src/armnn/Graph.cpp | 18 +++--- src/armnn/Graph.hpp | 6 +- src/armnn/Network.cpp | 64 ++++++++++++---------- src/armnn/SubgraphView.cpp | 18 ++++++ src/armnn/SubgraphView.hpp | 7 ++- src/armnn/test/SubgraphViewTests.cpp | 16 +++--- src/backends/backendsCommon/CMakeLists.txt | 2 + src/backends/backendsCommon/IBackendInternal.hpp | 36 +++++++++++- src/backends/backendsCommon/OptimizationViews.cpp | 67 +++++++++++++++++++++++ src/backends/backendsCommon/OptimizationViews.hpp | 53 ++++++++++++++++++ src/backends/backendsCommon/common.mk | 1 + 12 files changed, 242 insertions(+), 54 deletions(-) create mode 100644 src/backends/backendsCommon/OptimizationViews.cpp create mode 100644 src/backends/backendsCommon/OptimizationViews.hpp diff --git a/src/armnn/BackendSettings.hpp b/src/armnn/BackendSettings.hpp index 931a0681db..e1344ab650 100644 --- a/src/armnn/BackendSettings.hpp +++ b/src/armnn/BackendSettings.hpp @@ -26,6 +26,14 @@ struct BackendSettings Initialize(preferredBackends, deviceSpec); } + BackendSettings(const BackendSettings& other) + : m_PreferredBackends(other.m_PreferredBackends) + , m_SupportedBackends(other.m_SupportedBackends) + , m_SelectedBackends(other.m_SelectedBackends) + , m_IgnoredBackends(other.m_IgnoredBackends) + { + } + bool IsBackendPreferred(const BackendId& backend) const { return IsBackendInCollection(backend, m_PreferredBackends); diff --git a/src/armnn/Graph.cpp b/src/armnn/Graph.cpp index 9827b70de9..8c2b232ead 100644 --- a/src/armnn/Graph.cpp +++ b/src/armnn/Graph.cpp @@ -298,21 +298,18 @@ void Graph::AddCopyLayers() } } -void Graph::SubstituteSubgraph(std::unique_ptr subgraph, IConnectableLayer* substituteLayer) +void Graph::SubstituteSubgraph(SubgraphView& subgraph, IConnectableLayer* substituteLayer) { - BOOST_ASSERT(subgraph != nullptr); BOOST_ASSERT(substituteLayer != nullptr); - ReplaceSubgraphConnections(*subgraph, substituteLayer); - EraseSubgraphLayers(*subgraph); + ReplaceSubgraphConnections(subgraph, substituteLayer); + EraseSubgraphLayers(subgraph); } -void Graph::SubstituteSubgraph(std::unique_ptr subgraph, const SubgraphView& substituteSubgraph) +void Graph::SubstituteSubgraph(SubgraphView& subgraph, const SubgraphView& substituteSubgraph) { - BOOST_ASSERT(subgraph); - - ReplaceSubgraphConnections(*subgraph, substituteSubgraph); - EraseSubgraphLayers(*subgraph); + ReplaceSubgraphConnections(subgraph, substituteSubgraph); + EraseSubgraphLayers(subgraph); } void Graph::ReplaceSubgraphConnections(const SubgraphView& subgraph, IConnectableLayer* substituteLayer) @@ -377,12 +374,13 @@ void Graph::ReplaceSubgraphConnections(const SubgraphView& subgraph, const Subgr } } -void Graph::EraseSubgraphLayers(const SubgraphView &subgraph) +void Graph::EraseSubgraphLayers(SubgraphView &subgraph) { for (auto layer : subgraph.GetLayers()) { EraseLayer(layer); } + subgraph.Clear(); } void Graph::InferTensorInfos() diff --git a/src/armnn/Graph.hpp b/src/armnn/Graph.hpp index cc0ccaea77..88d2002112 100644 --- a/src/armnn/Graph.hpp +++ b/src/armnn/Graph.hpp @@ -163,8 +163,8 @@ public: /// Substitutes the given sub-graph with either a new layer or a new sub-graph. /// In either case, the given layer or all the layers in the given sub-graph must belong to this graph. - void SubstituteSubgraph(std::unique_ptr subgraph, IConnectableLayer* substituteLayer); - void SubstituteSubgraph(std::unique_ptr subgraph, const SubgraphView& substituteSubgraph); + void SubstituteSubgraph(SubgraphView& subgraph, IConnectableLayer* substituteLayer); + void SubstituteSubgraph(SubgraphView& subgraph, const SubgraphView& substituteSubgraph); void InferTensorInfos(); @@ -219,7 +219,7 @@ private: void ReplaceSubgraphConnections(const SubgraphView& subgraph, IConnectableLayer* substituteLayer); void ReplaceSubgraphConnections(const SubgraphView& subgraph, const SubgraphView& substituteSubgraph); - void EraseSubgraphLayers(const SubgraphView &subgraph); + void EraseSubgraphLayers(SubgraphView &subgraph); /// Mutable to allow sorting on const object. mutable LayerList m_Layers; diff --git a/src/armnn/Network.cpp b/src/armnn/Network.cpp index 1047567cc4..1eb40d5ba0 100644 --- a/src/armnn/Network.cpp +++ b/src/armnn/Network.cpp @@ -365,53 +365,57 @@ OptimizationResult ApplyBackendOptimizations(OptimizedNetwork* optNetObjPtr, for (auto& subgraph : subgraphs) { // Try to optimize the current sub-graph - bool optimizationAttempted = false; - SubgraphView::SubgraphViewPtr optSubgraph = backendObjPtr->OptimizeSubgraphView(*subgraph, - optimizationAttempted); - - // Check if the optimization has been attempted - if (!optimizationAttempted) - { - // No optimization attempted, keep the current sub-graph as it is and move to the next one - continue; - } + OptimizationViews optViews = backendObjPtr->OptimizeSubgraphView(*subgraph); + BOOST_ASSERT(optViews.Validate(*subgraph)); // Optimization attempted, check the resulting optimized sub-graph - if (optSubgraph) + for (auto& substitution : optViews.GetSubstitutions()) { // Sub-graph optimized, substitute the sub-graph with the new optimized one in the main optimized graph - optGraph.SubstituteSubgraph(std::move(subgraph), *optSubgraph); + SubgraphView& optSubgraph = substitution.m_ReplacementSubgraph; + optGraph.SubstituteSubgraph(substitution.m_SubstitutableSubgraph, optSubgraph); // Assign the current backend to the optimized sub-graph - std::for_each(optSubgraph->begin(), optSubgraph->end(), [&selectedBackend](Layer* l) - { - BOOST_ASSERT(l); - l->SetBackendId(selectedBackend); - }); + std::for_each(optSubgraph.begin(), optSubgraph.end(), [&selectedBackend](Layer* l) + { + BOOST_ASSERT(l); + l->SetBackendId(selectedBackend); + }); } - else + + if (!optViews.GetFailedSubgraphs().empty()) { - // An error occurred: the optimization was attempted but not performed, try different backends std::stringstream warningMsg; - warningMsg << "Sub-graph failed to get optimized on " << backendObjPtr->GetId() << ". " - << "Re-assigning backends to " << subgraph->GetLayers().size() << " layers inside sub-graph"; + warningMsg << "Some sub-graph(s) failed to optimized on " << backendObjPtr->GetId() << " backend."; ReportWarning(warningMsg.str(), errMessages); // Failed to optimize the given sub-graph, re-assign the sub-graph layers to other available backends + BackendSettings settingsCopy(backendSettings); if (!backendObjPtr->GetId().IsCpuRef()) { // Add the current backend to the list of backends to ignore - backendSettings.m_IgnoredBackends.insert(backendObjPtr->GetId()); + settingsCopy.m_IgnoredBackends.insert(backendObjPtr->GetId()); } - OptimizationResult reassignmentResult = AssignBackends(optNetObjPtr, - backendSettings, - *subgraph, - errMessages); - if (reassignmentResult.m_Error) + + int count=0; + for (auto& failedSubgraph : optViews.GetFailedSubgraphs()) { - // Failed to re-assign one of the remaining backends to each layer of the sub-graph - result.m_Error = true; - return result; + // An error occurred: the optimization was attempted but not performed, try different backends + std::stringstream subgraphMsg; + subgraphMsg << "Re-assigning backends to " << failedSubgraph.GetLayers().size() + << " layers inside sub-graph " << count++; + ReportWarning(warningMsg.str(), errMessages); + + OptimizationResult reassignmentResult = AssignBackends(optNetObjPtr, + settingsCopy, + *subgraph, + errMessages); + if (reassignmentResult.m_Error) + { + // Failed to re-assign one of the remaining backends to each layer of the sub-graph + result.m_Error = true; + return result; + } } } } diff --git a/src/armnn/SubgraphView.cpp b/src/armnn/SubgraphView.cpp index 9426f1eefc..a87cc9b268 100644 --- a/src/armnn/SubgraphView.cpp +++ b/src/armnn/SubgraphView.cpp @@ -92,6 +92,17 @@ SubgraphView::SubgraphView(IConnectableLayer* layer) CheckSubgraph(); } +SubgraphView& SubgraphView::operator=(SubgraphView&& other) +{ + m_InputSlots = std::move(other.m_InputSlots); + m_OutputSlots = std::move(other.m_OutputSlots); + m_Layers = std::move(other.m_Layers); + + CheckSubgraph(); + + return *this; +} + void SubgraphView::CheckSubgraph() { // Check for invalid or duplicate input slots @@ -179,4 +190,11 @@ SubgraphView::ConstIterator SubgraphView::cend() const return end(); } +void SubgraphView::Clear() +{ + m_InputSlots.clear(); + m_OutputSlots.clear(); + m_Layers.clear(); +} + } // namespace armnn diff --git a/src/armnn/SubgraphView.hpp b/src/armnn/SubgraphView.hpp index d4d92bbf6c..d86f1c1c93 100644 --- a/src/armnn/SubgraphView.hpp +++ b/src/armnn/SubgraphView.hpp @@ -31,7 +31,7 @@ public: using ConstIterator = Layers::const_iterator; /// Constructs a sub-graph from the entire given graph. - SubgraphView(Graph& graph); + explicit SubgraphView(Graph& graph); /// Constructs a sub-graph with the given arguments. SubgraphView(InputSlots&& inputs, OutputSlots&& outputs, Layers&& layers); @@ -45,6 +45,9 @@ public: /// Constructs a sub-graph with only the given layer. SubgraphView(IConnectableLayer* layer); + /// Move-assignment operator. + SubgraphView& operator=(SubgraphView&& other); + const InputSlots& GetInputSlots() const; const OutputSlots& GetOutputSlots() const; const Layers& GetLayers() const; @@ -67,6 +70,8 @@ public: ConstIterator cbegin() const; ConstIterator cend() const; + void Clear(); + private: void CheckSubgraph(); diff --git a/src/armnn/test/SubgraphViewTests.cpp b/src/armnn/test/SubgraphViewTests.cpp index d580385797..7938171a33 100644 --- a/src/armnn/test/SubgraphViewTests.cpp +++ b/src/armnn/test/SubgraphViewTests.cpp @@ -159,7 +159,7 @@ BOOST_AUTO_TEST_CASE(SingleInputSingleOutput) Layer* const preCompiledLayer = graph.AddLayer(preCompiledDescriptor, "pre-compiled"); // Substitute sub-graph with pre-compiled layer - graph.SubstituteSubgraph(std::move(subgraph), preCompiledLayer); + graph.SubstituteSubgraph(*subgraph, preCompiledLayer); // Check that connections are correct after substitution BOOST_CHECK_EQUAL(preCompiledLayer->GetInputSlot(0).GetConnection(), subgraphInputConn); @@ -208,7 +208,7 @@ BOOST_AUTO_TEST_CASE(MultiInputSingleOutput) Layer* const preCompiledLayer = graph.AddLayer(preCompiledDescriptor, "pre-compiled"); // Substitute sub-graph with pre-compiled layer - graph.SubstituteSubgraph(std::move(subgraph), preCompiledLayer); + graph.SubstituteSubgraph(*subgraph, preCompiledLayer); // Check that connections are correct after substitution BOOST_CHECK_EQUAL(preCompiledLayer->GetInputSlot(0).GetConnection(), subgraphInputConn1); @@ -257,7 +257,7 @@ BOOST_AUTO_TEST_CASE(SingleInputMultiOutput) Layer* const preCompiledLayer = graph.AddLayer(preCompiledDescriptor, "pre-compiled"); // Substitute sub-graph with pre-compiled layer - graph.SubstituteSubgraph(std::move(subgraph), preCompiledLayer); + graph.SubstituteSubgraph(*subgraph, preCompiledLayer); // Check that connections are correct after substitution BOOST_CHECK_EQUAL(preCompiledLayer->GetInputSlot(0).GetConnection(), subgraphInputConn1); @@ -309,7 +309,7 @@ BOOST_AUTO_TEST_CASE(MultiInputMultiOutput) Layer* const preCompiledLayer = graph.AddLayer(preCompiledDescriptor, "pre-compiled"); // Substitute sub-graph with pre-compiled layer - graph.SubstituteSubgraph(std::move(subgraph), preCompiledLayer); + graph.SubstituteSubgraph(*subgraph, preCompiledLayer); // Check that connections are correct after substitution BOOST_CHECK_EQUAL(preCompiledLayer->GetInputSlot(0).GetConnection(), subgraphInputConn1); @@ -354,7 +354,7 @@ BOOST_AUTO_TEST_CASE(EraseReplacedLayers) const SubgraphView::Layers subgraphLayers = subgraph->GetLayers(); // Substitute sub-graph with pre-compiled layer - graph.SubstituteSubgraph(std::move(subgraph), preCompiledLayer); + graph.SubstituteSubgraph(*subgraph, preCompiledLayer); // Check that the layers belonging to the sub-graph have been erased from the graph after substitution BOOST_CHECK(!AreAnySubgraphLayersPresentInGraph(subgraphLayers, graph)); @@ -923,7 +923,7 @@ BOOST_AUTO_TEST_CASE(SingleSubgraph) Layer* const preCompiledLayer = graph.AddLayer(preCompiledDescriptor, "pre-compiled"); // Substitute sub-graph with pre-compiled layer - graph.SubstituteSubgraph((std::move(subgraphs[0])), preCompiledLayer); + graph.SubstituteSubgraph(*subgraphs[0], preCompiledLayer); // Check that connections are correct after substitution BOOST_CHECK_EQUAL(preCompiledLayer->GetInputSlot(0).GetConnection(), subgraphInputConn1); @@ -1013,8 +1013,8 @@ BOOST_AUTO_TEST_CASE(MultipleSubgraphs) Layer* const preCompiledLayer2 = graph.AddLayer(preCompiledDescriptor2, "pre-compiled2"); // Substitute sub-graph with pre-compiled layer - graph.SubstituteSubgraph((std::move(subgraphs[0])), preCompiledLayer1); - graph.SubstituteSubgraph((std::move(subgraphs[1])), preCompiledLayer2); + graph.SubstituteSubgraph(*subgraphs[0], preCompiledLayer1); + graph.SubstituteSubgraph(*subgraphs[1], preCompiledLayer2); // Check that connections are correct after substitution BOOST_CHECK_EQUAL(preCompiledLayer1->GetInputSlot(0).GetConnection(), subgraph1InputConn); diff --git a/src/backends/backendsCommon/CMakeLists.txt b/src/backends/backendsCommon/CMakeLists.txt index 1aa4d99dc3..e1e387bc6f 100644 --- a/src/backends/backendsCommon/CMakeLists.txt +++ b/src/backends/backendsCommon/CMakeLists.txt @@ -18,6 +18,8 @@ list(APPEND armnnBackendsCommon_sources MakeWorkloadHelper.hpp MemCopyWorkload.cpp MemCopyWorkload.hpp + OptimizationViews.cpp + OptimizationViews.hpp OutputHandler.cpp OutputHandler.hpp WorkloadDataCollector.hpp diff --git a/src/backends/backendsCommon/IBackendInternal.hpp b/src/backends/backendsCommon/IBackendInternal.hpp index b3ddb55676..f49a210988 100644 --- a/src/backends/backendsCommon/IBackendInternal.hpp +++ b/src/backends/backendsCommon/IBackendInternal.hpp @@ -10,6 +10,8 @@ #include #include +#include "OptimizationViews.hpp" + #include namespace armnn @@ -54,8 +56,38 @@ public: virtual Optimizations GetOptimizations() const = 0; virtual ILayerSupportSharedPtr GetLayerSupport() const = 0; - virtual SubgraphViewUniquePtr OptimizeSubgraphView(const SubgraphView& subgraph, bool& optimizationAttempted) - const = 0; + // @deprecated Use "OptimizationViews OptimizeSubgraphView(const SubgraphView&);" instead. + virtual SubgraphViewUniquePtr OptimizeSubgraphView(const SubgraphView& subgraph, bool& optimizationAttempted) const + { + optimizationAttempted=false; + return nullptr; + } + + // Default implementation of OptimizeSubgraphView for backward compatibility with old API. + // Override this method with a custom optimization implementation. + virtual OptimizationViews OptimizeSubgraphView(const SubgraphView& subgraph) + { + bool attempted=false; + SubgraphViewUniquePtr optSubgraph = OptimizeSubgraphView(subgraph, attempted); + + OptimizationViews result; + if (!attempted) + { + result.AddUntouchedSubgraph(SubgraphView(subgraph)); + } + else + { + if (optSubgraph) + { + result.AddSubstituion({*optSubgraph.get(), subgraph}); + } + else + { + result.AddFailedSubgraph(SubgraphView(subgraph)); + } + } + return result; + } }; using IBackendInternalUniquePtr = std::unique_ptr; diff --git a/src/backends/backendsCommon/OptimizationViews.cpp b/src/backends/backendsCommon/OptimizationViews.cpp new file mode 100644 index 0000000000..1190eea57d --- /dev/null +++ b/src/backends/backendsCommon/OptimizationViews.cpp @@ -0,0 +1,67 @@ +// +// Copyright © 2017 Arm Ltd. All rights reserved. +// SPDX-License-Identifier: MIT +// + +#include "OptimizationViews.hpp" + + +namespace armnn +{ + +bool OptimizationViews::Validate(const armnn::SubgraphView& originalSubgraph) const +{ + //This needs to verify that: + // 1) the sum of m_SuccesfulOptimizations & m_FailedOptimizations & m_UntouchedSubgraphs contains subgraphviews + // which cover the entire space of the originalSubgraph. + // 2) Each SubstitutionPair contains matching inputs and outputs + bool valid = true; + + // Create a copy of the layer list from the original subgraph and sort it + SubgraphView::Layers originalLayers = originalSubgraph.GetLayers(); + originalLayers.sort(); + + // Create a new list based on the sum of all the subgraphs and sort it + SubgraphView::Layers countedLayers; + for (auto& failed : m_FailedOptimizations) + { + countedLayers.insert(countedLayers.end(), failed.GetLayers().begin(), failed.GetLayers().end()); + } + for (auto& untouched : m_UntouchedSubgraphs) + { + countedLayers.insert(countedLayers.end(), untouched.GetLayers().begin(), untouched.GetLayers().end()); + } + for (auto& successful : m_SuccesfulOptimizations) + { + countedLayers.insert(countedLayers.end(), + successful.m_SubstitutableSubgraph.GetLayers().begin(), + successful.m_SubstitutableSubgraph.GetLayers().end()); + } + countedLayers.sort(); + + // Compare the two lists to make sure they match + valid &= originalLayers.size() == countedLayers.size(); + + auto oIt = originalLayers.begin(); + auto cIt = countedLayers.begin(); + for (size_t i=0; i < originalLayers.size() && valid; ++i, ++oIt, ++cIt) + { + valid &= (*oIt == *cIt); + } + + // Compare the substitution subgraphs to ensure they are compatible + if (valid) + { + for (auto& substitution : m_SuccesfulOptimizations) + { + bool validSubstitution = true; + const SubgraphView& replacement = substitution.m_ReplacementSubgraph; + const SubgraphView& old = substitution.m_SubstitutableSubgraph; + validSubstitution &= replacement.GetInputSlots().size() == old.GetInputSlots().size(); + validSubstitution &= replacement.GetOutputSlots().size() == old.GetOutputSlots().size(); + valid &= validSubstitution; + } + } + return valid; +} +} //namespace armnn diff --git a/src/backends/backendsCommon/OptimizationViews.hpp b/src/backends/backendsCommon/OptimizationViews.hpp new file mode 100644 index 0000000000..cf7051d887 --- /dev/null +++ b/src/backends/backendsCommon/OptimizationViews.hpp @@ -0,0 +1,53 @@ +// +// Copyright © 2017 Arm Ltd. All rights reserved. +// SPDX-License-Identifier: MIT +// + +#pragma once +#include + +namespace armnn +{ +class OptimizationViews +{ +public: + OptimizationViews() = default; + + struct SubstitutionPair + { + /// Subgraph of Layers from the original graph which should be replaced + SubgraphView m_SubstitutableSubgraph; + + /// A subgraph of new layers which will replace layers in m_SubstitutableSubgraph + SubgraphView m_ReplacementSubgraph; + }; + + using Subgraphs = std::vector; + using Substitutions = std::vector; + + void AddSubstituion(SubstitutionPair&& substitution) + { + m_SuccesfulOptimizations.emplace_back(substitution); + } + + void AddFailedSubgraph(SubgraphView&& subgraph) + { + m_FailedOptimizations.emplace_back(subgraph); + } + + void AddUntouchedSubgraph(SubgraphView&& subgraph) + { + m_UntouchedSubgraphs.emplace_back(subgraph); + } + + Substitutions GetSubstitutions() const { return m_SuccesfulOptimizations; } + Subgraphs GetFailedSubgraphs() const { return m_FailedOptimizations; } + Subgraphs GetUntouchedSubgraphs() const { return m_UntouchedSubgraphs; } + bool Validate(const SubgraphView& originalSubgraph) const; + +private: + Substitutions m_SuccesfulOptimizations; ///< Proposed substitutions from successful optimizations + Subgraphs m_FailedOptimizations; ///< Subgraphs from the original subgraph which cannot be supported + Subgraphs m_UntouchedSubgraphs; ///< Subgraphs from the original subgraph which remain unmodified +}; +} //namespace armnn \ No newline at end of file diff --git a/src/backends/backendsCommon/common.mk b/src/backends/backendsCommon/common.mk index a1cc0c1b3a..c993bfb674 100644 --- a/src/backends/backendsCommon/common.mk +++ b/src/backends/backendsCommon/common.mk @@ -12,6 +12,7 @@ COMMON_SOURCES := \ CpuTensorHandle.cpp \ LayerSupportBase.cpp \ MemCopyWorkload.cpp \ + OptimizationViews.cpp \ OutputHandler.cpp \ WorkloadData.cpp \ WorkloadFactory.cpp \ -- cgit v1.2.1