OMP SIMD 逻辑与 unsigned long long
OMP SIMD logical AND on unsigned long long
我一直在研究 SIMD OMP 指令，但我没有让编译器在我的场景中发出 ANDPS。
我想做什么：
- 这是此 problem 的一个实现（tldr：查找具有共同朋友的一对用户）。我的做法是把64位（不管是不是朋友）打包成一个
unsigned long long.
- 我的 SIMD 方法：在两个关系向量和
reduce 之间取 AND，OR 非常适合 OMP 的 reduction pattern。
g++ 指令（在 2019 intel i-7 macbookPro 上）：
g++-11 friends.cpp -S -O3 -fopenmp -fsanitize=address -Wshadow -Wall -march=native --std=c++17;
下面是我的实现
#include <vector>
#include <algorithm>
#include "iostream"
#include <cmath>
#include <numeric>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ull find_sol(vector<vector<ull>> & input_data, int q) {
bool not_friend = false;
ull cnt = 0;
int size_arr = (int) input_data[0].size();
for (int i = 0; i < q; ++i) // from these friends
{
for (int j = i+1; j < q; ++j) // to these friends
{
int step = j/64;
int remainder = j - 64*step;
not_friend = (input_data[i].at(step) >> remainder) % 2 == 0;
if(not_friend){
bool counter = false;
vector<ull> & v1 = input_data[i];
vector<ull> & v2 = input_data[j];
#pragma omp simd reduction(|:counter)
for (int c = 0; c < size_arr; ++c)
{
__asm__ ("entry");
counter |= (v1[c] & v2[c])>0;
__asm__ ("exit");
}
if(counter>0)
cnt++;
}
}
}
return cnt << 1;
}
int main(){
int q;
cin >> q;
vector<vector<ull>> input_data(q,vector<ull>(1 + q/64,0ULL));
for (int i = 0; i < q; ++i)
{
string s;
cin >> s;
for (int j = 0; j < 1 + q/64; ++j)
{
string str = s.substr(j*64,64);
reverse(str.begin(),str.end());
ull ul = std::stoull(str,nullptr,2);
input_data.at(i).at(j) = ul;
}
}
cout << find_sol(input_data,q) << endl;
}
查看循环内的程序集，我希望有一些 SIMD 指令（特别是 andps），但我看不到它们。是什么阻止我的编译器发出它们？另外，有没有办法让编译器发出警告 re:what 错误（会很有帮助）？
entry
# 0 "" 2
cmpb [=11=], (%rbx)
jne L53
movq (%r8), %rdx
leaq 0(,%rax,8), %rdi
addq %rdi, %rdx
movq %rdx, %r15
shrq , %r15
cmpb [=11=], (%r15,%rcx)
jne L54
cmpb [=11=], (%r11)
movq (%rdx), %rdx
jne L55
addq (%r9), %rdi
movq %rdi, %r15
shrq , %r15
cmpb [=11=], (%r15,%rcx)
jne L56
andq (%rdi), %rdx
movzbl (%r12), %edx
setne %dil
cmpb %r13b, %dl
jg L21
testb %dl, %dl
jne L57
L21:
orb %dil, -32(%r10)
编辑 1：
按照 Peter 的第一个和第二个建议，我将标记移出了循环，并用一个简单的 OR 替换了二值化。不过，我仍然没有收到 SIMD 指令：
ull counter = 0;
vector<ull> & v1 = input_data[i];
vector<ull> & v2 = input_data[j];
__asm__ ("entry" :::);
#pragma omp simd reduction(|:counter)
for (int c = 0; c < size_arr; ++c)
{
counter |= v1[c] & v2[c];
}
__asm__ ("exit" :::);
if(counter!=0)
cnt++;
第一个问题：asm。在最近的 GCC 中，像 __asm__ ("entry"); 这样的非空 Basic Asm 语句有一个隐式的 ::: "memory" 破坏，使得编译器不可能跨迭代组合数组访问。如果你真的想要这些标记，也许试试 __asm__ ("entry" :::);。 （没有内存破坏的扩展 asm）。
或者更好的是，使用更好的工具来查看编译器输出，例如 Godbolt 编译器资源管理器 (https://godbolt.org/)，它可以让您右键单击源代码行并转到相应的 asm。 （优化会使这有点不稳定，因此有时您必须找到 asm 并将鼠标悬停在它上面以确保它来自该源代码行。）
见
第二个问题： -fsanitize=address 使编译器更难优化。我只查看了没有该选项的 GCC 输出。
向量化 OR 缩减
修复这些问题后：
您强制编译器在内部循环中布尔化为 8 位 bool，而不是仅仅将整数与 |= 的结果缩减为相同类型的变量。 （你在循环后检查一次。）这可能是 GCC 遇到困难的部分原因；当它完全矢量化时，它经常会弄乱不同大小的整数类型。
(v1[c] & v2[c]) > 0; 需要 SSE4.1 pcmpeqqvs。只需在循环中使用 SIMD OR 并在循环后检查 counter 是否为 !=0。 （你有 bool counter，考虑到 counter>0 作为一种语义上奇怪的检查无符号值是否为非零的方式，这真的很令人惊讶。对于 bool 更令人意外。）
更改后，如果您使用 -O3（包括 -ftree-vectorize），GCC 会按照我在没有 OpenMP 的情况下预期的方式自动矢量化。它当然与 vpand 一起使用，而不是 vandps，因为 FP 布尔值在某些 CPU 上的吞吐量较低。 （你没有说 -march=native 适合你；如果你只有 AVX1，例如在 Sandybridge 上，那么 vandps 是合理的。）
ull counter = 0;
// #pragma omp simd reduction(|:counter)
for (int c = 0; c < size_arr; ++c)
{
//__asm__ ("entry");
counter |= (v1[c] & v2[c]);
//__asm__ ("exit");
}
if(counter != 0)
cnt++;
来自 Godbolt compiler explorer（您应该使用它而不是用 asm 语句乱扔代码）
# g++ 11.2 -O3 -march=skylake **without** OpenMP
.L7: # the vector part of the inner-most loop
vmovdqu ymm2, YMMWORD PTR [rsi+rax]
vpand ymm0, ymm2, YMMWORD PTR [rcx+rax]
add rax, 32
vpor ymm1, ymm1, ymm0
cmp rax, r8
jne .L7
vextracti128 xmm0, ymm1, 0x1
vpor xmm0, xmm0, xmm1
vpsrldq xmm1, xmm0, 8
... (horizontal OR reduction of that one SIMD vector, eventually vmovq to RAX)
GCC OpenMP 会矢量化，但很糟糕/很奇怪
使用 OpenMP，有一个矢量化版本的循环，但它很糟糕，进行洗牌和收集负载，并将结果存储到稍后读取的本地缓冲区中。我不太了解 OpenMP，但除非你用错了，否则这是一个重大的优化失误。可能它是用乘法而不是递增指针来缩放循环计数器，这太可怕了。
(Godbolt)
# g++ 11.2 -Wall -O3 -fopenmp -march=skylake -std=gnu++17
# with the #pragma uncommented
.L10:
vmovdqa ymm0, ymm3
vpermq ymm0, ymm0, 216
vpshufd ymm1, ymm0, 80 # unpack for 32x32 => 64-bit multiplies?
vpmuldq ymm1, ymm1, ymm4
vpshufd ymm0, ymm0, 250
vpmuldq ymm0, ymm0, ymm4
vmovdqa ymm7, ymm6 # ymm6 = set1(-1) outside the loop, gather mask
add rsi, 64
vpaddq ymm1, ymm1, ymm5
vpgatherqq ymm2, QWORD PTR [0+ymm1*1], ymm7
vpaddq ymm0, ymm0, ymm5
vmovdqa ymm7, ymm6
vpgatherqq ymm1, QWORD PTR [0+ymm0*1], ymm7
vpand ymm0, ymm1, YMMWORD PTR [rsi-32] # memory source = one array
vpand ymm1, ymm2, YMMWORD PTR [rsi-64]
vpor ymm0, ymm0, YMMWORD PTR [rsp+64] # OR with old contents of local buffer
vpor ymm1, ymm1, YMMWORD PTR [rsp+32]
vpaddd ymm3, ymm3, ymm4
vmovdqa YMMWORD PTR [rsp+32], ymm1 # and store back into it.
vmovdqa YMMWORD PTR [rsp+64], ymm0
cmp r9, rsi
jne .L10
mov edi, DWORD PTR [rsp+16] # outer loop tail
cmp DWORD PTR [rsp+20], edi
je .L7
这个 64 字节的缓冲区在 .L7（外循环）
的顶部读取
.L7:
vmovdqa ymm2, YMMWORD PTR [rsp+32]
vpor ymm1, ymm2, YMMWORD PTR [rsp+64]
vextracti128 xmm0, ymm1, 0x1
vpor xmm0, xmm0, xmm1
vpsrldq xmm1, xmm0, 8
vpor xmm0, xmm0, xmm1
vmovq rsi, xmm0
cmp rsi, 1 # sets CF unless RSI=0
sbb r13, -1 # R13 -= -1 +CF i.e. increment if CF=0
IDK 如果有办法让编译器生成更好的 asm；也许用指针宽度循环计数器？
GCC5.4 -O3 -fopenmp -march=haswell -std=gnu++17 使 asm 合理，只有 vpand / vpor 和循环中的数组索引增量。循环外的内容与 OpenMP 与普通矢量化有点不同，OpenMP 使用矢量存储/标量重新加载来对最终矢量进行水平或缩减。
我一直在研究 SIMD OMP 指令，但我没有让编译器在我的场景中发出 ANDPS。
我想做什么：
- 这是此 problem 的一个实现（tldr：查找具有共同朋友的一对用户）。我的做法是把64位（不管是不是朋友）打包成一个
unsigned long long. - 我的 SIMD 方法：在两个关系向量和
reduce之间取AND，OR非常适合 OMP 的 reduction pattern。
g++ 指令（在 2019 intel i-7 macbookPro 上）：
g++-11 friends.cpp -S -O3 -fopenmp -fsanitize=address -Wshadow -Wall -march=native --std=c++17;
下面是我的实现
#include <vector>
#include <algorithm>
#include "iostream"
#include <cmath>
#include <numeric>
typedef long long ll;
typedef unsigned long long ull;
using namespace std;
ull find_sol(vector<vector<ull>> & input_data, int q) {
bool not_friend = false;
ull cnt = 0;
int size_arr = (int) input_data[0].size();
for (int i = 0; i < q; ++i) // from these friends
{
for (int j = i+1; j < q; ++j) // to these friends
{
int step = j/64;
int remainder = j - 64*step;
not_friend = (input_data[i].at(step) >> remainder) % 2 == 0;
if(not_friend){
bool counter = false;
vector<ull> & v1 = input_data[i];
vector<ull> & v2 = input_data[j];
#pragma omp simd reduction(|:counter)
for (int c = 0; c < size_arr; ++c)
{
__asm__ ("entry");
counter |= (v1[c] & v2[c])>0;
__asm__ ("exit");
}
if(counter>0)
cnt++;
}
}
}
return cnt << 1;
}
int main(){
int q;
cin >> q;
vector<vector<ull>> input_data(q,vector<ull>(1 + q/64,0ULL));
for (int i = 0; i < q; ++i)
{
string s;
cin >> s;
for (int j = 0; j < 1 + q/64; ++j)
{
string str = s.substr(j*64,64);
reverse(str.begin(),str.end());
ull ul = std::stoull(str,nullptr,2);
input_data.at(i).at(j) = ul;
}
}
cout << find_sol(input_data,q) << endl;
}
查看循环内的程序集，我希望有一些 SIMD 指令（特别是 andps），但我看不到它们。是什么阻止我的编译器发出它们？另外，有没有办法让编译器发出警告 re:what 错误（会很有帮助）？
entry
# 0 "" 2
cmpb [=11=], (%rbx)
jne L53
movq (%r8), %rdx
leaq 0(,%rax,8), %rdi
addq %rdi, %rdx
movq %rdx, %r15
shrq , %r15
cmpb [=11=], (%r15,%rcx)
jne L54
cmpb [=11=], (%r11)
movq (%rdx), %rdx
jne L55
addq (%r9), %rdi
movq %rdi, %r15
shrq , %r15
cmpb [=11=], (%r15,%rcx)
jne L56
andq (%rdi), %rdx
movzbl (%r12), %edx
setne %dil
cmpb %r13b, %dl
jg L21
testb %dl, %dl
jne L57
L21:
orb %dil, -32(%r10)
编辑 1：
按照 Peter 的第一个和第二个建议，我将标记移出了循环，并用一个简单的 OR 替换了二值化。不过，我仍然没有收到 SIMD 指令：
ull counter = 0;
vector<ull> & v1 = input_data[i];
vector<ull> & v2 = input_data[j];
__asm__ ("entry" :::);
#pragma omp simd reduction(|:counter)
for (int c = 0; c < size_arr; ++c)
{
counter |= v1[c] & v2[c];
}
__asm__ ("exit" :::);
if(counter!=0)
cnt++;
第一个问题：asm。在最近的 GCC 中，像 __asm__ ("entry"); 这样的非空 Basic Asm 语句有一个隐式的 ::: "memory" 破坏，使得编译器不可能跨迭代组合数组访问。如果你真的想要这些标记，也许试试 __asm__ ("entry" :::);。 （没有内存破坏的扩展 asm）。
或者更好的是，使用更好的工具来查看编译器输出，例如 Godbolt 编译器资源管理器 (https://godbolt.org/)，它可以让您右键单击源代码行并转到相应的 asm。 （优化会使这有点不稳定，因此有时您必须找到 asm 并将鼠标悬停在它上面以确保它来自该源代码行。）
见
第二个问题： -fsanitize=address 使编译器更难优化。我只查看了没有该选项的 GCC 输出。
向量化 OR 缩减
修复这些问题后：
您强制编译器在内部循环中布尔化为 8 位 bool，而不是仅仅将整数与 |= 的结果缩减为相同类型的变量。 （你在循环后检查一次。）这可能是 GCC 遇到困难的部分原因；当它完全矢量化时，它经常会弄乱不同大小的整数类型。
(v1[c] & v2[c]) > 0; 需要 SSE4.1 pcmpeqqvs。只需在循环中使用 SIMD OR 并在循环后检查 counter 是否为 !=0。 （你有 bool counter，考虑到 counter>0 作为一种语义上奇怪的检查无符号值是否为非零的方式，这真的很令人惊讶。对于 bool 更令人意外。）
更改后，如果您使用 -O3（包括 -ftree-vectorize），GCC 会按照我在没有 OpenMP 的情况下预期的方式自动矢量化。它当然与 vpand 一起使用，而不是 vandps，因为 FP 布尔值在某些 CPU 上的吞吐量较低。 （你没有说 -march=native 适合你；如果你只有 AVX1，例如在 Sandybridge 上，那么 vandps 是合理的。）
ull counter = 0;
// #pragma omp simd reduction(|:counter)
for (int c = 0; c < size_arr; ++c)
{
//__asm__ ("entry");
counter |= (v1[c] & v2[c]);
//__asm__ ("exit");
}
if(counter != 0)
cnt++;
来自 Godbolt compiler explorer（您应该使用它而不是用 asm 语句乱扔代码）
# g++ 11.2 -O3 -march=skylake **without** OpenMP
.L7: # the vector part of the inner-most loop
vmovdqu ymm2, YMMWORD PTR [rsi+rax]
vpand ymm0, ymm2, YMMWORD PTR [rcx+rax]
add rax, 32
vpor ymm1, ymm1, ymm0
cmp rax, r8
jne .L7
vextracti128 xmm0, ymm1, 0x1
vpor xmm0, xmm0, xmm1
vpsrldq xmm1, xmm0, 8
... (horizontal OR reduction of that one SIMD vector, eventually vmovq to RAX)
GCC OpenMP 会矢量化，但很糟糕/很奇怪
使用 OpenMP，有一个矢量化版本的循环，但它很糟糕，进行洗牌和收集负载，并将结果存储到稍后读取的本地缓冲区中。我不太了解 OpenMP，但除非你用错了，否则这是一个重大的优化失误。可能它是用乘法而不是递增指针来缩放循环计数器，这太可怕了。
(Godbolt)
# g++ 11.2 -Wall -O3 -fopenmp -march=skylake -std=gnu++17
# with the #pragma uncommented
.L10:
vmovdqa ymm0, ymm3
vpermq ymm0, ymm0, 216
vpshufd ymm1, ymm0, 80 # unpack for 32x32 => 64-bit multiplies?
vpmuldq ymm1, ymm1, ymm4
vpshufd ymm0, ymm0, 250
vpmuldq ymm0, ymm0, ymm4
vmovdqa ymm7, ymm6 # ymm6 = set1(-1) outside the loop, gather mask
add rsi, 64
vpaddq ymm1, ymm1, ymm5
vpgatherqq ymm2, QWORD PTR [0+ymm1*1], ymm7
vpaddq ymm0, ymm0, ymm5
vmovdqa ymm7, ymm6
vpgatherqq ymm1, QWORD PTR [0+ymm0*1], ymm7
vpand ymm0, ymm1, YMMWORD PTR [rsi-32] # memory source = one array
vpand ymm1, ymm2, YMMWORD PTR [rsi-64]
vpor ymm0, ymm0, YMMWORD PTR [rsp+64] # OR with old contents of local buffer
vpor ymm1, ymm1, YMMWORD PTR [rsp+32]
vpaddd ymm3, ymm3, ymm4
vmovdqa YMMWORD PTR [rsp+32], ymm1 # and store back into it.
vmovdqa YMMWORD PTR [rsp+64], ymm0
cmp r9, rsi
jne .L10
mov edi, DWORD PTR [rsp+16] # outer loop tail
cmp DWORD PTR [rsp+20], edi
je .L7
这个 64 字节的缓冲区在 .L7（外循环）
.L7:
vmovdqa ymm2, YMMWORD PTR [rsp+32]
vpor ymm1, ymm2, YMMWORD PTR [rsp+64]
vextracti128 xmm0, ymm1, 0x1
vpor xmm0, xmm0, xmm1
vpsrldq xmm1, xmm0, 8
vpor xmm0, xmm0, xmm1
vmovq rsi, xmm0
cmp rsi, 1 # sets CF unless RSI=0
sbb r13, -1 # R13 -= -1 +CF i.e. increment if CF=0
IDK 如果有办法让编译器生成更好的 asm；也许用指针宽度循环计数器？
GCC5.4 -O3 -fopenmp -march=haswell -std=gnu++17 使 asm 合理，只有 vpand / vpor 和循环中的数组索引增量。循环外的内容与 OpenMP 与普通矢量化有点不同，OpenMP 使用矢量存储/标量重新加载来对最终矢量进行水平或缩减。