Skip to content

Wrong scheduling because of the lack of memory dependencies #1283

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

Closed
qcolombet opened this issue Jul 16, 2018 · 4 comments
Closed

Wrong scheduling because of the lack of memory dependencies #1283

qcolombet opened this issue Jul 16, 2018 · 4 comments
Assignees

Comments

@qcolombet
Copy link
Contributor

Our graph does not model the memory dependencies explicitly.
As a result, if we have a variable is written and read on different
data paths, the scheduler may be unlucky and we read the wrong
version of the variable.

Essentially, if you have:
     A
    / \
write read

The scheduler can produce either:
write A
read A
or
read A
write A

Obviously this does not produce the same output.
Glow intended semantic is that write should happen last, but with
our current algorithm, this is actually possible to fool the
scheduler not to do that.

I'm going to send a PR to show how we can fool the scheduler.

@qcolombet
Copy link
Contributor Author

Problem illustrated in #1284.

This PR adds two test cases that build exactly the same graph. However, by just changing the order of the creation of the nodes, we can trick the scheduler to produce an invalid schedule.

@qcolombet qcolombet self-assigned this Jul 16, 2018
@qcolombet
Copy link
Contributor Author

After talking with @nadavrot this morning, we are going to explicit state that save nodes happen after the last use of the related variable. In other words, referencing a variable will always get you the old value.

Similarly we are going to enforce that every variable has at most one save nodes. That way it will remove the ambiguity of which save should happen last (all the others would have been dead because of the other restriction.)

@qcolombet
Copy link
Contributor Author

As expected while reviewing #1176, I realize that our implicit memory dependencies are going to bite us again during graph partitioning.

The problem there is that the post order visiting methods don't see the memory dependencies edges. So, we will have to do one of the following fix the visiting scheme, come up with targeted fix for the graph partitioning stuff, or model the memory dependencies.

qcolombet pushed a commit that referenced this issue Jul 23, 2018
When a variable is used as output in a save node, this is expected
to be its last use. Make sure the GraphSchedule looks at the implicit
dependencies between all the uses of a variable and its save node
when walking the dependencies.

This fixes issue #1283.
@qcolombet
Copy link
Contributor Author

Fixed by #1307.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
None yet
Projects
None yet
Development

No branches or pull requests

1 participant