Qual è l’istruzione che dà FP FPmin e max su x86?

Per citare (grazie all’autore per lo sviluppo e la condivisione dell’algoritmo!):

Fast, Branchless Ray/Bounding Box Intersections

Poiché i moderni set di istruzioni a virgola mobile possono calcolare min e max senza rami

Il codice corrispondente dell’autore è giusto

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

Conosco ad esempio _mm_max_ps , ma questa è un’istruzione vettoriale. Il codice sopra ovviamente è pensato per essere usato in una forma scalare.

Domanda:

  • Cos’è l’istruzione minmax senza branch scalare su x86? È una sequenza di istruzioni?
  • È sicuro assumere che verrà applicato, o come lo chiamo?
  • Ha senso preoccuparsi della assenza di rami di min / max? Da quello che ho capito, per un software di raytracer e / o altri software, data una routine di intersezione di ray-box, non esiste un modello affidabile per il predittore del ramo da rilevare, quindi ha senso eliminare il ramo. Ho ragione su questo?
  • La cosa più importante è che l’algoritmo discusso si basa sul confronto con (+/-) INFINITY. Questo è affidabile rispetto all’istruzione (sconosciuta) di cui stiamo discutendo e allo standard in virgola mobile?

Nel caso in cui: ho familiarità con l’ uso di funzioni min e max in C ++ , credo che sia correlato, ma non proprio la mia domanda.

Solutions Collecting From Web of "Qual è l’istruzione che dà FP FPmin e max su x86?"

La maggior parte delle istruzioni FP vettoriali hanno equivalenti scalari. MINSS / MAXSS / MINSD / MAXSD sono ciò che desideri. Gestiscono +/- Infinity come ti aspetteresti.

MINSS a,b esattamente gli attrezzi (a (a secondo le regole IEEE , con tutto ciò che implica zero firmato, NaN e Infiniti. (cioè mantiene l'operando sorgente, b , su non ordinato.) Ciò significa che i compilatori possono usarli per std::min(b,a) e std::max(b,a) , perché quelle funzioni sono basate sulla stessa espressione .

MAXSS a,b esattamente implementa (b (b , di nuovo mantenendo l'operando sorgente su non ordinato. Il loop su un array con maxss xmm0, [rsi] risulterà in NaN se la matrice contiene qualsiasi NaN, propagando NaN attraverso il calcolo come è normale per altre operazioni FP. Significa anche che è ansible xmm0 con NaN (usando pcmpeqd xmm0,xmm0 ) invece di -Inf o il primo elemento dell'array; questo potrebbe semplificare la gestione di liste potenzialmente vuote.


Non provare a usare _mm_min_ss su _mm_min_ss scalari; l'intrinseco è disponibile solo con __m128 operandi __m128 e le intrinseche di Intel non forniscono alcun modo per ottenere un float scalare nell'elemento basso di un __m128 senza azzerare gli elementi alti o in qualche modo fare un lavoro extra. La maggior parte dei compilatori emetterà effettivamente le istruzioni inutili per farlo anche se il risultato finale non dipende da nulla negli elementi superiori. Non c'è niente come __m256 _mm256_castps128_ps256 (__m128 a) per lanciare un float su un __m128 con garbage negli elementi in alto. Considero questo un difetto di progettazione. : /

Ma per fortuna non è necessario farlo manualmente, i compilatori sanno come usare SSE / SSE2 min / max per te. Scrivi la tua C in modo che possano. La funzione nella tua domanda è l'ideale: come mostrato di seguito (link 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; } 

Nota il loro comportamento asimmetrico con NaN : se gli operandi non sono ordinati, dest = src (cioè prende il secondo operando se uno degli operandi è NaN). Questo può essere utile per gli aggiornamenti condizionali SIMD, vedi sotto.

(A e b sono non ordinati se uno di questi è NaN. Ciò significa che a , a==b , e a>b sono tutti falsi. Consulta la serie di articoli di Bruce Dawson su virgola mobile per molti trucchi FP .)

Gli intrinseci _mm_min_ss / _mm_min_ps corrispondenti possono o non possono avere questo comportamento, a seconda del compilatore.

Penso che gli intrinseci debbano avere la stessa semantica degli ordini operandi delle istruzioni asm, ma gcc ha trattato gli operandi su _mm_min_ps come commutativi anche senza -ffast-math per molto tempo, gcc4.4 o forse prima. GCC 7 finalmente lo ha cambiato per abbinare ICC e clang.

Il ricercatore di intrinsecamente online di Intel non documenta tale comportamento per la funzione, ma forse non dovrebbe essere esaustivo. Il manuale di asm insn ref non dice che l'intrinseco non ha quella proprietà; elenca solo _mm_min_ss come l'intrinseco di MINSS.

Quando ho "_mm_min_ps" NaN su "_mm_min_ps" NaN , ho trovato questo codice reale e qualche altra discussione sull'uso dell'intrinseca per gestire i NaN, quindi molte persone si aspettano che l'intrinseco si comporti come l'istruzione asm. (Mi è venuto in mente un codice che stavo scrivendo ieri, e stavo già pensando di scriverlo come una domanda e risposta auto-risposta).

Data l'esistenza di questo bug di lunga durata, il codice portatile che vuole sfruttare la gestione del NaN di MINPS deve prendere precauzioni. La versione standard di gcc su molte distribuzioni Linux esistenti comporrà erroneamente il tuo codice se dipende dall'ordine degli operandi a _mm_min_ps . Quindi probabilmente hai bisogno di un #ifdef per rilevare l'attuale gcc (non clang, ecc.) E un'alternativa. O fallo in modo diverso in un primo momento: / Forse con _mm_cmplt_ps e booleano AND / ANDNOT / OR.

Abilitando -ffast-math rende anche _mm_min_ps commutativo su tutti i compilatori.


Come al solito, i compilatori sanno come utilizzare il set di istruzioni per implementare correttamente la semantica C. MINSS e MAXSS sono più veloci di qualsiasi cosa tu possa fare con un ramo , quindi basta scrivere codice che possa essere compilato in uno di questi.

Il problema commutativo- _mm_min_ps si applica solo all'intrinseco: gcc sa esattamente come funziona MINSS / MINPS e li utilizza per implementare correttamente la semantica FP rigida (quando non si utilizza -ffast-math).

Di solito non è necessario fare nulla di speciale per ottenere un codice scalare decente da un compilatore. Se hai intenzione di dedicare del tempo a pensare a quali istruzioni usa il compilatore, dovresti probabilmente iniziare a vettorizzare manualmente il tuo codice se il compilatore non lo sta facendo.

(Ci possono essere rari casi in cui un ramo è il migliore, se la condizione quasi sempre va da una parte e la latenza è più importante della velocità effettiva.La latenza MINPS è ~ 3 cicli, ma un ramo perfettamente previsto aggiunge 0 cicli alla catena di dipendenze della critica sentiero.)


In C ++, usa std::min e std::max , che sono definiti in termini di > o < , e non hanno gli stessi requisiti sul comportamento NaN che fmin e fmax fanno. Evita fmin e fmax meno che tu non abbia bisogno del loro comportamento NaN.

In C, penso di scrivere le tue funzioni min e max (o macro se lo fai in modo sicuro).


C & asm sul explorer del compilatore Godbolt

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

Se vuoi usare _mm_min_ss / _mm_min_ps tu stesso, scrivi un codice che permetta al compilatore di fare bene asm anche senza -ffast-math.

Se non ti aspetti NaN, o vuoi gestirli appositamente, scrivi cose come

 lowest = _mm_min_ps(lowest, some_loop_variable); 

quindi il registro che contiene il lowest può essere aggiornato sul posto (anche senza AVX).


Approfittando del comportamento NaN di MINPS:

Dì che il tuo codice scalare è qualcosa di simile

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

Si supponga che la condizione possa essere vettorizzata con CMPPS, in modo da avere un vettore di elementi con i bit tutti impostati o tutti chiari. (O forse puoi andare via con ANDPS / ORPS / XORPS sui float direttamente, se ti interessa il loro segno e non ti importa dello zero negativo. Questo crea un valore di verità nel bit del segno, con spazzatura altrove. al bit del segno, quindi può essere molto utile oppure puoi trasmettere il bit di segno con PSRAD xmm, 31 )

Il modo diretto per implementare questo sarebbe quello di fondere x con +Inf base alla maschera di condizione. Oppure fai newval = min(lowest, x); e mescola newval in lowest . (sia BLENDVPS o AND / ANDNOT / OR).

Ma il trucco è che tutto a un bit è un NaN, e un OR bit a bit lo propagherà . Così:

 __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. 

Quindi, con solo SSE2, abbiamo eseguito un MINPS condizionale in due istruzioni aggiuntive (ORPS e MOVAPS, a meno che lo srotolamento del loop non comporti la scomparsa di MOVAPS).

L'alternativa senza SSE4.1 BLENDVPS è ANDPS / ANDNPS / ORPS da miscelare, più un MOVAPS in più. ORPS è comunque più efficiente di BLENDVPS (sono 2 uops sulla maggior parte delle CPU).

La risposta di Peter Cordes è grandiosa, ho appena pensato di entrare con alcune risposte più brevi punto per punto:

  • Cos’è l’istruzione minmax senza branch scalare su x86? È una sequenza di istruzioni?

Mi riferivo a minss / minsd . E anche altre architetture prive di tali istruzioni dovrebbero essere in grado di farlo senza branch con mosse condizionate.

  • È sicuro assumere che verrà applicato, o come lo chiamo?

gcc e clang ottimizzeranno entrambi (a < b) ? a : b (a < b) ? a : b su minss / minsd , quindi non mi preoccupo di usare intrinsecamente. Non posso parlare ad altri compilatori però.

  • Ha senso preoccuparsi della assenza di rami di min / max? Da quello che ho capito, per un software di raytracer e / o altri software, data una routine di intersezione di ray-box, non esiste un modello affidabile per il predittore del ramo da rilevare, quindi ha senso eliminare il ramo. Ho ragione su questo?

I singoli a < b test sono praticamente completamente imprevedibili, quindi è molto importante evitare la ramificazione per quelli. Test come if (ray.dir.x != 0.0) sono molto prevedibili, quindi evitare quei rami è meno importante, ma riduce le dimensioni del codice e rende più facile la vettorizzazione. La parte più importante è probabilmente la rimozione delle divisioni però.

  • La cosa più importante è che l'algoritmo discusso si basa sul confronto con (+/-) INFINITY. Questo è affidabile rispetto all'istruzione (sconosciuta) di cui stiamo discutendo e allo standard in virgola mobile?

Sì, minss / minsd comportano esattamente come (a < b) ? a : b (a < b) ? a : b , compreso il trattamento di infiniti e NaN.

Inoltre, ho scritto un post successivo a quello a cui hai fatto riferimento che parla di NaNs e min / max in modo più dettagliato.