8

我对掩蔽在理论上可以对分支做什么感到困惑。假设我有一个 Skylake-SP(哈,我希望..),我们忽略了编译器功能,这在理论上是可能的:

如果分支条件依赖于静态标志,并且所有分支都将数组设置为计算结果,假设编译器无论如何都不会将其优化为两个单独的循环,它可以向量化吗?

do i = 1, nx
  if (my_flag .eq. 0) then
    a(i) = b(i) ** 2
  else
    a(i) = b(i) ** 3
  end if
end do

如果仅作为分支的子集设置有问题的值,它可以向量化吗?

do i = 1, nx
  if (my_flag .eq. 0) then
    a(i) = b(i) ** 2
  end if
end do

如果分支条件本身依赖于向量数据,它可以向量化吗?

do i = 1, nx
  if (c(i) > 0) then
    a(i) = b(i) ** 2
  else
    a(i) = b(i) ** 3
  end if
end do
4

2 回答 2

7

是的,对于所有循环,SSE2 / SSE4.1 (for blendps) / AVX / AVX-512 中的任何一个都可以实现高效的 asm,并且编译器在实践中会自动矢量化,但是 gcc7.2 / clang5.0 / ICC18 都错过了优化。

根据对 Skylake-AVX512 的静态分析(见下文),最终循环的有效展开实现可以在每 1.25 个时钟周期以一个 64 字节的结果向量运行(加上循环开销取决于展开的数量)。在实践中,如果您的数据在 L1D 缓存中很热,则每个向量可能可以实现 1.33 或 1.5 个时钟周期。否则,您很容易成为 L2 带宽的瓶颈,因为每个存储向量 64B 存储加载 2x 64B。

对于循环的 C 版本,gcc、clang 和 ICC 都或多或少地像我手动一样自动矢量化:请参阅Godbolt 编译器资源管理器上的 source + asm 。

我不得不使用-ffast-mathgcc 来自动矢量化。IDK 为什么它没有意识到它可以在不违反严格的 FP 规则的情况下安全地自动矢量化。

Clang 似乎在单独评估tmp*tmptmp*tmp*tmp混合这两个结果,而不是有条件地进行第二次乘法。

gcc 进行乘法运算并使用单独的 movaps 以另一种方式合并,因为它不知道如何反转条件。

ICC 用于KNOTW反转条件,然后像我一样使用合并屏蔽进行第二次乘法。

更改代码以在分支而不是分支中进行额外的乘法(**3而不是**2),这使得所有 3 个编译器都生成了更好的代码ifelse,而它们的每一个错过的优化都不会从另一个方向分支。(仍然缺少对 gcc 的优化,但 ICC 和 clang 看起来很可靠,它们基本上都在做我手写代码所做的事情。)

ICC 选择仅使用 256b 向量对其进行自动向量化。也许它默认这样做是为了避免降低最大涡轮时钟速度?也许可以选择使用全角向量?gcc 8.0 快照也这样做,但 gcc7.2 使用 ZMM 向量。


AVX-512 掩码寄存器和合并掩码使其更加高效,但是很长一段时间以来,双向执行然后混合一直是 SIMD(甚至非 SIMD 无分支代码)的事情。例如,根据向量比较结果有条件地相加,使用该向量比较结果作为 AND 掩码,使某些元素保持不变,并使其他元素为零。

0是加法恒等式:x + 0 = x. x + (y&mask)如果掩码全为零,或者掩码全为一,则无操作也是如此x+y。请参阅如何在内部函数中使用 if 条件。(有趣的技巧:使用压缩比较结果作为整数 -1 或 0,因此您可以计算匹配但减去比较掩码)。

乘法不太简单,因为1它是乘法恒等式,但您可以通过混合来解决这个问题。

假设编译器无论如何都没有将其优化为两个单独的循环,它可以向量化吗?

在第一种情况下,如果编译器没有将条件提升到循环之外并进行两个循环,那么您应该对编译器不满意。特别是在第二种情况下,它只需要一个循环,因为如果条件为假,则不会修改数组。


让我们谈谈第三种情况,因为它只是编译器不应该只提升条件的一种情况。(如果你的编译器感觉很笨,它可以使用这个版本和其他版本的全零或全一的循环不变掩码)。

if (c(i) > 0)

所以我们需要加载一个元素向量c并与零进行比较。AVX512 可以对 16 个单精度向量执行此float操作,其中一条指令具有掩码寄存器目标和内存源操作数。

; with zmm0 = 0.0 in all elements, from vxorps xmm0,xmm0,xmm0 outside the loop.
vcmpps    k1, zmm0, [rdx],  _CMP_NLT_UQ     ; !(0 < c(i))

我知道(已经写下下一部分)对于条件为假的元素,我想要k1为真。c(i) > 0只有第二个向量操作数可以是内存而不是寄存器,所以我不得不反转它并使用不小于而不是不大于。(而且我不能只使用>=而不是<,因为这会将无序的情况(一个或两个 NaN)放在错误的类别中。FP 比较有 4 个可能的结果:高于/低于/等于/无序,所以你必须选择一个对于所有 4 种情况,您想要的谓词(即源所说的,如果您是编译器)。如果您使用 编译-ffast-math,则允许编译器忽略 NaN 的可能性。

如果您需要将两个条件链接在一起,AVX512 compare-into-mask 指令可以使用零掩码或合并掩码来掩码写入掩码的操作。

vcmpltps    k1,        zmm1, zmm2       ; k1 = zmm1<zmm2
vcmpltps    k2{k1}{z}, zmm3, zmm4       ; k2 = (zmm3<zmm4) & (zmm1<zmm2)

k2在 zmm3k1 为零的任何地方都是 0,因为我们用作k1零掩码。


  if (c(i) > 0) then
    a(i) = b(i) ** 2
  else
    a(i) = b(i) ** 3
  end if

这里的常见子表达式b(i) * b(i). 我们可以b(i)**3通过乘以b(i)一个额外的时间来得到。

vmovups    zmm1, [rsi]       ; load a vector from b(i)
vmulps     zmm2, zmm1, zmm1  ; zmm2 = zmm1*zmm1 = b(i)**2

AVX-512 可以基于掩码作为(几乎)任何其他指令的一部分进行合并。

vmulps     zmm2{k1}, zmm2, zmm1  ; zmm2 *= zmm1   for elements where k1 is true

vmovups    [rdi], zmm2           ; store all 16 elements into a(i)

顺便说一句,AVX512 具有商店的合并屏蔽功能。以前的 SIMD 指令集将从 加载[rdi]、混合,然后存储回[rdi]. 这意味着您可以a(i)使用每个元素条件比使用 AVX1/AVX2 更有效地实现第二个循环(有时保持不变)。


把这一切放在一起:(NASM语法)

 ; x86-64 System V calling convention
 ; args: rdi = a() output array.
 ;       rsi = b() input array
 ;       rdx = c() array to be tested for positive numbers
 ;       rcx = count (in elements)
 ; preferably all 64-byte aligned, but will work slowly if some aren't
 ; rcx must be >= 16, and a multiple of 16, because I didn't write any cleanup code

global square_or_cube
square_or_cube: 

    vxorps     xmm0,  xmm0,xmm0

 .loop:                          ; do {
    vcmpps     k1, zmm0, [rdx], 21    ; _CMP_NLT_UQ  ; !(0 < c(i))

    vmovups    zmm1, [rsi]            ; load a vector from b(i)
    vmulps     zmm2,     zmm1, zmm1   ; zmm2 = zmm1*zmm1 = b(i)**2

    vmulps     zmm2{k1}, zmm2, zmm1   ; zmm2 *= zmm1   for elements where k1 is true, otherwise unmodified.
    vmovups    [rdi], zmm2            ; store all 16 elements into a(i)

    ; TODO: unroll some and/or use indexed addressing mode tricks to save instructions
    add         rdi, 64      ; pointer increments
    add         rsi, 64
    add         rdx, 64

    sub         rcx, 16         ;  count -= 16 
    ja        .loop             ; } while(count>0);

我用 IACA 分析了这个(省略了指针增量指令来模拟展开和更聪明的 asm 技巧)。根据 IACA 的说法,即使是合并屏蔽vmulps也是单个 uop,并且内存源指令微融合到前端的单个 uop。(商店也是。)这就是我所希望的,IACA 的输出在这种情况下看起来是正确的,尽管我无法访问 SKL-SP 硬件上的性能计数器来检查这一点。

$ iaca.sh -arch SKX avx512-conditional
Intel(R) Architecture Code Analyzer Version - 2.3 build:246dfea (Thu, 6 Jul 2017 13:38:05 +0300)
Analyzed File - avx512-conditional
Binary Format - 64Bit
Architecture  - SKX
Analysis Type - Throughput

Throughput Analysis Report
--------------------------
Block Throughput: 1.50 Cycles       Throughput Bottleneck: FrontEnd

Port Binding In Cycles Per Iteration:
---------------------------------------------------------------------------------------
|  Port  |  0   -  DV  |  1   |  2   -  D   |  3   -  D   |  4   |  5   |  6   |  7   |
---------------------------------------------------------------------------------------
| Cycles | 1.5    0.0  | 0.0  | 1.0    1.0  | 1.0    1.0  | 1.0  | 1.5  | 1.0  | 1.0  |
---------------------------------------------------------------------------------------

N - port number or number of cycles resource conflict caused delay, DV - Divider pipe (on port 0)
D - Data fetch pipe (on ports 2 and 3), CP - on a critical path
F - Macro Fusion with the previous instruction occurred
* - instruction micro-ops not bound to a port
^ - Micro Fusion happened
# - ESP Tracking sync uop was issued
@ - SSE instruction followed an AVX256/AVX512 instruction, dozens of cycles penalty is expected
X - instruction not supported, was not accounted in Analysis

| Num Of |                    Ports pressure in cycles                     |    |
|  Uops  |  0  - DV  |  1  |  2  -  D  |  3  -  D  |  4  |  5  |  6  |  7  |    |
---------------------------------------------------------------------------------
|   2^   |           |     | 1.0   1.0 |           |     | 1.0 |     |     | CP | vcmpps k1, zmm0, zmmword ptr [rdx], 0x15
|   1    |           |     |           | 1.0   1.0 |     |     |     |     |    | vmovups zmm1, zmmword ptr [rsi]
|   1    | 1.0       |     |           |           |     |     |     |     | CP | vmulps zmm2, zmm1, zmm1
|   1    | 0.5       |     |           |           |     | 0.5 |     |     | CP | vmulps zmm2{k1}, zmm2, zmm1
|   2^   |           |     |           |           | 1.0 |     |     | 1.0 |    | vmovups zmmword ptr [rdi], zmm2
|   1    |           |     |           |           |     |     | 1.0 |     |    | sub rcx, 0x10
|   0F   |           |     |           |           |     |     |     |     |    | jnbe 0xffffffffffffffdd
Total Num Of Uops: 8

AVX-512 实际上有vfpclassps(C/C++ intrinsic [_mm512_fpclass_ps_mask] 4,asm 文档,在相关vfpclasspd(packed double)中有一个表) 可以根据您选择的谓词对 FP 值进行分类。它可能比对另一个恰好为零的寄存器进行完全比较更有效。
(实际上,根据 IACA,它不是。InstLatx64 电子表格将两者都列为 3 个周期延迟。Agnercmpps Fog在 Skylake-S(非 AVX512 桌面芯片)上对 AVX2 的测量显示 4 个周期,所以奇怪的是 AVX512在生成掩码寄存器结果而不是向量时,版本具有较低的延迟。

我希望结果仅对正数为假,我认为vfpclassps可以通过设置几乎所有谓词位来获得 -Inf、有限负数、安静和信号 NaN、-0.0 和 +0.0 来做到这一点。

vfpclassps    k1, [rdx], 0x1 | 0x2 | 0x4 | 0x10 | 0x40 | 0x80     ; QNaN | -0.0 | +0.0 | -Infinity | Negative (finite) | SNaN
; k1 = a 16-bit bitmap of which elements (from memory at [rdx]) need an extra multiply

vpfclassps很有趣,因为它可以让您区分 +0.0 和 -0.0,就像您可以通过检查二进制表示中的符号位一样(就像您可以使用 AVX2vblendps将符号位用作混合控制,而无需先进行比较)。

此外,在这种情况下,它会在循环之外保存一条指令,设置一个全零寄存器。


相关:AVX512 具有乘以2**floor(x)( vscalefpd) 的指令,但不能将数字提高到任意幂(整数或其他)。 Xeon Phi 有 AVX512ER,它可以为您提供快速的近似值2**x(没有地板x),但我们也不能在这里直接使用指数函数,而且 SKL-SP 无论如何都没有 AVX512ER。


IACA_start / end 的 NASM 宏

我是基于iaca_marks.hC/C++ 头文件编写的。

%if 1
%macro  IACA_start 0
     mov ebx, 111
     db 0x64, 0x67, 0x90
%endmacro
%macro  IACA_end 0
     mov ebx, 222
     db 0x64, 0x67, 0x90
%endmacro
%else
%define IACA_start
%define IACA_end
%endif

将它们包裹在您要分析的任何代码周围。


循环内循环不变条件的条件分支

编译器可以在循环内分支。IDK 如果有的话会编写这样的代码,但他们当然可以。

; rdi = destination
; rsi = source
; edx = condition
; rcx = element count
global square_or_cube
square_or_cube: 

 .loop:                          ; do {
    vmovups    zmm1, [rsi]            ; load a vector from b(i)
    vmulps     zmm2, zmm1, zmm1   ; zmm2 = zmm1*zmm1 = b(i)**2

    test       edx,edx
    jz        .only_square        ; test-and-branch to conditionally skip the 2nd multiply
    vmulps     zmm2, zmm2, zmm1   ; zmm2 *= zmm1
   .only_square:

    vmovups    [rdi], zmm2        ; store all 16 elements into a(i)

    add         rdi, 64      ; pointer increments
    add         rsi, 64

    sub         rcx, 16         ;  count -= 16 
    ja        .loop             ; } while(count>0);
于 2017-11-25T11:37:31.900 回答
4

注意:这个答案主要讨论了一个非常具体的内存访问问题,当涉及到矢量化时,它主要适用于概念级别,将一系列对数组的标量访问转换为矢量化访问,而不假设底层数组的哪些部分被映射. 在像 Fortran 这样的语言中,语言本身的语义可以保证数组是连续映射的,或者在进入循环之前进行边界检查可能足以避免下面提到的问题。

一般来说,这个答案不应该被视为对矢量化的良好处理,当然也不应该专门用于 Fortran。另一个答案中出现了对矢量化问题的更全面的处理,该答案也专门针对 AVX-512。


向量化条件经常被忽视的一个问题是,编译器可以通过混合或其他逐元素预测技术对您感兴趣的类型的条件循环进行向量化,前提是它们可以证明向量化访问的元素与在标量逐个元素的实现。如果指令集没有提供一种元素方式来执行向量加载,或者编译器无法使用它们,这可以有效地阻止向量化。

换句话说,如果通过循环体的所有路径都访问相同的元素,编译器通常只能使用纯向量加载完全向量化。

根本原因是编译后的代码不能访问原始代码语义未访问的元素,即使它们后来被“混合”,因为这样做可能会导致错误!如果指令集没有提供指令来有条件地访问内存中的元素并抑制未选择元素的故障,那么这是优化的一个重要障碍。

在您给出的示例中,这意味着(1)和(3)可以“在不提升条件”的情况下进行矢量化,而(2)不能,因为(2)访问a[i]并且b[i]仅在if正文中,但如果if不执行. 当然,一个真正的编译器只会在循环中提升一个微不足道的标志检查,并且在这种myflag == false情况下根本不执行循环,所以这不是一个很好的例子。

让我们看几个包含所有示例的案例。首先,我们需要一个不能被提升的标志——让我们只使用一个bool值数组。因此,一个带有输出数组a、两个输入数组bc一个标志数组的有趣的通用循环f可能看起来像:

do i = 1, nx
  if (f(i) > 0) then
    a(i) = g(b(i), c(i));
  else
    a(i) = h(b(i), c(i));
  end if
end do

根据f(i)与每个元素对应的标志,我们将函数应用gh输入元素b(i)c(i)。根据我上面的条件,我们只有在两者g并且h实际访问 和 的相同元素时才能进行矢量bc

让我们继续看上面的两个实际工作示例:

void example1(bool* f, int* __restrict__ a, int* __restrict__ b, int* __restrict__ c, size_t n) {
    for (size_t i = 0; i < n; i++) {
        if (f[i]) {
            a[i] = b[i];
        } else {
            a[i] = c[i];
        }
    }
}

void example2(bool* f, int* __restrict__ a, int* __restrict__ b, int* __restrict__ c, size_t n) {
    for (size_t i = 0; i < n; i++) {
        if (f[i]) {
            a[i] = b[i] + c[i] ;
        } else {
            a[i] = b[i] - c[i] * 2 + 1 ;
        }
    }
}

两者具有相同的基本形式,但哪个更难矢量化?第一个是简单的直接分配b[i]或者c[i]取决于标志。第二个是两者 b[i]的更复杂的功能,并且c[i]在两条路径上都存在显着差异。

好吧,第二个更容易矢量化,因为它可以b[i]无条件c[i]地访问。事实上,gcc由于某种原因,它无法对任何一个进行矢量化。clang仅矢量化第二个。有点令人惊讶地icc设法将两者矢量化- 因为它足够聪明,可以使用vpmaskmovd它是一个掩蔽负载,它可以抑制未加载元素的故障。

您可以在 godbolt 上检查生成的程序集

我最初开始这个答案的想法是访问不同的数组元素目前是当前编译器矢量化的一个不可逾越的障碍,但那是因为我通常不检查icc. icc以这种方式使用蒙面动作对我来说实际上是新闻。所以障碍就在那里,但至少有一些编译器可以解决它2

作为开发人员,您通常知道两个数组都是完全可访问的,因此访问范围内的所有元素是安全的,b并且最好将其传达给编译器。我尝试添加无条件的虚拟语句,例如or应该编译为空,但至少允许编译器从语义上看到所有元素都被访问。确实“编译掉”,但代码生成没有改进:没有发生额外的矢量化。在向量化分析完成之前,它们可能已经在编译过程的早期被消除,因此向量化器会丢失信息。c[0, n)b[i] = b[i]; c[i] = c[i];... + c[i] * 0

除了不自由且不完全通用的屏蔽移动指令之外,还有其他方法可以改善这种情况吗?编译器可以利用其对平台内存保护模型的了解。例如,一旦 x86 上 4K 页面中的任何字节被访问,就可以自由读取该页面上的所有其他字节。可以想象一个复杂的实现,它以安全的标量代码开始,但是一旦“注意到”对两个数组的写入,就会切换到页面其余部分的向量化循环。

如果数组访问是对齐的,则可以使用类似的技巧:向量化循环可以检查标志数组是一致为 0 还是一致为 1,如果不是,则使用直接的无条件无掩码读取实现是安全的,否则它将回退到更多认真执行。这种转换显然只有在掩码很少统一或几乎总是统一3的情况下才会有利可图,因此在实践中可能不太可能实施。


2至少在 AVX 可用的情况下:icc如果您将第一个示例限制为前 AVX 指令,它仍然无法矢量化,因为那vpmaskmovd/qvmaskmovps/pd引入的时间。

3由于在这种情况下,如果您已经确定蒙版是统一的,您可以无条件地执行操作,只需根据它是统一的还是统一的,只执行 的选定侧而不if进行任何掩蔽/混合。因此,您最终会得到三个内部实现的循环:全零标志情况、全一标志情况和混合标志情况,当下一个标志向量与当前循环不同时,它们之间会跳转.01

于 2017-11-25T22:27:36.847 回答