x86 instructions asm max/min?

Question

Y a-t-il des instructions asm qui peuvent accélérer le calcul de min/max de vecteur de doubles/entiers sur l'architecture Core i7?

Mise à jour:

Je ne pensais pas ces réponses riches, je vous remercie. Donc je vois que max/min est possible de faire sans branchement. J'ai sous-question:

Existe-t-il un moyen efficace d'obtenir l'indice du plus grand double dans le tableau?

Answer 1

SSE4 a PMAXSD ou PMAXUD pour les entiers 32 bits signés/non signés, ce qui peut être utile.

SSE2 a MAXPD et MAXSD qui comparent entre et à travers 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'entrecroisement habituelle des charges et des opérations.

Il existe des équivalents MIN de ce qui précède.

pour le double cas, vous n'êtes probablement pas faire mieux en assembleur d'un C demi-décent ++ compilateur en mode ESS:

peregrino:$ g++ -O3 src/min_max.cpp -o bin/min_max 
peregrino:$ g++ -O3 -msse4 -mfpmath=sse src/min_max.cpp -o bin/min_max_sse 
peregrino:$ time bin/min_max 
0,40 

real 0m0.874s 
user 0m0.796s 
sys 0m0.004s 
peregrino:$ time bin/min_max_sse 
0,40 

real 0m0.457s 
user 0m0.404s 
sys 0m0.000s 

où min_max calcule min et max d'un tableau de 500 doubles 100.000 fois en utilisant une boucle naïve:

bool min_max (double array[], size_t len, double& min, double& max) 
{ 
    double min_value = array [ 0 ]; 
    double max_value = array [ 0 ]; 

    for (size_t index = 1; index < len; ++index) { 
     if (array [ index ] < min_value) min_value = array [ index ]; 
     if (array [ index ] > max_value) max_value = array [ index ]; 
    } 

    min = min_value; 
    max = max_value; 
} 

---

En réponse à la deuxième partie, l'optimisation traditionnelle pour éliminer les ramifications d'une opération max est de comparer les valeurs, obtenir le drapeau comme chanter le bit (donnant 0 ou 1), soustraire un (donnant 0 ou 0xffff_ffff) et 'et' avec le xor des deux résultats possibles, donc vous obtenez l'équivalent de (a > best ? (current_index^best_index) : 0)^best_index). Je doute qu'il existe une méthode SSE simple pour cela, simplement parce que SSE a tendance à opérer sur des valeurs condensées plutôt que sur des valeurs étiquetées; il y a quelques opérations d'index horizontales, donc vous pourriez essayer de trouver le maximum, puis soustraire cela de tous les éléments du vecteur original, puis rassembler le bit de signe, et le zéro signé correspondrait à l'index du maximum, mais cela ne pas être une amélioration, sauf si vous utilisiez des shorts ou des octets.

Answer 2

MAXPS et MINPS de SSE fonctionnent tous les deux sur des nombres à virgule flottante simple précision. PMAXSW, PMINSW, PMAXUB et PMINUB fonctionnent tous sur des mots compressés de 8 bits, signés ou non. Veuillez noter que ceux-ci comparent les deux registres SSE d'entrée ou les emplacements d'adresses par élément et stockent le résultat dans un registre SSE ou dans un emplacement mémoire.

Les versions SSE2 de MAXPS et MINPS devraient fonctionner sur les flotteurs à double précision. Quels drapeaux de compilateur et d'optimisation utilisez-vous? gcc 4.0 et mieux devraient automatiquement vectoriser les opérations si votre cible les supporte, les versions antérieures peuvent avoir besoin d'un drapeau spécifique.

Answer 3

si que vous utilisez la bibliothèque IPP d'Intel, vous pouvez utiliser le vecteur statistical functions pour calculer vecteur min/max (entre autres)

Answer 4

En réponse à votre deuxième question: sur la plupart des plates-formes, il existe des bibliothèques qui contenait déjà optimisés implémentations de cette opération même (et la plupart des autres opérations vectorielles simples). Utilisez-les.

• Sur OS X, il est vDSP_maxviD() et cblas_idamax() dans le Accelerate.framework
• Les compilateurs Intel comprennent les bibliothèques IPP et MKL, qui ont mises en œuvre de haute performance, y compris cblas_idamax()
• La plupart des systèmes Linux auront cblas_idamax() dans la bibliothèque BLAS, qui peut ou non être bien réglée en fonction de sa provenance; Les utilisateurs qui se soucient des performances auront généralement une bonne implémentation (ou peuvent être persuadés d'en installer un)
• Si tout le reste échoue, vous pouvez utiliser ATLAS (logiciel d'algèbre linéaire à réglage automatique) pour obtenir une implémentation de performance décente sur la plate-forme cible

Answer 5

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

Vous pouvez stocker les données dans un arbre B qui conserve les données triées en tout temps, ne nécessitant que des opérations de comparaison logarithmiques.

Ensuite, vous savez à tout moment où le maximum est.

http://en.wikipedia.org/wiki/B_tree

Answer 6

Mise à jour: Je viens de réaliser que vous avez dit « tableau », pas « vecteur » dans la partie 2. Je vais laisser ce ici de toute façon dans le cas où il est utile.

---

re: deuxième partie: trouver l'indice de l'élément max/min dans un vecteur SSE:

• Faites un maximum horizontal. Pour un vecteur 128b de 2 double éléments, c'est juste un shufpd + maxpd pour laisser le résultat diffusé aux deux éléments.

  Pour d'autres cas, il faudra bien sûr prendre plus de mesures. Voir Fastest way to do horizontal float vector sum on x86 pour des idées, en remplaçant addps avec maxps ou minps. (Mais notez que nombre entier de 16 bits est spécial, parce que vous pouvez utiliser SSE4 phminposuw. Pour max, soustraire 255)

• Faites une comparaison emballé entre le vecteur vecteur original et le vecteur où chaque élément est le max.

  (pcmpeqq les modèles de bits entiers ou les cmpeqpd habituels fonctionneraient tous les deux pour le cas double).

• int _mm_movemask_pd (__m128d a) (movmskpd) pour obtenir le résultat de la comparaison en tant que bitmap entier.
• bit-scan (bsf) pour la (première) correspondance: index = _bit_scan_forward(cmpmask). cmpmask = 0 est impossible si vous avez utilisé des nombres entiers (car au moins un élément correspond même s'ils sont NaN).

Cela devrait compiler à seulement 6 instructions (y compris un movapd). Oui, juste vérifié sur the Godbolt compiler explorer et il le fait, avec SSE.

#include <immintrin.h> 
#include <x86intrin.h> 

int maxpos(__m128d v) { 
    __m128d swapped = _mm_shuffle_pd(v,v, 1); 
    __m128d maxbcast = _mm_max_pd(swapped, v); 
    __m128d cmp = _mm_cmpeq_pd(maxbcast, v); 
    int cmpmask = _mm_movemask_pd(cmp); 
    return _bit_scan_forward(cmpmask); 
} 

Notez que _mm_max_pd is not commutative with NaN inputs.Si NaN est possible et que vous ne vous souciez pas des performances sur Intel Nehalem, vous pouvez envisager d'utiliser _mm_cmpeq_epi64 pour comparer les modèles de bits. Contournement de float à vec-int est un problème sur Nehalem, cependant.

NaN! = NaN en virgule flottante IEEE, donc le masque de résultat _mm_cmpeq_pd peut être tout à zéro dans le cas tout-NaN.

Une autre chose que vous pouvez faire dans le cas de 2 éléments pour obtenir toujours un 0 ou 1 est de remplacer le bit-scan par cmpmask >> 1. (bsf est bizarre avec entrée = tout-zéro).