36 votes

FFTW vs Matlab FFT

J'ai posté ceci sur matlab central, mais n'a pas obtenu toutes les réponses alors j'ai pensé reposter ici.

J'ai récemment écrit un simple routine Matlab qui utilise une FFT dans une boucle for; la FFT domine les calculs. J'ai écrit la même routine mex juste pour fins d'expérimentation et il appelle la FFTW 3.3 de la bibliothèque. Il s'avère que la routine matlab court plus vite que le mex routine pour les tableaux de très grande taille (environ deux fois plus rapide). Le mex routine utilise la sagesse et de la et effectue les mêmes calculs de FFT. Je sais aussi matlab utilise FFTW, mais est-il possible que leur version est un peu plus optimisé? J'ai même utilisé le FFTW_EXHAUSTIVE drapeau et de son encore environ deux fois plus lent pour les grands tableaux de l'MATLAB homologue. En outre, j'ai assuré la matlab que j'ai utilisé était mono-thread avec le "-singleCompThread" drapeau et le mex fichier que j'ai utilisé n'était pas en mode debug. Juste curieux de savoir si c'était le cas ou si il y a quelques optimisations à l'aide de matlab est sous le capot que je ne sais pas sur. Merci.

Voici le mex partie:

void class_cg_toeplitz::analysis() {
// This method computes CG iterations using FFTs
    // Check for wisdom
    if(fftw_import_wisdom_from_filename("cd.wis") == 0) {
        mexPrintf("wisdom not loaded.\n");
    } else {
        mexPrintf("wisdom loaded.\n");
    }

    // Set FFTW Plan - use interleaved FFTW
    fftw_plan plan_forward_d_buffer;    
    fftw_plan plan_forward_A_vec;       
    fftw_plan plan_backward_Ad_buffer;
    fftw_complex *A_vec_fft;
    fftw_complex *d_buffer_fft;
    A_vec_fft = fftw_alloc_complex(n);
    d_buffer_fft = fftw_alloc_complex(n);

    // CREATE MASTER PLAN - Do this on an empty vector as creating a plane 
    // with FFTW_MEASURE will erase the contents; 
    // Use d_buffer
    // This is somewhat dangerous because Ad_buffer is a vector; but it does not
    // get resized so &Ad_buffer[0] should work
    plan_forward_d_buffer = fftw_plan_dft_r2c_1d(d_buffer.size(),&d_buffer[0],d_buffer_fft,FFTW_EXHAUSTIVE);
    plan_forward_A_vec = fftw_plan_dft_r2c_1d(A_vec.height,A_vec.value,A_vec_fft,FFTW_WISDOM_ONLY);
    // A_vec_fft.*d_buffer_fft will overwrite d_buffer_fft
    plan_backward_Ad_buffer = fftw_plan_dft_c2r_1d(Ad_buffer.size(),d_buffer_fft,&Ad_buffer[0],FFTW_EXHAUSTIVE);

    // Get A_vec_fft
    fftw_execute(plan_forward_A_vec);

    // Find initial direction - this is the initial residual
    for (int i=0;i<n;i++) {
        d_buffer[i] = b.value[i];
        r_buffer[i] = b.value[i];
    }    

    // Start CG iterations
    norm_ro = norm(r_buffer);
    double fft_reduction = (double)Ad_buffer.size(); // Must divide by size of vector because inverse FFT does not do this
    while (norm(r_buffer)/norm_ro > relativeresidual_cutoff) {        
        // Find Ad - use fft
        fftw_execute(plan_forward_d_buffer);    
        // Get A_vec_fft.*fft(d) - A_vec_fft is only real, but d_buffer_fft
        // has complex elements; Overwrite d_buffer_fft        
        for (int i=0;i<n;i++) {
            d_buffer_fft[i][0] = d_buffer_fft[i][0]*A_vec_fft[i][0]/fft_reduction;
            d_buffer_fft[i][1] = d_buffer_fft[i][1]*A_vec_fft[i][0]/fft_reduction;
        }        
        fftw_execute(plan_backward_Ad_buffer); 

        // Calculate r'*r
        rtr_buffer = 0;
        for (int i=0;i<n;i++) {
            rtr_buffer = rtr_buffer + r_buffer[i]*r_buffer[i];
        }    

        // Calculate alpha
        alpha = 0;
        for (int i=0;i<n;i++) {
            alpha = alpha + d_buffer[i]*Ad_buffer[i];
        }    
        alpha = rtr_buffer/alpha;

        // Calculate new x
        for (int i=0;i<n;i++) {
            x[i] = x[i] + alpha*d_buffer[i];
        }   

        // Calculate new residual
        for (int i=0;i<n;i++) {
            r_buffer[i] = r_buffer[i] - alpha*Ad_buffer[i];
        }   

        // Calculate beta
        beta = 0;
        for (int i=0;i<n;i++) {
            beta = beta + r_buffer[i]*r_buffer[i];
        }  
        beta = beta/rtr_buffer;

        // Calculate new direction vector
        for (int i=0;i<n;i++) {
            d_buffer[i] = r_buffer[i] + beta*d_buffer[i];
        }  

        *total_counter = *total_counter+1;
        if(*total_counter >= iteration_cutoff) {
            // Set total_counter to -1, this indicates failure
            *total_counter = -1;
            break;
        }
    }

    // Store Wisdom
    fftw_export_wisdom_to_filename("cd.wis");

    // Free fft alloc'd memory and plans
    fftw_destroy_plan(plan_forward_d_buffer);
    fftw_destroy_plan(plan_forward_A_vec);
    fftw_destroy_plan(plan_backward_Ad_buffer);
    fftw_free(A_vec_fft);
    fftw_free(d_buffer_fft);
};

Voici le matlab partie:

% Take FFT of A_vec.
A_vec_fft = fft(A_vec); % Take fft once

% Find initial direction - this is the initial residual 
x = zeros(n,1); % search direction
r = zeros(n,1); % residual
d = zeros(n+(n-2),1); % search direction; pad to allow FFT
for i = 1:n
    d(i) = b(i); 
    r(i) = b(i); 
end

% Enter CG iterations
total_counter = 0;
rtr_buffer = 0;
alpha = 0;
beta = 0;
Ad_buffer = zeros(n+(n-2),1); % This holds the product of A*d - calculate this once per iteration and using FFT; only 1:n is used
norm_ro = norm(r);

while(norm(r)/norm_ro > 10^-6)
    % Find Ad - use fft
    Ad_buffer = ifft(A_vec_fft.*fft(d)); 

    % Calculate rtr_buffer
    rtr_buffer = r'*r;

    % Calculate alpha    
    alpha = rtr_buffer/(d(1:n)'*Ad_buffer(1:n));

    % Calculate new x
    x = x + alpha*d(1:n);

    % Calculate new residual
    r = r - alpha*Ad_buffer(1:n);

    % Calculate beta
    beta = r'*r/(rtr_buffer);

    % Calculate new direction vector
    d(1:n) = r + beta*d(1:n);      

    % Update counter
    total_counter = total_counter+1; 
end

En termes de temps, pour N = 50000 et b = 1:n, il faut environ 10.5 secondes avec mex et 4,4 secondes avec matlab. Je suis en utilisant R2011b. Merci

14voto

Lolo Points 1295

Quelques observations plutôt qu'une réponse définitive, car je ne connais pas toutes les spécificités de la FFT de MATLAB mise en œuvre:

  • Basé sur le code que vous avez, je vois deux explications à la différence de vitesse:
    • la différence de vitesse est expliqué par des différences dans les niveaux de l'optimisation de la FFT
    • la boucle while dans MATLAB est exécutée un nombre nettement inférieur de fois

Je suppose que vous déjà regardé dans la deuxième question, et que le nombre d'itérations sont comparables. (Si ils ne le sont pas, il est plus vraisemblable que certains problèmes liés à l'exactitude et de la valeur des investigations complémentaires.)

Maintenant, quant à la FFT comparaison de la vitesse:

  • Oui, la théorie est que FFTW est plus rapide que les autres de haut niveau FFT implémentations, mais il n'est utile aussi longtemps que vous comparez des pommes avec des pommes: ici, vous comparez des implémentations à un niveau plus bas, au niveau de l'assemblage, où non seulement la sélection de l'algorithme, mais sa réelle optimisation pour un processeur spécifique et par des développeurs de logiciels avec différentes compétences en jeu
  • J'ai optimisé ou examinés optimisé Fft en assemblée sur le nombre de processeurs installés au cours de l'année (j'étais dans l'analyse comparative de l'industrie) et la grande-algorithmes ne sont qu'une partie de l'histoire. Il y a des aspects qui sont très spécifiques à l'architecture vous sont codant pour (comptabilité pour les latences, la planification des instructions, de l'optimisation de registre d'utilisation, organisation des données dans la mémoire, de la comptabilité pour la branche prises ou pas prises latences, etc.) et que faire des différences aussi importantes que le choix de l'algorithme.
  • Avec N=500000, nous parlons aussi de grands tampons de mémoire: encore une autre porte pour plus d'optimisations qui peut rapidement devenir assez spécifique à la plate-forme vous exécutez votre code sur: comment vous parvenez à éviter les défauts de cache ne sera pas dicté par l'algorithme autant que par la façon dont le flux de données et que les optimisations d'un développeur de logiciel peut-être utilisé pour importer des données dans et hors de la mémoire de manière efficace.
  • Mais je ne connais pas les détails de la FFT de MATLAB mise en œuvre, je suis assez sûr qu'une armée de DSP ingénieurs a été (et est encore) le rodage de son optimisation car il est essentiel pour si de nombreux modèles. Ce pourrait très bien dire que MATLAB eu la bonne combinaison de développeurs pour produire un beaucoup plus rapide FFT.

8voto

reverse_engineer Points 608

C'est un gain de performances classique grâce à une optimisation de bas niveau et spécifique à l'architecture.

Matlab utilise la FFT du fichier binaire (mkl.dll) Intel MKL (Math Kernel Library). Ce sont des routines optimisées (au niveau de l'assemblage) par Intel pour les processeurs Intel. Même sur AMD, il semble donner de belles augmentations de performances.

FFTW semble être une bibliothèque normale qui n’est pas aussi optimisée. D'où le gain de performance lié à l'utilisation du MKL.

3voto

Normadize Points 319

Tout d'abord, désolé d'être un an de retard. Je ne suis pas convaincu que l'augmentation de la vitesse que vous voyez vient de MKL ou d'autres optimisations. Il y a quelque chose de fondamentalement différent entre FFTW et Matlab, et c'est de cette façon complexe les données sont stockées dans la mémoire.

Dans Matlab, la réelle et la partie imaginaire d'un complexe vecteur X sont des tableaux distincts Xre[i] et Xim[i] (linéaire dans la mémoire, efficace lors de l'utilisation de l'un ou l'autre séparément).

Dans FFTW, les parties réelles et imaginaires sont entrelacés comme double[2] par défaut, c'est à dire X[i][0] est la partie réelle, et X[i][1] est la partie imaginaire.

Ainsi, l'utilisation de la bibliothèque FFTW à mex fichiers on ne peut pas utiliser le Matlab tableau directement, mais doit allouer de la mémoire d'abord, puis mettez-le d'entrée de Matlab dans FFTW format, puis déballez la sortie de FFTW en format Matlab. c'est à dire

X = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);
Y = (fftw_complex*) fftw_malloc(sizeof(fftw_complex) * N);

alors

for (size_t i=0; i<N; ++i) {
    X[i][0] = Xre[i];
    X[i][1] = Xim[i];
}

alors

for (size_t i=0; i<N; ++i) {
    Yre[i] = Y[i][0];
    Yim[i] = Y[i][1];
}

Par conséquent, cela nécessite 2x allocations de mémoire + 4x lit + 4x écrit -- tous de taille N. il prend un péage en termes de vitesse sur les grands problèmes.

J'ai un pressentiment que Mathworks peut avoir piraté le FFTW3 code pour permettre la lecture des vecteurs en entrée directement dans le format Matlab, ce qui permet d'éviter tous les ci-dessus.

Dans ce scénario, on ne peut allouer de l'X et de l'utilisation de X pour Y exécuter FFTW en place (en tant que fftw_plan_*(N, X, X, ...) au lieu de fftw_plan_*(N, X, Y, ...)), depuis ça va être copié dans le Yre et Yim Matlab vecteur, à moins que l'application nécessite des avantages de l'observance de X et Y distincts.

EDIT: en Regardant la consommation de mémoire en temps réel lors de l'exécution de Matlab fft2() et mon code en fonction de la fftw3 de la bibliothèque, il montre que Matlab n'alloue une gamme complexe (la sortie), alors que mon code doit deux de ces tableaux (l' *fftw_complex tampon plus le Matlab de sortie). Une conversion entre l'Matlab et fftw formats n'est pas possible parce que le Matlab du réel et de l'imaginaire des tableaux ne sont pas consécutifs en mémoire. Ceci suggère que Mathworks piraté le fftw3 bibliothèque pour lire/écrire les données en utilisant le format Matlab.

Une autre optimisation pour les appels multiples, est de répartir de façon persistante (à l'aide d' mexMakeMemoryPersistent()). Je ne suis pas sûr si le Matlab mise en œuvre fait aussi bien.

Des acclamations.

p.s. Comme une note côté, le Matlab complexes format de stockage des données est plus efficace pour les opérations sur le réel ou imaginaire vecteurs séparément. Sur FFTW du format que vous avez à faire ++2 lectures de mémoire.

3voto

ObeyTheDiode Points 41

J'ai trouvé le commentaire suivant sur le site de MathWorks [1]:

Note sur les grandes puissances de 2: FFT dimensions qui sont des puissances de 2, entre 2^14 et 2^22, logiciel MATLAB utilise spécial préchargé les informations dans sa base de données interne pour optimiser le calcul de la FFT. Aucun ajustement n'est effectué lorsque la dimension de la TTF est une puissance de 2, sauf si vous désactivez la base de données à l'aide de la commande fftw ("sagesse", []).

Bien qu'il se rapporte à des puissances de 2, il peut soupçon sur que MATLAB dispose de ses propres spéciale "de la sagesse" lors de l'utilisation de FFTW pour certain (grand) tableau des tailles. Considérer: 2^16 = 65536.

[1] R2013b de la Documentation disponible à partir de http://www.mathworks.de/de/help/matlab/ref/fftw.html (consulté le 29 octobre 2013)

Prograide.com

Prograide est une communauté de développeurs qui cherche à élargir la connaissance de la programmation au-delà de l'anglais.
Pour cela nous avons les plus grands doutes résolus en français et vous pouvez aussi poser vos propres questions ou résoudre celles des autres.

Powered by:

X