generalize graph partitioning. #11

zheng-da · 2018-05-30T22:16:58Z

Description

(Brief description on what this PR is about)

Checklist

Essentials

Please feel free to remove inapplicable items for your PR.

The PR title starts with [MXNET-$JIRA_ID], where $JIRA_ID refers to the relevant JIRA issue created (except PRs with tiny changes)
Changes are complete (i.e. I finished coding on this PR)
All changes have test coverage:
Unit tests are added for small changes to verify correctness (e.g. adding a new operator)
Nightly tests are added for complicated/long-running ones (e.g. changing distributed kvstore)
Build tests will be added for build configuration changes (e.g. adding a new build option with NCCL)
Code is well-documented:
For user-facing API changes, API doc string has been updated.
For new C++ functions in header files, their functionalities and arguments are documented.
For new examples, README.md is added to explain the what the example does, the source of the dataset, expected performance on test set and reference to the original paper if applicable
Check the API doc at http://mxnet-ci-doc.s3-accelerate.dualstack.amazonaws.com/PR-$PR_ID/$BUILD_ID/index.html
To the my best knowledge, examples are either not affected by this change, or have been fixed to be compatible with this change

Changes

Feature1, tests, (and when applicable, API doc)
Feature2, tests, (and when applicable, API doc)

Comments

If this change is a backward incompatible change, why must this change be made.
Interesting edge cases to note here

reminisce

Have you run the unit test in test_subgraph_op.py?

reminisce · 2018-05-31T05:23:31Z

src/operator/subgraph/partition_graph.cc

+ */
 void LabelSubgraph(const Graph&g,
-                   const std::unordered_set<std::string>& op_names,
+                   SubgraphSelectPtr selectFunc,


select_func

reminisce · 2018-05-31T05:25:51Z

src/operator/subgraph/partition_graph.cc

+          if (simple_nodes[nid]->label == -1) {
+            node_queue.push(simple_nodes[nid].get());
+          } else {
+            CHECK_EQ(simple_nodes[nid]->label, label);


This disallows adjacent subgraphs. Need to revisit this rule.

reminisce · 2018-05-31T05:28:30Z

src/operator/subgraph/partition_graph.cc

+ */
 void FindSubgraphs(const Graph& g,
-                   const std::unordered_set<std::string>& op_names,
+                   const SubgraphProperty &subgProperty,


subgraph_prop

reminisce · 2018-05-31T05:28:49Z

src/operator/subgraph/partition_graph.cc

  for (size_t i = 0; i < simple_nodes.size(); ++i) {
    nnvm::Node* node = simple_nodes[i]->node;
-    if (!node->is_variable() && simple_nodes[i]->label == -1 && op_names.count(node->op()->name)) {
+    auto selectFunc = subgProperty.CreateSubgraphSelect();


select_func

reminisce · 2018-05-31T05:34:53Z

src/operator/subgraph/partition_graph.cc

+    orig_entries->push_back(*e);
+    nnvm::Symbol sym;
+    sym.outputs.push_back(*e);
+    nnvm::NodePtr n = nnvm::CreateVariableNode(sym.ListOutputNames()[0]);


In order to reorder input entries of the subgraph op node, we need to keep the new variable node name the same as e->node->attrs.name+to_string(e.index). I can change this later.

reminisce · 2018-05-31T06:19:40Z

src/operator/subgraph/subgraph_op.h

+  std::shared_ptr<const std::unordered_set<std::string>> op_names;
+
+ public:
+  ContainOpSelect(std::shared_ptr<const std::unordered_set<std::string>> op_names) {


Why shared_ptr?

reminisce · 2018-05-31T06:22:41Z

src/operator/subgraph/subgraph_op.h

+  // execute the operators in the subgraph.
+  virtual nnvm::NodePtr GetSubgraphNode(const nnvm::Symbol &s) const = 0;
+  // Create a subgraph operator for execution.
+  virtual OpStatePtr CreateSubgraphOperator(const nnvm::Symbol &sym) const = 0;


CreateSubgraphOp

reminisce · 2018-05-31T06:25:35Z

src/operator/subgraph/subgraph_op.h

+
+ public:
+  SimpleSubgraphProperty(const std::unordered_set<std::string> &op_names) {
+    this->op_names = std::make_shared<std::unordered_set<std::string>>(op_names);


Why shared_ptr?

reminisce · 2018-05-31T06:33:01Z

src/operator/subgraph/subgraph_op.h

+    n->attrs.op = Op::Get("_subgraph_op");
+    n->attrs.name = "_subgraph_op";
+    n->attrs.dict.insert(std::pair<std::string, std::string>("exec_type", GetType()));
+    n->attrs.parsed = std::move(sym);


Do not move on a const reference.

reminisce · 2018-05-31T06:35:41Z

src/operator/subgraph/subgraph_op.h

+  }
+};
+
+using SubgraphSelectPtr = std::shared_ptr<SubgraphSelect>;


SubgraphSelectorPtr

reminisce · 2018-06-01T04:07:35Z

src/operator/subgraph/partition_graph.cc

    return ret;
  } else {
    using namespace sg;
+    SubgraphPropertyPtr subg_prop = g.GetAttr<SubgraphPropertyPtr>("subgraph_property");


This should be const SubgraphProperty&.

reminisce · 2018-06-01T04:21:13Z

src/operator/subgraph/subgraph_op.cc

+    return OpStatePtr::Create<SubgraphOpState>(op);
+  }
+
+  std::string exec_name = it->second;


const std::string

reminisce · 2018-06-01T04:37:09Z

src/operator/subgraph/subgraph_op.cc

+                                      const std::vector<NDArray>& inputs,
+                                      const std::vector<OpReqType>& req,
+                                      const std::vector<NDArray>& outputs) {
+  // We can create an executor to run this subgraph op


I will change the implementation here to adopt CachedOp since we want to support varied batch size seamlessly.

* add functions for cutting edges. * construct subgraphs. * generalize graph partition. * restructure the code. * create SubgraphOpState. * register subgraph property. * rename. * address comments. * update select API. * rename. * set subgraph property. * fix bugs. * fix bugs.

zheng-da force-pushed the subgraph_op branch from 8791b1e to da77422 Compare May 30, 2018 22:28

reminisce requested changes May 31, 2018

View reviewed changes

zheng-da added 13 commits May 31, 2018 21:46

add functions for cutting edges.

4ede83e

construct subgraphs.

5b9ace9

generalize graph partition.

34e4d72

restructure the code.

e642208

create SubgraphOpState.

83b0b7f

register subgraph property.

85da25e

rename.

07d5474

address comments.

581994d

update select API.

18057af

rename.

4b546c2

set subgraph property.

4401f90

fix bugs.

44b8114

fix bugs.

d6b71b1

zheng-da force-pushed the subgraph_op branch from 5c6abdd to d6b71b1 Compare May 31, 2018 22:32

reminisce reviewed Jun 1, 2018

View reviewed changes

reminisce merged commit 2f65d64 into reminisce:subgraph_op Jun 1, 2018

generalize graph partitioning. #11

generalize graph partitioning. #11

Uh oh!

Conversation

zheng-da commented May 30, 2018

Description

Checklist

Essentials

Changes

Comments

Uh oh!

reminisce left a comment

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

reminisce May 31, 2018 • edited Loading Uh oh! There was an error while loading. Please reload this page.

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Choose a reason for hiding this comment

Uh oh!

Reviewers

Assignees

Labels

Projects

Milestone

Development

Uh oh!

2 participants

reminisce May 31, 2018 •

edited

Loading