Оптимизация перебора битов в обратном порядке с использованием Intel intrinsics

Question

Некоторое время назад я оптимизировал функцию radix2 с использованием встроенных функций SSE, и я почти близок к производительности FFTW. Итак, мой следующий шаг - оптимизировать функцию обратного переупорядочения бит, которую я нашел с помощью конечно, оригинальный код, и я хочу его оптимизировать. Оригинальный код следующим образом:

void bit_reverse_reorder(float *x,float *y, int N) 
{ 
    int bits=0; 
    int i, j, k; 
    float tempr, tempi; 
    //MAXPOW = 12 

    for (i=0; i<MAXPOW; i++) 
     if (pow_2[i]==N) bits=i; 

    for (i=0; i<N; i++) 
    { 
     j=0; 
     for (k=0; k<bits; k++) 
     if (i&pow_2[k]) j+=pow_2[bits-k-1]; 
     if (j>i) 
     { 
     tempr=x[i]; 
     tempi=y[i]; 
     x[i]=x[j]; 
     y[i]=y[j]; 
     x[j]=tempr; 
     y[j]=tempi; 
     } 
    } 
} 

int main() 
{ 
    radix2(re,im,N); 

    bit_reverse_reorder(re,im,N); 
} 

PS: pow_2 [] представляет собой массив, содержащий предварительно вычисленное полномочия 2 (1,2,4,8,16,32, ...), N является число элементов = 4096, * x и * y представляет соответственно действительную и мнимую части каждого элемента входных данных.

Radix2 генерирует результаты, которые не упорядочены, поэтому заявленная функция изменит порядок результата.

Прежде всего, я не совсем понял, как работает бит-бит! Итак, я думаю, было бы хорошо, если бы кто-нибудь дал мне подсказки о том, как эта функция работает.

Во-вторых, я намерен использовать встроенные функции SSE для повышения производительности этой функции, есть ли какой-либо вектор из двух инструкций, которые могут быть использованы в цикле обмена?

Answer 1

Основываясь на ваших предложениях, я сделал пару модификаций, которые повысили производительность функции.

Во-первых, я заменил вызовы power_2 [], изменив инструкции.

Затем я создал функцию свопинга, которая использует операции добавления/подстановки для замены без использования третьей переменной.

void swap(float* a, float* b) 
{ 
*a = *a+*b; 
*b = *a-*b; 
*a = *a-*b; 
} 

void bit_reverse_reorder(float *x,float *y, int N) 
{ 
    int bits=0; 
    int i, j, k; 
    unsigned pow_bits=0; 

    for (i=0; i<MAXPOW; i++) 
     if (1 << i==N) bits=i-1; 
     for (i=1; i<N; i++) 
     { 
      j=0; 
      unsigned pow_2k=0,pow_2kj; 

      for (k=0; k<bits; k++) 
      { 
      pow_2k = 1<<k; 
      pow_2kj = 1<<(bits-k); 
      if (i&pow_2k) j+=pow_2kj; 
      } 
      if (j>i) 
      { 
      swap(&x[i],&x[j]); 
      swap(&y[i],&y[j]); 
      } 
     } 
} 

Число циклов сокращено с почти 500 000 циклов до примерно 180 000 циклов.

Answer 2

Благодаря @nwellnhof комментировать я сделал еще одну модификацию функции свопинга следующим образом:

void bit_reverse_reorder(float *x,float *y, int N) 
{ 
    unsigned i,j; 
    for (i = 0, j = 0; i < N; i++) { 
     if (i < j) 
     { 
     float tmpx = x[i]; 
     x[i] = x[j]; 
     x[j] = tmpx; 

     float tmpy = y[i]; 
     y[i] = y[j]; 
     y[j] = tmpy; 
     } 
     unsigned bit = ~i & (i + 1); 

     unsigned rev = (N/2)/bit; 

     j ^= (N - 1) & ~(rev - 1); 
    } 
} 

И теперь я получаю производительность 54 900 циклов для для цикла внутри функции, которая тоже хорошо :)