Calcola la differenza assoluta tra interi senza segno utilizzando SSE

Question

In C esiste una tecnica senza ramo per calcolare la differenza assoluta tra due valori non firmati? Ad esempio, date le variabili a e b, vorrei il valore 2 per i casi in cui a = 3, b = 5 o b = 3, a = 5. Idealmente mi piacerebbe anche essere in grado di vettorializzare il calcolo usando i registri SSE.

Answer 1

max(i,j) - min(i,j) 
(i>j)*(i-j) + (j>i)*(j-i) 

si può certamente utilizzare SSE registra, ma compilatore può fare questo per voi in ogni modo

Answer 2

Ci sono diversi modi per farlo, mi limiterò a citare uno:

SSE4

• Utilizzare PMINUD e PMAXUD per separare il valore maggiore nel registro # 1 e il valore minore nel registro # 2.
• Sottrarli.

MMX/SSE2

• flip il bit di segno dei due valori, perché l'istruzione successiva solo accetta firmato confronto intero.
• PCMPGTD. Usa questo risultato come maschera.
• Calcolare i risultati di entrambi (a-b) e (b-a)
• Usa POR (PAND (mask, a-b), PANDN (mask, b-a)) per selezionare il valore corretto per la differenza assoluta.

Answer 3

Prova questo (presuppone 2 ° complementi, che è judgning OK dal fatto che stai chiedendo SSE):

int d = a-b; 
int ad = ((d >> 30) | 1) * d; 

Spiegazione: segno-bit (bit 31) viene propagato fino al 1 ° po. il | 1 parte assicura che il moltiplicatore sia 1 o -1. Le moltiplicazioni sono veloci sulle moderne CPU.

Answer 4

calcolare la differenza e riportare il valore assoluto

__m128i diff = _mm_sub_epi32(a, b); 
__m128i mask = _mm_xor_si128(diff, a); 
mask = _mm_xor_si128(mask, b); 
mask = _mm_srai_epi32(mask, 31); 
diff = _mm_xor_si128(diff, mask); 
mask = _mm_srli_epi32(mask, 31); 
diff = _mm_add_epi32(diff, mask); 

Ciò richiede uno meno che usando l'operazione firmato confrontare op, e produce meno pressione registro.

Stessa quantità di pressione di registro come prima, 2 ulteriori operazioni, ramo migliore e unione di catene di dipendenze, associazione delle istruzioni per la decodifica di uops e utilizzo dell'unità separato. Anche se questo richiede un carico, che potrebbe essere esaurito nella cache. Sono fuori di idee dopo questo.

__m128i mask, diff; 
diff = _mm_set1_epi32(-1<<31); // dependency branch after 
a = _mm_add_epi32(a, diff); // arithmetic sign flip 
b = _mm_xor_si128(b, diff); // bitwise sign flip parallel with 'add' unit 
diff = _mm_xor_si128(a, b); // reduce uops, instruction already decoded 
mask = _mm_cmpgt_epi32(b, a); // parallel with xor 
mask = _mm_and_si128(mask, diff); // dependency merge, branch after 
a = _mm_xor_si128(a, mask); // if 2 'bit' units in CPU, parallel with next 
b = _mm_xor_si128(b, mask); // reduce uops, instruction already decoded 
diff = _mm_sub_epi32(a, b); // result 

Dopo aver cronometrato ogni versione con 2 milioni di iterazioni su un Core2Duo, le differenze sono incommensurabili. Quindi scegli ciò che è più facile da capire.

Answer 5

SSE2:

sembra essere circa la stessa velocità come seconda funzione di Phernost. A volte GCC lo pianifica per essere un ciclo completo più veloce, altre volte un po 'più lento.

__m128i big = _mm_set_epi32(INT_MIN, INT_MIN, INT_MIN, INT_MIN); 

a = _mm_add_epi32(a, big); // re-center the variables: send 0 to INT_MIN, 
b = _mm_add_epi32(b, big); // INT_MAX to -1, etc. 
__m128i diff = _mm_sub_epi32(a, b); // get signed difference 
__m128i mask = _mm_cmpgt_epi32(b, a); // mask: need to negate difference? 
mask = _mm_andnot_si128(big, mask); // mask = 0x7ffff... if negating 
diff = _mm_xor_si128(diff, mask); // 1's complement except MSB 
diff = _mm_sub_epi32(diff, mask); // add 1 and restore MSB 

SSSE3:

sempre in modo leggermente più veloce del precedente. Vi sono molte variazioni a seconda di come vengono dichiarate le cose al di fuori del ciclo. (Ad esempio, rendendo a e bvolatile rende le cose più veloci! Sembra essere un effetto casuale sulla pianificazione.) Ma questo è costantemente più veloce di un ciclo o così.

__m128i big = _mm_set_epi32(INT_MIN, INT_MIN, INT_MIN, INT_MIN); 

a = _mm_add_epi32(a, big); // re-center the variables: send 0 to INT_MIN, 
b = _mm_add_epi32(b, big); // INT_MAX to -1, etc. 
__m128i diff = _mm_sub_epi32(b, a); // get reverse signed difference 
__m128i mask = _mm_cmpgt_epi32(b, a); // mask: need to negate difference? 
mask = _mm_xor_si128(mask, big); // mask cannot be 0 for PSIGND insn 
diff = _mm_sign_epi32(diff, mask); // negate diff if needed 

SSE4 (thx rwong):

Non è possibile testare questo.

__m128i diff = _mm_sub_epi32(_mm_max_epu32(a, b), _mm_min_epu32(a, b)); 

Answer 6

Ehm ... la sua abbastanza facile ...

int diff = abs(a - b); 

facilmente vectorisable (Uso SSE3 come):

__m128i sseDiff = _mm_abs_epi32(_mm_sub_epi32(a, b)); 

a e b sono numeri interi senza segno. Considera a = 0 eb = 0xffffffff. La differenza assoluta corretta è 0xffffffff, ma la soluzione fornirà 1.

Answer 7

A partire da tommesani.com, una soluzione per questo problema consiste nell'utilizzare due volte la sottrazione senza segno.

Come la sottrazione saturazione non va mai sotto lo 0, si calcola: r1 = (ab) .saturating r2 = (ba) .saturating

Se a è maggiore di b, r1 conterrà la risposta, e r2 sarà 0 e viceversa per b> a. OR i due risultati parziali insieme daranno il risultato desiderato.

In base a the VTUNE users manual, PSUBUSB/PSUBUSW è disponibile per i registri a 128 bit, quindi è necessario essere in grado di ottenere un sacco di parallelizzazione in questo modo.

Answer 8

Uno o più dei seguenti risultati generano codice senza ramo, a seconda della macchina e del compilatore, poiché le espressioni condizionali sono tutte molto semplici.

Non ho ricevuto tutte le risposte di sse ma probabilmente alcuni dei seguenti sono rappresentati nel codice vettoriale; certamente tutti i sotto sono vettorizzabili (se si ha il paragone senza segno per cominciare, o si falsi passando prima al msb). Ho pensato che sarebbe stato utile avere delle risposte scalari pratiche alla domanda.

unsigned udiff(unsigned a, unsigned b) 
{ 
     unsigned result = a-b; // ok if a<b; 
     if(a <b) result = -result; 
     return result; 
} 
unsigned udiff(unsigned a, unsigned b) 
{ 
     unsigned n =(a<b)? (unsigned)-1 : 0u; 
     unsigned result = a-b; 
     return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF 
} 


unsigned udiff(unsigned a, unsigned b) 
{ 
     unsigned axb = a^b; 
     if(a < b) axb = 0; 
     return (axb^b) - (axb^a); // a-b, or b-a 
} 

Ciò funziona su x86_64 (o qualcosa in cui temps a 64 bit sono fondamentalmente liberi)

unsigned udiff(unsigned a, unsigned b) 
{ 
     unsigned n= (unsigned)( 
     (long long)((unsigned long long)a - (unsigned long long)b)>>32 
        ); // same n as 2nd example 
     unsigned result = a-b; 
     return (result^n)-n; // 'result' if n = 0; '-result' if n = 0xFFFFFFFF 
}