Kim, J. S. and Fox, G. C. and Aloisio, G. and Veneziani, M. (1988) The prime factor non-binary discrete Fourier transform and use of Crystal_Router as a general purpose communication routine. In: Proceedings of the third conference on Hypercube concurrent computers and applications (C^3P). Vol.2. ACM , New York, NY, pp. 1322-1327. ISBN 0-89791-278-0. https://resolver.caltech.edu/CaltechAUTHORS:20160415-104349160
Full text is not posted in this repository. Consult Related URLs below.
Use this Persistent URL to link to this item: https://resolver.caltech.edu/CaltechAUTHORS:20160415-104349160
Abstract
We have implemented one of the Fast Fourier Transform algorithms, the Prime Factor algorithm (PFA), on the hypercube. On sequential computers, the PFA and other discrete Fourier transforms (DFT) such as the Winograd algorithm (WFA) are known to be very efficient. However, both algorithms require full data shuffling and are thus challenging to any distributed memory parallel computers. We use a concurrent communication algorithm, called the Crystal_Router for communicating shuffled data. We will show that the speed gained in reduced arithmetic compared to binary FFT is sufficient to overcome the extra communication requirement up to a certain number of processors. Beyond this point the standard Cooley-Tukey FFT algorithm has the best performance. We comment briefly on the application of the DFT to signal processing in synthetic aperture radar (SAR).
Item Type: | Book Section | ||||||||||||
---|---|---|---|---|---|---|---|---|---|---|---|---|---|
Related URLs: |
| ||||||||||||
Additional Information: | © 1988 ACM. This work was supported in part by DOE grant DE-FG-03-85ER25009, Parsons and System Development Foundations, the office of the program manager of the Joint Tactical Fusion Office, and by the Italian National Space Plan grant PSN-87-04/AF-04. | ||||||||||||
Funders: |
| ||||||||||||
DOI: | 10.1145/63047.63087 | ||||||||||||
Record Number: | CaltechAUTHORS:20160415-104349160 | ||||||||||||
Persistent URL: | https://resolver.caltech.edu/CaltechAUTHORS:20160415-104349160 | ||||||||||||
Official Citation: | G. Aloisio, N. Veneziani, J. S. Kim, and G. C. Fox. 1989. The prime factor non-binary discrete Fourier transform and use of Crystal_Router as a general purpose communication routine. In Proceedings of the third conference on Hypercube concurrent computers and applications - Volume 2 (C3P), Geoffrey Fox (Ed.), Vol. 2. ACM, New York, NY, USA, 1322-1327. DOI=http://dx.doi.org/10.1145/63047.63087 | ||||||||||||
Usage Policy: | No commercial reproduction, distribution, display or performance rights in this work are provided. | ||||||||||||
ID Code: | 66219 | ||||||||||||
Collection: | CaltechAUTHORS | ||||||||||||
Deposited By: | Kristin Buxton | ||||||||||||
Deposited On: | 15 Apr 2016 18:13 | ||||||||||||
Last Modified: | 10 Nov 2021 23:54 |
Repository Staff Only: item control page