Fast Fourier Transform Using a Distributed Computing System

A non-transitory computer-readable medium having instructions stored thereon that are executable to perform a Fast Fourier Transform (FFT) by a computing system that includes a plurality of processing nodes, wherein each of the plurality of processing nodes includes a respective local memory and a respective local network interface (NI), wherein the plurality of processing nodes are configured to communicatively couple to a network via the NIs, wherein the instructions are executable to perform operations comprising:

• storing different portions of an input sequence for the FFT in the local memories such that the input sequence is distributed among the local memories;
• performing, by each of the processing nodes, one or more first local FFTs on the portion of the input sequence stored in its respective local memory;
• sending, by each of the processing nodes, results of the one or more first local FFTs to its respective local NI using first packets addressed to different ones of a plurality of registers included in the local NI;
• transmitting, by each of the local NIs, the results of the one or more first local FFTs to remote NIs using second packets, wherein the second packets are addressed based on addresses stored in the different ones of the plurality of registers;
• aggregating, by each of the local NIs, received packets addressed to the local NI by remote NIs and storing the results of the aggregated packets in the respective local memories;
• performing, by each of the processing nodes, one or more second local FFTs on the results stored in its respective local memory;
• and
• providing an FFT result based on the one or more second local FFTs.

A method for data processing using a system comprising a plurality of processing nodes, wherein each of the plurality of processing nodes includes a respective local memory and a respective local network interface (NI), wherein the plurality of processing nodes are configured to communicatively couple to a network via the NIs, the method comprising:

• storing different portions of input data in the local memories such that the input data is distributed among the local memories;
• performing, by each of the processing nodes, one or more first operations on at least a subset of the portion of the input data stored in its respective local memory;
• sending, by each of the processing nodes, results of the one or more first operations to its respective local NI using first packets addressed to different ones of a plurality of registers included in the local NI;
• transmitting, by each of the local NIs, the results of the one or more first operations to remote NIs using second packets, wherein the second packets are addressed based on addresses stored in the different ones of the plurality of registers;
• aggregating, by each of the local NIs, received packets addressed to the local NI by remote NIs and storing the aggregated packets in the respective local memories;
• and
• iteratively performing the transmitting and aggregating a plurality of times, using the same addresses stored in the different ones of the plurality of registers for each iteration, wherein the storing the aggregated packets for each iteration is performed to a location that is determined based on a count of a current number of performed iterations.