G - Physics – 06 – F
Patent
G - Physics
06
F
G06F 17/14 (2006.01) G06F 12/08 (2006.01) H05K 7/20 (2006.01)
Patent
CA 2437036
The present 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(100) comprising a plurality of nodes(Q11-Q33) in communication over a network, comprising distributing the plurali ty 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 facilitated efficient utilization of the network thereby efficiently implementing the multidimensional FFT. The "all-to-all" re- distribution of the array elements is further efficiently implemented in applications other that the multidimensional FFT on the distributed-memory parallel supercomputer.
La présente invention concerne un procédé, un système et un dispositif de stockage de programme visant à exécuter de manière efficace une transformée de Fourier rapide (FFT) d'un réseau multidimensionnel comprenant une pluralité d'éléments initialement distribués dans un système informatique multinodal comprenant une pluralité de noeuds en communication sur un réseau, ledit procédé consistant à distribuer la pluralité d'éléments du réseau dans une première dimension dans la pluralité de noeuds du système informatique sur le réseau afin de faciliter une première FFT unidimensionnelle ; à exécuter la première FFT unidimensionnelle sur les éléments du réseau distribués au niveau de chaque noeud dans la première dimension ; à redistribuer les éléments transformés par la FFT unidimensionnelle au niveau de chaque noeud dans une seconde dimension par l'intermédiaire d'un distribution <=tout-tout>= en ordre aléatoire dans d'autres noeuds du système informatique sur le réseau ; et à exécuter une seconde FFT unidimensionnelle sur les éléments du réseau redistribués au niveau de chaque noeud dans la seconde dimnension, l'ordre aléatoire facilitant l'utilisation efficace du réseau, et permettant ainsi d'exécuter de manière efficace la FFT multidimensionnelle. La redistribution <=tout-tout>= deséléments du réseau est également exécutée de manière efficace dans des applications autres que la FFT multidimensionnelle sur un superordinateur parallèle à mémoire distribuée.
Bhanot Gyan V.
Chen Dong
Gara Alan G.
Giampapa Mark E.
Heidelberger Philip
International Business Machines Corporation
Wang Peter
LandOfFree
Efficient implementation of a multidimensional fast fourier... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Efficient implementation of a multidimensional fast fourier..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Efficient implementation of a multidimensional fast fourier... will most certainly appreciate the feedback.
Profile ID: LFCA-PAI-O-1570518