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

Caching: add sub-expression caching support #7

Open
3 of 5 tasks
tspooner opened this issue Dec 30, 2022 · 1 comment
Open
3 of 5 tasks

Caching: add sub-expression caching support #7

tspooner opened this issue Dec 30, 2022 · 1 comment
Assignees
Labels
feature New feature or request

Comments

@tspooner
Copy link
Owner

tspooner commented Dec 30, 2022

Summary

At present, any given mathematical expression in aegir is formed as a (potentially very large) tree vis-a-vis symbolic differentiation. This leads to many challenges, but doesn't have to be a blocker if implemented correctly despite what many people claim [1]. The problem is, we are currently missing one crucial feature to avoid redundant computation.

Caching is fundamentally important for efficient computation in symbolic approaches to autodiff. The idea is to avoid computing the output every single operator if we can assert that the result has already been computed. This facilitates the transformation of expression trees into expression forests which are known to be equivalent to the DAGs used in more traditional implementations [1].

[1] Laue, Sören. "On the equivalence of forward mode automatic differentiation and symbolic differentiation." arXiv preprint arXiv:1904.02990 (2019).

To-Do List

  • Add trait for mutating entires in Context types.
  • Implement an operator, say Cached, that skips redundant computation.
  • Add Hash implementations for operator trees to facilitate identification.
  • Extend Context support for Hash-based access to cached results.
  • Facilitate propagation of Cached operator through Differentiable::adjoint.
@tspooner tspooner self-assigned this Dec 30, 2022
@tspooner tspooner added the feature New feature or request label Dec 30, 2022
@tspooner
Copy link
Owner Author

tspooner commented Jan 2, 2023

Progress is being made here: see commits 9ad7fcc through 380678c. Major roadblock will be in how to propagate Cached through Differentiable::adjoint. Similar challenge to #5 in which rewrites to the tree are not permitted when each operator is a unique type rather than an algebraic data type.

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

No branches or pull requests

1 participant