Algorithms for long fast Fourier transforms on a Connection Machine

Several fast algorithms are developed for very long one- and two-dimensional fast Fourier transforms (FFTs) on the Connection Machine CM-2. These codes maximally exploit the parallelism afforded by single-instruction multiple-data (SIMD) machines like the CM-2. Explicit advantage is taken of the CM-2 hardware (32-b FPA, 8-kb memory per processor, programmable hypercube connectivity) and software (Paris machine level language) to simulate the butterfly connectivity required for the FFT computation. A central processor unit (CPU) benchmark of 4.6 s for a complex 2²¹-point FFT is established, and an execution time of about 9.5 s is predicted for 2²²-point FFTs on a 16 K-processor CM-2. Longer FFTs, with lengths of at least 2²⁴ points, are possible on a full 64 K processor CM with no increase in CPU time. Also described are algorithms for use on Connection Machines for achieving coherence recovery of frequency-broadened signals