New issue
Have a question about this project? Sign up for a free GitHub account to open an issue and contact its maintainers and the community.
By clicking “Sign up for GitHub”, you agree to our terms of service and privacy statement. We’ll occasionally send you account related emails.
Already on GitHub? Sign in to your account
state.topological_sort is incorrect, while sdfg.utils.dfs_topological_sort is correct #1560
Comments
Yes, this seems to be a bug in Lines 367 to 390 in ee5a6df
This algorithm can fail for a graph like: A
| \
| \
v v
B <- C The only correct topological order would be A, C, B. Whereas the current algorithm can also produce the incorrect order of A, B, C (ignoring the dependency between B and C). My language server could find only three references to the broken I would suggest completely removing However... makes no sense to use The references that my language server found: dace/dace/codegen/targets/framecode.py Lines 534 to 570 in ee5a6df
Lines 2548 to 2605 in ee5a6df
dace/dace/transformation/passes/constant_propagation.py Lines 156 to 242 in ee5a6df
|
Describe the bug
When I call:
dace.sdfg.utils.dfs_topological_sort(state)
I have a correct topological sorting of nodes within a state but, calling:
state.topological_sort()
Results with an ordering that is not correct.
To Reproduce
Steps to reproduce the behavior:
I have a minimal program to reproduce the issue. In the example I reproduce, an access node, which has an edge to an map node, is listed after the map when sorted with
state.topological_sort
Expected behavior
When I print the nodes and edges in the order received from the nodes and their outgoing edges are printed as follows:
Expected would be: (the access node gpu_dataA that as outgoing edge to the kernel, needs to be before the kernel)
The generated example program I can't attach but here is the full code, it prints the nodes and saves the sdfg as ex.sdfg:
Desktop (please complete the following information):
The text was updated successfully, but these errors were encountered: