Riduzione somma dei byte senza segno senza overflow, utilizzando SSE2 su Intel

Question

Sto cercando di trovare la riduzione della somma di 32 elementi (ogni 1 byte di dati) su un processore Intel i3. Ho fatto questo:

s=0; 
for (i=0; i<32; i++) 
{ 
    s = s + a[i]; 
} 

Tuttavia, richiede più tempo, poiché la mia applicazione è un'applicazione in tempo reale che richiede molto meno tempo. Si noti che la somma finale potrebbe essere superiore a 255.

Esiste un modo per implementarlo utilizzando le istruzioni SIMD SSE2 di basso livello? Purtroppo non ho mai usato SSE. Ho provato a cercare la funzione sse2 per questo scopo, ma non è disponibile. È (sse) garantito per ridurre il tempo di calcolo per problemi così piccoli?

Qualche suggerimento ??

Nota: ho implementato gli algoritmi simili utilizzando OpenCL e CUDA e questo ha funzionato bene, ma solo quando la dimensione del problema era grande. Per i problemi di piccole dimensioni il costo del sovraccarico era maggiore. Non sai come funziona su SSE

Answer 1

È possibile utilizzare lo PSADBW per calcolare rapidamente le somme orizzontali di piccole dimensioni.

Qualcosa di simile a questo: (non testato)

pxor xmm0, xmm0 
psadbw xmm0, [a + 0] 
pxor xmm1, xmm1 
psadbw xmm1, [a + 16] 
paddw xmm0, xmm1 
pshufd xmm1, xmm0, 2 
paddw xmm0, xmm1 ; low word in xmm0 is the total sum 

---

intrinseche Tentativo versione:

non ho mai utilizzare intrinseche quindi questo codice probabilmente ha alcun senso. Lo smontaggio sembrava OK però.

uint16_t sum_32(const uint8_t a[32]) 
{ 
    __m128i zero = _mm_xor_si128(zero, zero); 
    __m128i sum0 = _mm_sad_epu8(
         zero, 
         _mm_load_si128(reinterpret_cast<const __m128i*>(a))); 
    __m128i sum1 = _mm_sad_epu8(
         zero, 
         _mm_load_si128(reinterpret_cast<const __m128i*>(&a[16]))); 
    __m128i sum2 = _mm_add_epi16(sum0, sum1); 
    __m128i totalsum = _mm_add_epi16(sum2, _mm_shuffle_epi32(sum2, 2)); 
    return totalsum.m128i_u16[0]; 
} 

Answer 2

Questo è un po 'prolisso, ma dovrebbe comunque essere di almeno 2 volte più veloce rispetto al codice scalare:

uint16_t sum_32(const uint8_t a[32]) 
{ 
    const __m128i vk0 = _mm_set1_epi8(0); // constant vector of all 0s for use with _mm_unpacklo_epi8/_mm_unpackhi_epi8 
    __m128i v = _mm_load_si128(a);   // load first vector of 8 bit values 
    __m128i vl = _mm_unpacklo_epi8(v, vk0); // unpack to two vectors of 16 bit values 
    __m128i vh = _mm_unpackhi_epi8(v, vk0); 
    __m128i vsum = _mm_add_epi16(vl, vh); 
    v = _mm_load_si128(&a[16]);    // load second vector of 8 bit values 
    vl = _mm_unpacklo_epi8(v, vk0);   // unpack to two vectors of 16 bit values 
    vh = _mm_unpackhi_epi8(v, vk0); 
    vsum = _mm_add_epi16(vsum, vl); 
    vsum = _mm_add_epi16(vsum, vh); 
    // horizontal sum 
    vsum = _mm_add_epi16(vsum, _mm_srli_si128(vsum, 8)); 
    vsum = _mm_add_epi16(vsum, _mm_srli_si128(vsum, 4)); 
    vsum = _mm_add_epi16(vsum, _mm_srli_si128(vsum, 2)); 
    return _mm_extract_epi16(vsum, 0); 
} 

Nota che a[] deve essere di 16 byte allineati.

Probabilmente è possibile migliorare il codice sopra utilizzando _mm_hadd_epi16.