How to compute the Latency Table and Noise Table?

[timzsu]

Hello,

I am trying to connect Lattigo with Dacapo for experiments, given that the HEAAN backend is not available. However, I don't completely understand what I should put in profiled_LATTIGO_CPU.json, and I wonder if you can give me some pointers. Here is my understanding:

1. "runtime" is the name of this VM.
2. "rescalingFactor" is the # bits in scaling factor
3. "polynomialDegree" is N (as defined in SEAL_HEVM.cpp)
4. "levelUpperBound" is L (as defined in SEAL_HEVM.cpp), the maximum level for encoding.
5. "levelLowerBound" is the minimum level for decryption.
6. "bootstrapLevelUpperBound" is the maximum level that can be achieved after bootstrapping.
7. "bootstrapLevelLowerBound" is the minimum level required to perform bootstrapping (i.e. with lower levels bootstrapping is not possible).
8. "latencyTable" and "noiseTable" are the estimated latency and noise for each operation on each level.

Besides, I am wondering about the format and functionality of the latency table and noise table. Are they used during the compilation, or are they just used for estimated latency after compilation? Is there any generation script that I can refer to? And why is there not a noise table for HEAAN?

Best regards,

Zhengyuan Su

[Seonyoung-Cheon]

Hello!

1. Your understanding of points 1-8 is correct.

2. The 'profiled_*.json' file is used only during the compilation process.

3. You can measure the time by checking the duration before and after calling the library API. In HEAAN_HEVM.cpp, you can easily measure the time by using a time measurement API such as chrono right before and after each API call. The experimental results will be output using Python's time, so there may be slight differences from the estimated latency, but the trends will be almost identical.

4. The noise table is part of the ELASM compiler, which manages error-latency-aware scale management. However, DaCapo focuses solely on latency optimization, so only the latency table is needed for testing with the DaCapo compiler. If you're only using the DaCapo compiler, you do not need to fill in the noise table.

Thank you for your interest :)

[timzsu]

Thank you for the response!

I have a quick follow-up question on the format of the latency table.

All operations other than the modswitch_single, bootstrap_single, and rescale_single contain L numbers, so I believe the i-th number means the latency of operation over ciphertext(s) with level i. But modswitch_single and rescale_single have L- 1 numbers, and bootstrap_single have bootstrapLevelUpperBound+1 numbers respectively.

rescale_single seems easier to explain, as ciphertexts with the lowest level cannot be rescaled further so slots might be omitted. However, I am confused about what exactly the i-th latency means for the other two operations.

Here are my guesses:
For modswitch_single, does the i-th number mean downFactor=i?
For bootstrap_single, does the i-th number mean targetLevel=i (i ranging from 0 to bootstrapLevelUpperBound)?

Thank you,

Zhengyuan

[Seonyoung-Cheon]

In modswitch_single, similar to rescale_single, the lowest level cannot be dropped. The downFactor parameter indicates how many levels to drop, which corresponds to the gap between the operand level and the result level.

For bootstrap_single, your understanding is correct. The i-th number represents the targetLevel i.

The HEaaN Library parameter set includes a base level modulus + L (29), meaning other operations involve L+1 (from level 0 to level 29, a total of 30 levels). Bootstrapping works the same way, with i ranging from 0 to bootstrapLevelUpperBound.

Thank you!

[timzsu]

For modswitch_single, do you mean the i-th number represents the latency of dropping downFactor=1 level for a ciphertext with level i (so i ranges from lowest level+1 to highest level)?

Thank you,

Zhengyuan

[Seonyoung-Cheon]

The i-th number in modswitch represents the target level after modswitch.

[timzsu]

Hello,

In mod switching profiling, do you fix the input ciphertext to have the maximum level (i.e. level change: L -> target_level) or the target level + 1?

Besides, for rotate_single, I think the latency is related to the offset (e.g. SEAL breaks the offset into NAF representation and does a series of rotations with the offset being powers of 2). Which offset do you use?

Thanks,

[Seonyoung-Cheon]

Hello!

I have updated (2024.11.18) the latency estimation for modswitch to account for the downFactor. So, when writing the latency table for the i-th number in modswitch_single, the operand ciphertext is at level i, and the target level is i-1. Then, the getLatency() in LatencyEstimator Pass adds the estimated latencies from level i to level i - downFactor + 1 for the operand ciphertext.

Also, for rotate_single, we used an offset of 1 in the latency table. The LatencyEstimator pass also takes this offset into account when considering performance.

Thanks! :)

[timzsu]

I see. Thank you for the clarification!

[timzsu]

Hi,

I am wondering how you compute the noise if I want to use ELASM. I see that there are only three entries - rescale_single, rotate_single, and mul_double, which I guess is because only they introduce "noise" according to ELASM table 1. Are those numbers computed using the theoretical upper bound? Or are they tested using real benchmarks?

If they are tested by experiments, how did you split the input error component from the overall noise in the resulting ciphertext?

Thank you!

[rovelace]

We profiled the noise of each operation by a microbenchmark.
The decryption sequence itself does not add noise. Encryption does.
Hence, comparing the noise between the encryption-decryption sequence and the encryption-rescale-decryption sequence could give you the separated error component.
I analyzed each operation in a complex benchmark (decrypting every intermediate value and comparing it) and the result confirms the assumption.