I have a code that computes butterflies and from a little profiling I found out that it is a little bit slow. So, it seemed that the better way to optimize its performance is vectorizing it using Intel SIMD Intrinsics.

This is the scalar version of the code that I want to optimize:

float bfly0_re, bfly1_re, bfly2_re, bfly3_re;
float bfly0_im, bfly1_im, bfly2_im, bfly3_im;
float x_n2, x_N2, x_N2_2, x_N2_3;
float y_n2, y_N2, y_N2_2, y_N2_3;
float a_c_add_re, a_c_add_im, a_c_sub_re, a_c_sub_im;
float b_d_add_re, b_d_add_im, b_d_sub_im, b_d_sub_re;

x_n2 =      x[n2];
x_N2 =      x[N2];
x_N2_2 =    x[N2_2];
x_N2_3 =    x[N2_3];

y_n2 =      y[n2];
y_N2 =      y[N2];
y_N2_2 =    y[N2_2];
y_N2_3 =    y[N2_3];

ADD(a_c_add_re, x_n2, x_N2_2)//ADD(res,op1,op2){res=op1+op2}
ADD(a_c_add_im, y_n2, y_N2_2)
SUB(a_c_sub_re, x_n2, x_N2_2)//SUB(res,op1,op2){res=op1-op2}
SUB(a_c_sub_im, y_n2, y_N2_2)
ADD(b_d_add_re, x_N2, x_N2_3)
ADD(b_d_add_im, y_N2, y_N2_3)
SUB(b_d_sub_im, y_N2, y_N2_3)
SUB(b_d_sub_re, x_N2, x_N2_3)

ADD(bfly0_re, a_c_add_re, b_d_add_re)
ADD(bfly0_im, a_c_add_im, b_d_add_im)
ADD(bfly1_re, a_c_sub_re, b_d_sub_im)
SUB(bfly1_im, a_c_sub_im, b_d_sub_re)
SUB(bfly2_re, a_c_add_re, b_d_add_re)
SUB(bfly2_im, a_c_add_im, b_d_add_im)
SUB(bfly3_re, a_c_sub_re, b_d_sub_im)
ADD(bfly3_im, a_c_sub_im, b_d_sub_re)

And Then this is the SIMD version that I intend to use:

__m128 Xn2_vec,XN22_vec;
__m128 YN2_vec,YN22_vec;

__m128 YXN2_vec,YXN23_vec;
__m128 XYN2_vec,XYN23_vec;

__m128 A_vec,B_vec,C_vec,D_vec;
__m128 bfly_iv,bfly_rv;

/*A_vec = {a_c_add_re, a_c_sub_re, a_c_add_re, a_c_sub_re}*/
Xn2_vec  = _mm_broadcast_ps(X[n2]);
XN22_vec = _mm_broadcast_ps(X[N22]);
A_vec    = _mm_addsub_ps   (Xn2_vec,XN22_vec); 

/*C_vec = {a_c_add_im, a_c_sub_im, a_c_add_im, a_c_sub_im}*/
Xn2_vec  = _mm_broadcast_ps(Y[n2]);
XN22_vec = _mm_broadcast_ps(Y[N22]);
C_vec    = _mm_addsub_ps   (Yn2_vec,YN22_vec);

/*B_vec = {b_d_add_re, b_d_sub_im, b_d_add_re, b_d_sub_im}*/
YXN2_vec  = _mm_set_ps   (X[N2], Y[N2], X[N2], Y[N2] );
YXN23_vec = _mm_set_ps   (X[N23],Y[N23],X[N23],Y[N23]);
B_vec     = _mm_addsub_ps(YXN2_vec,YXN23_vec);

/*D_vec = {b_d_add_im, b_d_sub_re, b_d_add_im, b_d_sub_re}*/
XYN2_vec  = _mm_shuffle_ps(YXN2_vec, YXN2_vec, _MM_SHUFFLE(2,3,0,1));
XYN23_vec = _mm_shuffle_ps(YXN23_vec,YXN23_vec,_MM_SHUFFLE(2,3,0,1));
D_vec     = _mm_addsub_ps(XYN2_vec,XYN23_vec);

bfly_rv   = _mm_addsub_ps(A_vec, B_vec);
bfly_iv   = _mm_addsub_ps(C_vec, D_vec);
/*Then Do another shuffling instructions on the butterflies to reorder them*/

n2, N2, N22, N23 are just indices because the values are not contiguous. I am using a Haswell architecture.

Here are my questions:

  • Is this code worth optimizing or not, knowing that it is repeated more than 1000 times?

  • Shall I use the _mm_load1_ps() instead of the _mm_broadcast_ps()intrinsic, or is there no difference?

  • Do you think that there is a better way of doing it?

  • 2
    \$\begingroup\$ Did you compare your code against your compiler's own vectorisation? I usually find that the latter comfortably beats my own attempts, without the maintenance penalty of per-target source code - and it may improve without any work just by upgrading the compiler. It sometimes helps to add a #pragma omp simd. \$\endgroup\$ – Toby Speight Jul 12 '17 at 13:24
  • \$\begingroup\$ Well, what if I decided to use different compilers or different hardware ... So, I think that it well not be possible to use it. \$\endgroup\$ – A.nechi Jul 12 '17 at 13:51
  • \$\begingroup\$ Not sure what you mean - using the compiler's own vectorisation means you can build for different platforms without re-writing your code. Why do you say it might be "not possible"? \$\endgroup\$ – Toby Speight Jul 12 '17 at 14:28
  • \$\begingroup\$ Oh ... ok, I misunderstood you. \$\endgroup\$ – A.nechi Jul 12 '17 at 14:37
  • 1
    \$\begingroup\$ Are you compiling with an OpenMP-capable compiler (such as gcc -fopenmp)? I think it needs to support OpenMP 4.0 to have the simd directive. If that's not an option for you, it may well be instructive to compile with -march=native -O3 (or similar) and inspect the generated assembly. \$\endgroup\$ – Toby Speight Jul 13 '17 at 15:08

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.