10
votes

X86 MAX / MIN INSTRUCTIONS ASM?

Y a-t-il des instructions d'ASM pouvant accélérer le calcul de min / max de vecteur de doubles / entiers sur l'architecture Core I7?

mise à jour:

Je ne m'attendais pas à de telles réponses riches, merci. Je vois donc que max / min est possible de faire sans ramification. J'ai une sous-question:

Y a-t-il un moyen efficace d'obtenir l'index du plus grand double de la matrice?


3 commentaires

Quelle est la langue d'hôte? Si c'est C / C ++, je ne m'en avais pas trop.


Max d'environ 300 doubles est dans la boucle la plus interne du grand programme. 85% du temps est passé dans environ 10 lignes de code de 8'000. La langue de l'hôte n'a pas d'importance juste à cause de cela. Mais oui c'est c ++


Connexe: Quelle est l'instruction qui donne à FP min et max sur X86 et max sur X86? a plus de détails sur les MINSS / MAXSS / MINSD / MAXSD, y compris leur Comportement de Na.


6 Réponses :


4
votes

MAXPS et MINPS de SSE fonctionnent tous les deux sur des nombres de points flottants à la précision à la précision emballés. Pmaxsw, PMINSW, Pmaxub et PMinub fonctionnent tous sur des mots de 8 bits emballés, signés ou non signés. Veuillez noter que celles-ci comparent les deux registres SSE d'entrée ou les emplacements d'adresse Élément-wise et stockent le résultat dans un registre ESS ou un emplacement de mémoire.

Les versions SSE2 de MAXPS et MINPS doivent fonctionner sur des flotteurs à double précision.

Quel drapeaux compilateur et optimisation utilisez-vous? GCC 4.0 et mieux devrait viller automatiquement les opérations si votre cible les prend en charge, des versions antérieures peuvent nécessiter un drapeau spécifique.


0 commentaires

13
votes

sse4 a Pmaxsd ou Pmaxud pour les entiers signés 32 bits / non signés, ce qui pourrait être utile.

sse2 a maxpd et maxd qui se comparent entre et entre les paires de doubles, de sorte que vous suivez n / 2-1 maxpds avec un maxSD pour obtenir le maximum d'un vecteur de n, avec l'entrelacement habituel des charges et des opérations.

Il y a des équivalents min de ce qui précède.

Pour le boîtier double, vous n'allez probablement pas mieux faire mieux en assembleur Plus d'un compilateur de C ++ à moitié décent en mode SSE: xxx

où min_max calcule min et max d'un tableau de 500 doubles 100 000 fois en utilisant une boucle naïve: < PRE> XXX


En réponse à la deuxième partie, l'optimisation traditionnelle pour éliminer la ramification d'une opération Max consiste à comparer les valeurs, à obtenir le drapeau comme un seul bit (10 ou 1), soustrayez Un (donnant 0 ou 0xFFFF_FFFF) et 'et' et 'et le' avec le Xor des deux résultats possibles, vous obtenez donc l'équivalent de (A> meilleur? (actuel_index ^ best_index): 0) ^ best_index) . Je doute qu'il y ait une simple façon de le faire, simplement parce que SSE a tendance à fonctionner sur des valeurs emballées plutôt que des valeurs marquées; Il existe certaines opérations d'index horizontales, de sorte que vous pourriez essayer de trouver le maximum, puis soustrayez-la de tous les éléments du vecteur d'origine, puis collectez le bit de signalisation et le zéro signé correspondrait à l'index du max, mais cela serait probablement ne pas être une amélioration à moins que vous utilisiez des shorts ou des octets.



2
votes

Si vous utilisez Intel's bibliothèque IPP Vous pouvez utiliser le vecteur Fonctions statistiques pour calculer Vecteur min / max (entre autres)


0 commentaires

2
votes

En réponse à votre deuxième question: sur la plupart des plates-formes, il existe des bibliothèques qui contenaient déjà des implémentations optimisées de cette opération très opérationnelle (et la plupart des autres opérations de vecteur simples). les utiliser .

  • sur OS X, il y a vdsp_maxvid () et cblas_idamax () dans l'accélération.framework
  • Les compilateurs Intel incluent les bibliothèques IPP et MKL, qui ont des implémentations de performances élevées, y compris cblas_idamax ()
  • la plupart des systèmes Linux auront cblas_idamax () dans la bibliothèque BLAS, qui peut être bien réglé en fonction de sa provenance; Les utilisateurs qui se soucient de la performance auront généralement une bonne implémentation (ou peuvent être convaincus d'installer un)
  • Si tout échoue, vous pouvez utiliser Atlas (logiciel algébrique linéaire automatique) pour obtenir une implémentation de performance décente sur la plate-forme cible

0 commentaires

-1
votes

En réponse à votre deuxième question, il peut être intéressant de penser à la façon dont vous collectez et stockez ces données.

Vous pouvez stocker les données dans un arbre B qui maintient les données triées à tout moment, nécessitant uniquement les opérations de comparaison logarithmiques.

alors vous savez à tout moment où le maximum est.

http://fr.wikipedia.org/wiki/b_tree


1 commentaires

Puisque vous traitez seulement 300 doubles, un arbre binaire auto-équilibré est probablement préférable. EN.Wikipedia.org/wiki/Self --Balancer_binaire_search_tree



1
votes

mise à jour: je viens de vous rendre compte que vous avez dit "tableau", pas "Vector" dans la partie 2. Je vais laisser cela ici quand même si cela sera utile.


RE: Trouvez l'index de la Élément max / min dans un vecteur SSE: P>


0 commentaires