Quelle est l’instruction qui donne FP min et max sans twigs sur x86?

Pour citer (merci à l’auteur pour avoir développé et partagé l’algorithme!):

Fast, Branchless Ray/Bounding Box Intersections

Depuis les jeux d’instructions à virgule flottante modernes peuvent calculer min et max sans twigs

Le code correspondant par l’auteur est juste

dmnsn_min(double a, double b) { return a < b ? a : b; } 

Je connais par exemple _mm_max_ps , mais c’est une instruction vectorielle. Le code ci-dessus est évidemment destiné à être utilisé sous une forme scalaire.

Question:

  • Quelle est l’instruction minarre scalaire sans twig sur x86? Est-ce une séquence d’instructions?
  • Est-il prudent de supposer que cela va être appliqué, ou comment puis-je l’appeler?
  • Est-il judicieux de s’occuper de l’absence de twigment de min / max? D’après ce que j’ai compris, pour un logiciel de lecture de rayons et / ou autre logiciel, dans le cas d’une routine d’intersection rayon-boîte, il n’existe pas de modèle fiable à prendre pour le prédicteur de twig. Il est donc logique d’éliminer la twig. Ai-je raison à ce sujet?
  • Plus important encore, l’algorithme présenté repose sur la comparaison avec (+/-) INFINITY. Est-ce fiable avec l’instruction (inconnue) dont nous discutons et la norme en virgule flottante?

Juste au cas où: Je connais bien l’ utilisation des fonctions min et max en C ++ , je pense que c’est lié, mais ce n’est pas tout à fait ma question.

La plupart des instructions de PF vectorielles ont des équivalents scalaires. MINSS / MAXSS / MINSD / MAXSD sont ce que vous voulez. Ils gèrent l’infini comme vous le souhaiteriez.

MINSS a,b implémente exactement (a (a selon les règles IEEE , avec tout ce que cela implique à propos de sign-zero, NaN et Infinities. Cela signifie que les compilateurs peuvent les utiliser pour std::min(b,a) et std::max(b,a) , car ces fonctions sont basées sur la même expression. .

MAXSS a,b implémente exactement (b (b , en maintenant à nouveau l'opérande source non ordonné. Boucler sur un tableau avec maxss xmm0, [rsi] donnera NaN si le tableau contient un NaN, propageant NaN dans votre calcul comme il est normal pour les autres opérations de PF. Cela signifie également que vous pouvez xmm0 avec NaN (en utilisant pcmpeqd xmm0,xmm0 ) au lieu de -Inf ou du premier élément de tableau; cela pourrait simplifier la gestion des listes éventuellement vides.


N'essayez pas d'utiliser _mm_min_ss sur les flotteurs scalaires; l'insortingnsèque n'est disponible qu'avec les opérandes __m128 , et les éléments insortingnsèques d'Intel ne fournissent aucun moyen d'obtenir un flottement scalaire dans l'élément low d'un __m128 sans mettre à zéro les éléments high ni effectuer de travail supplémentaire. La plupart des compilateurs émettront des instructions inutiles pour le faire, même si le résultat final ne dépend de rien dans les éléments supérieurs. Il n'y a rien de tel que __m256 _mm256_castps128_ps256 (__m128 a) pour simplement lancer un float sur un __m128 avec des ordures dans les éléments supérieurs. Je considère cela comme un défaut de conception. : /

Mais heureusement, vous n'avez pas besoin de le faire manuellement, les compilateurs savent comment utiliser SSE / SSE2 min / max pour vous. Il suffit d'écrire votre C tel qu'ils peuvent. La fonction de votre question est idéale: comme indiqué ci-dessous (lien Godbolt):

 // can and does inline to a single MINSD instruction, and can auto-vectorize easily static inline double dmnsn_min(double a, double b) { return a < b ? a : b; } 

Notez leur comportement asymésortingque avec NaN : si les opérandes ne sont pas ordonnés, dest = src (c’est-à-dire qu’il faut le second opérande si l’un des opérandes est NaN). Cela peut être utile pour les mises à jour conditionnelles SIMD, voir ci-dessous.

( a et b sont pas ordonnés si l'un d'eux est NaN. Cela signifie a , a==b et a>b sont tous faux. Voir la série d'articles de Bruce Dawson sur la virgule flottante pour de nombreux pièges de FP .)

Les _mm_min_ps insortingnsèques _mm_min_ss / _mm_min_ps correspondants peuvent ou non avoir ce comportement, selon le compilateur.

Je pense que les éléments insortingnsèques sont supposés avoir la même sémantique d'ordre d'opérande que les instructions asm, mais gcc a traité les opérandes en _mm_min_ps comme étant commutatifs, même sans -ffast-math pendant longtemps, gcc4.4 ou peut-être plus tôt. GCC 7 l'a finalement modifié pour qu'il corresponde à ICC et à Clang.

Le moteur de recherche d'insortingns en ligne d'Intel ne documente pas ce comportement pour la fonction, mais il n'est peut-être pas supposé être exhaustif. Le manuel asm insn ref ne dit pas que l'insortingnsèque n'a pas cette propriété; _mm_min_ss est _mm_min_ss tant qu'insortingnsèque pour MINSS.

Lorsque j'ai "_mm_min_ps" NaN sur "_mm_min_ps" NaN , j'ai trouvé ce code réel et quelques autres explications sur l'utilisation de l'insortingnsèque pour gérer NaNs, si bien que beaucoup de gens s'attendent à ce que l'insortingnsèque se comporte comme l'instruction asm. (Cela est arrivé pour un code que j'écrivais hier, et je pensais déjà l'écrire en tant que question auto-répondue.)

Compte tenu de l'existence de ce bogue gcc de longue date, le code portable qui veut tirer parti de la gestion NaN de MINPS doit prendre des précautions. La version standard de gcc sur de nombreuses dissortingbutions Linux existantes mal comstackra votre code si cela dépend de l'ordre des opérandes à _mm_min_ps . Donc, vous avez probablement besoin d'un #ifdef pour détecter le gcc réel (pas de bruit, etc.), et une alternative. Ou faites-le simplement différemment en premier lieu: / Peut-être avec un _mm_cmplt_ps et un booléen AND / ANDNOT / OR.

L'activation de -ffast-math rend également _mm_min_ps commutative sur tous les compilateurs.


Comme d’habitude, les compilateurs savent comment utiliser le jeu d’instructions pour implémenter correctement la sémantique C. MINSS et MAXSS sont de toute façon plus rapides que tout ce que vous pourriez faire avec une twig , écrivez donc simplement du code pouvant être compilé avec l’une de celles-ci.

Le problème commutatif- _mm_min_ps s'applique uniquement à l' _mm_min_ps insortingnsèque: gcc sait exactement comment fonctionnent MINSS / MINPS et les utilise pour mettre en œuvre correctement la sémantique ssortingcte de la FP (lorsque vous n'utilisez pas -ffast-math).

Vous n'avez généralement pas besoin de faire quelque chose de spécial pour obtenir du code scalaire décent d'un compilateur. Si vous passez du temps à vous soucier des instructions utilisées par le compilateur, vous devriez probablement commencer par vectoriser manuellement votre code si le compilateur ne le fait pas.

(Il peut y avoir de rares cas où une twig est préférable, si la condition va presque toujours dans un sens et que la latence est plus importante que le débit. La latence MINPS est d’environ 3 cycles, mais une twig parfaitement prédite ajoute 0 cycle à la chaîne de dépendance de la chaîne critique. chemin.)


En C ++, utilisez std::min et std::max , qui sont définis en termes de > ou < , et n'ont pas les mêmes exigences en matière de comportement NaN que fmin et fmax . Évitez fmin et fmax sauf si vous avez besoin de leur comportement NaN.

En C, je pense juste écrire vos propres fonctions min et max (ou des macros si vous le faites en toute sécurité).


C & asm sur l'explorateur du compilateur Godbolt

 float minfloat(float a, float b) { return (a 

Si vous voulez utiliser _mm_min_ss / _mm_min_ps vous-même, écrivez un code permettant au compilateur de comstackr asm même sans -ffast-math.

Si vous ne vous attendez pas à NaN, ou si vous voulez les manipuler spécialement, écrivez des choses comme

 lowest = _mm_min_ps(lowest, some_loop_variable); 

ainsi, le registre contenant le lowest peut être mis à jour sur place (même sans AVX).


Profiter du comportement NaN des MINPS:

Dites que votre code scalaire est quelque chose comme

 if(some condition) lowest = min(lowest, x); 

Supposons que la condition puisse être vectorisée avec CMPPS, de sorte que vous ayez un vecteur d'éléments avec les bits tous définis ou tous effacés. (Ou peut-être pouvez-vous vous en sortir avec ANDPS / ORPS / XORPS directement sur les flotteurs, si vous vous souciez de leur signe et du souci de zéro négatif. Cela crée une valeur de vérité dans le bit de signe, avec des déchets ailleurs. BLENDVPS ne fait que regarder. au niveau du bit de signe, cela peut donc être super utile. Ou vous pouvez diffuser le bit de signe avec PSRAD xmm, 31 )

La méthode la plus simple pour implémenter cela serait de mélanger x avec +Inf fonction du masque de condition. Ou ne newval = min(lowest, x); et mélangez newval au lowest . (soit BLENDVPS ou AND / ANDNOT / OR).

Mais l'astuce est que tout-un-bits est un NaN, et un OU au niveau du bit le propagera . Alors:

 __m128 inverse_condition = _mm_cmplt_ps(foo, bar); __m128 x = whatever; x = _mm_or_ps(x, condition); // turn elements into NaN where the mask is all-ones lowest = _mm_min_ps(x, lowest); // NaN elements in x mean no change in lowest // REQUIRES NON-COMMUTATIVE _mm_min_ps: no -ffast-math // AND DOESN'T WORK AT ALL WITH MOST GCC VERSIONS. 

Donc, avec seulement SSE2, et nous avons fait un MINPS conditionnel dans deux instructions supplémentaires (ORPS et MOVAPS, sauf si le déroulement de la boucle laisse disparaître les MOVAPS).

L'option sans SSE4.1 BLENDVPS est ANDPS / ANDNPS / ORPS à mélanger, plus un MOVAPS supplémentaire. ORPS est de toute façon plus efficace que BLENDVPS (2 UPS sur la plupart des processeurs).

La réponse de Peter Cordes est excellente. Je pensais simplement que j’interviendrais avec des réponses plus courtes, point par point:

  • Quelle est l’instruction minarre scalaire sans twig sur x86? Est-ce une séquence d’instructions?

Je minss de minss / minsd . Et même les autres architectures ne disposant pas de telles instructions devraient pouvoir le faire sans twig avec des déplacements conditionnels.

  • Est-il prudent de supposer que cela va être appliqué, ou comment puis-je l’appeler?

gcc et clang optimiseront tous les deux (a < b) ? a : b (a < b) ? a : b à minss / minsd , donc je ne me préoccupe pas d’utiliser des minsd insortingnsèques. Ne peut pas parler à d'autres compilateurs cependant.

  • Est-il judicieux de s’occuper de l’absence de twigment de min / max? D'après ce que j'ai compris, pour un logiciel de lecture de rayons et / ou autre logiciel, dans le cas d'une routine d'intersection rayon-boîte, il n'existe pas de modèle fiable à prendre pour le prédicteur de twig. Il est donc logique d'éliminer la twig. Ai-je raison à ce sujet?

Les tests individuels a < b sont à peu près complètement imprévisibles, il est donc très important d'éviter de créer des twigs pour ceux-ci. Des tests tels que if (ray.dir.x != 0.0) sont très prévisibles. Il est donc moins important d'éviter ces twigs, mais cela réduit la taille du code et facilite la vectorisation. La partie la plus importante consiste probablement à supprimer les divisions.

  • Plus important encore, l'algorithme présenté repose sur la comparaison avec (+/-) INFINITY. Est-ce fiable avec l'instruction (inconnue) dont nous discutons et la norme en virgule flottante?

Oui, minss / minsd se comporte exactement comme (a < b) ? a : b (a < b) ? a : b , y compris leur traitement des infinis et des NaN.

De plus, j’ai écrit un article de suivi sur celui que vous avez mentionné, qui traite de NaNs et de min / max plus en détail.