Fast computation of general fourier transforms on graphics processing units

摘要

Described is a technology for use with general discrete Fourier transforms (DFTs) performed on a graphics processing unit (GPU). The technology is implemented in a general library accessed through GPU-independent APIs. The library handles complex and real data of any size, including for non-power-of-two data sizes. In one implementation, the radix-2 Stockham formulation of the fast Fourier transform (FFT) is used to avoid computationally expensive bit reversals. For non-power of two data sizes, a Bluestein z-chirp algorithm may be used.

主权项

1. In a computing environment that includes a programmable graphics processing unit, a method comprising:
receiving arbitrary-sized data including data comprising a sequence of numbers having a length that is a non-power of two and another sequence of numbers; evaluating how to compute discrete Fourier transforms on the graphics processing unit based upon a format of the data; determining whether the data is real-valued; and if the data is real-valued, packing elements of the sequence into a complex sequence, running at least some of the discrete Fourier transforms in parallel, and returning the computed discrete Fourier transforms, wherein when the sequence is one-dimensional and further comprising when a one-dimensional length is even, packing together even and odd elements of the sequence into packed data that comprises components of the complex sequence, performing the fast Fourier transforms on the packed data, and unpacking the packed data, or when the one-dimensional length is odd, packing together elements of the sequence and elements of the other sequence into a packed sequence that comprises components of the complex sequence, including if the data comprises an odd number of sequences, adding an extra sequence of zeros to make an even number of sequences, and performing the fast Fourier transforms on the packed sequence.