用 sse 累加整数向量
Accumulate vector of integer with sse
我试图更改此代码以处理 std::vector<int>。
float accumulate(const std::vector<float>& v)
{
// copy the length of v and a pointer to the data onto the local stack
const size_t N = v.size();
const float* p = (N > 0) ? &v.front() : NULL;
__m128 mmSum = _mm_setzero_ps();
size_t i = 0;
// unrolled loop that adds up 4 elements at a time
for(; i < ROUND_DOWN(N, 4); i+=4)
{
mmSum = _mm_add_ps(mmSum, _mm_loadu_ps(p + i));
}
// add up single values until all elements are covered
for(; i < N; i++)
{
mmSum = _mm_add_ss(mmSum, _mm_load_ss(p + i));
}
// add up the four float values from mmSum into a single value and return
mmSum = _mm_hadd_ps(mmSum, mmSum);
mmSum = _mm_hadd_ps(mmSum, mmSum);
return _mm_cvtss_f32(mmSum);
}
参考：http://fastcpp.blogspot.com.au/2011/04/how-to-process-stl-vector-using-sse.html
我将 _mm_setzero_ps 更改为 _mm_setzero_si128，将 _mm_loadu_ps 更改为 mm_loadl_epi64，将 _mm_add_ps 更改为 _mm_add_epi64。
我收到这个错误：
error: cannot convert ‘const int*’ to ‘const __m128i* {aka const __vector(2) long long int*}’ for argument ‘1’ to ‘__m128i _mm_loadl_epi64(const __m128i*)’
mmSum = _mm_add_epi64(mmSum, _mm_loadl_epi64(p + i + 0));
我是这个领域的新手。有什么好的资源可以学习这些东西吗？
这是我刚刚拼凑的 int 版本：
#include <iostream>
#include <vector>
#include <smmintrin.h> // SSE4
#define ROUND_DOWN(m, n) ((m) & ~((n) - 1))
static int accumulate(const std::vector<int>& v)
{
// copy the length of v and a pointer to the data onto the local stack
const size_t N = v.size();
const int* p = (N > 0) ? &v.front() : NULL;
__m128i mmSum = _mm_setzero_si128();
int sum = 0;
size_t i = 0;
// unrolled loop that adds up 4 elements at a time
for(; i < ROUND_DOWN(N, 4); i+=4)
{
mmSum = _mm_add_epi32(mmSum, _mm_loadu_si128((__m128i *)(p + i)));
}
// add up the four int values from mmSum into a single value
mmSum = _mm_hadd_epi32(mmSum, mmSum);
mmSum = _mm_hadd_epi32(mmSum, mmSum);
sum = _mm_extract_epi32(mmSum, 0);
// add up single values until all elements are covered
for(; i < N; i++)
{
sum += p[i];
}
return sum;
}
int main()
{
std::vector<int> v;
for (int i = 0; i < 10; ++i)
{
v.push_back(i);
}
int sum = accumulate(v);
std::cout << sum << std::endl;
return 0;
}
编译并运行:
$ g++ -Wall -msse4 -O3 accumulate.cpp && ./a.out
45
实现此目的的理想方法是让编译器自动向量化您的代码并保持代码简单易读。你不需要
int sum = 0;
for(int i=0; i<v.size(); i++) sum += v[i];
您指向的 link http://fastcpp.blogspot.com.au/2011/04/how-to-process-stl-vector-using-sse.html 似乎不明白如何让编译器对代码进行矢量化。
对于 link 使用的浮点数，您需要知道的是浮点运算不是关联的，因此取决于您进行归约的顺序。 GCC、MSVC 和 Clang 不会为缩减进行自动矢量化，除非您告诉它使用不同的浮点模型，否则您的结果可能取决于您的硬件。然而，ICC 默认使用关联浮点数学，因此它将使用例如向量化代码。 -O3.
除非允许关联数学，否则 GCC、MSVC 和 Clang 不仅不会矢量化，而且它们不会展开循环以允许部分求和以克服求和的延迟。 In this case only Clang and ICC will unroll to partial sums anyway. Clang unrolls four times and ICC twice.
使用 GCC 启用关联浮点运算的一种方法是使用 -Ofast 标志。使用 MSVC 使用 /fp:fast
我用 GCC 4.9.2、XeonE5-1620 (IVB) @ 3.60GHz、Ubuntu 15.04.
测试了下面的代码
-O3 -mavx -fopenmp 0.93 s
-Ofast -mavx -fopenmp 0.19 s
-Ofast -mavx -fopenmp -funroll-loops 0.19 s
这大约是速度的五倍。尽管 GCC 确实将循环展开八次，但它不执行独立的部分求和（请参见下面的程序集）。这就是展开版本好不到哪里去的原因。
我只使用 OpenMP 是因为它方便 cross-platform/compiler 定时功能：omp_get_wtime().
自动矢量化的另一个优势是它只需启用编译器开关（例如 -mavx）即可用于 AVX。否则，如果你想要 AVX，你将不得不重写你的代码以使用 AVX 内在函数，并且可能不得不在 SO 上问另一个关于如何做到这一点的问题。
因此，目前唯一会自动向量化循环并展开为四个部分和的编译器是 Clang。 请参阅此答案末尾的代码和程序集。
这是我用来测试性能的代码
#include <stdio.h>
#include <omp.h>
#include <vector>
float sumf(float *x, int n)
{
float sum = 0;
for(int i=0; i<n; i++) sum += x[i];
return sum;
}
#define N 10000 // the link used this value
int main(void)
{
std::vector<float> x;
for(int i=0; i<N; i++) x.push_back(1 -2*(i%2==0));
//float x[N]; for(int i=0; i<N; i++) x[i] = 1 -2*(i%2==0);
float sum = 0;
sum += sumf(x.data(),N);
double dtime = -omp_get_wtime();
for(int r=0; r<100000; r++) {
sum += sumf(x.data(),N);
}
dtime +=omp_get_wtime();
printf("sum %f time %f\n", sum, dtime);
}
编辑：
我应该听取自己的建议并查看程序集。
-O3 的主循环。很明显它只做标量和。
.L3:
vaddss (%rdi), %xmm0, %xmm0
addq , %rdi
cmpq %rax, %rdi
jne .L3
-Ofast 的主循环。它执行向量求和但不展开。
.L8:
addl , %eax
vaddps (%r8), %ymm1, %ymm1
addq , %r8
cmpl %eax, %ecx
ja .L8
-O3 -funroll-loops 的主循环。向量和 8x 展开
.L8:
vaddps (%rax), %ymm1, %ymm2
addl , %ebx
addq 6, %rax
vaddps -224(%rax), %ymm2, %ymm3
vaddps -192(%rax), %ymm3, %ymm4
vaddps -160(%rax), %ymm4, %ymm5
vaddps -128(%rax), %ymm5, %ymm6
vaddps -96(%rax), %ymm6, %ymm7
vaddps -64(%rax), %ymm7, %ymm8
vaddps -32(%rax), %ymm8, %ymm1
cmpl %ebx, %r9d
ja .L8
编辑：
将以下代码放入 Clang 3.7 (-O3 -fverbose-asm -mavx)
float sumi(int *x)
{
x = (int*)__builtin_assume_aligned(x, 64);
int sum = 0;
for(int i=0; i<2048; i++) sum += x[i];
return sum;
}
生成以下程序集。请注意，它被矢量化为四个独立的部分和。
sumi(int*): # @sumi(int*)
vpxor xmm0, xmm0, xmm0
xor eax, eax
vpxor xmm1, xmm1, xmm1
vpxor xmm2, xmm2, xmm2
vpxor xmm3, xmm3, xmm3
.LBB0_1: # %vector.body
vpaddd xmm0, xmm0, xmmword ptr [rdi + 4*rax]
vpaddd xmm1, xmm1, xmmword ptr [rdi + 4*rax + 16]
vpaddd xmm2, xmm2, xmmword ptr [rdi + 4*rax + 32]
vpaddd xmm3, xmm3, xmmword ptr [rdi + 4*rax + 48]
vpaddd xmm0, xmm0, xmmword ptr [rdi + 4*rax + 64]
vpaddd xmm1, xmm1, xmmword ptr [rdi + 4*rax + 80]
vpaddd xmm2, xmm2, xmmword ptr [rdi + 4*rax + 96]
vpaddd xmm3, xmm3, xmmword ptr [rdi + 4*rax + 112]
add rax, 32
cmp rax, 2048
jne .LBB0_1
vpaddd xmm0, xmm1, xmm0
vpaddd xmm0, xmm2, xmm0
vpaddd xmm0, xmm3, xmm0
vpshufd xmm1, xmm0, 78 # xmm1 = xmm0[2,3,0,1]
vpaddd xmm0, xmm0, xmm1
vphaddd xmm0, xmm0, xmm0
vmovd eax, xmm0
vxorps xmm0, xmm0, xmm0
vcvtsi2ss xmm0, xmm0, eax
ret
static inline int32_t accumulate(const int32_t *data, size_t size) {
constexpr const static size_t batch = 256 / 8 / sizeof(int32_t);
int32_t sum = 0;
size_t pos = 0;
if (size >= batch) {
// 7
__m256i mmSum = _mm256_loadu_si256((__m256i *)(data));
pos = batch;
// unrolled loop
for (; pos + batch < size; pos += batch) {
// 1 + 7
mmSum =
_mm256_add_epi32(mmSum, _mm256_loadu_si256((__m256i *)(data + pos)));
}
mmSum = _mm256_hadd_epi32(mmSum, mmSum);
mmSum = _mm256_hadd_epi32(mmSum, mmSum);
// 2 + 1 + 3 + 0
sum = _mm_cvtsi128_si32(_mm_add_epi32(_mm256_extractf128_si256(mmSum, 1),
_mm256_castsi256_si128(mmSum)));
}
// add up remain values
while (pos < size) {
sum += data[pos++];
}
return sum;
}
我试图更改此代码以处理 std::vector<int>。
float accumulate(const std::vector<float>& v)
{
// copy the length of v and a pointer to the data onto the local stack
const size_t N = v.size();
const float* p = (N > 0) ? &v.front() : NULL;
__m128 mmSum = _mm_setzero_ps();
size_t i = 0;
// unrolled loop that adds up 4 elements at a time
for(; i < ROUND_DOWN(N, 4); i+=4)
{
mmSum = _mm_add_ps(mmSum, _mm_loadu_ps(p + i));
}
// add up single values until all elements are covered
for(; i < N; i++)
{
mmSum = _mm_add_ss(mmSum, _mm_load_ss(p + i));
}
// add up the four float values from mmSum into a single value and return
mmSum = _mm_hadd_ps(mmSum, mmSum);
mmSum = _mm_hadd_ps(mmSum, mmSum);
return _mm_cvtss_f32(mmSum);
}
参考：http://fastcpp.blogspot.com.au/2011/04/how-to-process-stl-vector-using-sse.html
我将 _mm_setzero_ps 更改为 _mm_setzero_si128，将 _mm_loadu_ps 更改为 mm_loadl_epi64，将 _mm_add_ps 更改为 _mm_add_epi64。
我收到这个错误：
error: cannot convert ‘const int*’ to ‘const __m128i* {aka const __vector(2) long long int*}’ for argument ‘1’ to ‘__m128i _mm_loadl_epi64(const __m128i*)’
mmSum = _mm_add_epi64(mmSum, _mm_loadl_epi64(p + i + 0));
我是这个领域的新手。有什么好的资源可以学习这些东西吗？
这是我刚刚拼凑的 int 版本：
#include <iostream>
#include <vector>
#include <smmintrin.h> // SSE4
#define ROUND_DOWN(m, n) ((m) & ~((n) - 1))
static int accumulate(const std::vector<int>& v)
{
// copy the length of v and a pointer to the data onto the local stack
const size_t N = v.size();
const int* p = (N > 0) ? &v.front() : NULL;
__m128i mmSum = _mm_setzero_si128();
int sum = 0;
size_t i = 0;
// unrolled loop that adds up 4 elements at a time
for(; i < ROUND_DOWN(N, 4); i+=4)
{
mmSum = _mm_add_epi32(mmSum, _mm_loadu_si128((__m128i *)(p + i)));
}
// add up the four int values from mmSum into a single value
mmSum = _mm_hadd_epi32(mmSum, mmSum);
mmSum = _mm_hadd_epi32(mmSum, mmSum);
sum = _mm_extract_epi32(mmSum, 0);
// add up single values until all elements are covered
for(; i < N; i++)
{
sum += p[i];
}
return sum;
}
int main()
{
std::vector<int> v;
for (int i = 0; i < 10; ++i)
{
v.push_back(i);
}
int sum = accumulate(v);
std::cout << sum << std::endl;
return 0;
}
编译并运行:
$ g++ -Wall -msse4 -O3 accumulate.cpp && ./a.out
45
实现此目的的理想方法是让编译器自动向量化您的代码并保持代码简单易读。你不需要
int sum = 0;
for(int i=0; i<v.size(); i++) sum += v[i];
您指向的 link http://fastcpp.blogspot.com.au/2011/04/how-to-process-stl-vector-using-sse.html 似乎不明白如何让编译器对代码进行矢量化。
对于 link 使用的浮点数，您需要知道的是浮点运算不是关联的，因此取决于您进行归约的顺序。 GCC、MSVC 和 Clang 不会为缩减进行自动矢量化，除非您告诉它使用不同的浮点模型，否则您的结果可能取决于您的硬件。然而，ICC 默认使用关联浮点数学，因此它将使用例如向量化代码。 -O3.
除非允许关联数学，否则 GCC、MSVC 和 Clang 不仅不会矢量化，而且它们不会展开循环以允许部分求和以克服求和的延迟。 In this case only Clang and ICC will unroll to partial sums anyway. Clang unrolls four times and ICC twice.
使用 GCC 启用关联浮点运算的一种方法是使用 -Ofast 标志。使用 MSVC 使用 /fp:fast
我用 GCC 4.9.2、XeonE5-1620 (IVB) @ 3.60GHz、Ubuntu 15.04.
测试了下面的代码-O3 -mavx -fopenmp 0.93 s
-Ofast -mavx -fopenmp 0.19 s
-Ofast -mavx -fopenmp -funroll-loops 0.19 s
这大约是速度的五倍。尽管 GCC 确实将循环展开八次，但它不执行独立的部分求和（请参见下面的程序集）。这就是展开版本好不到哪里去的原因。
我只使用 OpenMP 是因为它方便 cross-platform/compiler 定时功能：omp_get_wtime().
自动矢量化的另一个优势是它只需启用编译器开关（例如 -mavx）即可用于 AVX。否则，如果你想要 AVX，你将不得不重写你的代码以使用 AVX 内在函数，并且可能不得不在 SO 上问另一个关于如何做到这一点的问题。
因此，目前唯一会自动向量化循环并展开为四个部分和的编译器是 Clang。 请参阅此答案末尾的代码和程序集。
这是我用来测试性能的代码
#include <stdio.h>
#include <omp.h>
#include <vector>
float sumf(float *x, int n)
{
float sum = 0;
for(int i=0; i<n; i++) sum += x[i];
return sum;
}
#define N 10000 // the link used this value
int main(void)
{
std::vector<float> x;
for(int i=0; i<N; i++) x.push_back(1 -2*(i%2==0));
//float x[N]; for(int i=0; i<N; i++) x[i] = 1 -2*(i%2==0);
float sum = 0;
sum += sumf(x.data(),N);
double dtime = -omp_get_wtime();
for(int r=0; r<100000; r++) {
sum += sumf(x.data(),N);
}
dtime +=omp_get_wtime();
printf("sum %f time %f\n", sum, dtime);
}
编辑：
我应该听取自己的建议并查看程序集。
-O3 的主循环。很明显它只做标量和。
.L3:
vaddss (%rdi), %xmm0, %xmm0
addq , %rdi
cmpq %rax, %rdi
jne .L3
-Ofast 的主循环。它执行向量求和但不展开。
.L8:
addl , %eax
vaddps (%r8), %ymm1, %ymm1
addq , %r8
cmpl %eax, %ecx
ja .L8
-O3 -funroll-loops 的主循环。向量和 8x 展开
.L8:
vaddps (%rax), %ymm1, %ymm2
addl , %ebx
addq 6, %rax
vaddps -224(%rax), %ymm2, %ymm3
vaddps -192(%rax), %ymm3, %ymm4
vaddps -160(%rax), %ymm4, %ymm5
vaddps -128(%rax), %ymm5, %ymm6
vaddps -96(%rax), %ymm6, %ymm7
vaddps -64(%rax), %ymm7, %ymm8
vaddps -32(%rax), %ymm8, %ymm1
cmpl %ebx, %r9d
ja .L8
编辑：
将以下代码放入 Clang 3.7 (-O3 -fverbose-asm -mavx)
float sumi(int *x)
{
x = (int*)__builtin_assume_aligned(x, 64);
int sum = 0;
for(int i=0; i<2048; i++) sum += x[i];
return sum;
}
生成以下程序集。请注意，它被矢量化为四个独立的部分和。
sumi(int*): # @sumi(int*)
vpxor xmm0, xmm0, xmm0
xor eax, eax
vpxor xmm1, xmm1, xmm1
vpxor xmm2, xmm2, xmm2
vpxor xmm3, xmm3, xmm3
.LBB0_1: # %vector.body
vpaddd xmm0, xmm0, xmmword ptr [rdi + 4*rax]
vpaddd xmm1, xmm1, xmmword ptr [rdi + 4*rax + 16]
vpaddd xmm2, xmm2, xmmword ptr [rdi + 4*rax + 32]
vpaddd xmm3, xmm3, xmmword ptr [rdi + 4*rax + 48]
vpaddd xmm0, xmm0, xmmword ptr [rdi + 4*rax + 64]
vpaddd xmm1, xmm1, xmmword ptr [rdi + 4*rax + 80]
vpaddd xmm2, xmm2, xmmword ptr [rdi + 4*rax + 96]
vpaddd xmm3, xmm3, xmmword ptr [rdi + 4*rax + 112]
add rax, 32
cmp rax, 2048
jne .LBB0_1
vpaddd xmm0, xmm1, xmm0
vpaddd xmm0, xmm2, xmm0
vpaddd xmm0, xmm3, xmm0
vpshufd xmm1, xmm0, 78 # xmm1 = xmm0[2,3,0,1]
vpaddd xmm0, xmm0, xmm1
vphaddd xmm0, xmm0, xmm0
vmovd eax, xmm0
vxorps xmm0, xmm0, xmm0
vcvtsi2ss xmm0, xmm0, eax
ret
static inline int32_t accumulate(const int32_t *data, size_t size) {
constexpr const static size_t batch = 256 / 8 / sizeof(int32_t);
int32_t sum = 0;
size_t pos = 0;
if (size >= batch) {
// 7
__m256i mmSum = _mm256_loadu_si256((__m256i *)(data));
pos = batch;
// unrolled loop
for (; pos + batch < size; pos += batch) {
// 1 + 7
mmSum =
_mm256_add_epi32(mmSum, _mm256_loadu_si256((__m256i *)(data + pos)));
}
mmSum = _mm256_hadd_epi32(mmSum, mmSum);
mmSum = _mm256_hadd_epi32(mmSum, mmSum);
// 2 + 1 + 3 + 0
sum = _mm_cvtsi128_si32(_mm_add_epi32(_mm256_extractf128_si256(mmSum, 1),
_mm256_castsi256_si128(mmSum)));
}
// add up remain values
while (pos < size) {
sum += data[pos++];
}
return sum;
}