Implement a simple cost model for FHE computations
- Dominant language
- MLIR
- Stars
- 906
- Forks
- 171
- Avg merge
- 4d 12h
- Merged PRs (30d)
- 32
Description
Starting this issue so I have a place to jot down notes as I come across relevant information in the literature.
Basically, various passes will eventually need to start making decisions about whether to choose one type of homomorphic operation or another. We should have a cost model (or multiple models) that help quantify these trade-offs. Eventually I think they will boil down to more quantifiable costs per hardware target, but for high level passes it will still be useful to have a relative tradeoff.
To start, the HyPHEN paper Kim-Park-Kim-Kim-Ahn 2023 (https://ieeexplore.ieee.org/stamp/stamp.jsp?arnumber=10376063) has a table of benchmark CKKS operation times; 64-threads across two 2.35 GHz CPUs, using RNS-CKKS HEaaN, `N=2^16` (see IV.A in the linked paper).
| Op | Runtime (ms) |
| -------- | ------- |
| Add plaintext | 0.169 |
| Add ciphertext | 0.202 |
| Mul plaintext | 0.506 |
| Mul ciphertext | 17.3 |
| Rescale | 3.90 |
| Plaintext rotate | 0.102 |
| Ciphertext rotate | 15.5 |
| Bootstrap | 2160 |
Contributor guide
Assessment
This issue has not been assessed yet.