Skip to content
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

Improve asymptotic efficiency of reverse-mode AD in interpreter #2187

Open
athas opened this issue Oct 14, 2024 · 1 comment
Open

Improve asymptotic efficiency of reverse-mode AD in interpreter #2187

athas opened this issue Oct 14, 2024 · 1 comment
Labels
enhancement student-viable Viable as a student project

Comments

@athas
Copy link
Member

athas commented Oct 14, 2024

#2186 added AD to the interpreter. For reverse-mode, this is done by associating each value with a computation graph (really, DAG) that represents how the value was constructed. This is equivalent to the "Wengert tape" notion of AD. To compute the derivative, this graph is then traversed. Currently, the computation graph is represented as a tree, meaning that we redundantly recompute parts of it, which results in potentially exponential overhead. To fix this, we must exploit sharing inherent in the graph structure. The easiest solution may be to associate every node in the tree with a unique number, which during the traversal would let us recognise that we are re-visiting a part of the graph. Since this number must be globally unique, it must be maintained in the interpreter state.

I am also open to other ways to represent the graph, but this is the simplest one I could come up with.

@athas
Copy link
Member Author

athas commented Nov 28, 2024

Note that this is a somewhat small project. If you are a student interested in doing this, then it is unlikely to fit more than a 7.5 ECTS POCS.

Sign up for free to join this conversation on GitHub. Already have an account? Sign in to comment
Labels
enhancement student-viable Viable as a student project
Projects
None yet
Development

No branches or pull requests

1 participant