Page History

...

We first generate a list of pairs of groups of nodes that are incompatibles incompatible (if the subgraph contains one node of one of the group groups (e.g. TensorRT compatible) then it can't contain any node in from the other group (non-TensorRT compatible)). This is done by running BFS and reverse BFS starting from all the non-TRT TensorRT compatible nodes.

Figure: Black nodes are not TRT TensorRT compatible. Focusing on node 4: we generate two groups (G1 / G2) by running reverse-BFS / BFS from this node. The properties of those two groups is that if one node of the subgraph is in one of the two group groups then you can't add any node from the other group (it will create a cycle that can't be solved broken by adding more nodes because this non-TRT TensorRT compatible node will stay in between).

We generate a list of pair of group groups (one pair for each nonTensorRT-TRT compatible incompatible node)

We add subgraph subgraphs one by one, using BFS:

 - start from a node which is not part of a subgraph, instantiate his its list of incompatibles incompatible nodes

 - grow the subgraph by on in DFS order (on both inputs and outputs with priority to inputs), to add a node to the subgraph it have has to be:

       1) TRT TensorRT compatible

       2) not in another subgraph

       3) not in the list of current subgraph incompatibles 's incompatible nodes

 - Once (and only if) a node is added to the subgraph we:

       1) Update the incompatibility list with new incompatible nodes

       2) Add his its inputs / outputs to the queue (for future visit)