NTT ideas

[catid]

I recently wrote some NTT code for my Leopard project and found a 50% speed boost using decimation-in-time version, where I take groups of 4 positions and operate on them (rather than 2 at a time). This allows us to effectively run two layers of the NTT/FFT/AFFT/etc in registers at a time rather than laborously writing them out and reading them back in again. It was hard to follow your AVX2 qhasm code but I think it doesn't do that so maybe a good win there?

e.g. https://github.com/catid/leopard/blob/master/LeopardFF16.cpp#L616

Another suggestion is to use ISPC instead of qhasm since it appears to support ARM NEON also, but I don't have any personal experience (yet) to back up that suggestion..

[catid]

Also FFT can run in parallel so maybe try OpenMP also? :)

e.g. https://github.com/catid/leopard/blob/master/LeopardFF16.cpp#L121

[cryptojedi]

"Christopher A. Taylor" <notifications@github.com> wrote: Hey Christopher,

Also FFT can run in parallel so maybe try OpenMP also? :)

That's certainly the wrong level to parallelize with OpenMP. If you do just *one* Kyber key generation, encapsulation, or decapsulation, you don't care about speed (it's fast enough). If you have many, you can trivially parallelize on a higher layer. Cheers, Peter

[cryptojedi]

"Christopher A. Taylor" <notifications@github.com> wrote: Hey Christopher,

I recently wrote some NTT code for my Leopard project and found a 50% speed boost using decimation-in-time version, where I take groups of 4 positions and operate on them (rather than 2 at a time). This allows us to effectively run two layers of the NTT/FFT/AFFT/etc in registers at a time rather than laborously writing them out and reading them back in again. It was hard to follow your AVX2 qhasm code but I think it doesn't do that so maybe a good win there?

We're certainly still looking into NTT optimization, but the current code is already picking up coefficients that interact through 3 layers of NTT (consuming 8 registers), doing the necessary operations, and only then writing back.

Another suggestion is to use ISPC instead of qhasm since it appears to support ARM NEON also, but I don't have any personal experience (yet) to back up that suggestion..

So does qhasm (the development version). I'd rather not have any compiler messing with register allocation etc., and my understanding is that ISPC is still too high level for what I want. Cheers, Peter

[catid]

Nice work!