article

Free access

An Adaptation of the Fast Fourier Transform for Parallel Processing

Author:

Marshall C. PeaseAuthors Info & Claims

Journal of the ACM (JACM), Volume 15, Issue 2

Pages 252 - 264

https://doi.org/10.1145/321450.321457

Published: 01 April 1968 Publication History

PDF eReader

Abstract

A modified version of the Fast Fourier Transform is developed and described. This version is well adapted for use in a special-purpose computer designed for the purpose. It is shown that only three operators are needed. One operator replaces successive pairs of data points by their sums and differences. The second operator performs a fixed permutation which is an ideal shuffle of the data. The third operator permits the multiplication of a selected subset of the data by a common complex multiplier.

If, as seems reasonable, the slowest operation is the complex multiplications required, then, for reasonably sized date sets—e.g. 512 complex numbers—parallelization by the method developed should allow an increase of speed over the serial use of the Fast Fourier Transform by about two orders of magnitude.

It is suggested that a machine to realize the speed improvement indicated is quite feasible.

The analysis is based on the use of the Kronecker product of matrices. It is suggested that this form is of general use in the development and classification of various modifications and extensions of the algorithm.

References

[1]

COOLEY, J. W., LEWIS, P. A. W., AND WELCH, P. D. Historical notes on the Fast Fourier Transform. IEEE Trans. A U-15 (June 1967), 76-79.

Google Scholar

[2]

. AND TUKEY, J .W . An algorithm for the machine calculation of colnplex Fourier series. Math. Comput. 19, 90 (April 1965), 297-301.

Google Scholar

[3]

STrocKnaM, T. G., JR. High-speed convolution and correlation. Proe. AF{PS 1966 Spring Joint Comput. Conf., Vol. 28, pp. 229-233.

Google Scholar

[4]

BINGHAM, C., GODFREY, M. D., AND TUKEY, J.W. Modern techniques of Power spectruin estimation. (Unpublished.)

Google Scholar

[5]

GENTLEMAN, W. M., AND SANDE, G. Fast Fourier Transforms- for fun and profit. Proe. AFIPS 1966 Fall Joint Comput. Conf., Vol. 29, pp. 563-578.

Google Scholar

[6]

SINGLETON, R. C; A method for computing the Fast Forelet Transform with auxiliary memory and limited high-speed storage. IEEE Trans. A U-15 (June 1967), 91-97.

Google Scholar

[7]

COOLEY, J. W., LEWIS, P. A. W., AND WELCH, P.D. Application of the Fast Fourier Transform to computation of Fourier integrals, Fourier series, and convolution integrals. IEEE' Trans. A U-15 (June 1967), 79-84.

Google Scholar

[8]

HELMS, H. D. Fast Fourier Transform method of computing difference equAtions and simulating filters. IEEE .Trans. A U-i5 (June 1967), 85-90.

Google Scholar

[9]

G-AE SUHUICMMUTEE ON MEASUREMENT CONCEPTS. What is the Fast Fourier Transforms IEEE Trans. A U-I5 (June 1967), 45-55.

Google Scholar

[10]

PEASE, M.C. Melhods of Malrix Algebra. Academic Press, New York, 1965, Ch. XIV.

Google Scholar

Cited By

View all

Langhammer MConstantinides G(2024)Soft GPGPU versus IP cores: Quantifying and Reducing the Performance GapProceedings of the 14th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies10.1145/3665283.3665288(44-52)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3665283.3665288
Liu SKuo CMo YSu T(2024)An Area-Efficient, Conflict-Free, and Configurable Architecture for Accelerating NTT/INTTIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2023.333695132:3(519-529)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1109/TVLSI.2023.3336951
Brinich PJohnson J(2024)Generating Formally Verified Quantum Fourier Transform AlgorithmsIntelligent Computer Mathematics10.1007/978-3-031-66997-2_15(261-276)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-66997-2_15
Show More Cited By

Index Terms

An Adaptation of the Fast Fourier Transform for Parallel Processing

Recommendations

Split vector-radix fast Fourier transform

The split-radix approach for computing the discrete Fourier transform (DFT) is extended for the vector-radix fast Fourier transform (FFT) to two and higher dimensions. It is obtained by further splitting the ( N /2× N /2) transforms with twiddle factors ...
A New Hybrid Algorithm for Computing a Fast Discrete Fourier Transform

In this paper for certain long transform lengths, Winograd's algorithm for computing the discrete Fourier transform (DFT) is extended considerably. This is accomplisbed by performing the cyclic convolution, required by Winograd's method, with the ...
Parallel Computing for the Radix-2 Fast Fourier Transform
DCABES '14: Proceedings of the 2014 13th International Symposium on Distributed Computing and Applications to Business, Engineering and Science

The fast Fourier transform (FFT) is a speed-up technique for calculating the discrete Fourier transform (DFT), which in turn is a discrete version of the continuous Fourier transform. The Fast Fourier Transform is used in linear systems analysis, ...

Comments

Information & Contributors

Information

Published In

Journal of the ACM Volume 15, Issue 2

April 1968

175 pages

ISSN:0004-5411

EISSN:1557-735X

DOI:10.1145/321450

Issue’s Table of Contents

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 April 1968

Published in JACM Volume 15, Issue 2

Permissions

Request permissions for this article.

Request Permissions

Check for updates

Qualifiers

Article

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

305
Total Citations
View Citations
2,776
Total Downloads

Downloads (Last 12 months)367
Downloads (Last 6 weeks)44

Reflects downloads up to 22 Sep 2024

Other Metrics

View Author Metrics

Citations

Cited By

View all

Langhammer MConstantinides G(2024)Soft GPGPU versus IP cores: Quantifying and Reducing the Performance GapProceedings of the 14th International Symposium on Highly Efficient Accelerators and Reconfigurable Technologies10.1145/3665283.3665288(44-52)Online publication date: 19-Jun-2024
https://dl.acm.org/doi/10.1145/3665283.3665288
Liu SKuo CMo YSu T(2024)An Area-Efficient, Conflict-Free, and Configurable Architecture for Accelerating NTT/INTTIEEE Transactions on Very Large Scale Integration (VLSI) Systems10.1109/TVLSI.2023.333695132:3(519-529)Online publication date: 1-Mar-2024
https://dl.acm.org/doi/10.1109/TVLSI.2023.3336951
Brinich PJohnson J(2024)Generating Formally Verified Quantum Fourier Transform AlgorithmsIntelligent Computer Mathematics10.1007/978-3-031-66997-2_15(261-276)Online publication date: 5-Aug-2024
https://dl.acm.org/doi/10.1007/978-3-031-66997-2_15
Soni DNeda NZhang NReynwar BGamil HHeyman BNabeel MBadawi APolyakov YCanida KPedram MManiatakos MCousins DFranchetti FFrench MSchmidt AReagen B(2023)RPU: The Ring Processing Unit2023 IEEE International Symposium on Performance Analysis of Systems and Software (ISPASS)10.1109/ISPASS57527.2023.00034(272-282)Online publication date: Apr-2023
https://doi.org/10.1109/ISPASS57527.2023.00034
Zhang NEbel ANeda NBrinich PReynwar BSchmidt AFranusich MJohnson JReagen BFranchetti F(2023)Generating High-Performance Number Theoretic Transform Implementations for Vector Architectures2023 IEEE High Performance Extreme Computing Conference (HPEC)10.1109/HPEC58863.2023.10363559(1-7)Online publication date: 25-Sep-2023
https://doi.org/10.1109/HPEC58863.2023.10363559
Hernández ILópez J(2023)Any-Radix Efficient Fully-Parallel Implementation of the Fast Fourier Transform on FPGAs2023 38th Conference on Design of Circuits and Integrated Systems (DCIS)10.1109/DCIS58620.2023.10335987(1-6)Online publication date: 15-Nov-2023
https://doi.org/10.1109/DCIS58620.2023.10335987
Park JLee SLee J(2023)NTT-PIM: Row-Centric Architecture and Mapping for Efficient Number-Theoretic Transform on PIM2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247747(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247747
Ren XChen ZGu ZLu YZhong RLu WZhang JZhang YWu HZheng XLiu HChu THong CWei CNiu DXie Y(2023)CHAM: A Customized Homomorphic Encryption Accelerator for Fast Matrix-Vector Product2023 60th ACM/IEEE Design Automation Conference (DAC)10.1109/DAC56929.2023.10247696(1-6)Online publication date: 9-Jul-2023
https://doi.org/10.1109/DAC56929.2023.10247696
A TV Z(2022)Avoiding the bit-reversed ordering in parallel multi-digit multiplication based on FFTArtificial Intelligence10.15407/jai2022.02.06127:AI.2022.27(2)(61-70)Online publication date: 29-Dec-2022
https://doi.org/10.15407/jai2022.02.061
Vizcaino PMantovani FFerrer RLabarta J(2022)Acceleration with long vector architectures: Implementation and evaluation of the FFT kernel on NEC SX‐Aurora and RISC‐V vector extensionConcurrency and Computation: Practice and Experience10.1002/cpe.742435:20Online publication date: 2-Nov-2022
https://doi.org/10.1002/cpe.7424
Show More Cited By

View Options

View options

PDF

View or Download as a PDF file.

PDF

eReader

View online with eReader.

eReader

Get Access

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Abstract

References

Cited By

Index Terms

Recommendations

Split vector-radix fast Fourier transform

A New Hybrid Algorithm for Computing a Fast Discrete Fourier Transform

Parallel Computing for the Radix-2 Fast Fourier Transform

Comments

Information

Published In

Publisher

Publication History

Permissions

Check for updates

Qualifiers

Contributors

Other Metrics

Bibliometrics

Article Metrics

Other Metrics

Citations

Cited By

View options

PDF

eReader

Get Access

Login options

Full Access

Figures

Other

Share

Share this Publication link

Share on social media

Affiliations