Parallel Fast Fourier Transform I
Embedded Files
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 11: Parallel Fast Fourier Transform I
This topic transitions to the Parallel FFT, starting with a necessary review of the sequential Cooley-Tukey algorithm and the structure of the butterfly computation, which forms the basis for parallel formulation. The primary focus is on mapping the butterfly network onto standard parallel architectures (like the Hypercube or Shuffle-Exchange) and analyzing the resulting communication patterns and complexity.
Learning Outcomes
Learning Outcomes
The recursive decomposition and butterfly computation of the Cooley–Tukey FFT algorithm are understood, and their effects on arithmetic complexity and memory access are analyzed.
The data-transposition approach for parallel FFT is explained, and its mapping to processor topologies such as hypercube and shuffle–exchange networks is evaluated.
The α–β communication model is applied to analyze the communication cost and scalability of distributed FFT implementations.
Topic Outline
Topic Outline
Handout: Parallel Fast Fourier Transform I*
When Time Becomes Frequency
Sequential FFT Background
The Butterfly: Sequential Core
Memory Access and Locality
Parallel Formulation of FFT
Data Transposition and Network Mapping
Communication Cost and Topology
From Transformation to Communication
Note: Links marked with an asterisk (*) lead to materials accessible only to members of the University community. Please log in with your official University account to view them.
Readings
Readings
Original Cooley–Tukey FFT Algorithm
Cooley, J. W., & Tukey, J. W. (1965). An algorithm for the machine calculation of complex Fourier series. Mathematics of computation, 19(90), 297–301.
Parallel FFT on Hypercubes and Network Mapping
Schwartz, S. D., & Shar, L. E. (1988). A survey of parallel algorithms for the fast Fourier transform. IEEE Transactions on Acoustics, Speech, and Signal Processing, 36(9), 1423–1436.
Comprehensive Parallel FFT Analysis and Cost Modeling
Grama, A., Gupta, A., Karypis, G., & Kumar, V. (2003). Introduction to parallel computing. Addison-Wesley.
Access Note: Published research articles and books are linked to their respective sources. Some materials are freely accessible within the University network or when logged in with official University credentials. Others will be provided to enrolled students through the class learning management system (LMS).
::: Home > Instruction > CMSC 280: Parallel Processing > Topic 11: Parallel Fast Fourier Transform I
Page updated
Report abuse