Big Prime Field FFT on Multi-core Processors

Abstract : We report on a multi-threaded implementation of Fast Fourier Transforms over generalized Fermat prime fields. This work extends a previous study realized on graphics processing units to multi-core processors. In this new context, we overcome the less fine control of hardware resources by successively using FFT in support of the multiplication in those fields. We obtain favorable speedup factors (up to 6.9x on a 6-core, 12 threads node, and 4.3x on a 4-core, 8 threads node) of our parallel implementation compared to the serial implementation for the overall application thanks to the low memory footprint and the sharp control of arithmetic instructions of our implementation of generalized Fermat prime fields.
Complete list of metadatas

Cited literature [22 references]  Display  Hide  Download

https://hal.inria.fr/hal-02191652
Contributor : Svyatoslav Covanov <>
Submitted on : Tuesday, July 23, 2019 - 5:09:37 PM
Last modification on : Friday, July 26, 2019 - 1:15:22 AM

File

cmmw-2019.ISSAC.sigconf.pdf
Files produced by the author(s)

Identifiers

  • HAL Id : hal-02191652, version 1

Collections

Citation

Svyatoslav Covanov, Davood Mohajerani, Marc Moreno Maza, Linxiao Wang. Big Prime Field FFT on Multi-core Processors. ISSAC 2019 - International Symposium on Symbolic and Algebraic Computation, Jul 2019, Pékin, China. ⟨hal-02191652⟩

Share

Metrics

Record views

22

Files downloads

223