A generalized algorithm has been derived for the execution of the Cooley-Tukey FFT algorithm on a distributed memory machine. This algorithm is based on an approach that combines a large number of butterfly operations into one large process per processor. The performance can be predicted from theory. The actual algorithm has been implemented on a transputer array, and the performance of the implementation has been measured for various sizes of the complex input vector. It is shown that the algorithm scales linearly with the number of transputers and the problem size.
|Title of host publication||Transputer research and applications 4|
|Subtitle of host publication||NATUG-4, proceedings of the Fourth Conference of the North American Transputer Users Group, October 11-12, 1990, Ithaca, NY|
|Editors||Daniel L. Fielding|
|Place of Publication||Amsterdam|
|Number of pages||0|
|Publication status||Published - 1 Sep 1990|
|Event||4th North American Transputer User Group Meeting, NATUG 1990 - Ithaca, United States|
Duration: 11 Oct 1990 → 12 Oct 1990
Conference number: 4
|Name||Transputer and occam engineering series|
|Conference||4th North American Transputer User Group Meeting, NATUG 1990|
|Period||11/10/90 → 12/10/90|
Roebbers, H. W., Welch, P. H., & Wijbrans, K. C. J. (1990). A generalized FFT algorithm on transputers. In D. L. Fielding (Ed.), Transputer research and applications 4: NATUG-4, proceedings of the Fourth Conference of the North American Transputer Users Group, October 11-12, 1990, Ithaca, NY (Transputer and occam engineering series). Amsterdam: IOS Press.