Compilers

[Janmajayamall]

https://dl.acm.org/doi/pdf/10.1145/3591228

Paper introduces Poly, ModArth MLIR dialects and shows that HE related routines (i.e. routines of CKKS/BFV) written in MLIR using Poly, ModArth dialects, due to compiler optimisations leveraged in the dialects, can outperform HEaaN.it and SEAL.

FHE follows circuit model. So the general idea is to take the code written in DSL by the programmer, run several optimisation using dialects (HE related operations themselves are coded in MLIR as dialects) and output only backend specific instructions (for example, Poly operations specific to a FHE accelerator OR CPU instructions).

[Janmajayamall]

HEIR - https://eprint.iacr.org/2023/1445.pdf

1. designing a set of new multi-level intermediate representation (IR) dialects tailored for FHE, we can fully utilize the SIMD capability [2, 4, 20] of FHE ciphertexts. Furthermore, the proposed program transformation passes can seamlessly extract non-polynomial computations out of the plaintext program and map the target computations into proper FHE operators. Consequently, HEIR can simultaneously achieve superior performance against circuit-based compiler frameworks and functional complete usability compared to compilers that can only handle polynomial functions

2. HEIR is DSL free and functional complete.

3. Coefficient encoding is commonly used in sample extraction [18] and CKKS bootstrapping [15, 16, 82–85]. Besides, coefficient representation is found to be more efficient than slot representation in implementing homomorphic inner products and convolutions [2, 4].

4. HEIR uses Polygeist (C++ frontend for MLIR) because

   Polygeist can lower a C program to a variety of high-level built-in IRs in the MLIR framework. The key advantage of directly employing Polygeist is that generic program optimizations can be decoupled with the subsequent FHE-specific transformations and optimizations. Consequently, different from existing FHE compilers like [62], we do not need to manually re-implement generic program optimizations such as common sub-expression elimination (CSE) and dead-code elimination and maximize the utilization of the existing tools.

5. HEIR mention multi-modulus bootstrapping technique that can transform input ciphertext with small ciphertext modulus into a chiphertext with a large modulus while retaining small ciphertext noises.

6. To resolve the problem of scheduling scheme switching based on operand:

   . To enable operatorbased operand conversion, we take a simple yet effective approach: we first initialize all variables to be non-vectorized (i.e., LWE) ciphertext, and then scan the entire program to see if there exists regions we can schedule a scheme-switching conversion to leverage the SIMD capability of arithmetic FHE using an RLWE ciphertext.

7. Introduces Mini-Repack algorithm for LWE to RLWE:

   We observe that a lightweight REPACK algorithm for packing a small number of ciphertexts is valuable, as further discussed in Appendix C. To meet the above needs, we proposed a Mini-Repack algorithm which is tailored for packing a small number of LWE ciphertexts as demonstrated in Algorithm 1.

8. To properly schedule Slot/Coeff encoding:

   To correctly capture the encoding characteristics in general programs, we proposed a novel encoding pass such that RLWE ciphertexts can be set in the most efficient encoding methods throughout the program. Similar to that of scheme-switching scheduling, in the encoding pass, we first set all RLWE ciphertexts to be in the slot representation, and then execute Algorithm 4 in Appendix D to identify program fragments that are more suitable to be in the coefficient encoding formats (Jay: Seems like we have a reason to support coefficient encoding in gauss)

9. It may be nice idea to check how HEIR handles re-scaling for CKKS. I think it is manual and not automated (Oops their FHE library is closed source)

[Janmajayamall]

HECO https://arxiv.org/pdf/2202.01649.pdf

1. HECO compiler consists of

   1. Program optimisation
   2. Circuit optimisation
   3. Crypto optimisation
   4. Target optimisation

2. The compiler is capable of using multiple backends. For example, we can use SEAL/Lattigo as the backend. Or use some FHE hardware accelerator that accelerates only ring operations as backend. This is also the place where "progressive lowering" of MLIR becomes useful. Depending on the target, inside target optimisation, we can define FHE scheme specific dialects. If the target is some library (for ex, SEAL) then the output uses library APIs. If the target is some FHE accelerator that only provides poly operations, then the output binary will only contain poly operations (this implies scheme specific routines are coded as dialects in MLIR)

3. Target Optimisations; Page 6

   Initial work in this space has already shown that code generation and scheduling can have a significant impact on accelerator performance [29,30].

4. Automated batching is important. We will have to figure out necessary transformations

5. Implementation https://github.com/MarbleHE/HECO

6. I tried testing HECO but honestly, due to burden of LLVM, it is quite hard to do so.

7. Automated SIMD (and its passes) is the most important thing introduced in HECO; HEIR (2023/1445) uses Algorithm 2 as subroutine.

[Janmajayamall]

HECATE http://corelab.or.kr/Pubs/cgo22_hecate.pdf

1. For RNS-CKKS, compilers CHET, EVA, nGraph, nGraph2, ease the burden of manual rescaling by setting a waterline re-scaling factor and whenever the scale of ciphertext exceeds the waterline, rescaling operation is added. However the compiler do not consider the performance impact of this naive technique.

2. HECATE compiler optimises for scales of ciphertext while minimising the performance impact of added rescaling operations.

   First, HECATE proposes a new parameter switching operation called downscale that rescales a ciphertext even though its scale is smaller than the sum of rescaling factor and waterline, thus enabling proactive rescaling. Second, HECATE analyzes ciphertexts and their FHE operations and generates scale management units by grouping ciphertexts that have the same scale and rescaling level. Third, HECATE constructs various scale management plans, estimates their performance, and finds the optimal scale management plan. Furthermore, to respect the constraints on scales and rescaling levels of FHE operands, HECATE introduces a new type system that verifies the scales and levels.

3. Rescale: scales by last prime and switches the mod to level i+1. Modswitch: only switches the mod to level i+1

4. Scale management exploration space

   To achieve better performance, HECATE automatically explores the scale management space, determining where and which one of rescale, modswitch, and/or downscale to place

   HECATE explores the scale management space by the hill-climbing method. Given the scale management units, HECATE constructs scale management plans by changing one step from the previous iteration. Then it generates FHE codes with scale management operators, which meet the constraints (C1-C3). Finally, it estimates the performance of each plan. The one with the best-estimated performance is passed to the next iteration until the hilltop is reached.

5. Benefit of tying plan for rescale procedures with performance is illustrated in figure 2c where, although the scale factor of end result if 60 (3x of waterline 20), 3 multiplications for cubing z, to improve performance, are performed at level 1.