Discussion :

[Aida]

Bonjour,
J'ai developpé un bout de code qui permet de retourner la transformée de fourier discrète d'un vecteur tout en minimisant la complexité de l'algo(avec la stragtégie divier pour regner), mais le problème c'est que j'aboutis à des résultats non attendus, si vous pouvez voir le code et detecter la source du problème.
Merci.
Aida.

voilà le code:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
 
procedure FFTRecursive(real a[*], ref real fftrel[*], ref real fftimg[*], int n)
#precondition n = 2**m
 
{
  if (n == 1)
     { fftrel[1] = a[1]; 
       fftimg[1] = a[1];}
  else
     { int m = n/2;
       real wn = exp(2*3.14/n);
       real w = 1;
       real fftrel[1:n], fftimg[1:n];
       real b[1:m], c[1:m], fftrelb[1:m],fftimgb[1:m], fftrelc[1:m], fftimgc[1:m];
       for[i = 1 to m]
          { b[i] = a[2*i];
            c[i] = a[2*i-1];
          }
       FFTRecursive(b,fftrelb,fftimgb,m);
       FFTRecursive(c,fftrelc,fftimgc,m);
       for[k = 1 to m]
          { fftrel[k] = fftrelb[k];
            fftimg[k] = fftimgc[k] * w;
            fftrel[k+m] = fftrelb[k];
            fftimg[k+m] = fftimgc[k] * (-w);
            w = w * wn;
          } 
     }
}
FFTRecursive(A,tabrel,tabimg,n);
for[i = 1 to n]
   { fft[i] = (tabrel[i] * tabrel[i]) + (tabimg[i] * tabimg[i]); }

[Invité(e)]

Bonjour
Serait il possible de ?
De plus, la signification des variables n'est pas très claire.... pourrais tu préciser ? Merci

[Charlemagne]

Salut
J'ai pas cherché à comprendre ton code. A mon avis, c'est pas une bonne idée de le rendre récurssif.

Voici mon impléméntation de la FFT à radix 2 d'un signal complex.
Elle utilise la class 'complex' de la STL.
Elle utilise la classe 'Vector' de ma librarie mathématique, mais c'est facile à adapter en C

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
 
template<class G> Vector<G> &bitreverse_order(Vector<G> &X)
{
  size_t i;
  size_t j = 0;
 
  size_t n = X.size();
 
  for (i = 0; i < n - 1; ++i)
  {
    size_t k=n/2;
    if (i<j) swap(X[i],X[j]);
    while (k<=j) 
    { 
      j=j-k; k=k/2;
    }
    j+=k;
  }
  return X;
}
 
 
template<class G>
Vector<G> &complex_radix2_fft_in_place(Vector<G> &X)
{
  typedef Vector<G> array_type;
  typedef typename array_type::size_type size_type;
  typedef PROMOTE2(complex<float>,typename array_type::value_type) value_type;
  typedef PROMOTE2(complex<float>,typename value_type_traits<value_type>::value_type) complex_type;
  typedef typename complex_type::value_type real_type;
 
  size_type n = X.size();
 
  assert(log2n(n)>=0);
 
  bitreverse_order(X);
 
  for (int dual=1; dual<n; dual*=2)
  {
    real_type theta = -PI/dual;
    real_type s  = sin(theta);
    real_type s2 = real_type(2)*sqr(sin(real_type(0.5)*theta));
 
    complex_type w(1,0);
 
    value_type wd;
    for (size_t a=0; a<dual; ++a, w+=s*complex_type(-w.imag(),w.real())-s2*w)
      for (size_t b=0; b<n; b+=2*dual)
      {
        value_type &Ti=X[b+a];
        value_type &Tj=X[b+a+dual];
        wd=w*Tj;
        Tj=Ti-wd;
        Ti+=wd;
      }
  }
  return X;
}

[Aida]

Bonjour,

D abord je vous remercie pour l interet que vous avez porte a mon sujet.

Pour, le fait que j ai utilise une approche recursive c est parce qu on me demande de le faire recursivement, et pour le type complexe, je dois programmer avec un langage ou ce type n existe pas, donc je dois programmer avec certaines contraintes et je souhaite que vous puissiez jetter un coup d oeil sur mon bout de code.

Pour les balises, excuse mais je les ai oublie.

Merci.

Aida.

[Invité(e)]

Pour les balises, excuse mais je les ai oublie.

Tu peux néammoins éditer ton post (bouton edit) pour les rajouter
De plus, pourrais tu (désolé je me répète) nous expliquer quelles sont tes variables ?

Sinon, deux choses :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 if (n == 1)
{
   fftrel[1] = a[1];
   fftimg[1] = a[1];
}

me parrait louche (mais sans savoir ce qu'est n exactement, cela ne peut etre qu'une intuition.

[Charlemagne]

A moins que ce ne soit un exercice, je vois pas l'intérêt de la récursivité: ca va sérieusement rallonger le temps d'exécution.
Et en général quand on programme une fft c'est bien pour gagner de la vitesse d'execution.
Déjà que radix2 n'est pas la plus rapide des fft; elle n'est néanmoins pas mal du tout point de vue rapport vitesse/complexité.

En ce qui concerne les nombres complexes, on peut facilement s'en passer, en décomposant les operations sur des réels. Le code est moins lisible, c'est tout.

J'avais pas remarqué que c'était pas du C, ça y ressemble en tout cas, sauf pour les déclarations...

J'ai l'impression que tu ne donnes que des réels en entrée. Si c'est le cas j'ai une autre implementation de la radix2 pour un signal réel, plus rapide qu'avec un signal complexe. Je peux te le poster sur demande...

A priori, je regrouperais les parties réelles et imaginaire en sortie, pour rendre un tableau de complexes, plutôt que 2 tableaux séparés.
A moins que tu ne fasses une tranformée 'in place': c'est le cas de mon implémentation.

J'ai pas le temps d'éplucher ton algorithme (et puis c'est pas facile), peut-être que tu peux décalquer le mien pour le rendre récursif...

[Aida]

J utilise l apporche recursive, parce que je vais par la suite faire des comparaisons un pgm resursif et un autre iteratif, et par la suite utiliser plus qu un processuer pour le rendre plus rapide.
Pour le langage de programmation que j utilise c est du mpd, il est base sur pascal et c et il permet d utiliser une programmation parallele.
Si tu peux m envoyer le code dont tu as parle pour que je puisse le voir.
Pour mon programme, je lui fais passer en entree un vecteur de donnees qui sont des valeurs reeles et il doit me fournir en sortie sa transformee de fourier.
Mon probleme c est que je ne comprends pas la transformee de fourier mais je suis obligee de l utiliser sans rentrer dans les details parce que c est la complexite et la nalyse de l algo qui m interesse.
Alors, lorsque j execute mon code il me donne du n importe quoi, donc je crois que j ai des pbs au niveai de l implementation de la fft c est pour cette raison que j aurai aime que qqn jette un coup d oeil sur mon code pour voir la source du pb peut etre que je n ai pas compris qqc.
Merci.
Aida.

[Charlemagne]

Je connais pas la programmation parallele, je sais pas à quel point ca peut apporter de la vitesse à la FFT.
Je me demande à quel niveau la programmation parallèle vaut le coup pour une FFT.
-Si la finalité est de transformer par example une matrice alors je prefererais a priori envoyer chaque ligne/colonne de la matrice sur un processeur different: les FFT de chaque ligne/colonne étant indépendante.
-Par contre, s'il s'agit d'accélérer le calcul d'une seule FFT d'un long signal en parallele, alors ça doit sérieusement se corser. Les performances de la FFT sont très dépendantes du cache et des registres. J'ai moi-même programmé une implémentation optimisé avec SSE/SSE2/SSE3, et je te promet, c'est une autre paire de manche.
La librairie www.fftw.org est une réference. Je crois pas qu'elle fasse du calcul multiprocesseur.

Voici le code de la FFT radix 2 d'un signal réel, j'ai également la IFFT:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
 
template<class G>
void real_radix2_fft_in_place(Vector<G> &X)
{
  typedef Vector<G> array_type;
  typedef typename array_type::size_type size_type;
  typedef PROMOTE2(float,typename array_type::value_type) value_type;
  typedef PROMOTE2(complex<float>,typename array_type::value_type) complex_value_type;
  typedef PROMOTE2(complex<float>,typename value_type_traits<value_type>::value_type) complex_type;
  typedef typename complex_type::value_type real_type;
 
  size_type n = X.size();
  assert(log2n(n)>=0);
 
  bitreverse_order(X);
 
  for (size_t p_1=1, p=2, q=n/2; p_1<n; p_1=p, p*=2, q/=2)
  {
    complex_type w(1,0);
    real_type theta = -2*PI/p;
    real_type s  = sin (theta);
    real_type s2 = 2*sqr(sin(theta/2));
 
    {
      value_type t0;
      for (size_type b=0; b<q; b++)
      {
        typename array_type::reference r0 = X[b*p];
        typename array_type::reference r1 = X[b*p+p_1];
 
        t0 = r0+r1;
        r1 = r0-r1;
        r0 = t0;
	    }
    }
 
    complex_value_type z0, z1, z2;
    for (size_t a=1; a<p_1/2; ++a)
    {
      w+=s*complex_type(-w.imag(),w.real())-s2*w;
      for (size_t b=0; b<q; ++b)
      {
        typename array_type::reference r0 = X[b*p+a];
        typename array_type::reference r1 = X[b*p+p_1-a];
        typename array_type::reference r2 = X[b*p+p_1+a];
        typename array_type::reference r3 = X[b*p+p-a];
 
        real(z0)=r2; imag(z0)=r3;
        real(z1)=r0; imag(z1)=r1;
 
        z0 *= w;
 
        z2 = z1+z0;
        z1 -= z0;
 
        r0 = real(z2);
        r3 = imag(z2);
 
        r1 = real(z1);
        r2 = -imag(z1);
      }
    }
    if (p_1>1) for (size_t b=0; b<q; b++) X[b*p+p-p_1/2]*=double(-1);
  }
}
 
template<class G> 
void real_radix2_ifft_in_place(Vector<G> &X)
{
  typedef Vector<G> array_type;
  typedef typename array_type::size_type size_type;
  typedef PROMOTE2(float,typename array_type::value_type) value_type;
  typedef PROMOTE2(complex<float>,typename array_type::value_type) complex_value_type;
  typedef PROMOTE2(complex<float>,typename value_type_traits<value_type>::value_type) complex_type;
  typedef typename complex_type::value_type real_type;
 
  //typedef Vector<G> array_type;
  //typedef typename array_type::size_type size_type;
  //typedef PROMOTE2(complex<float>,typename Vector<G>::value_type) value_type;
  //typedef typename value_type::value_type real_type;
 
  size_type n = X.size();
  assert(log2n(n)>=0);
 
  for (size_t p_1=n/2, p=n, q=1; q<n; p=p_1, p_1/=2, q*=2)
  {
    complex_type w(1,0);
    real_type theta = 2*PI/p;
    real_type s  = sin (theta);
    real_type s2 = 2*sqr(sin(theta/2));
 
    {
      value_type t0;
      for (size_t b=0; b<q; b++)
      {
        typename array_type::reference r0 = X[b*p];
        typename array_type::reference r1 = X[b*p+p_1];
 
        t0 = r0+r1;
        r1 = r0-r1;
        r0 = t0;
	    }  
	  }  
 
    complex_value_type z0;
    for (size_t a=1; a<p_1/2; ++a)
    {
      w+=s*complex_type(-w.imag(),w.real())-s2*w;
      for (size_t b=0; b<q; ++b)
      {
        typename array_type::reference r0 = X[b*p+a];
        typename array_type::reference r1 = X[b*p+p-a];
        typename array_type::reference r2 = X[b*p+p_1-a];
        typename array_type::reference r3 = X[b*p+p_1+a];
 
        real(z0)=r0-r2; imag(z0)=r1+r3;
        z0 *= w;
 
        r0 += r2;
        r2 = r1-r3;
 
        r3 = real(z0);
        r1 = imag(z0);
      }
    }
    if (p_1>1) for (size_t b=0; b<q; b++) { X[b*p+p_1/2]*=2; X[b*p+p_1+p_1/2]*=-2; }
 
  }
  bitreverse_order(X);
  X/=n;
}

[Charlemagne]

J'oubliais:
C'est une implémentation 'in place'.
La sortie complexe du signal réel est donc compactée, en tenant compte de la symmétrie complexe:
Y[i]=conj(Y[n-i])

[Aida]

oK, Merci.
Je vais voir ce code.
Mais, j ayyends tjs qu une personne puisse jetter un coup d oeil sur mon pgm parce que je dois le faire comem je l ai deja fait j ai pas vraiment le choix je suis obligee.

Aida.

[Aida]

Pour mabu, n est la taille de mon vecteur.
n == 1 cette condition me permet d arreter la recursion lorsque la taille de mon vecteur est de 1, moi aussi je ne sais pas si je dois le faire comme ca ou autrement.

Aida.

[Charlemagne]

Petit détail:
Il vaut mieux faire le test de fin de récursion avant l'appel de la fonction récursive, plutôt qu'au début de cette dernière: c'est nettement plus rapide.

Mais je maintiens ce que j'ai dis sur les fonctions récursives, c'est une très mauvaise idée.
Je ne sais pas comment marche ton language de prog multi-processeurs, mais vu que la fft est en O(n*logn), je doute que tu aies nlogn processeurs.
Tout au plus je ferais une première étape récursive, pour ensuite appeler une fft non récursive sur différents processeurs.

Avec mon implémentation SIMD (SSE) sur Pentium, j'ai gagné un facteur 10 à 15 (avec une FFT à radix variable) par rapport au code que je t'ai donné.
Ca sera difficile (pour ne pas dire impossible) de faire mieux sans SIMD, même avec plusieurs processeurs.

[Charlemagne]

Le débat est vieux.

Inutile d'écrire en gras des choses fausses.
La récursivité n'est pas rapide, surtout pas pour une FFT.
Et je m'y connais en FFT.

cf mon site:
http://www.ient.rwth-aachen.de/team/laurent/genial/genial.html
ou www.fftw.org/

[Mac LAK]

Je connais pas la programmation parallele, je sais pas à quel point ca peut apporter de la vitesse à la FFT.
Je me demande à quel niveau la programmation parallèle vaut le coup pour une FFT.

En fait, la programmation parallèle apporte énormément à la FFT, mais ce n'est pas forcément sur du multithread... L'idéal pour la FFT, c'est l'architecture SIMD (Single Instruction Multiple Data), qui permet d'accélérer monstrueusement ce type de calcul... Mais c'est quand même de la programmation parallèle.

Par contre, un domaine où elle apportera toujours des performances supplémentaires, c'est sur un système multiprocesseurs : en effet, tu peux découper ton signal discret en autant de parties (à peu près égales) qu'il y a de processeurs, et mettre un thread sur chaque bout. A chaque étape du papillon, tu redistribue seulement les éléments. Comme tout est en mémoire, le gain de temps pour un multithreading mono-processeur ne doit pas être très significatif (pas de temps d'attente des I/O permettant d'exécuter les autres threads sur du temps mort, notamment). Mais sur une archi MP, c'est différent...

[Charlemagne]

C'est bien ce que je disais un peu plus haut:
-pas la peine de faire du multiprocesseur si on n'a pas déjà regardé du coté des SIMD
-pour du multiprocesseur, diviser le signal en des morceaux les plus gros possibles. Chaque processeur recevant son morceau. Pas la peine de donner pleins de petit morceaux à chaque processeur.

[Mac LAK]

-pas la peine de faire du multiprocesseur si on n'a pas déjà regardé du coté des SIMD

Ben, parfois, tu n'as pas le choix : si tu n'as pas d'architecture SIMD disponible, ou si tu n'as que ça de dispo, tu fais avec... Sur Pentium, utiliser les instructions MMX/SSE permet d'accélérer la FFT assez lourdement, par exemple.

Pas la peine de donner pleins de petit morceaux à chaque processeur.

C'est exactement ça : les blocs les plus volumineux possible... Dans l'absolu, il faudrait également vérifier que le processeur ne soit pas virtuel (CPU HyperThreading), car si le processeur "vrai" est chargé à 100% sur un tel calcul, le second (virtuel) sera tellement à la traîne qu'il ne pourra calculer son bloc ... qu'après la complétion du premier ! Ben oui : charge 100% sur un calcul sans temps mort => processeur virtuel en rideau...

Par contre, un (et un seul) thread "vrai" servant à distribuer/découper les données, ça peut être avantageux... Mais bon, j'appelle pas ça de la vraie programmation parallèle non plus, c'est juste un "truc et astuce" pour simplifier le code.

[Charlemagne]

Oui, tu confirmes ce que je dis.

Par contre les calculs SIMD des pentiums ne permettent pas d'accélérer "monstrueusement" ou "lourdement" les calculs de la FFT.
Ca vient du fait qu'on ne peut faire des calculs parallèles que sur 4 floats (2 complexes), ou 2 doubles (1 complexe).
J'ai fais des comparaisons.

La vitesse de ma FFT est du même ordre de grandeur que FFTW sous toutes les configurations possibles (avec ou sans SSE/SSE2/SSE3), donc difficile de faire plus rapide.
- avec SSE (4 floats parallèle) environ 2.5 fois plus rapide que sans SIMD.
C'est pas 4 fois plus rapide comme on aurait pu le supposer pour tout un tas de raisons (certaines parties du calcul pas entièrement parallèlisable, même quantité de mémoire à charger...)
- avec SSE2 (2 doubles), presque 2 fois plus rapide que sans SIMD. Ici le gain de vitesse est plus conforme à ce qu'on peut a priori attendre, parceque c'est plus facilement parallelisable: 1 registre = 1 complexe.

Un facteur 2 ou 2.5, c'est toujours bon à prendre, mais c'est pas ce que j'appelle "monstrueux".
Les SIMD sont dans l'ensemble plus favorables aux calculs sur les entiers.
(16 chars, 8 shorts, ou 4 entiers dans un registre)

Un autre moyen de gagner beaucoup de vitesse (environ de 5 par rapport à la radix 2 (papillon), consiste à augmenter le radix: 4,8,16,32 ou même d'utiliser un radix variable (FFT mixte). Y'a plusieurs facteurs qui expliquent le gain de vitesse: moins de chargement/sauvegarde en mémoire, meilleure utilisation des registres, moins de sauts...

Alors, et seulemnent alors, pour être plus rapide on peut envisager de faire du multi-processeurs. Mais en général les gens sont incapables d'optimiser un calcul, et veulent commencer d'emblée à faire du multi-processeurs....

[Mac LAK]

Un facteur 2 ou 2.5, c'est toujours bon à prendre, mais c'est pas ce que j'appelle "monstrueux".

J'ai pas dit "monstrueusement", mais "lourdement"... Facteur deux au bas mot, j'appelle ça "lourd", pas toi ? ;-)

Les SIMD sont dans l'ensemble plus favorables aux calculs sur les entiers.

Ca, c'est indéniable... Mais même sur les floats, ça aide quand même pas mal.

Mais en général les gens sont incapables d'optimiser un calcul, et veulent commencer d'emblée à faire du multi-processeurs....

Ca, je suis bien d'accord avec toi. Perso, j'envisage le MP comme un simple outil : avec la "démocratisation" des systèmes MP, il est dommage de ne pas prévoir, dans un algo, d'utiliser cette capacité de traitement lorsqu'elle est disponible.

Par exemple, pour une FFT "classique", déterminer au démarrage de l'application la présence d'un véritable MP (pour les raisons que j'avais indiquées, les procs virtuels HT ne sont pas éligibles) et varier son algorithme en fonction du nombre de processeurs est à mon avis une très bonne solution. Un proc virtuel HT est par contre parfaitement utilisable pour des opérations sur disque (là, il se comporte presque comme un proc "normal" en terme d'efficacité).
Dans tous les cas, l'affinité avec le processeur d'un thread donné devra être soigneusement préparée, et ça, c'est déjà un algo à part entière...

Par contre, dire "Il me faut un système quadriproc" parcequ'on ne sait pas optimiser son algo, là, je prépare direct un bûcher... De bois vert, en plus...

[Charlemagne]

Si, si, tu as dis "monstreusement". Regarde un peu plus haut.

L'idéal pour la FFT, c'est l'architecture SIMD (Single Instruction Multiple Data), qui permet d'accélérer monstrueusement ce type de calcul...

Par exemple, pour une FFT "classique", déterminer au démarrage de l'application la présence d'un véritable MP (pour les raisons que j'avais indiquées, les procs virtuels HT ne sont pas éligibles) et varier son algorithme en fonction du nombre de processeurs est à mon avis une très bonne solution. Un proc virtuel HT est par contre parfaitement utilisable pour des opérations sur disque (là, il se comporte presque comme un proc "normal" en terme d'efficacité).
Dans tous les cas, l'affinité avec le processeur d'un thread donné devra être soigneusement préparée, et ça, c'est déjà un algo à part entière...

Effectivement, 2 FFTs parallèles sur un pentium HyperThread, ça me parait sérieusement compromis:
-En calculs SIMD, Le Pentium passe beaucoup de temps à attendre le chargement/écriture des données en mémoire. Avant de programmer en SIMD, je m'étais jamais préoccupé de ça.
-Vu que les 2 FFTs utiliseraient les mêmes instructions, et mêmes registres je crois pas que le gain serait fulgurant, puisque l'architure HT (pour autant que je sache) se base sur 2 processus dont les instructions ne se tamponnent pas.

J'ai pas la possibilité de programmer en multi processeur. Il peut y avoir des gains, mais c'est pas évident. Il faut voir si l'acces mémoire n'est pas un goulot d'étranglement pour la vitesse.
De toute façon, je suis d'accord pour dire que l'algo n'est pas évident en soit (il suffit pas de dire qu'on a un compilo multiprocesseur).

Il semblerait que les futurs processeurs multi-noyaux, n'aporteront aucun (ou peu) de gain de vitesse, sans utiliser leurs instructions spécifiques.

[Mac LAK]

Tes balises "quote" sont HS sur le post précédent...

Si, si, tu as dis "monstreusement". Regarde un peu plus haut.

Oui, dans le cas général : avec une archi SIMD à 128 unités d'exécution flottantes, c'est monstrueux... Sur Pentium/SSE, j'ai juste dit "lourdement"...

Effectivement, 2 FFTs parallèles sur un pentium HyperThread, ça me parait sérieusement compromis:

Ah, toi aussi, hein.... ;-)

-Vu que les 2 FFTs utiliseraient les mêmes instructions, et mêmes registres je crois pas que le gain serait fulgurant, puisque l'architure HT (pour autant que je sache) se base sur 2 processus dont les instructions ne se tamponnent pas.

Surtout que tu n'as PAS deux unités SSE, mais une seule... Pour le HT, c'est en fait (en très simplifié) l'équivalent d'un 2nd jeu de registres (=état machine) câblé "en dur", et pouvant être commuté extrêmement rapidement par hardware. En fait, ça fait exactement ce que fait un OS lorsqu'il commute deux processus, mais en hard. L'avantage, c'est que la gestion est automatique : lorsque l'exécution du 1er processeur est bloquée (pour une raison X ou Y), c'est le 2nd processeur (le virtuel) qui prends le relais, permettant ainsi de mieux profiter des "trous" dans le pipeline d'exécution... De même que la structure superscalaire permet d'exécuter deux instruction décorrélées simultanément, ça ne profite que des "trous" => ça permet, au bilan final, d'utiliser le processeur à 99.99% de sa capacité, mais si un thread/processus utilise déjà le processeur à son maximum (genre, justement, calculs intensifs en RAM uniquement), alors l'HT ne permet quasiment aucun gain... Disons 5% de perfs en plus dans le meilleur des cas, et encore...
Référence : Technologie HT. C'est très intéressant, et plutôt accessible, je conseille aux lecteurs de ce topic d'aller jeter un oeil. Au moins pour la "culture générale".

J'ai pas la possibilité de programmer en multi processeur. Il peut y avoir des gains, mais c'est pas évident. Il faut voir si l'acces mémoire n'est pas un goulot d'étranglement pour la vitesse.

Je devrais bientôt pouvoir le faire, par contre. Disons qu'en général, en contexte MP, on mets de la RAM par banques séparées, permettant ainsi aux deux processeurs de taper dans deux banques différentes, donc l'accès simultané est possible.
Par contre, c'est sûr que s'ils travaillents sur la même zone mémoire, les opérations de transfert vont pénaliser l'exécution, sauf si la perte de temps occasionnée par le transfert mémoire (c'est très rapide, quand même) est inférieure au gain de temps apporté par le second processeur.
En gros, tu vas te retrouver avec deux fonctions affines : une pour le calcul SP, une pour le calcul MP (disons bi-proc pour simplifier). En abscisse, le nombre N d'échantillons. En ordonnée, le temps T d'exécution.
A un moment donné, les deux courbes se croisent : reste juste à savoir où. Si c'est pour N=64 (c'est très peu pour une FFT, quand même), alors le MP sera presque toujours avantageux. Si c'est pour N=2^24, alors on est tranquille, et le MP n'offrira aucun avantage... ;-)

De toute façon, je suis d'accord pour dire que l'algo n'est pas évident en soit (il suffit pas de dire qu'on a un compilo multiprocesseur).

Ce n'est pas le compilateur qui gère ça, mais l'OS. De plus, tu oublies un cas plutôt vicieux, mais qui devrait être (théoriquement) le plus efficace :
- Charger le 1er processeur avec 66% des échantillons, calculés par SSE2.
- Charger le 2nd processeur avec 33% des échanitllons, calculés de manière "classique".
A peu de choses près, les deux processeurs vont terminer leur exécution en même temps. Cependant, le réglage d'un tel algo risque d'être méchamment chaud à faire... Surtout qu'il va forcément dépendre de l'architecture de la machine (type de RAM notamment) => il faudrait "calibrer" le programme de FFT avant de l'utiliser !!

Il semblerait que les futurs processeurs multi-noyaux, n'aporteront aucun (ou peu) de gain de vitesse, sans utiliser leurs instructions spécifiques.

Attention, si ce sont vraiment des CPU multi-noyaux, c'est transparent : ça représente deux processeurs réels (pas des virtuels, donc) => transparent pour le logiciel, c'est bien deux "vrais" CPU. C'est au niveau hard que ça simplifie les choses, car il n'y a qu'un seul socket CPU, même s'il y a plus de pins bien sûr.