Fast computation of general fourier transforms on graphics processing units

Abstract

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.

What is claimed is: 
     
         1 . An apparatus, comprising:
 a programmable graphics processing unit (GPU);   logic for a discrete Fourier transform library operative on the GPU to:
 receive input data; 
 determine that the input data comprises sequences of which a numerical sequence corresponds to a length that is a non-power of two; 
 determine whether the input data is real-valued, and if so, packing elements of the numerical sequence into a complex sequence; 
 concatenate the sequences of the input data; and 
 wrap the concatenated sequences into a texture as a wrapped representation when at least one of the sequences exceeds a maximum texture dimension and computing Fourier transforms on the wrapped representation. 
   
     
     
         2 . The apparatus of  claim 1 , the logic further operative to compute logical indexes based on physical addresses in the texture. 
     
     
         3 . The apparatus of  claim 1 , the logic further operative to run a discrete fast Fourier transform. 
     
     
         4 . The apparatus of  claim 1 , the logic further operative to perform one or more iterations of the one or more appropriate Fast Fourier transforms on the input data. 
     
     
         5 . The apparatus of  claim 1 , the logic further operative to remove numerical imprecision corresponding to the input data. 
     
     
         6 . The apparatus of  claim 1 , the logic further operative to determine that the input data corresponds to a length that is a non-power of two and perform a convolution via a Fast Fourier transform, wherein the logic is further configured to run the fast Fourier transform on two sequences computed from the input data by computing a dot product of the transformed data, run an inverse fast Fourier transform on the result of the dot product computation, multiply a result of the inverse fast Fourier transform with a conjugate of a second sequence of the complex sequence, and output a result corresponding to the conjugate. 
     
     
         7 . The apparatus of  claim 1 , wherein a total number of elements in the fast Fourier transform is less than or equal to a number of elements in a largest allocatable texture on the programmable graphics processing unit and wherein the largest allocatable texture is swizzled in memory coupled to the GPU. 
     
     
         8 . The apparatus of  claim 1 , the logic further operative to perform at least one computation on a CPU where double precision is implemented. 
     
     
         9 . In a computing environment that includes a programmable graphics processing unit, a method comprising:
 receiving input data;   determining that the input data comprises sequences of which a numerical sequence corresponds to a length that is a non-power of two;   determining whether the input data is real-valued, and if so, packing elements of the numerical sequence into a complex sequence;   concatenating the sequences of the input data; and   wrapping the concatenated sequences into a texture as a wrapped representation when at least one of the sequences exceeds a maximum texture dimension and computing Fourier transforms on the wrapped representation.   
     
     
         10 . The method of  claim 9 , wherein the input data comprises arbitrary-sized data including the numerical sequence. 
     
     
         11 . The method of  claim 9  further comprising running at least some of the Fourier transforms in parallel and returning the computed Fourier transforms. 
     
     
         12 . The method of  claim 11  wherein running at least some of the discrete Fourier transforms in parallel further comprises using a fast Fourier transform based on a radix-2 Stockham formulation. 
     
     
         13 . The method of  claim 9 , wherein when the numerical sequence is one-dimensional and a one-dimensional length is even, packing together even and odd elements of the numerical 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. 
     
     
         14 . The method of  claim 9  wherein when the input data is two-dimensional and a length along at least one of the dimensions is even, packing together even and odd elements into packed data, performing two-dimensional fast Fourier transforms on the packed data, and unpacking the packed data. 
     
     
         15 . The method of  claim 9  wherein when the input data is two-dimensional and the length along both dimensions is odd, packing consecutive pairs of sequences of the data in one dimension, performing the fast Fourier transforms along the packed consecutive sequences of the data, unpacking the packed consecutive sequences into a partially unpacked set, performing the fast Fourier transforms on columns of this set into a partial result, and reflecting and conjugating the partial result. 
     
     
         16 . The method of  claim 9  further comprising, performing a convolution to compute the discrete Fourier transform by performing a fast Fourier transform on two sets of data elements that comprise the data, performing a dot product on the two sets of data elements, and performing an inverse fast Fourier transform on a result of the dot product. 
     
     
         17 . The method of  claim 16  further comprising padding a first set of data elements and a second set of data elements each to a size corresponding to a power of two. 
     
     
         18 . The method of  claim 17  further comprising moving data corresponding to negative indices to a position in an array in which the indices are non-negative. 
     
     
         19 . One or more computer-readable storage media having computer-executable instructions, which when executed perform steps, comprising:
 receiving input data;   determining that the input data comprises sequences of which a numerical sequence corresponds to a length that is a non-power of two;   determining whether the input data is real-valued, and if so, packing elements of the numerical sequence into a complex sequence;   concatenating the sequences of the input data; and   wrapping the concatenated sequences into a texture as a wrapped representation when at least one of the sequences exceeds a maximum texture dimension and computing Fourier transforms on the wrapped representation.   
     
     
         20 . The method of  claim 1  further comprising computing Fourier transforms on the wrapped representation by computing logical indexes based on physical addresses in the texture.