google / google/heir

Enhance layout optimization cost model to include multiplicative depth

Open
#2,351 4 comments 0 reactions 0 assignees View on GitHub
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

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.