Efficient Complex Multiplication and Fast Fourier Transform (FFT) Implementation on the ManArray Architecture
AssigneeAltera Corporation
InventorsNikos P. Pitsianis, Gerald George Pechanek, Ricardo Rodriguez
Life of this patent
Estimating the term…
Abstract
Efficient computation of complex multiplication results and very efficient fast Fourier transforms (FFTs) are provided. A parallel array VLIW digital signal processor is employed along with specialized complex multiplication instructions and communication operations between the processing elements which are overlapped with computation to provide very high performance operation. Successive iterations of a loop of tightly packed VLIWs are used allowing the complex multiplication pipeline hardware to be efficiently used. In addition, efficient techniques for supporting combined multiply accumulate operations are described.
Claims20
A method for calculating a distributed Fast Fourier Transform (FFT) on an array of processing elements (PEs), the method comprising:
- loading complex numbers and twiddle factor values in each PE;
- executing multiply complex instructions in each PE to multiply a loaded complex number with an associated and loaded twiddle factor value to produce complex results in each PE;
- and
- communicating the complex results between the PEs overlapped with operations on local values and previously communicated results in each PE to generate an FFT result distributed on the array of PEs.
An apparatus for calculating a distributed Fast Fourier Transform (FFT) on an array of processing elements (PEs), the apparatus comprising:
- a plurality of data memories, each data memory storing complex numbers and twiddle factor values;
- a plurality of PEs, each PE associated with a data memory from the plurality of data memories, and each PE configured to load a complex number and associated twiddle factor value as a second complex number to each PE from the associated data memory and each PE having an associated multiply complex execution unit configured for multiplying the loaded complex number with the loaded associated twiddle factor value to produce a complex result in each PE;
- and
- an interconnection network having hypercube connection paths between PEs and each PE selecting a hypercube connection path to communicate the complex result between PEs, wherein the communication of the complex result is overlapped with operations in each PE and each PE generates an FFT result distributed on the plurality of PEs.
A method for calculating a distributed Fast Fourier Transform (FFT) on an array of processing elements (PEs), the method comprising:
- fetching a first complex number and a second complex number in each PE;
- executing multiply complex instructions in each PE to multiply the first complex number with the second complex number to produce complex results in each PE;
- and
- communicating the complex results between the PEs over hypercube connection paths overlapped with operations on local values and previously communicated results in each PE to generate an FFT result distributed on the array of PEs.
Dependencies are inferred from the claim text.