File ParallelFFT.h

↰ Parent directory (ADS/parallel)

The parallel fast Fourier transform, beyond the book: fft( ex , a , inverse ) is the transform of fft( a , inverse ) [see File FFT.h] on the threads of an executor [see File Executor.h], by the four steps of Bailey on top of the sequential fft().

Definition (ADS/parallel/ParallelFFT.h)

Detailed Description

The :math:` n = n_1 n_2 ` points, :math:` n_1 = 2^{lfloor k / 2 rfloor} ` for :math:` n = 2^k , are the matrix :math: a_{j_1 j_2} = a[ j_1 n_2 + j_2 ] ` of :math:` n_1 ` rows, and with :math:` omega_N = e^{-2 pi i / N} ` :math:`[

hat a[ k_1 + n_1 k_2 ] = sum_{j_2} omega_{n_2}^{j_2 k_2} Bigl( omega_n^{j_2 k_1} sum_{j_1} omega_{n_1}^{j_1 k_1} a_{j_1 j_2} Bigr) ,

` i.e., the :math:` n_2 ` transforms of the columns, the multiplication by the twiddle factors :math:` omega_n^{j_2 k_1} , the :math: n_1 ` transforms of the rows, and the transposition of the result. The transforms of length :math:` n_1 ` or :math:` n_2 ` (about :math:` sqrt n , in the cache of each core) are independent, each the sequential fft() of a row copied into a vector of its thread, and they run in parallel loops; the columns become rows, and the rows columns, by three parallel transpositions through a buffer of n points [see :ref:`file_ADS_parallel_Scratch.h], each in tasks of 16 rows by 256 columns and tiles of 16 x 16. A transposition that walks whole columns instead, e.g., gathering 8 columns at a time from the rows, crosses a page at each row (a row of :math:` 2^{11} ` points is 32 KB) and misses the TLB at each one: on the benchmark, gathering and putting back the columns of :math:` 2^{22} ` points takes longer than the whole sequential transform. The work is that of the sequential transform plus the twiddles and 4 passes of moves (3 transpositions and the copy of the result back), :math:` O( n log n / p ) ` time on p threads, the transform of a row not split. The result equals the sequential one up to the rounding, the error of both being :math:` O( epsilon log n ) ` relative to the norm.

The contracts [see File Contract.h]: the size of a is a power of 2 (or 0). D. H. Bailey, FFTs in external or hierarchical memory, The Journal of Supercomputing 4(1), 23-35, 1990, doi:10.1007/BF00162341

  1. Van Loan, Computational Frameworks for the Fast Fourier Transform, SIAM, 1992, doi:10.1137/1.9781611970999

Donato Meoli

Dipartimento di Informatica Universita’ di Pisa

by Donato Meoli

Includes

Namespaces

Functions

Variables