计算大点产品的最快方法是什么？

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 几百.
• dot本身将用于紧密循环

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];
}

请注意,如果您可以保证a和b是16字节对齐,那么您可以使用_mm_load_pd而不是_mm_loadu_pd可以帮助提高性能,尤其是在较旧的(pre Nehalem)CPU上.

还要注意,对于诸如此类的循环,其中相对于负载数量的算术指令非常少,那么性能很可能受到存储器带宽的限制,并且在实践中可能无法实现预期的矢量化加速.

如果你想用AVX定位CPU,那么从上面的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];
}