Pourquoi SSE scalaire sqrt (x) est-il plus lent que rsqrt (x) * x?

Question

J'ai été profilage certains de nos noyau de calcul sur un processeur Intel Core Duo, et en regardant les diverses approches de la racine carrée, j'ai remarqué quelque chose d'étrange: à l'aide de l'ESS scalaire opérations, il est plus rapide de prendre une réciprocité de racine carrée et de le multiplier pour obtenir la racine carrée, c'est d'utiliser le natif sqrt opcode!

Je suis en essais avec une boucle quelque chose comme:

inline float TestSqrtFunction( float in );

void TestFunc()
{
  #define ARRAYSIZE 4096
  #define NUMITERS 16386
  float flIn[ ARRAYSIZE ]; // filled with random numbers ( 0 .. 2^22 )
  float flOut [ ARRAYSIZE ]; // filled with 0 to force fetch into L1 cache

  cyclecounter.Start();
  for ( int i = 0 ; i < NUMITERS ; ++i )
    for ( int j = 0 ; j < ARRAYSIZE ; ++j )
    {
       flOut[j] = TestSqrtFunction( flIn[j] );
       // unrolling this loop makes no difference -- I tested it.
    }
  cyclecounter.Stop();
  printf( "%d loops over %d floats took %.3f milliseconds",
          NUMITERS, ARRAYSIZE, cyclecounter.Milliseconds() );
}

J'ai essayé avec différents organismes pour la TestSqrtFunction, et j'ai quelques timings qui sont vraiment à me gratter la tête. Le pire de tous, de loin, l'aide la native sqrt() de la fonction et de laisser le "smart" compilateur "optimiser". Au 24ns/float, à l'aide de la FPU x87 c'était pathétiquement mauvais:

inline float TestSqrtFunction( float in )
{  return sqrt(in); }

La prochaine chose que j'ai essayé a l'aide d'un intrinsèques pour forcer le compilateur à utiliser de l'ESS scalaire sqrt opcode:

inline void SSESqrt( float * restrict pOut, float * restrict pIn )
{
   _mm_store_ss( pOut, _mm_sqrt_ss( _mm_load_ss( pIn ) ) );
   // compiles to movss, sqrtss, movss
}

C'était mieux, à 11,9 ns/float. J'ai aussi essayé Carmack est loufoque Newton-Rhapson rapprochement technique, qui a couru encore mieux que le matériel, à 4,3 ns/float, mais avec une erreur de 1 à 2¹⁰ (qui est beaucoup trop pour mes besoins).

La rude bataille a été quand j'ai essayé de l'ESS op pour la réciproque de la racine carrée, et ensuite utilisé un de se multiplier pour obtenir la racine carrée ( x * 1/√x = √x ). Même si cela prend deux opérations dépendantes, c'était la solution la plus rapide, et de loin, à 1,24 ns/float et précises à 2^-14:

inline void SSESqrt_Recip_Times_X( float * restrict pOut, float * restrict pIn )
{
   __m128 in = _mm_load_ss( pIn );
   _mm_store_ss( pOut, _mm_mul_ss( in, _mm_rsqrt_ss( in ) ) );
   // compiles to movss, movaps, rsqrtss, mulss, movss
}

Ma question est fondamentalement ce qui donne? Pourquoi est-ESS intégré-à-matériel racine carrée de l'opcode plus lent que la synthèse de la sortir de deux autres opérations mathématiques?

Je suis sûr que c'est vraiment le coût de l'op elle-même, parce que j'ai vérifié:

• Toutes les données s'inscrit dans le cache, et accès séquentiel
• les fonctions sont intégrées
• dérouler la boucle ne fait aucune différence
• les drapeaux de compilation sont définies pour une optimisation complète (et l'ensemble est bonne, j'ai vérifié)

(edit: stephentyrone souligne à juste titre que les opérations sur les longues chaînes de chiffres devraient utiliser la vectorisation SIMD paniers ops, comme rsqrtps — mais la matrice de structure de données est ici à des fins de test uniquement: ce que je suis vraiment en essayant de mesure scalaire de la performance pour une utilisation dans le code qui ne peut pas être vectorisé.)

Answer 1

sqrtss donne un correctement résultat arrondi. rsqrtss donne une approximation de l'inverse, précise à propos de 11 bits.

sqrtss est de générer un beaucoup plus précis, lorsque la précision est de mise. rsqrtss existe pour les cas où un rapprochement suffit, mais la vitesse n'est requise. Si vous lisez Intel documentation, vous trouverez également une séquence d'instruction (réciproque de racine carrée de rapprochement, suivi par un seul de Newton-Raphson étape) qui donne presque plus de précision (~23 bits de précision, si je me souviens correctement), et est encore un peu plus vite que d' sqrtss.

edit: Si la vitesse est essentielle, et vous êtes vraiment appeler cela dans une boucle pour de nombreuses valeurs, vous devriez être en utilisant la vectorisé versions de ces instructions, rsqrtps ou sqrtps, les deux processus de quatre chars, par instruction.

Answer 2

Ceci est également vrai pour la division. MULSS (a, RCPSS (b)) est bien plus rapide que DIVSS (a, b). En fait, il est encore plus rapide même lorsque vous augmentez sa précision avec une itération Newton-Rhapson.

Intel et AMD recommandent tous les deux cette technique dans leurs manuels d’optimisation. Dans les applications qui ne nécessitent pas la conformité IEEE-754, la seule raison d'utiliser div / sqrt est la lisibilité du code.

Answer 3

Au lieu de fournir une réponse, c'est peut-être incorrect (je suis aussi ne va pas vérifier ou de discuter à propos de cache et d'autres choses, disons qu'elles sont identiques), je vais essayer de vous mettre à la source qui peut répondre à votre question.
La différence pourrait résider dans la façon dont sqrt et rsqrt sont calculées. Vous pouvez en lire plus ici http://www.intel.com/products/processor/manuals/. Je vous suggère de commencer à partir de la lecture sur le processeur fonctions que vous utilisez, il y a certaines informations, en particulier sur rsqrt (cpu est à l'aide de la table de choix avec d'énormes approximation, ce qui le rend beaucoup plus simple pour obtenir le résultat). Il peut sembler, que rsqrt est donc beaucoup plus rapide que sqrt, que 1 de l'opération mul (ce qui n'est pas cher) pourrait ne pas changer la situation ici.

Edit: Quelques faits qui pourraient être utile de mentionner:
1. Une fois que je faisais des micro optimalizations pour mes graphiques de la bibliothèque et je l'ai utilisé rsqrt pour le calcul de la longueur des vecteurs. (au lieu de sqrt, j'ai multiplié mon somme des carrés par rsqrt, ce qui est exactement ce que vous avez fait dans vos tests), et il a réalisé de mieux.
2. Le calcul de rsqrt à l'aide de simple table de recherche pourrait être plus facile, comme pour rsqrt, lorsque x tend vers l'infini, 1/sqrt(x) tend vers 0, donc pour les petits x les valeurs de la fonction ne change pas (beaucoup), alors que pour sqrt - il va à l'infini, donc c'est très simple ;).

Aussi, des précisions: je ne suis pas sûr de l'endroit où je l'ai trouvé dans des livres que j'ai lié, mais je suis assez sûr que j'ai lu que rsqrt est l'utilisation de certaines table de recherche, et il doit être utilisé uniquement lorsque le résultat n'a pas besoin d'être exact, bien que - j'ai peut-être tort que de bien, comme il l'était il y a quelques temps :).

Answer 4

Newton-Raphson converge vers le zéro de l' f(x) en utilisant des incréments est égal à -f/f' où f' est la dérivée.

Pour x=sqrt(y), vous pouvez essayer de résoudre f(x) = 0 pour x l'aide f(x) = x^2 - y;

Ensuite, l'incrément est: dx = -f/f' = 1/2 (x - y/x) = 1/2 (x^2 - y) / x qui a une lente diviser.

Vous pouvez essayer d'autres fonctions (comme f(x) = 1/y - 1/x^2), mais ils seront tout aussi compliquée.

Regardons 1/sqrt(y) maintenant. Vous pouvez essayer d' f(x) = x^2 - 1/y, mais il sera tout aussi compliqué: dx = 2xy / (y*x^2 - 1) par exemple. Un non-évidentes autre choix pour f(x) est: f(x) = y - 1/x^2

Alors: dx = -f/f' = (y - 1/x^2) / (2/x^3) = 1/2 * x * (1 - y * x^2)

Ah! Ce n'est pas une expression triviale, mais vous avez seulement se multiplie dans, pas de fossé. => Le plus rapide!

Et: la mise à jour complète de l'étape new_x = x + dx lit:

x *= 3/2 - y/2 * x * x qui est trop facile.