google / google/heir

Multiplicative and Additive Balancing

Open
#836 2 comments 0 reactions 1 assignee Claimed by @lawrencekhlim View on GitHub
good first issue newcomer project optimization
Dominant language
MLIR
Stars
906
Forks
171
Avg merge
4d 12h
Merged PRs (30d)
32

Description

Given a tree of associative operations, say (((a * b) * c) * d), then rebalance the tree to be (a * b) * (c * d). This improves performance because the latter lowers the multiplicative depth by one. One can implement the algorithm provided in this paper:
[https://eprint.iacr.org/2021/1505.pdf](https://eprint.iacr.org/2021/1505.pdf).

This can also be useful for Additive Operations because it means that Additive Operations can be parallelized with better performance.

EDIT: This issue is addressed by #878, see below for more TODOs for a starter project.
See also #837 for a distributive property optimization.

Contributor guide

Open the contributing guide

Assessment

This issue has not been assessed yet.

Get new issues in your inbox

A short digest of beginner-friendly GitHub issues.