What is the fastest way for adding the vector elements horizontally in odd order?

Question

According to this question I implemented the horizontal addition this time 5 by 5 and 7 by 7. It does the job correctly but it is not fast enough. Can it be faster than what it is? I tried to use hadd and other instruction but the improvement is restricted. For examlple, when I use _mm256_bsrli_epi128 it is slightly better but it needs some extra permutation that ruins the benefit because of the lanes. So the question is how it should be implemented to gain more performance. The same story is for 9 elements, etc.

This adds 5 elements horizontally and puts the results in places 0, 5, and 10:

//it put the results in places 0, 5, and 10 
inline __m256i _mm256_hadd5x5_epi16(__m256i a  )
{
    __m256i a1, a2, a3, a4;

    a1 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 1 * 2);
    a2 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 2 * 2); 
    a3 = _mm256_bsrli_epi128(a2, 2);
    a4 = _mm256_bsrli_epi128(a3, 2);

    return _mm256_add_epi16(_mm256_add_epi16(_mm256_add_epi16(a1, a2), _mm256_add_epi16(a3, a4)) , a );
}

And this adds 7 elements horizontally and puts the results in places 0 and 7:

inline __m256i _mm256_hadd7x7_epi16(__m256i a  )
{
    __m256i a1, a2, a3, a4, a5, a6;

    a1 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 1 * 2);
    a2 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 2 * 2);
    a3 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 3 * 2);
    a4 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 4 * 2);
    a5 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 5 * 2);
    a6 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 6 * 2);

    return _mm256_add_epi16(_mm256_add_epi16(_mm256_add_epi16(a1, a2), _mm256_add_epi16(a3, a4)) ,  _mm256_add_epi16(_mm256_add_epi16(a5, a6), a ));
}

Answer 1

Indeed it is possible calculate these sums with less instructions. The idea is to accumulate the partial sums not only in columns 10, 5 and 0, but also in other columns. This reduces the number of vpaddw instructions and the number of 'shuffles' compared to your solution.

#include <stdio.h>
#include <x86intrin.h>
/*  gcc -O3 -Wall -m64 -march=haswell hor_sum5x5.c   */
int print_vec_short(__m256i x);
int print_10_5_0_short(__m256i x);
__m256i _mm256_hadd5x5_epi16(__m256i a  );
__m256i _mm256_hadd7x7_epi16(__m256i a  );

int main() {
   short x[16];

   for(int i=0; i<16; i++) x[i] = i+1;   /* arbitrary initial values */

   __m256i t0     = _mm256_loadu_si256((__m256i*)x);                              
   __m256i t2     = _mm256_permutevar8x32_epi32(t0,_mm256_set_epi32(0,7,6,5,4,3,2,1));
   __m256i t02    = _mm256_add_epi16(t0,t2);
   __m256i t3     = _mm256_bsrli_epi128(t2,4);    /* byte shift right */
   __m256i t023   = _mm256_add_epi16(t02,t3);
   __m256i t13    = _mm256_srli_epi64(t02,16);    /* bit shift right  */
   __m256i sum    = _mm256_add_epi16(t023,t13);

   printf("t0  = ");print_vec_short(t0  );
   printf("t2  = ");print_vec_short(t2  );
   printf("t02 = ");print_vec_short(t02 );
   printf("t3  = ");print_vec_short(t3  );
   printf("t023= ");print_vec_short(t023);
   printf("t13 = ");print_vec_short(t13 );
   printf("sum = ");print_vec_short(sum );


   printf("\nVector elements of interest: columns  10, 5, 0:\n");
   printf("t0  [10, 5, 0]  = ");print_10_5_0_short(t0  );
   printf("t2  [10, 5, 0]  = ");print_10_5_0_short(t2  );
   printf("t02 [10, 5, 0]  = ");print_10_5_0_short(t02 );
   printf("t3  [10, 5, 0]  = ");print_10_5_0_short(t3  );
   printf("t023[10, 5, 0]  = ");print_10_5_0_short(t023);
   printf("t13 [10, 5, 0]  = ");print_10_5_0_short(t13 );
   printf("sum [10, 5, 0]  = ");print_10_5_0_short(sum );


   printf("\nSum with _mm256_hadd5x5_epi16(t0)\n");
   sum = _mm256_hadd5x5_epi16(t0);
   printf("sum [10, 5, 0]  = ");print_10_5_0_short(sum );

   /* now the sum of 7 elements: */
   printf("\n\nSum of short ints 13...7 and short ints 6...0:\n");

   __m256i t      = _mm256_loadu_si256((__m256i*)x);                              
           t0     = _mm256_permutevar8x32_epi32(t0,_mm256_set_epi32(3,6,5,4,3,2,1,0));
           t0     = _mm256_and_si256(t0,_mm256_set_epi16(0xFFFF,0,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,   0,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF,0xFFFF));
   __m256i t1     = _mm256_alignr_epi8(t0,t0,2);
   __m256i t01    = _mm256_add_epi16(t0,t1);
   __m256i t23    = _mm256_alignr_epi8(t01,t01,4);
   __m256i t0123  = _mm256_add_epi16(t01,t23);
   __m256i t4567  = _mm256_alignr_epi8(t0123,t0123,8);
   __m256i sum08  = _mm256_add_epi16(t0123,t4567);      /* all elements are summed, but another permutation is needed to get the answer at position 7 */
           sum    = _mm256_permutevar8x32_epi32(sum08,_mm256_set_epi32(4,4,4,4,4,0,0,0));

   printf("t     = ");print_vec_short(t     );
   printf("t0    = ");print_vec_short(t0    );
   printf("t1    = ");print_vec_short(t1    );
   printf("t01   = ");print_vec_short(t01   );
   printf("t23   = ");print_vec_short(t23   );
   printf("t0123 = ");print_vec_short(t0123 );
   printf("t4567 = ");print_vec_short(t4567 );
   printf("sum08 = ");print_vec_short(sum08 );
   printf("sum   = ");print_vec_short(sum   );

   printf("\nSum with _mm256_hadd7x7_epi16(t)     (the answer is in column 0 and in column 7)\n");
   sum = _mm256_hadd7x7_epi16(t);
   printf("sum   = ");print_vec_short(sum   );


   return 0;
}



inline __m256i _mm256_hadd5x5_epi16(__m256i a  )
{
    __m256i a1, a2, a3, a4;

    a1 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 1 * 2);
    a2 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 2 * 2); 
    a3 = _mm256_bsrli_epi128(a2, 2);
    a4 = _mm256_bsrli_epi128(a3, 2);

    return _mm256_add_epi16(_mm256_add_epi16(_mm256_add_epi16(a1, a2), _mm256_add_epi16(a3, a4)) , a );
}


inline __m256i _mm256_hadd7x7_epi16(__m256i a  )
{
    __m256i a1, a2, a3, a4, a5, a6;

    a1 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 1 * 2);
    a2 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 2 * 2);
    a3 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 3 * 2);
    a4 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 4 * 2);
    a5 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 5 * 2);
    a6 = _mm256_alignr_epi8(_mm256_permute2x128_si256(a, _mm256_setzero_si256(), 0x31), a, 6 * 2);

   return _mm256_add_epi16(_mm256_add_epi16(_mm256_add_epi16(a1, a2), _mm256_add_epi16(a3, a4)) ,  _mm256_add_epi16(_mm256_add_epi16(a5, a6), a ));
}


int print_vec_short(__m256i x){
   short int v[16];
   _mm256_storeu_si256((__m256i *)v,x);
   printf("%4hi %4hi %4hi %4hi | %4hi %4hi %4hi %4hi | %4hi %4hi %4hi %4hi  | %4hi %4hi %4hi %4hi \n",
          v[15],v[14],v[13],v[12],v[11],v[10],v[9],v[8],v[7],v[6],v[5],v[4],v[3],v[2],v[1],v[0]);
   return 0;
}

int print_10_5_0_short(__m256i x){
   short int v[16];
   _mm256_storeu_si256((__m256i *)v,x);
   printf("%4hi %4hi %4hi   \n",v[10],v[5],v[0]);
   return 0;
}

The output is:

$ ./a.out
t0  =   16   15   14   13 |   12   11   10    9 |    8    7    6    5  |    4    3    2    1 
t2  =    2    1   16   15 |   14   13   12   11 |   10    9    8    7  |    6    5    4    3 
t02 =   18   16   30   28 |   26   24   22   20 |   18   16   14   12  |   10    8    6    4 
t3  =    0    0    2    1 |   16   15   14   13 |    0    0   10    9  |    8    7    6    5 
t023=   18   16   32   29 |   42   39   36   33 |   18   16   24   21  |   18   15   12    9 
t13 =    0   18   16   30 |    0   26   24   22 |    0   18   16   14  |    0   10    8    6 
sum =   18   34   48   59 |   42   65   60   55 |   18   34   40   35  |   18   25   20   15 

Vector elements of interest: columns  10, 5, 0:
t0  [10, 5, 0]  =   11    6    1   
t2  [10, 5, 0]  =   13    8    3   
t02 [10, 5, 0]  =   24   14    4   
t3  [10, 5, 0]  =   15   10    5   
t023[10, 5, 0]  =   39   24    9   
t13 [10, 5, 0]  =   26   16    6   
sum [10, 5, 0]  =   65   40   15   

Sum with _mm256_hadd5x5_epi16(t0)
sum [10, 5, 0]  =   65   40   15   


Sum of short ints 13...7 and short ints 6...0:
t     =   16   15   14   13 |   12   11   10    9 |    8    7    6    5  |    4    3    2    1 
t0    =    8    0   14   13 |   12   11   10    9 |    0    7    6    5  |    4    3    2    1 
t1    =    9    8    0   14 |   13   12   11   10 |    1    0    7    6  |    5    4    3    2 
t01   =   17    8   14   27 |   25   23   21   19 |    1    7   13   11  |    9    7    5    3 
t23   =   21   19   17    8 |   14   27   25   23 |    5    3    1    7  |   13   11    9    7 
t0123 =   38   27   31   35 |   39   50   46   42 |    6   10   14   18  |   22   18   14   10 
t4567 =   39   50   46   42 |   38   27   31   35 |   22   18   14   10  |    6   10   14   18 
sum08 =   77   77   77   77 |   77   77   77   77 |   28   28   28   28  |   28   28   28   28 
sum   =   77   77   77   77 |   77   77   77   77 |   77   77   28   28  |   28   28   28   28 

Sum with _mm256_hadd7x7_epi16(t)     (the answer is in column 0 and in column 7)
sum   =   16   31   45   58 |   70   81   91   84 |   77   70   63   56  |   49   42   35   28