Suma redukcja niepodpisane bajtów bez przelewu, za pomocą SSE2 na Intel

Question

Próbuję znaleźć zmniejszenie sumy 32 elementów (każdy bajt danych 1) na i3 procesorem Intel. Zrobiłem to:

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

Jednak jego biorąc więcej czasu, ponieważ moja aplikacja jest aplikacją w czasie rzeczywistym wymagające znacznie mniej czasu. Należy pamiętać, że ostateczna suma może być więcej niż 255.

Czy istnieje sposób można zaimplementować to przy użyciu niskiego poziomu instrukcji SIMD SSE2? Niestety nigdy nie używałem SSE. Próbowałem w tym celu wyszukać funkcję sse2, ale nie jest ona również dostępna. Czy jest to (s) gwarantowane zmniejszenie czasu obliczeń dla tak małych problemów?

Jakieś sugestie?

Uwaga: ja wdrożyły podobne algorytmy wykorzystaniem OpenCL i CUDA i pracował wielki, ale tylko wtedy, gdy wielkość problemem była duża. W przypadku małych problemów koszt dodatkowych kosztów był większy. Nie wiem, jak to działa na SSE

Answer 1

można nadużywać PSADBW szybko obliczyć małych sum poziomych.

Coś jak to: (nie badane)

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 

---

próba wersja intrinsics:

nigdy nie używam intrinsics więc ten kod prawdopodobnie nie ma sensu w ogóle. Demontaż wyglądał jednak dobrze.

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

Jest nieco rozwlekły, ale w dalszym ciągu powinno być co najmniej 2x szybsze niż kod skalarnego:

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); 
} 

Zauważ, że a[] musi być 16 bajty.

Prawdopodobnie można poprawić na powyższym kodzie, używając _mm_hadd_epi16.