klm*_*123 7 c++ parallel-processing performance simd seeding
我有一个任务来计算数组中的xor-sum字节:
X = char1 XOR char2 XOR char3 ... charN;
我正在尝试并行化它,而是使用__m128.这应该加速因子4.另外,要重新检查算法,我使用int.这应该加速因子4.测试程序是100行,我不能让它更短,但它很简单:
#include "xmmintrin.h" // simulation of the SSE instruction
#include <ctime>
#include <iostream>
using namespace std;
#include <stdlib.h> // rand
const int NIter = 100;
const int N = 40000000; // matrix size. Has to be dividable by 4.
unsigned char str[N] __attribute__ ((aligned(16)));
template< typename T >
T Sum(const T* data, const int N)
{
T sum = 0;
for ( int i = 0; i < N; ++i )
sum = sum ^ data[i];
return sum;
}
template<>
__m128 Sum(const __m128* data, const int N)
{
__m128 sum = _mm_set_ps1(0);
for ( int i = 0; i < N; ++i )
sum = _mm_xor_ps(sum,data[i]);
return sum;
}
int main() {
// fill string by random values
for( int i = 0; i < N; i++ ) {
str[i] = 256 * ( double(rand()) / RAND_MAX ); // put a random value, from 0 to 255
}
/// -- CALCULATE --
/// SCALAR
unsigned char sumS = 0;
std::clock_t c_start = std::clock();
for( int ii = 0; ii < NIter; ii++ )
sumS = Sum<unsigned char>( str, N );
double tScal = 1000.0 * (std::clock()-c_start) / CLOCKS_PER_SEC;
/// SIMD
unsigned char sumV = 0;
const int m128CharLen = 4*4;
const int NV = N/m128CharLen;
c_start = std::clock();
for( int ii = 0; ii < NIter; ii++ ) {
__m128 sumVV = _mm_set_ps1(0);
sumVV = Sum<__m128>( reinterpret_cast<__m128*>(str), NV );
unsigned char *sumVS = reinterpret_cast<unsigned char*>(&sumVV);
sumV = sumVS[0];
for ( int iE = 1; iE < m128CharLen; ++iE )
sumV ^= sumVS[iE];
}
double tSIMD = 1000.0 * (std::clock()-c_start) / CLOCKS_PER_SEC;
/// SCALAR INTEGER
unsigned char sumI = 0;
const int intCharLen = 4;
const int NI = N/intCharLen;
c_start = std::clock();
for( int ii = 0; ii < NIter; ii++ ) {
int sumII = Sum<int>( reinterpret_cast<int*>(str), NI );
unsigned char *sumIS = reinterpret_cast<unsigned char*>(&sumII);
sumI = sumIS[0];
for ( int iE = 1; iE < intCharLen; ++iE )
sumI ^= sumIS[iE];
}
double tINT = 1000.0 * (std::clock()-c_start) / CLOCKS_PER_SEC;
/// -- OUTPUT --
cout << "Time scalar: " << tScal << " ms " << endl;
cout << "Time INT: " << tINT << " ms, speed up " << tScal/tINT << endl;
cout << "Time SIMD: " << tSIMD << " ms, speed up " << tScal/tSIMD << endl;
if(sumV == sumS && sumI == sumS )
std::cout << "Results are the same." << std::endl;
else
std::cout << "ERROR! Results are not the same." << std::endl;
return 1;
}
典型的结果:
[10:46:20]$ g++ test.cpp -O3 -fno-tree-vectorize; ./a.out
Time scalar: 3540 ms
Time INT: 890 ms, speed up 3.97753
Time SIMD: 280 ms, speed up 12.6429
Results are the same.
[10:46:27]$ g++ test.cpp -O3 -fno-tree-vectorize; ./a.out
Time scalar: 3540 ms
Time INT: 890 ms, speed up 3.97753
Time SIMD: 280 ms, speed up 12.6429
Results are the same.
[10:46:35]$ g++ test.cpp -O3 -fno-tree-vectorize; ./a.out
Time scalar: 3640 ms
Time INT: 880 ms, speed up 4.13636
Time SIMD: 290 ms, speed up 12.5517
Results are the same.
如你所见,int版本理想地工作,但是simd版本失去了25%的速度,这是稳定的.我试图改变数组大小,这没有用.
另外,如果我切换到-O2,我会在simd版本中失去75%的速度:
[10:50:25]$ g++ test.cpp -O2 -fno-tree-vectorize; ./a.out
Time scalar: 3640 ms
Time INT: 880 ms, speed up 4.13636
Time SIMD: 890 ms, speed up 4.08989
Results are the same.
[10:51:16]$ g++ test.cpp -O2 -fno-tree-vectorize; ./a.out
Time scalar: 3640 ms
Time INT: 900 ms, speed up 4.04444
Time SIMD: 880 ms, speed up 4.13636
Results are the same.
有人可以解释一下吗？
附加信息:
我有g ++(GCC)4.7.3; 英特尔(R)Xeon(R)CPU E7-4860
我使用-fno-tree-vectorize来防止自动矢量化.如果没有带-O3的此标志,则预期的加速时间为1,因为任务很简单.这就是我得到的:
[10:55:40]$ g++ test.cpp -O3; ./a.out
Time scalar: 270 ms
Time INT: 270 ms, speed up 1
Time SIMD: 280 ms, speed up 0.964286
Results are the same.
但是-O2结果仍然很奇怪:
[10:55:02]$ g++ test.cpp -O2; ./a.out
Time scalar: 3540 ms
Time INT: 990 ms, speed up 3.57576
Time SIMD: 880 ms, speed up 4.02273
Results are the same.
当我改变
for ( int i = 0; i < N; i+=1 )
sum = sum ^ data[i];
相当于:
for ( int i = 0; i < N; i+=8 )
sum = (data[i] ^ data[i+1]) ^ (data[i+2] ^ data[i+3]) ^ (data[i+4] ^ data[i+5]) ^ (data[i+6] ^ data[i+7]) ^ sum;
我确实看到标量速度提高了2倍.但我没有看到加速的改进.之前:intSpeedUp 3.98416,SIMDSpeedUP 12.5283.之后:intSpeedUp 3.5572,SIMDSpeedUP 6.8523.
我认为您可能会遇到内存带宽的上限。这可能是本例中加速比为 12.6 倍而不是 16 倍的原因-O3。
然而，gcc 4.7.3 在内联时将无用的存储指令放入微小的未展开向量循环中，但不在标量或intSWAR 循环中（见下文），因此这可能是解释。
矢量吞吐量的减少-O2都是由于 gcc 4.7.3 做得更糟糕，并将累加器发送到内存的往返（存储转发）。
要分析该额外存储指令的含义，请参阅最后的部分。
通常使用_mm_xor_si128, 不_mm_xor_ps用于像这样的批量异或工作。
N巨大（40MB），因此内存/缓存带宽是一个问题。Xeon E7-4860采用 32nm Nehalem 微架构，具有 256kiB 二级缓存（每个核心）和 24MiB 共享三级缓存。它具有最高支持 DDR3-1066 的四通道内存控制器（与 SnB 或 Haswell 等典型桌面 CPU 的双通道 DDR3-1333 或 DDR3-1600 相比）。
理论上，典型的 3GHz 桌面 Intel CPU 可以维持 DRAM 大约 8B/周期的负载带宽。（例如，具有双通道 DDR3-1600 的 i5-4670 的理论最大内存带宽为 25.6GB/s）。在实际的单线程中实现这一点可能行不通，尤其是。当使用整数 4B 或 8B 负载时。对于像 2267MHz Nehalem Xeon 这样速度较慢的 CPU，具有四通道（但速度也较慢）内存，每个时钟 16B 可能会超出上限。
独立版本看起来不错（但内联版本不是），见下文！），循环是
## float __vector Sum(...) non-inlined version
.L3:
xorps xmm0, XMMWORD PTR [rdi]
add rdi, 16
cmp rdi, rax
jne .L3
这是 3 个融合域微指令，并且应该在每个时钟迭代一次时发出和执行。实际上，它不能，因为xorps融合比较和分支都需要端口5。
N是巨大的，所以笨重的一次字符水平异或的开销不会发挥作用，即使 gcc 4.7 为其发出糟糕的代码（sumVV存储到堆栈的多个副本等）。（请参阅在 x86 上进行水平浮点向量求和的最快方法，了解使用 SIMD 将数据减少到 4B 的方法。将movd数据放入整数寄存器并在最后 4B -> 1B 中使用整数移位/异或可能会更快，尤其是。如果您不使用 AVX。编译器可能能够利用al/ah低 8 位和高 8 位组件寄存器。）
## float __vector Sum(...) inlined into main at -O3
.L12:
xorps xmm0, XMMWORD PTR [rdx]
add rdx, 16
cmp rdx, rbx
movaps XMMWORD PTR [rsp+64], xmm0
jne .L12
它在每次迭代时存储累加器，而不是在最后一次迭代之后存储累加器！由于 gcc 没有/没有默认优化宏融合，它甚至没有将它们放在cmp/jne一起，以便它们可以在 Intel 和 AMD CPU 上融合成单个微指令，因此循环有 5 个融合域哦。这意味着如果 Nehalem 前端/循环缓冲区与 Sandybridge 循环缓冲区类似，它只能每 2 个时钟发出一次。uop 以 4 组为一组发出，并且预测采用的分支结束一个发出块。因此它以 4/1/4/1 uop 模式发出，而不是 4/4/4/4。这意味着每 2 个时钟的持续吞吐量我们最多可以获得 1 个 16B 负载。
-mtune=core2可能会使吞吐量加倍，因为它将它们放在cmp/jne一起。存储可以微融合到单个微指令中，xorps内存源操作数也可以。旧的 gcc 不支持-mtune=nehalem，或者更通用的-mtune=intel。Nehalem 可以维持每个时钟一次加载和一次存储，但显然循环中根本没有存储要好得多。
-O2 会产生更糟糕的代码：内联内部循环现在从内存加载累加器并存储它，因此累加器所属的循环携带依赖项中有一个存储转发往返：
## float __vector Sum(...) inlined at -O2
.L14:
movaps xmm0, XMMWORD PTR [rsp+16] # reload sum
xorps xmm0, XMMWORD PTR [rdx] # load data[i]
add rdx, 16
cmp rdx, rbx
movaps XMMWORD PTR [rsp+16], xmm0 # spill sum
jne .L14
至少使用 -O2 时，水平字节异或编译为普通整数字节循环，而不会将 xmm0 的 15 个副本喷射到堆栈上。
这只是完全脑残的代码，因为我们没有让引用/指针转义sumVV该函数，因此没有其他线程可以观察正在进行的累加器。（即使是这样，也没有同步阻止 gcc 在 reg 中累积并存储最终结果）。非内联版本仍然没问题。
-O2 -fno-tree-vectorize即使我将函数重命名为其他名称，直到gcc 4.9.2 为止，这个巨大的性能错误仍然存在main，因此它充分受益于 gcc 的优化工作。（不要将微基准测试放在里面main，因为 gcc 将其标记为“冷”并且优化较少。）
gcc 5.1 为template<>
__m128 Sum(const __m128* data, const int N). 我没有用 clang 检查。
这个额外的循环承载 dep 链几乎可以肯定是矢量版本的加速比较小的原因-O2。 即这是一个编译器错误，已在 gcc5 中修复。
带 -O2 的标量版本是
.L12:
xor bpl, BYTE PTR [rdx] # sumS, MEM[base: D.27594_156, offset: 0B]
add rdx, 1 # ivtmp.135,
cmp rdx, rbx # ivtmp.135, D.27613
jne .L12 #,
所以它基本上是最优的。Nehalem 每个时钟只能维持一个负载，因此无需使用更多累加器。
版本int是
.L18:
xor ecx, DWORD PTR [rdx] # sum, MEM[base: D.27549_296, offset: 0B]
add rdx, 4 # ivtmp.135,
cmp rbx, rdx # D.27613, ivtmp.135
jne .L18 #,
再说一遍，这正是您所期望的。它应该维持每个时钟的负载。
对于每个时钟可以承受两个负载的 uarch（Intel SnB 系列和 AMD），您应该使用两个累加器。编译器实现的-funroll-loops通常只是减少循环开销而不引入多个累加器。:(
您希望编译器生成如下代码：
xorps xmm0, xmm0
xorps xmm1, xmm1
.Lunrolled:
pxor xmm0, XMMWORD PTR [rdi]
pxor xmm1, XMMWORD PTR [rdi+16]
pxor xmm0, XMMWORD PTR [rdi+32]
pxor xmm1, XMMWORD PTR [rdi+48]
add rdi, 64
cmp rdi, rax
jb .Lunrolled
pxor xmm0, xmm1
# horizontal xor of xmm0
movhlps xmm1, xmm0
pxor xmm0, xmm1
...
按两个 ( pxor/// )进行滚动将形成pxor一个循环，该循环可以每 1c 进行一次迭代，但需要四个 ALU 执行端口。只有 Haswell 及更高版本可以跟上这个吞吐量。（或者 AMD Bulldozer 系列，因为向量和整数指令不会竞争执行端口，但相反，只有两个整数 ALU 管道，因此它们只能通过混合代码来最大化指令吞吐量。）addcmp/jne
这种四次展开是循环中的 6 个融合域微指令，因此它可以轻松地以每 2c 发出一个，并且 SnB/IvB 可以跟上每个时钟 3 个 ALU 微指令。
请注意，在通过 Broadwell 的 Intel Nehalem 上，pxor( ) 比( )_mm_xor_si128具有更好的吞吐量，因为它可以在更多执行端口上运行。如果您使用 AVX 但不使用 AVX2，则使用 256b而不是更有意义，因为需要 AVX2。xorps_mm_xor_ps_mm256_xor_ps_mm_xor_si128_mm256_xor_si256
Nehalem 的循环缓冲区（又名循环流解码器或 LSD）具有“一个时钟延迟”（根据Agner Fog 的 microarch pdf），因此如果我理解正确的话，带有 uops 的循环N将需要ceil(N/4.0) + 1多个周期才能从循环缓冲区中发出。他没有明确说明如果少于 4 个微指令，最后一组微指令会发生什么，但 SnB 系列 CPU 就是这样工作的（除以 4 并向上取整）。他们无法从所采用的分支之后的下一次迭代中发出微指令。我尝试用谷歌搜索有关 nehalem 的信息，但找不到任何有用的信息。
因此char和int循环可能以 1 个负载和xor每 2 个时钟运行一次（因为它们是 3 个融合域微指令）。循环展开可以将其吞吐量加倍，直至使装载端口饱和。SnB 系列 CPU 没有一个时钟延迟，因此它们可以在每次迭代时以一个时钟运行微小循环。
使用性能计数器或至少微基准来确保绝对吞吐量符合您的预期是一个好主意。仅凭您的相对测量结果，如果没有这种分析，您就没有任何迹象表明您将一半的表现留在桌面上。
矢量 -O3 循环是 5 个融合域微指令，因此应该需要三个时钟周期来发出。完成 16 倍的工作量，但每次迭代使用 3 个周期而不是 2 个周期，将使我们的速度提高16 * 2/3 = 10.66. 我们实际上比这要好一些，我不明白。
我将在这里停下来，而不是挖出一台 Nehalem 笔记本电脑并运行实际的基准测试，因为 Nehalem 太旧了，在这种细节级别上调整起来没什么意思。
你可能用 编译过吗-mtune=core2？或者也许您的 gcc 有不同的默认tune设置，并且没有拆分比较和分支？在这种情况下，前端可能不是瓶颈，吞吐量可能会受到内存带宽或内存错误依赖性的轻微限制：
Core 2 和 Nehalem 都在具有相同集合和偏移量（即距离是 4 kB 倍数）的内存地址之间存在错误相关性。
这可能会导致管道中每 4k 出现一个短气泡。
在我检查 Nehalem 的循环缓冲区并发现每个循环额外的 1c 之前，我有一个理论，现在我确信它是不正确的：
我认为循环中额外的存储微指令将其提升超过 4 微指令，本质上会将速度减半，因此您会看到大约 6 的加速。然而，也许存在一些执行瓶颈，使得前端问题吞吐量毕竟不是瓶颈？
或者 Nehalem 的循环缓冲区可能与 SnB 的不同，并且不会在预测采用的分支处结束问题组。16 * 4/5 = 12.8对于 -O3 向量循环，如果它是 5 个融合域微指令，则可以以一致的每个时钟 4 个发出，这将为 -O3 向量循环带来 的吞吐量加速。这与 12.6429 加速因子的实验数据非常吻合：由于带宽需求增加（当预取器落后时，偶尔会出现缓存未命中停顿），因此预计会略低于 12.8。
（标量循环仍然只在每个时钟运行一次迭代：每个时钟发出多次迭代仅意味着它们在每个时钟一次负载以及 1 周期循环xor携带依赖性上遇到瓶颈。）
这是不对的，因为xorps在 Nehalem 中只能在 port5 上运行，与融合比较和分支相同。因此，非展开向量循环不可能每 2 个周期运行一次以上迭代。
根据 Agner Fog 的表格，条件分支在 Nehalem 上的吞吐量为每 2c 一个，进一步证实这是一个虚假的理论。
在处理完全并行的数据时，SSE2 是最佳选择。例如
for (int i = 0 ; i < N ; ++i)
z[i] = _mm_xor_ps(x[i], y[i]);
但在您的情况下，循环的每次迭代都取决于前一次迭代的输出。这称为依赖链。简而言之，这意味着每个连续的异或操作都必须等待前一个异或操作的整个延迟才能继续，因此会降低吞吐量。
| 归档时间： |
|
| 查看次数： |
1182 次 |
| 最近记录： |