Efficient Complex Multiplication and Fast Fourier Transform (FFT) Implementation on the ManArray Architecture

An apparatus for the efficient processing of an FFT on an array processor, the apparatus comprising:

• a plurality of P processing elements (PEs), each PE having a data memory storing a subset of input data, a very long instruction word (VLIW) memory holding multiply complex instructions in one or more VLIWs, a multiply complex execution unit for executing a multiply complex instruction to multiply two complex number input operands both of a first format to form a complex number result having the same format as the first format, an instruction port, and a data port;
• an interconnection network coupled to the data port of each PE along hypercube data paths between the PEs;
• and
• a control processor causing a sequence of instructions to be fetched and distributed to the instruction port of each of the PEs to calculate an FFT of size T on input data, whereby the sequence of instructions selects a sequence of VLIWs to be fetched from the VLIW memory in each PE causing the execution of the multiply complex instructions on each PE to calculate a local FFT on the subset of input data, whereby P local FFTs are calculated, and to calculate T/P distributed FFTs on the results of the P local FFTs using data communicated between PEs along the hypercube data paths, whereby the FFT of size T is calculated on the input data.

A method for the efficient processing of an FFT on an array processor of P processing elements (PEs) that are connected by hypercube datapaths, the method comprising:

• loading a set of instructions in one or more VLIWs in each PE to be used in a software pipeline;
• executing the one or more VLIWs in a software pipeline, the software pipeline in each PE comprising:
• loading from a local PE data memory complex input data and twiddle factor values formatted with a first format;
• and
• calculating the mathematical operation (FP{circle around (x)}IT/P)DP,T/P, wherein DP,T/P is a matrix of twiddle factors for scaling local data on each PE, (IT/P) is a (T/P)×(T/P) identity matrix, (Fp) is an FFT of length P, and {circle around (x)} is a symbol for a Kronecker product of two matrices, wherein the mathematical operation includes use of multiply complex instructions and PE exchange instructions for communicating between hypercube neighbor PEs along the hypercube datapaths, the multiply complex instructions and the PE exchange instructions selected for execution in parallel from the one or more VLIWs.

An apparatus for the efficient processing of an FFT on an array processor comprising:

• a plurality of P processing elements (PEs), each PE having a multiply complex execution unit configured for executing multiply complex instructions and generating a complex number result for each execution of a multiply complex instruction, the complex number result used directly as a complex numbers input for a subsequent instruction;
• a plurality of P data memories, each data memory coupled with a corresponding PE and storing a subset of input data associated with each PE;
• an interconnection network coupling each of the PEs configured for communicating data between pairs of PEs in parallel along hypercube couplings;
• a very long instruction word (VLIW) memory associated with each PE configured for storing VLIWs having one or more multiply complex instructions for individual selection and execution to process the input data according to an FFT program;
• and
• a controller sequence processor (SP) coupled to each of the PEs by an instruction bus for distributing PE instructions to the PEs according to the FFT program, wherein local FFTs maybe calculated on each PE and distributed FFTs may be calculated on the array processor to efficiently calculate an FFT.