Esistono istruzioni asm che possono velocizzare il calcolo del valore minimo/massimo del vettore di doppi/interi nell'architettura Core i7?x86 max/min istruzioni asm?
Aggiornamento:
Non mi aspettavo queste risposte ricche, grazie. Quindi vedo che max/min è possibile fare senza branching. Ho una domanda secondaria:
Esiste un modo efficiente per ottenere l'indice del doppio più grande nell'array?
SSE4 ha PMAXSD o PMAXUD per numeri interi a 32 bit con segno/senza segno, che potrebbero essere utili.
SSE2 ha MAXPD e MAXSD che confrontano tra e attraverso coppie di doppio, in modo da seguire la N/2-1 MAXPDs con uno MAXSD per ottenere il massimo di un vettore di n, con il solito intreccio dei carichi e delle operazioni.
Ci sono MIN equivalenti di quanto sopra.
per il doppio caso, probabilmente non state andando a fare meglio in assembler di un ++ compiler semidecente C in modalità 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
dove min_max calcola min e max di un array di 500 camere doppie 100.000 volte utilizzando un ciclo 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;
}
In risposta alla seconda parte, l'ottimizzazione tradizionale per rimuovere ramificazione da un'operazione di massima è quello di confrontare i valori, ottenere la bandiera come cantare le bit (dando 0 o 1), sottrarre uno (dando 0 o 0xffff_ffff) e 'e' esso con lo xor dei due risultati possibili, in modo da ottenere l'equivalente di (a > best ? (current_index^best_index) : 0)^best_index). Dubito che ci sia un semplice modo per farlo, semplicemente perché l'SSE tende a operare su valori compressi piuttosto che su valori taggati; ci sono alcune operazioni sull'indice orizzontale, quindi puoi provare a trovare il massimo, quindi sottrarre quello da tutti gli elementi nel vettore originale, quindi raccogliere il bit del segno, e lo zero firmato corrisponde all'indice del massimo, ma probabilmente non essere un miglioramento a meno che non stiate usando shorts o byte.
Hai solo bisogno di log2 (vector_length) shuffle + MAXPS/MAXPD operazioni, non VL/2, per ottenere il massimo orizzontale di un singolo vettore SIMD. È fondamentalmente la stessa idea di [una somma orizzontale] (https://stackoverflow.com/questions/6996764/fastest-way-to-do-horizontal-float-vector-sum-on-x86): stretta a metà ogni volta . (O per lasciare la trasmissione del risultato a ogni elemento, scambiare alto/basso). –
Lo srotolamento con accumulatori multipli dovrebbe dare un miglioramento di velocità superiore a 2x, se non si ha un collo di bottiglia in memoria. ('MAXPD' ha una latenza di 3 o 4 cicli, ma un throughput di 1 per ciclo, quindi è necessario che il compilatore emetta asm che utilizza più vettori e li combina alla fine dell'array.) Clang tende a farlo mentre auto- vettorizzazione, ma gcc continua a non farlo. –
MAXPS e MINPS di SSE operano entrambi su numeri in virgola mobile a precisione singola. PMAXSW, PMINSW, PMAXUB e PMINUB funzionano tutti con parole a 8 bit compresse, firmate o non firmate. Si prega di notare che questi confrontano i due registri SSE di ingresso o le posizioni degli indirizzi in base agli elementi e memorizzano il risultato in un registro SSE o in una posizione di memoria.
Le versioni SSE2 di MAXPS e MINPS dovrebbero funzionare su galleggianti a precisione doppia.
Quali flag di compilazione e ottimizzazione stai utilizzando? gcc 4.0 e migliori dovrebbero automaticamente vettorializzare le operazioni se il vostro target le supporta, versioni precedenti potrebbero aver bisogno di un flag specifico.
se si sta usando la biblioteca di Intel IPP è possibile utilizzare il vettore statistical functions per calcolare vettore min/max (tra le altre cose)
In risposta alla tua seconda domanda: sulla maggior parte delle piattaforme, ci sono librerie che già contenevano ottimizzati implementazioni di questa stessa operazione (e molte altre operazioni vettoriali semplici). Utilizzali.
vDSP_maxviD() e cblas_idamax() nel Accelerate.frameworkcblas_idamax()cblas_idamax() nella libreria BLAS, che può o meno essere ottimizzata a seconda della sua provenienza; gli utenti che si preoccupano delle prestazioni generalmente hanno una buona implementazione (o possono essere persuasi di installarne uno)In risposta alla tua seconda domanda, potrebbe essere utile per te riflettere sul modo in cui raccogli e memorizzi questi dati.
È possibile memorizzare i dati in un albero B che mantenga i dati ordinati in qualsiasi momento, richiedendo solo operazioni di confronto logaritmico.
Allora sai sempre dove si trova il massimo.
Dato che hai a che fare con soli 300 doppi, un binario con bilanciamento automatico è probabilmente il migliore. http://en.wikipedia.org/wiki/Self-balancing_binary_search_tree – Drew
Perché non un heap binario? Tempo costante migliore di logaritmico ... –
Aggiornamento: Ho appena realizzato che hai detto "allineamento", non "vettore" nella parte 2. Lascio questo qui comunque nel caso in cui è utile.
Re: parte due: trovare l'indice dell'elemento max/min in un vettore di SSE:
fare un massimo orizzontale. Per un vettore 128b di 2 elementi double, è solo uno shufpd + maxpd lasciare la trasmissione dei risultati a entrambi gli elementi.
Per gli altri casi, ovviamente richiederà più passaggi. Vedere Fastest way to do horizontal float vector sum on x86 per idee, in sostituzione di addps con maxps o minps. (Si noti che il numero intero a 16 bit è speciale, perché è possibile utilizzare SSE4 phminposuw. Per max, sottrarre da 255)
Fare un confronto a raffronto tra il vettore originale vettoriale e il vettore in cui ogni elemento è il massimo.
(pcmpeqq modelli di bit interi o il solito cmpeqpd funzionerebbero entrambi per il caso double).
int _mm_movemask_pd (__m128d a) (movmskpd) per ottenere il risultato di confronto come bitmap intero.bsf) per la (prima) corrispondenza: index = _bit_scan_forward(cmpmask). cmpmask = 0 è impossibile se si utilizza un confronto intero (poiché almeno un elemento corrisponde anche se è NaN).Questo dovrebbe compilare solo 6 istruzioni (incluso un movapd). Sì, appena controllato su the Godbolt compiler explorer e lo fa, 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);
}
Si noti che _mm_max_pd is not commutative with NaN inputs.Se NaN è possibile e non ti interessa le prestazioni su Intel Nehalem, potresti prendere in considerazione l'utilizzo di _mm_cmpeq_epi64 per confrontare i pattern di bit. Bypass-delay da float a vec-int è un problema su Nehalem, però.
NaN! = NaN in virgola mobile IEEE, pertanto la maschera dei risultati _mm_cmpeq_pd potrebbe essere azzerata nel caso di tutti i NaN.
Un'altra cosa che è possibile fare nel caso di 2 elementi per ottenere sempre uno 0 o 1 è sostituire il bit-scan con cmpmask >> 1. (bsf è strano con input = all-zero).
Qual è la lingua host? Se è c/C++ non mi preoccuperei troppo. –
massimo di circa 300 doppi è nel ciclo più interno del programma di grandi dimensioni. L'85% del tempo è trascorso in circa 10 delle 8.000 linee di codice. Il linguaggio host non ha importanza solo per questo. Ma sì, è C++ –