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