Skip to Content
Find More Like This
Return to Search

Efficient implementation of a multidimensional fast fourier transform on a distributed-memory parallel multi-node computer

United States Patent

January 1, 2008
View the Complete Patent at the US Patent & Trademark Office
Lawrence Livermore National Laboratory - Visit the Industrial Partnerships Office Website
The present in invention is directed to a method, system and program storage device for efficiently implementing a multidimensional Fast Fourier Transform (FFT) of a multidimensional array comprising a plurality of elements initially distributed in a multi-node computer system comprising a plurality of nodes in communication over a network, comprising: distributing the plurality of elements of the array in a first dimension across the plurality of nodes of the computer system over the network to facilitate a first one-dimensional FFT; performing the first one-dimensional FFT on the elements of the array distributed at each node in the first dimension; re-distributing the one-dimensional FFT-transformed elements at each node in a second dimension via "all-to-all" distribution in random order across other nodes of the computer system over the network; and performing a second one-dimensional FFT on elements of the array re-distributed at each node in the second dimension, wherein the random order facilitates efficient utilization of the network thereby efficiently implementing the multidimensional FFT. The "all-to-all" re-distribution of array elements is further efficiently implemented in applications other than the multidimensional FFT on the distributed-memory parallel supercomputer.
Bhanot; Gyan V. (Princeton, NJ), Chen; Dong (Croton-On-Hudson, NY), Gara; Alan G. (Mount Kisco, NY), Giampapa; Mark E. (Irvington, NY), Heidelberger; Philip (Cortlandt Manor, NY), Steinmacher-Burow; Burkhard D. (Mount Kisco, NY), Vranas; Pavlos M. (Bedford Hills, NY)
International Business Machines Corporation (Armonk, NY)
10/ 468,998
February 25, 2002
This invention was made with Government support under subcontract number B517552 under prime contract number W-7405-ENG-48 awarded by the Department of Energy. The Government has certain rights in this invention.