  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 single-threaded Intel Math Kernel Library (MKL) implementation
of 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.5x, and faster than FFTW by up to 2.5x. The code
of EFFT is available for free download under the GPLv3 license. This work
provides a new efficient DFFT implementation, and at the same time demonstrates
an educational example of how computer science problems with complex parallel
patterns can be optimized for high performance using the Intel Cilk Plus
framework.
