Intel Cilk Plus for complex parallel algorithms: 'Enormous Fast Fourier Transforms' (EFFT) library

摘要

In this paper we demonstrate the methodology for parallelizing the computation of large one-dimensional discrete fast Fourier transforms (DFFTs) on multi-core Intel Xeon processors. DFFTs based on the recursive Cooley-Tukey method have to control cache utilization, memory bandwidth and vector hardware usage, and at the same time scale across multiple threads or compute nodes. Our method builds on a single-threaded Intel Math Kernel Library (MKL) implementation of real-to-complex DFFT, and uses the Intel Cilk Plus framework for thread parallelism. We demonstrate the ability of Intel Cilk Plus to handle parallel recursion with nested loop-centric parallelism without tuning the code to the number of cores or cache metrics. The result of our work is a library called EFFT that performs 1D DFTs of size 2(N) for N >= 21 faster than the corresponding Intel MKL parallel DFT implementation by up to 1.5 x , and faster than FFTW by up to 2.5x. The code of EFFT is available for free download under the GPLv3 license.