Go to the first, previous, next, last section, table of contents.
Ce manuel documente la version 2.1.3 de FFTW, la Fastest Fourier Transform in the West. FFTW est une collection complète de routines C pour calculer les transformées discrètes de Fourier (DFT) pour une ou plusieurs dimensions de données réelles ou complexes et de taille d'entrée arbitraire. FFTW inclus aussi des transformées parallèles pour les systèmes de mémoire partagés et distribués. Nous supposons ici que le lecteur est déjà familier avec les propriétés et l'utilisation de la DFT qui sont associés à son application. Sinon, consultez e.g. The Fast Fourier Transform par E. O. Brigham (Prentice-Hall, Englewood Cliffs, NJ, 1974). Notre page web a aussi des liens sur des informations à propos de FFT en ligne.
FFTW est réellement plus rapide (et quelquefois beaucoup plus rapide) que tous les autres programmes de transformée de Fourier disponibles librement sur le Net. Pour les transformées dont la taille est une puissance de deux, elles se comparent favorablement avec les codes FFT de la Bibliothèque Performance de Sun et la bibliothèque ESSL d'IBM qui sont déstinées pour des machines spécifiques. De plus, les performances de FFTW sont portables. En effet, FFTW est unique dans le sens où il s'adapte automatiquement à votre machine votre cache, la taille de mémoire, le nombre de registres et tous les autres facteurs qui rendent normalement l'optimisation impossible d'un programme pour plus d'une machine. Une comparaison extensive des performances de FFTW avec les autres codes pour transformées de Fourier a été réalisée. Les résultats sont disponibles sur le Web sur la page benchFFT.
De manière à utiliser FFTW efficacement, vous avez besoin de connaître un des concepts de base de la structure interne de FFTW. Il n'utilise pas un algorithme fixé pour le calcul de la transformée mais il adapte l'algorithme DFT aux détails du matériel sous-jacent de manière à réaliser les meilleures performances. C'est pourquoi la transformée est séparée en deux phases. En premier la planification FFTW est appelée, qui "apprend" le meilleur chemin pour calculer la transformée sur votre machine. La planification produit une structure de donnée appelée un plan qui contient cette information. Postérieurement, le plan est passé dans l'executor FFTW avec un tableau de données d'entrée. L'éxécuteur calcule la transformée réelle, comme indiqué par le plan. Le plan peut être réutilisé autant de fois que nécessaire. Dans les applications hautes performances typiques, plusieurs transformées de la même taille sont calculées et, par conséquent, une initialisation relativement dépensière en temps est acceptable pour le tri. D'un autre coté, si vous avez besoin d'une transformée simple d'une taille donnée, le coût unique de la planification devient significatif. Pour ce cas, FFTW fournit des planificateurs plus rapides basés sur l'heuristique ou sur les plans déjà calculés.
Le motif de la planification/exécution s'applique aux quatre modes opératoires de FFTW, qui sont, I)transformée complexe à une dimension (FFTW), II) transformée complexe multi dimension (FFTWND), III) transformée de données réelles une dimension (RFFTW), IV) transformée de données réelles multi dimension (RFFTWND). Chaque mode est fourni avec son propre plan et exécuteur.
En plus de l'adaptation automatique de la performance effectué par le planificateur, il est aussi possible des les utilisateurs avancés de personaliser FFTW pour leurs besoins spéciaux. Distribué, FFTW travaille plus efficacement pour les tableaux dont les tailles peuvent être factorisées dans des petits premiers (2, 3, 5, et 7), et utilise une routine lente générale pour les autres facteurs. FFTW, néanmoins, arrive avec un générateur de code qui peut produire des programmes C rapides pour toute taille de tableau que vous devez traiter. Par exemple, si vous avez besoin d'une transformée de taille 513 = 19*33, vous pouvez personnaliser FFTW pour supporter le facteur 19 efficacement.
FFTW peut exploiter de multiples procésseurs si vous en avez. FFTW respecte l'implémentation de mémoire partagée pour les threads POSIX (et similaires),de même que l'implémentation de mémoire distribuée basée sur MPI. Nous fournissons aussi une implémentaion expérimentale parallèle écrite en Cilk, the superior programming tool of choice for discriminating hackers (Olin Shivers). (Voir la page d'accueil Cilk.)
Pour plus d'informations à propos de FFTW, consultez l'article, "The Fastest Fourier Transform in the West," by M. Frigo and S. G. Johnson, qui est le rapport technique MIT-LCS-TR-728 (Sep. '97). Vous pouvez voir aussi, "FFTW: An Adaptive Software Architecture for the FFT," by M. Frigo and S. G. Johnson, qui est apparu dans la 23rd International Conference on Acoustics, Speech, and Signal Processing (Proc. ICASSP 1998 3, p. 1381). Le générateur de code est décrit dans l'article "A Fast Fourier Transform Compiler", par M. Frigo, à parraitre dans le Proceedings of the 1999 ACM SIGPLAN Conference on Programming Language Design and Implementation (PLDI), Atlanta, Georgia, May 1999. Ces articles, ainsi que les dernières versions de FFTW, la FAQ, les benchmarks, et autres liens sont disponibles sur la page d'accueil FFTW. La version actuelle de FFTW incorpore plusieurs bonnes idées provenant des trente dernières années de la litérature FFT. D'une manière ou d'une autre, FFTW utilise l'algorithme de Cooley-Tukey, l'algorithme des Facteurs Premiers, l'algorithme de Rader pour les tailles des nombres premiers et l'algorithme (((((((((split-radix)))))))))) (avec une variation dûe à Dan Bernstein). Notre générateur de code produit aussi de nouveaux algorithmes que nous n'avons pas encore complètement compris. Le lecteur est renvoyé aux différents articles pour des références appropriées.
Le reste de ce manuel est organisé comme suit. Nous partons de l'implémentation séquentielle (un processeur). Nous commençons par décrire les possibilités de base de FFTW dans la Section Formation. Cette discussion inclu le schéma de stockage des tableaux multi dimension (Section Format des Tableaux Multi dimension) et le mécanisme de FFTW pour stocker les plans sur le disque (Section Mots de Sagesse). Ensuite, la Section Référence FFTW fournit une documentation compréhensible de toutes les possibilités de FFTW. Les transformées parallèles sont expliquées dans leur propre chapitre Section FFTW Parallèle. Les programmeurs Fortran peuvent aussi utiliser FFTW, comme décrit dans la Section Appeler FFTW à partir de Fortran. La Section Installation et Personnalisation explique comment installer FFTW sur votre ordinateur et comment adapter FFTW à vos besoins. Les informations de license et copyright sont données dans la Section License et Copyright. Finallement, nous remercions toutes les personnes qui nous ont aidé dans la Section Remerciements.
Go to the first, previous, next, last section, table of contents.