From e4ae5c4662c375d39bd3866163ffdfe52c594996 Mon Sep 17 00:00:00 2001 From: =?utf8?q?=EA=B9=80=EC=9A=A9=EC=84=AD/On-Device=20Lab=28SR=29/Enginee?= =?utf8?q?r/=EC=82=BC=EC=84=B1=EC=A0=84=EC=9E=90?= Date: Wed, 27 Feb 2019 16:17:54 +0900 Subject: [PATCH] [neurun] Revise graph partitioning code (#4510) * [neurun] Revise graph partitioning code - Move graph paritionining code from Linear to Graph. - Handle Subgraphs as like LowerInfo until Execution * Add skipped code to fix failed test * Change the access specifier of partition method from public to private Signed-off-by: Yongseop Kim --- runtimes/neurun/src/compiler/Compiler.cc | 6 +- runtimes/neurun/src/exec/Executor.h | 3 +- runtimes/neurun/src/exec/ExecutorBase.cc | 8 ++- runtimes/neurun/src/exec/ExecutorBase.h | 3 + runtimes/neurun/src/graph/Graph.cc | 98 ++++++++++++++++++++++++++- runtimes/neurun/src/graph/Graph.h | 12 ++++ runtimes/neurun/src/linear/Linear.cc | 112 +++---------------------------- runtimes/neurun/src/linear/Linear.h | 21 +++--- 8 files changed, 143 insertions(+), 120 deletions(-) diff --git a/runtimes/neurun/src/compiler/Compiler.cc b/runtimes/neurun/src/compiler/Compiler.cc index 03bb7c6..82a9b90 100644 --- a/runtimes/neurun/src/compiler/Compiler.cc +++ b/runtimes/neurun/src/compiler/Compiler.cc @@ -66,7 +66,7 @@ void Compiler::compile(void) dot_dumper.dumpIfNeeded("after_lower"); - // linearize with subgraphs + // linearize auto linear = _model->linearize(); _state = State::LINEARIZED; @@ -118,8 +118,8 @@ void Compiler::compile(void) * Code generation phase finished ********************************/ auto plan = std::make_shared(operand_context, operation_sequence); - _executor = - std::make_shared(_model->shareModel(), linear->releaseLowerInfo(), plan); + _executor = std::make_shared(_model->shareModel(), linear->releaseSubgraphSet(), + linear->releaseLowerInfo(), plan); _state = State::COMPILED; } diff --git a/runtimes/neurun/src/exec/Executor.h b/runtimes/neurun/src/exec/Executor.h index 00b60ac..5555beb 100644 --- a/runtimes/neurun/src/exec/Executor.h +++ b/runtimes/neurun/src/exec/Executor.h @@ -40,9 +40,10 @@ public: * @param[in] plan Execution plan generated by compiled result */ Executor(const std::shared_ptr &model, + std::unique_ptr>> subg_set, std::unique_ptr lower_info, const std::shared_ptr &plan) - : ExecutorBase{model, std::move(lower_info)}, _plan{plan} + : ExecutorBase{model, std::move(subg_set), std::move(lower_info)}, _plan{plan} { } diff --git a/runtimes/neurun/src/exec/ExecutorBase.cc b/runtimes/neurun/src/exec/ExecutorBase.cc index 581dce3..db982a8 100644 --- a/runtimes/neurun/src/exec/ExecutorBase.cc +++ b/runtimes/neurun/src/exec/ExecutorBase.cc @@ -21,9 +21,11 @@ namespace neurun namespace exec { -ExecutorBase::ExecutorBase(const std::shared_ptr &model, - std::unique_ptr lower_info) - : _model{model}, _lower_info{std::move(lower_info)} +ExecutorBase::ExecutorBase( + const std::shared_ptr &model, + std::unique_ptr>> subg_set, + std::unique_ptr lower_info) + : _model{model}, _subg_set{std::move(subg_set)}, _lower_info{std::move(lower_info)} { _sources.resize(_model->inputs.size()); _sinks.resize(_model->outputs.size()); diff --git a/runtimes/neurun/src/exec/ExecutorBase.h b/runtimes/neurun/src/exec/ExecutorBase.h index e8f1740..e8d4bec 100644 --- a/runtimes/neurun/src/exec/ExecutorBase.h +++ b/runtimes/neurun/src/exec/ExecutorBase.h @@ -24,6 +24,7 @@ #include "graph/LowerInfoMap.h" #include "backend/interface/IConfig.h" #include "compiler/TensorInfo.h" +#include "model/operation/Subgraph.h" namespace neurun { @@ -34,6 +35,7 @@ class ExecutorBase : public IExecutor { public: ExecutorBase(const std::shared_ptr &model, + std::unique_ptr>> subg_set, std::unique_ptr lower_info); virtual ~ExecutorBase() = default; @@ -115,6 +117,7 @@ private: protected: std::shared_ptr _model; + std::unique_ptr>> _subg_set; std::unique_ptr _lower_info; std::vector> _sources; std::vector> _sinks; diff --git a/runtimes/neurun/src/graph/Graph.cc b/runtimes/neurun/src/graph/Graph.cc index 50acab8..9ad5759 100644 --- a/runtimes/neurun/src/graph/Graph.cc +++ b/runtimes/neurun/src/graph/Graph.cc @@ -91,6 +91,8 @@ void Graph::lower(void) { assert(_phase == Phase::MODEL); + partition(); + // Lower { // operand::LowerInfo holder @@ -213,7 +215,8 @@ std::unique_ptr Graph::linearize(void) { assert(_phase == Phase::MODEL); - auto linear = nnfw::cpp14::make_unique(*this, releaseLowerInfo()); + auto linear = + nnfw::cpp14::make_unique(*this, releaseSubgraphSet(), releaseLowerInfo()); // TODO Move the operations and operands to linear object return std::move(linear); @@ -281,6 +284,99 @@ void Graph::setLowerInfo(const model::operand::Index &index, _lower_info_map->operand.insert(std::make_pair(index, std::move(lower_info))); } +void Graph::partition() +{ + // Partition the graph into some subgraphs by topological sort while assuming that + // a subgraph has linear form + // + // algorithm + // 0. Create new subgraph + // 1. Add a node into current subgraph + // 2. Test two stuff for checking new subgraph is needed + // - Current node has multiple inputs like concat? + // - Does current node have two or more than previous operation? + // + // [CONV] [CONV] [CONV] [MAX_POOL] + // | | | | + // [0] [1] [2] [3] + // \ | | / + // [ C O N C A T ] # current node + // + // - Current node is on the separated branch at the beginning? + // - Does current node's input operand's uses have two or more than? + // + // [CONV] + // | + // [0]----. + // | | + // [CONV] [CONV] # current node + // | | + // [1] [2] + // \ / + // [CONCAT] + // + + _subg_set = nnfw::cpp14::make_unique>>(); + + { + std::unique_ptr subg = nullptr; + Graph::PostDfsConstIterator().iterate( + *this, [&](const model::operation::Index &index, const model::operation::Node &node) { + + if (!subg) + subg = nnfw::cpp14::make_unique(); + + subg->appendOperation(index, node); + + bool finish_subg = false; + size_t prev_op_cnt = 0; + for (auto input : node.getInputs()) + { + const auto &operand = this->operands().at(input); + if (operand.getDef().list().size() > 0) + ++prev_op_cnt; + + if (prev_op_cnt > 1 || operand.getUses().list().size() > 1) + { + finish_subg = true; + break; + } + } + + if (finish_subg) + { + _subg_set->emplace_back(std::move(subg)); + subg = nullptr; + } + }); + + // If the last subgraph leaves, append it to the subgraph set + if (subg && subg->operations().size() > 0) + _subg_set->emplace_back(std::move(subg)); + + // NOTE. Now these subgraph are on the reverse order + } + + // Set input/output of each subgraph while reversing + std::reverse(_subg_set->begin(), _subg_set->end()); + for (auto &subg : *_subg_set) + { + // output + auto it = std::begin(subg->operations()); + subg->setOutputs((*it).node->getOutputs()); + + std::reverse(std::begin(subg->operations()), std::end(subg->operations())); + + // input + it = std::begin(subg->operations()); + subg->setInputs((*it).node->getInputs()); + } + + VERBOSE(Subgraph) << "Subgraphs" << std::endl; + for (const auto &subg : *_subg_set) + VERBOSE(Subgraph) << subg->getStr() << std::endl; +} + } // namespace graph } // namespace neurun diff --git a/runtimes/neurun/src/graph/Graph.h b/runtimes/neurun/src/graph/Graph.h index 17eecf8..89e1f3a 100644 --- a/runtimes/neurun/src/graph/Graph.h +++ b/runtimes/neurun/src/graph/Graph.h @@ -22,6 +22,7 @@ #include "model/operation/Node.h" #include "model/Model.h" #include "graph/LowerInfoMap.h" +#include "model/operation/Subgraph.h" namespace neurun { @@ -125,6 +126,10 @@ public: bool isBuildingPhase(void) const { return _phase == Phase::BUILDING; } std::shared_ptr shareModel() { return _model; } std::unique_ptr releaseLowerInfo() { return std::move(_lower_info_map); } + std::unique_ptr>> releaseSubgraphSet() + { + return std::move(_subg_set); + } private: void initializeUseDef(); @@ -161,6 +166,13 @@ public: private: std::unique_ptr _backend_resolver; std::unique_ptr _lower_info_map; + + // For Subgraph +private: + void partition(); + +private: + std::unique_ptr>> _subg_set; }; } // namespace graph diff --git a/runtimes/neurun/src/linear/Linear.cc b/runtimes/neurun/src/linear/Linear.cc index 3ff73a6..cc79cbc 100644 --- a/runtimes/neurun/src/linear/Linear.cc +++ b/runtimes/neurun/src/linear/Linear.cc @@ -35,112 +35,18 @@ namespace neurun namespace linear { -Linear::Linear(const graph::Graph &graph, std::unique_ptr lower_info_map) - : _graph(graph), _lower_info_map(std::move(lower_info_map)) +Linear::Linear(const graph::Graph &graph, + std::unique_ptr>> subg_set, + std::unique_ptr lower_info_map) + : _graph(graph), _subg_set(std::move(subg_set)), _lower_info_map(std::move(lower_info_map)) { - assert(_lower_info_map); - - // TODO: Move this code to graph - - // Linearize graph with subgraphs by topological sort while assuming that - // a subgraph has linear form - // - // algorithm - // 0. Create new subgraph - // 1. Add a node into current subgraph - // 2. Test two stuff for checking new subgraph is needed - // - Current node has multiple inputs like concat? - // - Does current node have two or more than previous operation? - // - // [CONV] [CONV] [CONV] [MAX_POOL] - // | | | | - // [0] [1] [2] [3] - // \ | | / - // [ C O N C A T ] # current node - // - // - Current node is on the separated branch at the beginning? - // - Does current node's input operand's uses have two or more than? - // - // [CONV] - // | - // [0]----. - // | | - // [CONV] [CONV] # current node - // | | - // [1] [2] - // \ / - // [CONCAT] - // - // 3. If needed, push current subgraph to the set and create new subgraph - - auto subgraph_set = - nnfw::cpp14::make_unique>>(); + assert(_subg_set && _lower_info_map); + for (const auto &subg : *_subg_set) { - std::unique_ptr subgraph = nullptr; - graph::Graph::PostDfsConstIterator().iterate( - graph, [&](const model::operation::Index &index, const model::operation::Node &node) { - - if (!subgraph) - subgraph = nnfw::cpp14::make_unique(); - - subgraph->appendOperation(index, node); - - bool new_subgraph = false; - size_t prev_op_cnt = 0; - for (auto input : node.getInputs()) - { - const auto &operand = graph.operands().at(input); - if (operand.getDef().list().size() > 0) - ++prev_op_cnt; - - if (prev_op_cnt > 1 || operand.getUses().list().size() > 1) - { - new_subgraph = true; - break; - } - } - - if (new_subgraph) - { - subgraph_set->emplace_back(std::move(subgraph)); - subgraph = nullptr; - } - }); - - // If the last subgraph leaves, append it to the subgraph set - if (subgraph && subgraph->operations().size() > 0) - subgraph_set->emplace_back(std::move(subgraph)); - - // NOTE. Now these subgraph are on the reverse order - } - - // Set input/output of each subgraph while reversing - std::reverse(subgraph_set->begin(), subgraph_set->end()); - for (auto &subgraph : *subgraph_set) - { - // output - auto it = std::begin(subgraph->operations()); - subgraph->setOutputs((*it).node->getOutputs()); - - std::reverse(std::begin(subgraph->operations()), std::end(subgraph->operations())); - - // input - it = std::begin(subgraph->operations()); - subgraph->setInputs((*it).node->getInputs()); - } - - // Now ordered subgraphs are ready - for (auto &subgraph : *subgraph_set) - { - // Assume that the backend of all nodes on a subgraph are identified on the subgraph - const auto &first_ind = subgraph->operations()[0].index; - auto lower_info = getLowerInfo(first_ind); - _elements.emplace_back(std::move(subgraph), lower_info); + // Assume that the lower_infos of all nodes on a subgraph are identified on the subgraph + const auto &first_ind = subg->operations()[0].index; + _elements.emplace_back(subg.get(), getLowerInfo(first_ind)); } - - VERBOSE(LINEAR) << "Subgraphs" << std::endl; - for (const auto &element : _elements) - VERBOSE(LINEAR) << element.subgraph->getStr() << std::endl; } void Linear::accept(model::operation::NodeVisitor &&visitor) const diff --git a/runtimes/neurun/src/linear/Linear.h b/runtimes/neurun/src/linear/Linear.h index b513db4..99b3389 100644 --- a/runtimes/neurun/src/linear/Linear.h +++ b/runtimes/neurun/src/linear/Linear.h @@ -50,14 +50,11 @@ namespace linear struct Element { - // TODO: Change unique_ptr to ptr after Graph has Subgraphs - std::unique_ptr subgraph; - + const model::operation::Subgraph *subgraph; const graph::operation::LowerInfo *lower_info; - Element(std::unique_ptr subgraph, - const graph::operation::LowerInfo *lower_info) - : subgraph{std::move(subgraph)}, lower_info{lower_info} + Element(const model::operation::Subgraph *subgraph, const graph::operation::LowerInfo *lower_info) + : subgraph{subgraph}, lower_info{lower_info} { // DO NOTHING } @@ -67,7 +64,9 @@ class Linear { public: // TODO Change std::shared_ptr instead of Graph - Linear(const graph::Graph &graph, std::unique_ptr lower_info_map); + Linear(const graph::Graph &graph, + std::unique_ptr>> subg_set, + std::unique_ptr lower_info_map); public: Linear(const Linear &linear) = delete; @@ -81,17 +80,21 @@ public: void iterate(const std::function &fn) const; std::unique_ptr releaseLowerInfo() { return std::move(_lower_info_map); } - graph::LowerInfoMap *getLowerInfo() { return _lower_info_map.get(); } + std::unique_ptr>> releaseSubgraphSet() + { + return std::move(_subg_set); + } + private: // TODO Replace these getLowerInfo methods with ones of LowerInfoMap in the future const graph::operation::LowerInfo *getLowerInfo(const model::operation::Index &index) const; - const graph::operand::LowerInfo *getLowerInfo(const model::operand::Index &index) const; private: const graph::Graph &_graph; + std::unique_ptr>> _subg_set; std::unique_ptr _lower_info_map; std::vector _elements; }; -- 2.7.4