Fast Fourier transform algorithms for parallel computers

Preface......Page 6
Contents......Page 7
1 Introduction......Page 10
 References......Page 11
 2.2 Basic Idea of FFT......Page 13
 2.3 Cooley–Tukey FFT Algorithm......Page 17
 2.5 Stockham FFT Algorithm......Page 18
  2.6.1 FFT of Two Real Data Simultaneously......Page 19
  2.6.2 n-Point Real FFT Using n/2-Point Complex FFT......Page 20
 References......Page 21
 3.1 Two-Dimensional Formulation of DFT......Page 22
 3.2 Radix-3 FFT Algorithm......Page 23
 3.4 Radix-5 FFT Algorithm......Page 24
 3.5 Radix-8 FFT Algorithm......Page 25
 References......Page 26
 4.1 Split-Radix FFT Algorithm......Page 28
 4.2 Extended Split-Radix FFT Algorithm......Page 30
 References......Page 40
 5.1 Definition of Two-Dimensional DFT......Page 41
 5.2 Two-Dimensional FFT Algorithm......Page 42
 5.4 Three-Dimensional FFT Algorithm......Page 43
 Reference......Page 46
 6.1 Four-Step FFT Algorithm......Page 47
 6.2 Five-Step FFT Algorithm......Page 49
 6.3 Six-Step FFT Algorithm......Page 50
 6.4 Blocked Six-Step FFT Algorithm......Page 52
 6.5 Nine-Step FFT Algorithm......Page 54
 6.6 Recursive Six-Step FFT Algorithm......Page 57
  6.7.2 Blocked Three-Dimensional FFT Algorithm......Page 59
  6.8.1 Introduction......Page 60
  6.8.3 Goedecker's Technique......Page 61
  6.8.4 Radix-16 FFT Algorithm......Page 62
  6.8.6 Evaluation......Page 65
  6.9.1 Introduction......Page 69
  6.9.2 Vectorization of FFT Kernels Using Intel SSE3 Instructions......Page 70
  6.9.3 Vectorization of FFT Kernels Using Intel AVX-512 Instructions......Page 71
 References......Page 72
  7.1.1 Introduction......Page 75
  7.1.2 A Recursive Three-Step FFT Algorithm......Page 76
  7.2.1 Introduction......Page 78
  7.2.2 Parallelization of Six-Step FFT......Page 79
  7.2.3 Performance Results......Page 80
 References......Page 82
  8.1.1 Parallel One-Dimensional FFT Using Block Distribution......Page 83
  8.1.2 Parallel One-Dimensional FFT Using Cyclic Distribution......Page 85
  8.1.3 Parallel Two-Dimensional FFT in Distributed-Memory Parallel Computers......Page 87
  8.1.4 Parallel Three-Dimensional FFT in Distributed-Memory Parallel Computers......Page 88
  8.2.1 Introduction......Page 89
  8.2.3 Automatic Tuning of Parallel One-Dimensional FFT......Page 90
  8.2.4 Performance Results......Page 93
  8.3.1 Introduction......Page 94
  8.3.2 Implementation of Parallel Three-Dimensional FFT Using Two-Dimensional Decomposition......Page 95
  8.3.3 Communication Time in One-Dimensional Decomposition and Two-Dimensional Decomposition......Page 98
  8.3.4 Performance Results......Page 99
  8.4.1 Introduction......Page 102
  8.4.2 Two-Step All-to-All Communication Algorithm......Page 103
  8.4.3 Communication Times of All-to-All Communication Algorithms......Page 104
  8.4.4 Performance Results......Page 105
  8.5.1 Introduction......Page 108
  8.5.2 Implementation of Parallel One-Dimensional FFT  in a GPU Cluster......Page 109
  8.5.3 Performance Results......Page 112
 References......Page 115
Index......Page 119