Cycle detection in computation graph during fusion

When nodes are merged (graph fusion pass for example), how are cycles detected/avoided? Is it taken care by moveAfterTopologicallyValid in alias analysis? What algorithm is used here? Any pointers would be highly appreciated :slight_smile:

What do you mean by cycles?
The graphs are acyclic and we loop until there is no more nodes to add to a fusion group…

Best regards

Thomas

Lets consider a graph, like the following,
image
(Copied from here)

If we combine 1, 3, 4 red nodes above, we form a loop right? Considering 1, 3, 4 are can be grouped, what prevents the fusion from happening? If my question doesn’t make sense, please feel free to correct me :slight_smile: .

Yes, moveAfterTopologicallyValid takes care of that. It does dependence analysis to make sure that this merging is disallowed.

2 Likes

Cool. Thanks for the response :slight_smile:.