mkolod edited a comment on issue #11325: Added TensorRT runtime integration URL: https://github.com/apache/incubator-mxnet/pull/11325#issuecomment-404320678 @reminisce Regarding your question about the cycle check, I'd like to juxtapose two approaches, one of which is the one taken here, and the other is more typical but probably less efficient for large graphs. Here's your graph (starred nodes are TensorRT-compatible, unstarred ones are not): ``` A* → D ↓ ↓ B* → C* ``` **Approach 1 - greedily growing the subgraph and checking for cycles each time** This approach tests adding a new node while greedily growing the subgraph and if a cycle is formed while adding a new node, the node is rejected from the growing subgraph. Taking your graph as an example, say we start with A*. Clearly TensorRT only helps when there are 2 or more nodes, due to its benefit being mainly due to fusion. So, we get (A*, B*) in the set of nodes in the TensorRT graph. This is fine, there's no cycle, because the edge from the node replacing the subgraph is from B* to C*, not the other way around. So, we have the following: ``` ↗ D T* ↓ ↘ C* ``` Now we try adding C*, to get (A*, B*, C*) in the TensorRT subgraph. Let's call this subgraph T*. Now D is the only node outside the subgraph and we have a cycle from T* to D, back to T*. This was an illegal contraction, so the last step is rejected, and only A* → B* gets substituted with T*. Hence, the most contracted legal subgraph contains the nodes T*, D and C*. This is in fact how TensorRT integration with TensorFlow works, or used to, the last time I checked. **Approach 2 - Examining sets of pairs** Instead of the greedy subgraph growth with cycle checks after each node addition to the subgraph, let's enumerate all pairs of nodes that are TensorRT-compatible or incompatible. A pair is compatible if both nodes between the edge are TensorRT-compatible - only then can they go into the TensorRT subgraph. For the graph above, this would be A* → B* and B* → C*. A* → D is incompatible because D is incompatible, so the whole pair is incompatible. Similarly, D → C* is incompatible because D is incompatible. However, if there is a node which is part of both a compatible pair and of an incompatible pair, it's no longer a candidate for the TensorRT graph. The contradiction forces it into the incompatible class. Such a node is A*. That's because even though it's compatible in one pair (A* → B*), it's incompatible in another (A* → D). So, the only edge that can be collapsed is B* → C* and these two nodes become T*. Now the graph after the rewrite will look as follows: ``` A* → D ↘ T* ↙ ``` The graph partitioner for this PR takes Approach 2. The nice thing is that the pair compatibility can be determined once to test all possibilities of subgraph growing, instead of having to do a full search (e.g. DFS, DFS with graph coloring, Kahn's algorithm, whatever) every time a node is greedily added and substituted. Approach 2 works. We will add a unit test for this to show that it works for your scenario. I hope this clarifies your question as to how we handle cycles.
---------------------------------------------------------------- This is an automated message from the Apache Git Service. To respond to the message, please log on GitHub and use the URL above to go to the specific comment. For queries about this service, please contact Infrastructure at: us...@infra.apache.org With regards, Apache Git Services
