Fast Fourier Transform: Parallel Computing |
|
Ocius Technologies has developed a new algorithm (FFTpc) for fast filtering using a parallel implementation of the FFT that quickly separates data into streams that remain completely independent throughout the standard three-step convolution process. Parallel computing can enable massive speedups for many algorithms, and our parallel FFT could potentially achieve speedups 10 times faster than the standard computational methods. This can be applied to convolutional operations used for basic filtering of either signals or images, convolutional neural networks, and Orthogonal Frequency Division Multiplexing (OFDM) for communications.
The Advantages of Parallel FFT
- The effective speedup in computation is dependent on the number of processors available, but for vector input size of 1,024 or higher, we expect a speedup of up to 10 times.
- Our new parallel FFT contains NO complex multiplications. Contrary to most FFT algorithms, there are no butterfly operations that mix the real and imaginary parts of a complex vector together under multiplication. Only in the final output step does real input become complex valued with the correct magnitude of the standard FFT.
- If the user chooses to omit the final complex multiplications where the output has the correct magnitude, the underlying basis functions are still orthogonal. This means that OFDM can be done with only a ”magnitude correct” FFT instead of the traditional FFT.
- Complex-valued input can be immediately split into real and imaginary parts and processed in parallel, with the output of each parallel stream simply summed together. This immediately provides a 2x speedup.
- These ideas extend to FFT computations for images. For example, the FFT of a 2D rectangular image can be processed in parallel, similarly to the 1D FFT for signals.
Additional Information Available Soon. Please Contact Us With Inquiries.