David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 1 | // |
| 2 | // Copyright © 2017 Arm Ltd. All rights reserved. |
| 3 | // SPDX-License-Identifier: MIT |
| 4 | // |
| 5 | |
Derek Lamberti | ff05cc5 | 2019-04-26 13:05:17 +0100 | [diff] [blame] | 6 | #include "SubgraphViewSelector.hpp" |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 7 | #include "Graph.hpp" |
| 8 | #include <boost/assert.hpp> |
| 9 | #include <algorithm> |
| 10 | #include <unordered_map> |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 11 | #include <queue> |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 12 | |
| 13 | namespace armnn |
| 14 | { |
| 15 | |
| 16 | namespace |
| 17 | { |
| 18 | |
| 19 | struct LayerSelectionInfo |
| 20 | { |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 21 | using SplitId = uint32_t; |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 22 | using LayerInfoContainer = std::unordered_map<Layer*, LayerSelectionInfo>; |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 23 | using LayerInfoQueue = std::queue<LayerSelectionInfo*>; |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 24 | static constexpr uint32_t InitialSplitId() { return 1; } |
| 25 | |
Derek Lamberti | ff05cc5 | 2019-04-26 13:05:17 +0100 | [diff] [blame] | 26 | LayerSelectionInfo(Layer* layer, const SubgraphViewSelector::LayerSelectorFunction& selector) |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 27 | : m_Layer{layer} |
| 28 | , m_SplitId{0} |
| 29 | , m_IsSelected{selector(*layer)} |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 30 | , m_IsProcessed(false) |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 31 | { |
| 32 | // fill topology information by storing direct children |
| 33 | for (auto&& slot = m_Layer->BeginOutputSlots(); slot != m_Layer->EndOutputSlots(); ++slot) |
| 34 | { |
| 35 | for (InputSlot* childLayerInputSlot : slot->GetConnections()) |
| 36 | { |
| 37 | Layer& childLayer = childLayerInputSlot->GetOwningLayer(); |
| 38 | m_DirectChildren.push_back(&childLayer); |
| 39 | } |
| 40 | } |
| 41 | } |
| 42 | |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 43 | bool IsInputLayer() const |
| 44 | { |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 45 | return m_Layer->GetType() == armnn::LayerType::Input || m_Layer->GetType() == armnn::LayerType::Constant; |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 46 | } |
| 47 | |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 48 | void CollectNonSelectedInputs(LayerSelectionInfo::LayerInfoContainer& layerInfos, |
| 49 | SubgraphView::InputSlots& inputSlots) |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 50 | { |
| 51 | for (auto&& slot = m_Layer->BeginInputSlots(); slot != m_Layer->EndInputSlots(); ++slot) |
| 52 | { |
| 53 | OutputSlot* parentLayerOutputSlot = slot->GetConnectedOutputSlot(); |
Matteo Martincigh | adddddb | 2019-01-24 14:06:23 +0000 | [diff] [blame] | 54 | BOOST_ASSERT_MSG(parentLayerOutputSlot != nullptr, "The input slots must be connected here."); |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 55 | if (parentLayerOutputSlot) |
| 56 | { |
| 57 | Layer& parentLayer = parentLayerOutputSlot->GetOwningLayer(); |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 58 | auto parentInfo = layerInfos.find(&parentLayer); |
| 59 | if (m_SplitId != parentInfo->second.m_SplitId) |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 60 | { |
Matteo Martincigh | adddddb | 2019-01-24 14:06:23 +0000 | [diff] [blame] | 61 | inputSlots.push_back(&(*slot)); |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 62 | } |
| 63 | } |
| 64 | } |
| 65 | } |
| 66 | |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 67 | void CollectNonSelectedOutputSlots(LayerSelectionInfo::LayerInfoContainer& layerInfos, |
| 68 | SubgraphView::OutputSlots& outputSlots) |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 69 | { |
| 70 | for (auto&& slot = m_Layer->BeginOutputSlots(); slot != m_Layer->EndOutputSlots(); ++slot) |
| 71 | { |
| 72 | for (InputSlot* childLayerInputSlot : slot->GetConnections()) |
| 73 | { |
| 74 | Layer& childLayer = childLayerInputSlot->GetOwningLayer(); |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 75 | auto childInfo = layerInfos.find(&childLayer); |
| 76 | if (m_SplitId != childInfo->second.m_SplitId) |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 77 | { |
Matteo Martincigh | adddddb | 2019-01-24 14:06:23 +0000 | [diff] [blame] | 78 | outputSlots.push_back(&(*slot)); |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 79 | } |
| 80 | } |
| 81 | } |
| 82 | } |
| 83 | |
| 84 | std::vector<Layer*> m_DirectChildren; |
| 85 | Layer* m_Layer; |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 86 | SplitId m_SplitId; |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 87 | bool m_IsSelected; |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 88 | bool m_IsProcessed; |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 89 | }; |
| 90 | |
| 91 | } // namespace <anonymous> |
| 92 | |
Derek Lamberti | ff05cc5 | 2019-04-26 13:05:17 +0100 | [diff] [blame] | 93 | SubgraphViewSelector::Subgraphs |
| 94 | SubgraphViewSelector::SelectSubgraphs(Graph& graph, const LayerSelectorFunction& selector) |
Matteo Martincigh | adddddb | 2019-01-24 14:06:23 +0000 | [diff] [blame] | 95 | { |
Derek Lamberti | ff05cc5 | 2019-04-26 13:05:17 +0100 | [diff] [blame] | 96 | SubgraphView subgraph(graph); |
| 97 | return SubgraphViewSelector::SelectSubgraphs(subgraph, selector); |
Matteo Martincigh | adddddb | 2019-01-24 14:06:23 +0000 | [diff] [blame] | 98 | } |
| 99 | |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 100 | |
| 101 | template<typename Delegate> |
| 102 | void ForEachLayerInput(LayerSelectionInfo::LayerInfoContainer& layerInfos, |
| 103 | LayerSelectionInfo& layerInfo, |
| 104 | Delegate function) |
| 105 | { |
| 106 | Layer& layer = *layerInfo.m_Layer; |
| 107 | |
| 108 | for (auto inputSlot : layer.GetInputSlots()) |
| 109 | { |
| 110 | auto connectedInput = boost::polymorphic_downcast<OutputSlot*>(inputSlot.GetConnection()); |
| 111 | BOOST_ASSERT_MSG(connectedInput, "Dangling input slot detected."); |
| 112 | Layer& inputLayer = connectedInput->GetOwningLayer(); |
| 113 | |
| 114 | auto parentInfo = layerInfos.find(&inputLayer); |
| 115 | function(parentInfo->second); |
| 116 | } |
| 117 | } |
| 118 | |
| 119 | template<typename Delegate> |
| 120 | void ForEachLayerOutput(LayerSelectionInfo::LayerInfoContainer& layerInfos, |
| 121 | LayerSelectionInfo& layerInfo, |
| 122 | Delegate function) |
| 123 | { |
| 124 | Layer& layer= *layerInfo.m_Layer; |
| 125 | |
| 126 | for (auto& outputSlot : layer.GetOutputSlots()) |
| 127 | { |
| 128 | for (auto& output : outputSlot.GetConnections()) |
| 129 | { |
| 130 | Layer& childLayer = output->GetOwningLayer(); |
| 131 | |
| 132 | auto childInfo = layerInfos.find(&childLayer); |
| 133 | function(childInfo->second); |
| 134 | } |
| 135 | } |
| 136 | } |
| 137 | |
| 138 | void AssignSplitId(LayerSelectionInfo::LayerInfoContainer& layerInfos, LayerSelectionInfo& layerInfo) |
| 139 | { |
| 140 | bool newSplit = false; |
| 141 | LayerSelectionInfo::SplitId minSplitId = std::numeric_limits<LayerSelectionInfo::SplitId>::max(); |
| 142 | LayerSelectionInfo::SplitId maxSplitId = std::numeric_limits<LayerSelectionInfo::SplitId>::lowest(); |
| 143 | LayerSelectionInfo::SplitId maxSelectableId = std::numeric_limits<LayerSelectionInfo::SplitId>::lowest(); |
| 144 | |
| 145 | ForEachLayerInput(layerInfos, layerInfo, [&newSplit, &minSplitId, &maxSplitId, &maxSelectableId, &layerInfo]( |
| 146 | LayerSelectionInfo& parentInfo) |
| 147 | { |
| 148 | minSplitId = std::min(minSplitId, parentInfo.m_SplitId); |
| 149 | maxSplitId = std::max(maxSplitId, parentInfo.m_SplitId); |
| 150 | if (parentInfo.m_IsSelected && layerInfo.m_IsSelected) |
| 151 | { |
| 152 | maxSelectableId = std::max(maxSelectableId, parentInfo.m_SplitId); |
| 153 | } |
| 154 | |
| 155 | if (layerInfo.m_IsSelected != parentInfo.m_IsSelected) |
| 156 | { |
| 157 | newSplit = true; |
| 158 | } |
| 159 | |
| 160 | }); |
| 161 | |
| 162 | // Assign the split Id for the current layerInfo |
| 163 | if (newSplit) |
| 164 | { |
| 165 | if (maxSelectableId > minSplitId) |
| 166 | { |
| 167 | // We can be overly aggressive when choosing to create a new split so |
| 168 | // here we determine if one of the parent branches are suitable candidates for continuation instead. |
| 169 | // Any splitId > minSplitId will come from a shorter branch...and therefore should not be from |
| 170 | // the split containing the original fork and thus we avoid the execution dependency. |
| 171 | layerInfo.m_SplitId = maxSelectableId; |
| 172 | } |
| 173 | else |
| 174 | { |
| 175 | layerInfo.m_SplitId = ++maxSplitId; |
| 176 | } |
| 177 | } else |
| 178 | { |
| 179 | // The branch with the highest splitId represents the shortest path of selected nodes. |
| 180 | layerInfo.m_SplitId = maxSplitId; |
| 181 | } |
| 182 | } |
| 183 | |
| 184 | bool IsReadyForSplitAssignment(LayerSelectionInfo::LayerInfoContainer& layerInfos, LayerSelectionInfo& layerInfo) |
| 185 | { |
| 186 | bool ready = true; |
| 187 | ForEachLayerInput(layerInfos, layerInfo, |
| 188 | [&ready](LayerSelectionInfo& parentInfo) |
| 189 | { |
| 190 | if (!parentInfo.m_IsProcessed) |
| 191 | { |
| 192 | ready = false; |
| 193 | } |
| 194 | }); |
| 195 | return ready; |
| 196 | } |
| 197 | |
Derek Lamberti | ff05cc5 | 2019-04-26 13:05:17 +0100 | [diff] [blame] | 198 | SubgraphViewSelector::Subgraphs |
| 199 | SubgraphViewSelector::SelectSubgraphs(SubgraphView& subgraph, const LayerSelectorFunction& selector) |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 200 | { |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 201 | LayerSelectionInfo::LayerInfoContainer layerInfos; |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 202 | |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 203 | LayerSelectionInfo::LayerInfoQueue processQueue; |
Derek Lamberti | ff05cc5 | 2019-04-26 13:05:17 +0100 | [diff] [blame] | 204 | for (auto& layer : subgraph) |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 205 | { |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 206 | auto emplaced = layerInfos.emplace(layer, LayerSelectionInfo{layer, selector}); |
| 207 | LayerSelectionInfo& layerInfo = emplaced.first->second; |
| 208 | |
| 209 | // Start with Input type layers |
| 210 | if (layerInfo.IsInputLayer()) |
| 211 | { |
| 212 | processQueue.push(&layerInfo); |
| 213 | } |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 214 | } |
| 215 | |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 216 | while (!processQueue.empty()) |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 217 | { |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 218 | LayerSelectionInfo& layerInfo = *processQueue.front(); |
| 219 | processQueue.pop(); // remove front from queue |
| 220 | |
| 221 | // This layerInfo may have been added to the queue multiple times, so skip if we have already processed it |
| 222 | if (!layerInfo.m_IsProcessed) |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 223 | { |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 224 | |
| 225 | // Only process this layerInfo if all inputs have been processed |
| 226 | if (!IsReadyForSplitAssignment(layerInfos, layerInfo)) |
| 227 | { |
| 228 | // Put back of the process queue if we can't process it just yet |
| 229 | processQueue.push(&layerInfo); |
| 230 | continue; // Skip to next iteration |
| 231 | } |
| 232 | |
| 233 | // Now we do the processing |
| 234 | AssignSplitId(layerInfos, layerInfo); |
| 235 | |
| 236 | // Queue any child nodes for processing |
| 237 | ForEachLayerOutput(layerInfos, layerInfo, [&processQueue](LayerSelectionInfo& childInfo) |
| 238 | { |
| 239 | processQueue.push(&childInfo); |
| 240 | }); |
| 241 | |
| 242 | // We don't need to process this node again |
| 243 | layerInfo.m_IsProcessed = true; |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 244 | } |
| 245 | } |
| 246 | |
| 247 | // Collect all selected layers keyed by split id into a map |
| 248 | using SelectionInfoPtrs = std::vector<LayerSelectionInfo*>; |
| 249 | std::unordered_map<uint32_t, SelectionInfoPtrs> splitMap; |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 250 | for (auto& info : layerInfos) |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 251 | { |
| 252 | if (info.second.m_IsSelected) |
| 253 | { |
| 254 | auto it = splitMap.find(info.second.m_SplitId); |
| 255 | if (it == splitMap.end()) |
| 256 | { |
| 257 | splitMap.insert(std::make_pair(info.second.m_SplitId, SelectionInfoPtrs{&info.second})); |
| 258 | } |
| 259 | else |
| 260 | { |
| 261 | it->second.push_back(&info.second); |
| 262 | } |
| 263 | } |
| 264 | } |
| 265 | |
| 266 | // Now each non-empty split id represents a subgraph |
Derek Lamberti | ff05cc5 | 2019-04-26 13:05:17 +0100 | [diff] [blame] | 267 | Subgraphs result; |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 268 | for (auto& splitGraph : splitMap) |
| 269 | { |
| 270 | if (splitGraph.second.empty() == false) |
| 271 | { |
Derek Lamberti | ff05cc5 | 2019-04-26 13:05:17 +0100 | [diff] [blame] | 272 | SubgraphView::InputSlots inputs; |
| 273 | SubgraphView::OutputSlots outputs; |
| 274 | SubgraphView::Layers layers; |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 275 | for (auto&& infoPtr : splitGraph.second) |
| 276 | { |
Derek Lamberti | 5cf4d1c | 2019-05-03 18:57:12 +0100 | [diff] [blame^] | 277 | infoPtr->CollectNonSelectedInputs(layerInfos, inputs); |
| 278 | infoPtr->CollectNonSelectedOutputSlots(layerInfos, outputs); |
Matteo Martincigh | 4912402 | 2019-01-11 13:25:59 +0000 | [diff] [blame] | 279 | layers.push_back(infoPtr->m_Layer); |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 280 | } |
Matteo Martincigh | 602af09 | 2019-05-01 10:31:27 +0100 | [diff] [blame] | 281 | // Create a new sub-graph with the new lists of input/output slots and layer |
| 282 | result.emplace_back(std::make_unique<SubgraphView>(std::move(inputs), |
Derek Lamberti | ff05cc5 | 2019-04-26 13:05:17 +0100 | [diff] [blame] | 283 | std::move(outputs), |
| 284 | std::move(layers))); |
David Beck | f98d21a | 2018-10-26 16:03:03 +0100 | [diff] [blame] | 285 | } |
| 286 | } |
| 287 | |
| 288 | return result; |
| 289 | } |
| 290 | |
| 291 | } // namespace armnn |