Как улучшить работу следующей петли

Question

У меня есть простая петля в C, где я конвертирую magnitude и angle в real и imaginary. У меня две версии цикла. Version 1 представляет собой простой цикл, где я выполнить преобразование, используя следующий код

for(k = 0; k < n; k++){ 
    xReal[k] = Mag[k] * cos(Angle[k]); 
    xImag[k] = Mag[k] * sin(Angle[k]); 
} 

Version 2, где Intrinsics используются для векторизации цикла.

__m256d cosVec, sinVec; 
__m256d resultReal, resultImag; 
__m256d angVec, voltVec; 
for(k = 0; k < SysData->totNumOfBus; k+=4){ 

    voltVec = _mm256_loadu_pd(volt + k); 
    angVec = _mm256_loadu_pd(theta + k); 

    sinVec = _mm256_sincos_pd(&cosVec, angVec); 

    resultImag = _mm256_mul_pd(voltVec, sinVec); 
    resultReal = _mm256_mul_pd(voltVec, cosVec); 

    _mm256_store_pd(xReal+k, resultReal); 
    _mm256_store_pd(xImag+k, resultImag); 

} 

На Core i7 2600k @3.4GHz процессоре, эти петли дают следующие результаты:

Version 1: n = 18562320, Time: 0.2sec 
Version 2: n = 18562320, Time: 0.16sec 

простого вычисления с этими значениями показывают, что в version 1, каждая итерация занимает почти 36 циклы должны быть завершены в то время как он принимает 117 циклов для Version 2. Учитывая тот факт, что вычисления функций sine и cosine, естественно, дороги, эти цифры, похоже, не страшны. Однако этот цикл является серьезным узким местом моей функции, поскольку профилирование показывает, что в цикле проводится почти 1/3 времени. Поэтому мне интересно, есть ли способ ускорить этот цикл (например, вычислять функции sine и cosine по-разному). Понятно, помогите мне решить эту проблему и сообщить мне, есть ли возможность улучшить производительность этого цикла.

Заранее спасибо за вашу помощь

PS: Я использую icc для компиляции кода. Кроме того, я должен упомянуть, что данные не выровнены (и не могут быть). Однако выравнивание данных приводит лишь к незначительному улучшению производительности (менее 1 процента).

Answer 1

пожалуйста, проверьте:

1. ли начальный адрес массива выравнивается 16byte. i7 поддерживает высокую задержку без выравненной нагрузки avx без жалобы «ошибка шины»

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

3. вы можете понизить точность или использовать таблицу результатов для расчета sin и cos.

4. , пожалуйста, подумайте о том, сколько вы улучшите производительность. Так как версия 1 цикла занимает всего 1/3 от общего времени работы. если оптимизировать цикл до нуля, производительность только улучшить 30%

Answer 2

Время результаты, которые вы перечисляете показывают, что версия 2 работает быстрее (на 20%) по сравнению с версией 1.

Version 1: n = 18562320, Time: 0.2sec 
Version 2: n = 18562320, Time: 0.16sec 

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

Или еще один способ объяснить это, что при векторизации элементы данных доступны без какого-либо времени ожидания для извлечения памяти.

Answer 3

Я рекомендую использовать функцию sin/cos, основанную на последовательности tayler, и _mm256_stream_pd() для хранения данных. Вот базовый пример кода.

__m256d sin_req[10]; 
    __m256d cos_req[10]; 
    __m256d one_pd = _mm256_set1_pd(1.0); 

    for(int i=0; i<10; ++i) 
    { 
     sin_req[i] = i%2 == 0 ? _mm256_set1_pd(-1.0/Factorial((i+1)*2+1)) : _mm256_set1_pd(+1.0/Factorial((i+1)*2+1)); 
     cos_req[i] = i%2 == 0 ? _mm256_set1_pd(-1.0/Factorial((i+1)*2+0)) : _mm256_set1_pd(+1.0/Factorial((i+1)*2+0)); 
    } 

    for(int i=0; i<count; i+=4) 
    { 
      __m256d voltVec = _mm256_load_pd(volt + i); 
      __m256d angVec = _mm256_load_pd(theta + i); 

      // sin/cos by taylor series 
      __m256d angleSq = angVec * angVec; 
      __m256d sinVec = angVec; 
      __m256d cosVec = one_pd; 
      __m256d sin_serise = sinVec; 
      __m256d cos_serise = one_pd; 
      for(int j=0; j<10; ++j) 
      { 
       sin_serise = sin_serise * angleSq; // [1] 
       cos_serise = cos_serise * angleSq; 
       sinVec = sinVec + sin_serise * sin_req[j]; 
       cosVec = cosVec + cos_serise * cos_req[j]; 
      } 

      __m256d resultReal = voltVec * sinVec; 
      __m256d resultImag = voltVec * cosVec; 

      _mm256_store_pd(xReal + i, resultReal); 
      _mm256_store_pd(xImag + i, resultImag); 
    } 

Я могу получить 57 ~ 58 циклов процессора для расчета 4 компонентов.

Я искал google и провел несколько тестов для точности моего греха/cos. Некоторые статьи говорят, что 10-итерация имеет точность с двойной точностью, а -M_PI/2 < угол < + M_PI/2. И мой результат теста показывает, что он более точен, чем math.h's sin/cos на -M_PI < угол < + диапазон M_PI. Вы можете увеличить итерацию для большей точности при больших углах, если это необходимо.

Однако я пойду глубже оптимизирую этот код. Этот код имеет расчеты тайм-аутов тайм-аута. Многократная латентность AVX составляет 5 циклов процессора, это означает, что мы не можем запускать одну итерацию быстрее, чем 5 циклов, потому что [1] использует результат предыдущего результата итерации.

Мы можем просто развернуть его вот так.

for(int i=0; i<count; i+=8) 
    { 
     __m256d voltVec0 = _mm256_load_pd(volt + i + 0); 
     __m256d voltVec1 = _mm256_load_pd(volt + i + 4); 
     __m256d angVec0 = _mm256_load_pd(theta + i + 0); 
     __m256d angVec1 = _mm256_load_pd(theta + i + 4); 
     __m256d sinVec0; 
     __m256d sinVec1; 
     __m256d cosVec0; 
     __m256d cosVec1; 

     __m256d angleSq0 = angVec0 * angVec0; 
     __m256d angleSq1 = angVec1 * angVec1; 
     sinVec0 = angVec0; 
     sinVec1 = angVec1; 
     cosVec0 = one_pd; 
     cosVec1 = one_pd; 
     __m256d sin_serise0 = sinVec0; 
     __m256d sin_serise1 = sinVec1; 
     __m256d cos_serise0 = one_pd; 
     __m256d cos_serise1 = one_pd; 

     for(int j=0; j<10; ++j) 
     { 
      sin_serise0 = sin_serise0 * angleSq0; 
      cos_serise0 = cos_serise0 * angleSq0; 
      sin_serise1 = sin_serise1 * angleSq1; 
      cos_serise1 = cos_serise1 * angleSq1; 
      sinVec0 = sinVec0 + sin_serise0 * sin_req[j]; 
      cosVec0 = cosVec0 + cos_serise0 * cos_req[j]; 
      sinVec1 = sinVec1 + sin_serise1 * sin_req[j]; 
      cosVec1 = cosVec1 + cos_serise1 * cos_req[j]; 
     } 

     __m256d realResult0 = voltVec0 * sinVec0; 
     __m256d imagResult0 = voltVec0 * cosVec0; 
     __m256d realResult1 = voltVec1 * sinVec1; 
     __m256d imagResult1 = voltVec1 * cosVec1; 

     _mm256_store_pd(xReal + i + 0, realResult0); 
     _mm256_store_pd(xImag + i + 0, imagResult0); 
     _mm256_store_pd(xReal + i + 4, realResult1); 
     _mm256_store_pd(xImag + i + 4, imagResult1); 
    } 

Этот результат 51 ~ 51,5 циклов для расчета 4 компонент. (102 ~ 103 цикла для 8 компонентов)

Он устраняет заблуждение mutiply в контуре расчета тэйлора и использует 85% умножителя AVX. Unrolling будет решать множество проблем с задержкой, в то время как он не заменяет регистры на память. Генерируйте файл asm во время компиляции и посмотрите, как ваш компилятор обрабатывает ваш код. Я попробовал развернуть больше, но это привело к плохому, потому что оно не могло вписаться в 16 регистров AVX.

Теперь мы идем с опцией памяти. замените _mm256_store_ps() на _mm256_stream_ps().

_mm256_stream_pd(xReal + i + 0, realResult0); 
    _mm256_stream_pd(xImag + i + 0, imagResult0); 
    _mm256_stream_pd(xReal + i + 4, realResult1); 
    _mm256_stream_pd(xImag + i + 4, imagResult1); 

Замена данных для записи на память 48 циклов для расчета 4 компонент.

_mm256_stream_pd() всегда быстрее, если вы не собираетесь его читать. Он пропускает систему кэширования и отправляет данные прямо в контроллер памяти и не загрязняет ваш кеш. Вы получите больше пространства данных/кэша для чтения данных с помощью _mm256_stream_pd().

Давайте попробуем предварительную выборку.

for(int i=0; i<count; i+=8) 
    { 
    _mm_prefetch((const CHAR *)(volt + i + 5 * 8), _MM_HINT_T0); 
    _mm_prefetch((const CHAR *)(theta + i + 5 * 8), _MM_HINT_T0); 

      // calculations here. 
    } 

Теперь я получил 45,6 ~ 45,8 циклов ЦП за расчет. 94% заняты блоком умножения AVX.

Prefech подсказывает кеш для более быстрого чтения. Я рекомендую prefech до 400 ~ 500 циклов процессора, основанных на задержке RAS-CAS физической памяти. Задержка физической памяти может занять до 300 циклов в худшем случае. может варьироваться в зависимости от конфигурации оборудования, не будет меньше 200 циклов, даже если вы используете дорогостоящую память с задержкой RAS-CAS.

0,064 сек (кол = 18562320)

Конец греха/COS оптимизации. :-)