SIMD vectorizer: Handle arbitrary sized vectors using EVA style splitting and repeating

[asraa]

EXL (EVA extended library) supports general EXL vector sizes that are translated into CKKS ciphertext slots by the following:

• User specifies their arbitrary input EXL vector size
• The arbitrary EXL vector is split into a number of power-of-two sized vectors**, zero padded
• The power of two vectors are replicated into ciphertext slots

For example, this is how the process goes for an EXL vector of size 5

EXL vector: [1 2 3 4 5] Power of Two (size 4) vectors: [1 2 3 4] [5 0 0 0] SEAL vector: [1 2 3 4 1 2 3 4 ... 1 2 3 4] [5 0 0 0 5 0 0 0 ... 5 0 0 0]

**The user creates a program generator that loops over power of two vector sizes to find the smallest valid power of two vector size. (I'm not sure I understand their pseudocode for the generator on page 19 of their paper though).

In EXL the program must be recompiled in the program generator, we can definitely perform this within a pass.

Questions:

• I'm not how this will impact rotations, or if this should apply before rotations are inserted

[j2kun]

I would guess this should be the very first pass, but I'm not sure.

What we also need is a way to connect a single "input vector" to its representation as an expanded/packed set of ciphertexts. Without that, we won't be able to conceive of an addition of two input vectors.

What if we use the tensor encoding attribute for that? I.e., define an attribute that describes the packing, and then have a 1-1 mapping of input vectors to packed (multidimensional) vectors with the packing description attached to the latter.

[asraa]

I would guess this should be the very first pass, but I'm not sure.

Same here - I would expect that there would be smarter ways of ordering the elements too once we calculated out the possible rotations.

I think the first step is to implement the power of two replication first, which can help me build the vector -> packed vector abstraction first.

I know we talked about an affine-map-like attribute as well, so I'm going to peruse a little around on what can be friendly with replications

[asraa]

Just realized the tensor encoding attribute can have a map :)

[j2kun]

Labeling this issue for the remaining TODO

[asraa]

One thing we discussed was for smart plaintext packing, we can run a higher-level pass that runs on ops like matrix muls with plaintext or other high-level operations where we know a smarter pack.

The pass architecture could look something like:

1. Smart packer (diagonalizer on plaintext matrices, etc)
2. Collapse ND tensors to 1D
3. Align tensor sizes (not smart pass)
4. SIMD vectorizer (handling any remaining vectorization)