Каков самый быстрый способ вычисления больших точечных продуктов?

Question

Рассмотрим этот фрагмент:

double dot(double* a, double* b, int n) { 
    double sum = 0; 
    for (int i = 0; i < n; ++i) sum += a[i] * b[i]; 
    return sum; 
} 

Как я могу ускорить его с помощью встроенных средств или ассемблер?

Примечания:

• Можно считать новейшую архитектуру, в том числе расширений AVX.
• n несколько сотен.
• точка будет использовать себя в тугой петле

Answer 1

Вот простая реализация SSE:

#include "pmmintrin.h" 

__m128d vsum = _mm_set1_pd(0.0); 
double sum = 0.0; 
int k; 

// process 2 elements per iteration 
for (k = 0; k < n - 1; k += 2) 
{ 
    __m128d va = _mm_loadu_pd(&a[k]); 
    __m128d vb = _mm_loadu_pd(&b[k]); 
    __m128d vs = _mm_mul_pd(va, vb); 
    vsum = _mm_add_pd(vsum, vs); 
} 

// horizontal sum of 2 partial dot products 
vsum = _mm_hadd_pd(vsum, vsum); 
_mm_store_sd(&sum, vsum); 

// clean up any remaining elements 
for (; k < n; ++k) 
{ 
    sum += a[k] * b[k]; 
} 

Обратите внимание, что если вы можете гарантировать, что а и Ь 16 байт выровнены, то вы можете использовать _mm_load_pd, а не _mm_loadu_pd, что может помочь в производительности, особенно на старых (до Nehalem) процессорах.

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

---

Если вы хотите предназначаться процессоры с AVX, то это довольно простой переход от выше реализации SSE обрабатывать 4 элементов на итерацию, а не 2:

#include "immintrin.h" 

__m256d vsum = _mm256_set1_pd(0.0); 
double sum = 0.0; 
int k; 

// process 4 elements per iteration 
for (k = 0; k < n - 3; k += 4) 
{ 
    __m256d va = _mm256_loadu_pd(&a[k]); 
    __m256d vb = _mm256_loadu_pd(&b[k]); 
    __m256d vs = _mm256_mul_pd(va, vb); 
    vsum = _mm256_add_pd(vsum, vs); 
} 

// horizontal sum of 4 partial dot products 
vsum = _mm256_hadd_pd(_mm256_permute2f128_pd(vsum, vsum, 0x20), _mm256_permute2f128_pd(vsum, vsum, 0x31)); 
vsum = _mm256_hadd_pd(_mm256_permute2f128_pd(vsum, vsum, 0x20), _mm256_permute2f128_pd(vsum, vsum, 0x31)); 
_mm256_store_sd(&sum, vsum); 

// clean up any remaining elements 
for (; k < n; ++k) 
{ 
    sum += a[k] * b[k]; 
}