Port Viaduct-HE to HEIR
Opened this issue · 4 comments
The preprint paper "A Compiler from Array Programs to Vectorized Homomorphic Encryption" presents Viaduct-HE, a vectorizing HE compiler for an array-oriented source language. We could port their work to HEIR.
The full paper is available here.
Here's a brief walkthrough of viaduct-he from a code perspective.
@edwjchen Thanks for your summary and discussion on this in the last meeting (sorry for not being there 😴)
The basic approach of "pick a batching approach, then generate the circuit to get a cost estimate" does seem somewhat limiting if one were to do this at a high-ish point in the stack. I wonder how this approach compares to the HElayers packing optimizer...
More generally, @j2kun 's question on the order in which the compiler should make these decisions is a really, really though one. My guess would be the practical impact depends on whether or not we end up with many important optimizations that are not batching agnostic. For example, there's a bunch of LinAlg/ML techniques that have preconditions on the packing. However, if the batching step "re-invents" these approaches anyway (as Viaduct-HE seems to be capable of doing, if given enough search time), losing them might not be as critical.
There are other cases like this where there's a longish search that could be done to fix some parameter at the outset. I'm thinking of security parameter selection, how much to unroll loops, etc. it wouldn't be unreasonable to have a separate mode in the compiler where you run a program through a much longer set of analyses to get some statistics about the search space, then fix a few parameters for the final compilation. Rather than making the compiler encompass the entirety of the smarts in every run. Kinda like how a normal compiler hard-codes what goes into the -O3 optimization flag
The basic approach of "pick a batching approach, then generate the circuit to get a cost estimate" does seem somewhat limiting if one were to do this at a high-ish point in the stack. I wonder how this approach compares to the HElayers packing optimizer...
@AlexanderViand-Intel As far as the search approach is concerned, viaduct-he and HELayers seem to be fairly similar. Both approaches start with an initial packing layout, a set of transformations to permute the packings, and a local cost-evaluation loop to direct which permuted packings the system should keep searching on.
The difference in the cost evaluation step is that HELayers gets around "circuit generation" by representing packed vectors (ciphertexts) in their tile-tensors abstraction. With the final FHE program in hand, both systems then simulate the cost using a pre-calculated cost model (HELayers going further with simulating the memory consumptions as well).
In regards to @j2kun's point on the order of optimizations, viaduct-he (and I'm assuming HELayers also does this too) run circuit optimizations after the packing is set. An interesting direction would be to quantify the performance tradeoffs of applying circuit optimizations during or after the packing search phase (i.e., tradeoffs of search time to circuit evaluation time). We could then compare the results to see if there are any batching-agnostic optimizations worth noting.