Почему вычисление времени БПФ короче, чем умножение элементов на элементы в Intel MKL? - PullRequest
Новая
       25

Почему вычисление времени БПФ короче, чем умножение элементов на элементы в Intel MKL?

2 голосов
/ 19 марта 2019

У меня есть вектор из 1024 * 4608 элементов ( Original_signal ), который хранится в одномерном массиве.

И я увеличил Original_signal до Expand_signal , скопировав каждые 1024 элемента 32 раза до 1024 * 32 * 4608.

Затем я использую Com_array из 1024 * 32, чтобы выполнить умножение элемента на элемент с Expand_signal и выполнить 1024FFT массива умножения после.

Основной код выглядит следующим образом: 

//initialize Original_signal
MKL_Complex8 *Original_signal = new MKL_Complex8[1024*4608];
for (int i=0; i<4608; i++)
{
  for (int j=0; j<1024; j++)
    {
      Original_signal[j+i*1024].real=rand();
      Original_signal[j+i*1024].imag=rand();
    }
 }
//Com_array
MKL_Complex8 *Com_array= new MKL_Complex8[32*1024];
for (int i=0; i<32; i++)
  {
    for (int j=0; j<1024; j++)
      {
        Com_array[j+i*1024].real=cosf(2*pi*(i-16.0)/10.0*j^2);
        Com_array[j+i*1024].imag=sinf(2*pi*(i-16.0)/10.0*j^2);
      }
  }


//element-to-element multiplication
MKL_Complex8 *Temp_signal= new MKL_Complex8[1024*32];
MKL_Complex8 *Expand_signal= new MKL_Complex8[1024*32*4608];

gettimeofday(&Bgn_Time, 0);

for (int i=0; i<4608; i++)
  {
    for (int j=0; j<32; j++)
      {
        memcpy(Temp_signal+j*1024, Original_signal+i*1024, 1024*sizeof(MKL_Complex8));
      }
      vmcMul(1024*32, Temp_signal, Com_array, Expand_signal+i32);
  }

gettimeofday(&End_Time, 0);
double time_used = (double)(End_Time.tv_sec-Bgn_Time.tv_sec)*1000000+(double)(End_Time.tv_usec-Bgn_Time.tv_usec);
printf("element-to-element multiplication use time %fus\n, time_used ");


//FFT
DFTI_DESCRIPTOR_HANDLE h_FFT = 0;
DftiCreateDescriptor(&h_FFT, DFTI_SINGLE, DFTI_COMPLEX, 1, 1024);
DftiSetValue(h_FFT, DFTI_NUMBER_OF_TRANSFORMS, 32*4608);
DftiSetValue(h_FFT, DFTI_INPUT_DISTANCE, 1024);
DftiCommitDescriptor(h_FFT);


gettimeofday(&Bgn_Time, 0);

DftiComputeForward(h_FFT,Expand_signal);

gettimeofday(&End_Time, 0);
double time_used = (double)(End_Time.tv_sec-Bgn_Time.tv_sec)*1000000+(double)(End_Time.tv_usec-Bgn_Time.tv_usec);
printf("FFT use time %fus\n, time_used ");

Время умножения элемента на элемент составляет 700 мс (после удаления стоимости memcpy), а время БПФ - 500 мс.

Комплексное умножение FFT равно N / 2log2N, а умножение элемента на элемент равно N.

В этом проекте N = 1024. БПФ в 5 раз медленнее, чем умножение элементов на элементы в теории. Почему на самом деле быстрее. *1024*

Есть ли способ ускорить проект?

(обратите внимание, что Com_array симметричен)

1 Ответ

0 голосов
/ 22 марта 2019

В этом проекте N = 1024.БПФ в 5 раз медленнее, чем умножение элементов на элементы в теории.Почему в действительности быстрее?

Как указывалось в комментариях, временная сложность БПФ дает вам относительную меру для различных длин БПФ, вплоть до некоторого постоянного коэффициента.Этот фактор становится важным при сравнении с другими вычислениями.Кроме того, в вашем анализе предполагается, что производительность ограничена операциями с плавающей запятой, где в действительности реальная производительность кажется ограниченной другими факторами, такими как обработка в особых случаях (например, NaN, Inf), доступ к памяти и кэш-памяти.

Любой способ ускорить проект?

Поскольку узкое место в вашей производительности связано со сложной поэлементной операцией умножения векторов, следующие действия будут направлены на повышение производительности этой операции.

У меня нет MKL для выполнения реальных тестов, но, вероятно, справедливо предположить, что реализация vmcMul достаточно устойчива к особым случаям, таким как NaN и Inf, и довольно оптимизирована вобстоятельства.

Если вам не требуется устойчивость к особым случаям, работа на процессоре SSE3, может гарантировать, что размеры вашего массива кратны 2, и что они выровнены по 16 байтов, тогда вы можетеполучить некоторый прирост производительности, используя упрощенную реализацию, такую ​​какowing (на основе Себастьяна ответа на другой пост ): 

#include <pmmintrin.h>
#include <xmmintrin.h>

// Computes and element-by-element multiplication of complex vectors "a" and "b" and
// stores the results in "c".
// Vectors "a", "b" and "c" must be:
//   - vectors of even length N
//   - 16-bytes aligned
// Special cases such as NaN and Inf are not handled.
//
// based on /2493757/kompleks-mul-i-div-s-ispolzovaniem-instruktsii-sse#2493768
void packed_vec_mult(int N, MKL_Complex8* a, MKL_Complex8* b, MKL_Complex8* c)
{
  int M = N/2;

  __m128* aptr = reinterpret_cast<__m128*>(a);
  __m128* bptr = reinterpret_cast<__m128*>(b);
  __m128* cptr = reinterpret_cast<__m128*>(c);
  for (int i = 0; i < M; i++)
  {
    __m128 t0 = _mm_moveldup_ps(*aptr);
    __m128 t1 = *bptr;
    __m128 t2 = _mm_mul_ps(t0, t1);
    __m128 t3 = _mm_shuffle_ps(t1, t1, 0xb1);
    __m128 t4 = _mm_movehdup_ps(*aptr);
    __m128 t5 = _mm_mul_ps(t4, t3);
    *cptr = _mm_addsub_ps(t2, t5);

    ++aptr;
    ++bptr;
    ++cptr;
  }
}

Как только умножение оптимизировано, ваша реализация может быть улучшена путем избавления отдополнительные копии в Temp_signal с memcpy путем прямого умножения Orignal_signal во много раз на различные части Com_array, как показано ниже: 

MKL_Complex8* outptr = Expand_signal;
for (int i=0; i<4608; i++)
{
  for (int j=0; j<32; j++)
  {
    packed_vec_mult(1024, Original_signal+i*1024, Com_array+j*1024, outptr);
    outptr += 1024;
  }
}

Этот последний шаг даст вам еще ~ 20% улучшения производительности по сравнению с вашей реализацией с заменой vmcMul на packed_vec_mult.

Наконец, поскольку цикл выполняет операции с независимыми блоками, вы можете получить значительно более высокую пропускную способность (но с аналогичной задержкой), запустив параллельныйвычисления в нескольких потоках, так что процессор всегда занят, а не ожидает передачи данных в / из памяти.Мои тесты показывают улучшение где-то в 2 раза, но результаты могут отличаться в зависимости от вашей конкретной машины.

...