Determine the right tradeoff to use when baby-step-giant-step step sizes are not evenly divisible

[j2kun]

Filing issue for pending TODO.

The problem is that when we are lowering rotate-and-reduce via baby-step-giant-step, if the numBabySteps does not divide the total number of steps, we have two options:

1. Add some extra ops at the end to account for the leftover
2. Find the closest number to sqrt(n) that does divide steps and use that.

Not sure which is best, and I decided to punt on doing the most optimal thing for now and implementing a naive version of (2). It seems like (2) is suboptimal in extreme cases like a prime number of steps, so the question is how to select between (1) and (2)

[lawrencekhlim]

I may be able to provide some insight from my experience:

1. Let's say you want to do 11 periodic rotations (that all sum up) with BSGS. Ideally, you perform 3-4 baby steps and 3-4 giant steps. For instance, you can do 4 baby steps and 3 giant steps as follows:
   Baby steps: [0, 1, 2, 3]
   Giant Step 1: [0, 1, 2, 3]
   Giant Step 2: [4, 5, 6, 7]
   Giant Step 3: [8, 9, 10]

Note that in Giant Step 3, you do not need to add in the fourth baby step to achieve correctness. I guess a simple algorithm would be to round up from the square root of number of rotations (ceil(sqrt(N)), which would be the number of baby steps, and exclude leftovers from the final giant step.

In fact, in general, it's okay to skip summing some of the baby steps if they aren't needed.

2. If you (in the future) have hoisting or even double hoisting BSGS implemented, then the optimal ratio between N1 (number of baby steps) and N2 (number of giant steps) (for N1 * N2 = N) will differ. Single Hoisting will prefer N1 to be larger around 2 times N2, while double hoisting will prefer N1 to be larger around 8-16 times N2.

EDIT: Corrected some wrong information about double hoisting.

[github-actions]

This issue has 1 outstanding TODOs:

• lib/Kernel/KernelImplementation.h:170: determine the right tradeoff here

This comment was autogenerated by todo-backlinks

[seydang]

The OpenFHE default parameter selection for BSGS in bootstrapping favors the N2 (giant step) to be larger than N1 (baby step). I believe, the N1 and N2 in our discussion correspond to the b and g parameters in the permalink, respectively.
I tested the default parameter selection for level_budget = {{3,3}, {4,4}, {5,5}} and numberOfSlots = {1<<8, 1<<15}; the N1 was chosen as N2//4 or N2//8 for all configurations. I do not have experimental results for the runtimes, though.

One potential reason (although this argument is more applicable to GPUs) is that the number of rotation keys (for double hoisting) increases with N1, resulting in more memory traffic.

On another note, for matrix multiplications, here is a simple test to explore the effect of N1 on the runtime:
Test: JKLS Plaintext-Ciphertext Matrix Multiplication on GPU-accelerated FIDESlib. Matrices are of size 128x128, N = 128, parameter set = {ringDim = 1 << 16, L = 26, L_eff = 7, dnum = 5}. Timing on a single A100 GPU (each point is an average over 10 runs):

Although the optimal points are at N1=8 (N2=16) for both MMs, the performance is affected negligibly at N1=4 (N2=32) and N1=16(N2=8) cases. I believe setting N1 to be the closest power of 2 to sqrt(N) will perform well for PCMM and CCMMs. However, different applications (and target hardware) for BSGS may require a different ratio of N1/N2.

[j2kun]

Thank you both for the helpful explanations! I think there will come a time when we customize these passes for specific hardware backends, but for now the best approach is probably to give a heuristic that is decent for most workloads/platforms, and which can serve as a baseline. I don't think I will have the time to work on this in the next few months so it's open if anyone wants to give it a shot.

[eymay]

I agree with @lawrencekhlim that it is ok to skip some leftovers. But still we can nudge the number of leftovers by choosing whether to round with floor or ceil. For example here we went with ceil(sqrt(N)) for 11 meaning ceil(3.32)= 4 for giant step size:

Baby steps: [0, 1, 2, 3]
Giant Step 1: [0, 1, 2, 3]
Giant Step 2: [4, 5, 6, 7]
Giant Step 3: [8, 9, 10]

If we instead chose floor(sqrt(N)) then it would be g=3

Baby steps: [0, 1, 2]
Giant Step 1: [0, 1, 2]
Giant Step 2: [3, 4, 5]
Giant Step 3: [6, 7, 8]
Giant Step 4: [9, 10, 11]

The number of leftovers will actually be N mod g with g being ceil/floor(sqrt(N)) . The room for more baby rotations is going to be baby step size minus the leftovers as b - N mod g. This could provide a simple heuristic to minimize leftovers but it is worth considering hoisting and other effects.