Enhance layout optimization cost model to include multiplicative depth
- Dominant language
- MLIR
- Stars
- 906
- Forks
- 171
- Avg merge
- 4d 12h
- Merged PRs (30d)
- 32
Description
## Summary
Enhance the layout optimization cost model to track multiplicative depth in addition to rotation count, enabling more accurate kernel selection for layout optimization decisions.
## Background
PR #2347 implemented a DAG-based cost model for the layout optimization pass that counts rotations using symbolic execution with CSE. The cost model returns a scalar `Cost` representing the number of rotations required by a kernel (e.g., O(√n) for baby-step giant-step matrix-vector kernels).
While rotation count is a critical metric, multiplicative depth is another important factor in FHE performance. As discussed in #2347, future enhancements should track both metrics to make better-informed kernel selection decisions.
## Proposed Enhancement
1. Track multiplicative depth alongside rotation count by analyzing the `ArithmeticDag` structure
2. Return a multi-dimensional cost structure containing both rotation count and multiplicative depth
3. Develop a strategy for comparing and combining these metrics when selecting optimal kernels in `computeHoistingOptions()`
## Related
- #2316: Original issue for adding proper cost model (rotation counting implemented in #2347)
Contributor guide
Assessment
This issue has not been assessed yet.