x86 max/min asm instructions?

Question

¿Hay alguna instrucción asm que pueda acelerar el cálculo de min/max del vector de dobles/enteros en la arquitectura Core i7?

Actualización:

No esperaba este tipo de respuestas ricas, gracias. Entonces veo que es posible hacer un máximo/mínimo sin ramificar. Tengo una sub-pregunta:

¿Hay una manera eficiente de obtener el índice del doble más grande en la matriz?

Answer 1

SSE4 tiene PMAXSD o para enteros de 32 bits con signo/sin signo, que pueden ser útiles.

SSE2 tiene MAXPD y MAXSD que comparan entre ya través de pares de dobles, por lo que sigue n/2-1 MAXPDs con una MAXSD para obtener el máximo de un vector de n, con el entrelazado habitual de cargas y operaciones.

Hay MIN equivalentes de los anteriores.

Para el doble caso, es probable que no va a hacer mejor en ensamblador que un compilador de C de media decente ++ en modo SSE:

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 

donde min_max calcula mínimo y máximo de una matriz de 500 dobles 100.000 veces usando un bucle ingenua:

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 respuesta a la segunda parte, la optimización tradicional para eliminar la ramificación de una operación máx es comparar los valores, conseguir la bandera como un cantar le bit (dando 0 o 1), resta uno (dando 0 o 0xffff_ffff) y 'y' con el xor de los dos resultados posibles, por lo que obtienes el equivalente de (a > best ? (current_index^best_index) : 0)^best_index). Dudo que haya una forma sencilla de SSE de hacerlo, simplemente porque SSE tiende a operar en valores empaquetados en lugar de valores etiquetados; hay algunas operaciones de índice horizontal, por lo que podría intentar encontrar el máximo, luego restarlo de todos los elementos en el vector original, luego juntar el bit de signo, y el cero con signo correspondería al índice del máximo, pero eso probablemente no ser una mejora a menos que estuvieras usando cortos o bytes.

Answer 2

MAXPS y MINPS de SSE funcionan en números de coma flotante de precisión simple empaquetados. PMAXSW, PMINSW, PMAXUB y PMINUB operan todos en palabras empaquetadas de 8 bits, ya sea con o sin firma. Tenga en cuenta que estos comparan los dos registros SSE de entrada o las ubicaciones de direcciones en función de los elementos y almacenan el resultado en un registro SSE o ubicación de memoria.

Las versiones SSE2 de MAXPS y MINPS deberían funcionar en flotadores de doble precisión.

¿Qué indicadores de compilación y optimización está utilizando? gcc 4.0 y mejor deberían vectorizar automáticamente las operaciones si su destino las admite, las versiones anteriores pueden necesitar un indicador específico.

Answer 3

si su están utilizando IPP biblioteca de Intel puede utilizar el vector statistical functions para calcular el vector min/max (entre otras cosas)

Answer 4

En respuesta a la segunda pregunta: en la mayoría de plataformas, hay bibliotecas que ya contenían optimizados implementaciones de esta misma operación (y la mayoría de otras operaciones simples de vectores). Úselos.

• En OS X, no es vDSP_maxviD() y cblas_idamax() en el Accelerate.framework
• Los compiladores de Intel incluyen las bibliotecas IPP y MKL, que tienen implementaciones de alto rendimiento, incluyendo los sistemas de cblas_idamax()
• La mayoría de Linux tendrán cblas_idamax() en la biblioteca BLAS, que puede o no estar bien ajustada según su procedencia; los usuarios que se preocupan por el rendimiento generalmente tendrán una buena implementación (o pueden persuadirlos para instalar uno)
• Si todo lo demás falla, puede usar ATLAS (software de álgebra lineal sintonizado automáticamente) para obtener una implementación de rendimiento decente en la plataforma de destino

Answer 5

En respuesta a su segunda pregunta, puede valer la pena pensar en la forma en que recopila y almacena esta información.

Puede almacenar los datos en un B-tree que mantiene los datos ordenados en todo momento, requiriendo solo operaciones de comparación logarítmica.

Entonces usted sabe en todo momento dónde está el máximo.

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

Answer 6

Actualización: Me he dado cuenta de que has dicho "matriz", no "vector" en la parte 2. voy a dejar esto aquí de todos modos, en caso de que sea útil.

---

re: segunda parte: encontrar el índice del elemento max/min en un vector de SSE:

• Haz un máximo horizontal. Para un vector 128b de 2 double elementos, es solo un shufpd + maxpd para dejar el resultado transmitido a ambos elementos.

  Para otros casos, por supuesto tomará más pasos. Consulte Fastest way to do horizontal float vector sum on x86 para obtener ideas, en reemplazo de addps con maxps o minps. (Pero tenga en cuenta que el entero de 16 bits es especial, porque puede usar SSE4 phminposuw. Para máx., Restar de 255)

• Realice una comparativa compactada entre el vector original y el vector donde cada elemento es el máximo.

  (pcmpeqq patrones de bits enteros o el cmpeqpd normal ambos funcionarían para el caso double).

• int _mm_movemask_pd (__m128d a) (movmskpd) para obtener el resultado de comparación como un mapa de bits entero.
• bit-scan (bsf) para el (primer) partido: index = _bit_scan_forward(cmpmask). cmpmask = 0 es imposible si usaste comparaciones enteras (porque al menos un elemento coincidirá incluso si son NaN).

Esto debería compilar a solo 6 instrucciones (incluyendo un movapd). Sí, acabo de comprobar en the Godbolt compiler explorer y lo hace, con 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); 
} 

Tenga en cuenta que _mm_max_pd is not commutative with NaN inputs.Si NaN es posible, y no le importa el rendimiento en Intel Nehalem, puede considerar usar _mm_cmpeq_epi64 para comparar patrones de bits. Sin embargo, el retraso de bypass de float a vec-int es un problema en Nehalem.

NaN! = NaN en el punto flotante IEEE, por lo que la máscara de resultado _mm_cmpeq_pd podría ser cero en el caso de todos NaN.

Otra cosa que puede hacer en el caso de 2 elementos para obtener siempre un 0 o 1 es reemplazar el bit-scan con cmpmask >> 1. (bsf es raro con input = all-zero).