A64 NeonSIMD-256位比较

Question

我想比较两个小端点256位值与A64霓虹灯指令(asm)的效率.

等式(=)

为了平等，我已经找到了一个解决办法：

bool eq256(const UInt256 *lhs, const UInt256 *rhs) {
    bool result;

首先，将两个值加载到SIMD寄存器中。

    __asm__("ld1.2d    { v0, v1 }, %1    \n\t"
            "ld1.2d    { v2, v3 }, %2    \n\t"

将每一个64位的值进行比较。这将导致-1 (所有位集)的那些肢体是相等的，0(所有位清楚)，如果有一点不同。

            "cmeq.2d   v0, v0, v2        \n\t"
            "cmeq.2d   v1, v1, v3        \n\t"

将结果从2个向量减少到1个向量，如果存在，只保留包含"0 (所有比特清晰)“的向量。

            "uminp.16b v0, v0, v1        \n\t"

将结果从1向量减少到1字节，如果有0，只保留一个字节。

            "uminv.16b b0, v0            \n\t"

移动到ARM寄存器，然后与0xFF进行比较。这就是结果。

            "umov      %w0, v0.b[0]      \n\t"
            "cmp       %w0, 0xFF         \n\t"
            "cset      %w0, eq               "
            : "=r" (result)
            : "m" (*lhs->value), "m" (*rhs->value)
            : "v0", "v1", "v2", "v3", "cc");
    return result;
}

问题

• 这比用普通的老式ARM寄存器进行4次比较更有效吗？

- e.g. is there a source that quotes timings for the different operations? I'm doing this on iPhone 5s.

​

• 是否有进一步优化的方法？我认为我浪费了很多循环，只是为了将整个向量简化为一个单一的标量布尔值。

小于比较(<)

让我们将这两个ints表示为64位分支的元组(小endian)：

• lhs = (l0，l1，l2，l3)
• rhs = (r0，r1，r2，r3)

然后，lhs < rhs，如果计算结果为true：

(l3 < r3) &     1     &     1     &     1     |
(l3 = r3) & (l2 < r2) &     1     &     1     |
(l3 = r3) & (l2 = r2) & (l1 < r1) &     1     |
(l3 = r3) & (l2 = r2) & (l1 = r1) & (l0 < r0)

SIMD指令现在可以用于一次计算多个操作数。假设(l1，l2)，(l3，l4)，(r1，r2)，(r3，r4)是存储这两个256位数字的方式，我们可以很容易地获得所有所需的值(用粗体表示的有用值)：

• => (l1 < r1)，(l2 < r2)
• => (l3 < r3)，(l4 < r4)
• => (l1 = r1)，(l2 = r2)
• => (l3 = r3)，(l4 = r4)

问题

• 对于四个SIMD寄存器中的这些值，我现在想知道最好的策略是应用&和\\操作符，然后将其简化为一个布尔值。

更新

我刚把一个“小于”的工作实现拼凑在一起。

基本上，我用一个重复的条件替换了上面的1s，因为A & A == A & 1。

然后，我在我的矩阵中放置了三个2x2平方，并按位排列。现在，我使用按位for减少--首先从两个向量减少到一个向量，然后减少到一个字节，然后复制到ARM寄存器，然后测试0xFF。与上面的平等模式相同。

上述问题仍然有效。我还不确定代码是否是最优的，并且不知道我是否错过了一些通用的SIMD模式来更有效地完成这些工作。另外:当输入操作数来自内存时，在这种情况下，霓虹灯值得吗？

bool lt256(const UInt256 *lhs, const UInt256 *rhs) {
    bool result;
    __asm__(// (l3 < r3) & (l3 < r3) |
            // (l3 = r3) & (l2 < r2) |
            // (l3 = r3) & (l2 = r2) & (l1 < r1) & (l1 < r1) |
            // (l3 = r3) & (l2 = r2) & (l1 = r1) & (l0 < r0)

            "ld1.2d    { v0, v1 }, %1    \n\t"
            "ld1.2d    { v2, v3 }, %2    \n\t"

            // v0: [ l3 = r3 ] [ l2 = r2 ]
            // v1: [ l0 < r0 ] [ l1 < r1 ]
            // v2: [ l0 = r0 ] [ l1 = r1 ]
            // v3: [ l2 < r2 ] [ l3 < r3 ]
            // v4: [ l2 = r2 ] [ l3 = r3 ]
            "cmeq.2d   v4, v1, v3        \n\t"
            "cmlo.2d   v3, v1, v3        \n\t"
            "cmlo.2d   v1, v0, v2        \n\t"
            "cmeq.2d   v2, v0, v2        \n\t"
            "ext.16b   v0, v4, v4, 8     \n\t"

            // v2: [ l1 < r1 ] [ l1 = r1 ]
            // v1: [ l1 < r1 ] [ l0 < r0 ]
            "trn2.2d   v2, v1, v2        \n\t"
            "ext.16b   v1, v1, v1, 8     \n\t"

            // v1: [ l1 < r1  &  l1 < r1 ] [ l1 = r1  &  l0 < r0 ]
            "and.16b   v1, v2, v1        \n\t"

            // v2: [ l3 < r3 ] [ l3 = r3 ]
            // v3: [ l3 < r3 ] [ l2 < r2 ]
            "ext.16b   v2, v3, v0, 8     \n\t"
            "ext.16b   v3, v3, v3, 8     \n\t"

            // v3: [ l3 < r3  &  l3 < r3 ] [ l3 = r3  &  l2 < r2 ]
            "and.16b   v3, v2, v3        \n\t"

            // v2: [ l3 = r3 ] [ l3 = r3 ]
            // v4: [ l2 = r2 ] [ l2 = r2 ]
            "ext.16b   v2, v4, v0, 8     \n\t"
            "ext.16b   v4, v0, v4, 8     \n\t"

            // v2: [ l3 = r3  &  l2 = r2 ] [ l3 = r3  &  l2 = r2 ]
            "and.16b   v2, v2, v4        \n\t"

            // v1: [ l3 = r3 & l2 = r2 & l1 < r1 & l1 < r1 ]
            //     [ lr = r3 & l2 = r2 & l1 = r1 & l0 < r0 ]
            "and.16b   v1, v2, v1        \n\t"

            // v1: [ l3 < r3 & l3 < r3 |
            //       l3 = r3 & l2 = r2 & l1 < r1 & l1 < r1 ]
            //     [ l3 = r3 & l2 < r2 |
            //       lr = r3 & l2 = r2 & l1 = r1 & l0 < r0 ]
            "orr.16b   v1, v3, v1        \n\t"

            // b1: [ l3 < r3 & l3 < r3 |
            //       l3 = r3 & l2 = r2 & l1 < r1 & l1 < r1 |
            //       l3 = r3 & l2 < r2 |
            //       lr = r3 & l2 = r2 & l1 = r1 & l0 < r0 ]
            "umaxv.16b b1, v1            \n\t"
            "umov      %w0, v1.b[0]      \n\t"
            "cmp       %w0, 0xFF         \n\t"
            "cset      %w0, eq"
            : "=r" (result)
            : "m" (*lhs->value), "m" (*rhs->value)
            : "v0", "v1", "v2", "v3", "v4", "cc");
    return result;
}

Answer 1

使用基于Swift的测试运行程序使用XCTest measureMetrics进行基准测试。两个256位Ints被分配.然后，在相同的两个ints上重复操作1亿次，停止测量，用arc4random为两个ints的每个分支分配一个新的随机值。使用附加仪器执行第二次运行，并将每条指令的CPU时间分布记录为其旁边的注释。

Equality (==)

同样，当结果从SIMD寄存器转移回ARM寄存器时，SIMD似乎会丢失。当结果用于进一步的SIMD计算时，或者如果使用比256位更长的it (ld1似乎比ldp更快)，SIMD可能是值得的。

• SIMD bool结果；__asm__("ld1.2d { v0，v1 }，%1 \n\t“// 5.1% "ld1.2d { v2，v3 }，%2nt”// 26.4% "cmeq.2d v0，v0，v2 \n "cmeq.2d v1，v1，v3 \n\t“uminp.16b v0，v0，v1 \n“// 4.0% "uminv.16b b0，v0 \n”/ 26.7% "umov %w0，v0.bnt“/ 32.9% "cmp %w0，0xFF \n”/ 0.0% "cset %w0，eq："=r“(结果)："m”(*lhs->value)、"m“(*rhs->value)："v0”、"v1“、"v2”、"v3“、"cc")；返回结果；// 4.9% ("ret") 测量时间，秒平均: 11.558，相对标准偏差: 0.065%，值: 11.572626，11.560558，11.549322，11.568718，11.558530，11.550490，11.557086，11.551803，11.557529，11.549782
• 标准 这里的获胜者。ccmp指令确实在这里闪闪发光:-)显然，问题是内存绑定的。 bool结果；__asm__(“自民党x8，x9，%1 \n\t”// 33.4%“自民党x10，x11，%2 \n\t”"cmp x8，x10 \n“”cmp x9，x11，0，eq \n t“自民党x8，x9，%1，16 \n“// 34.1%”自民党x10，x11，%2，16 \t "ccmp x8，x10，0，eq \n t“/ 32.6% "ccmp x9，x11，0，eq \n "cset %w0，eq \n\t："=r“(结果)："m”(*lhs->value)、"m“(*rhs->value)："x8”、"x9“、"x10”、"x11“、"cc")；返回结果； 测量时间，秒平均: 11.146，相对标准偏差: 0.034%，值: 11.149754，11.142854，11.146840，11.149392，11.141254，11.148708，11.142293，11.150491，11.139593，11.145873
• C LLVM无法检测到"ccmp“是这里使用的一个很好的指令，并且比上面的asm版本慢。 返回lhs->值== rhs->lhs->Vale1 == rhs->value 1& lhs->value 2 == rhs->value 2&lhs->value 3 == rhs->==rhs->value 2==rhs->value 3==rhs->value 3==rhs->value 2==rhs->value 3==rhs->value 3==rhs->value 2==rhs->value 3==rhs->value 3==rhs->value 2==rhs->value 3==rhs->value 3==rhs->value 2==rhs->value 3==rhs->value 3==rh 汇编成 自民党x8、x9、x0 // 24.1%自民党x10、x11、x1 / 0.1% cmp x8、x10 / 0.4% cset w8、eq / 1.0% cmp x9、x11 // 23.7% cset w9、eq和w8、w8、w9 / 0.1% ldp x9、x10、x0、#16自民党x11、x12、x1、#16 / 24.8% cmp x9、x11 cset w9、eq / 0.2%和w8，w8，w9 cmp x10，x12 // 0.3% cset w9，eq // 25.2%和w0，w8，w9 ret / 0.1% 测量时间，秒平均: 11.531，相对标准偏差: 0.040%，值: 11.525511，11.529820，11.541940，11.531776，11.533287，11.526628，11.531392，11.526037，11.531784，11.533786

小于(<)

(待定-稍后更新)

Answer 2

由于简单的标量ccmp实现是等式测试的赢家，下面是一个同样简单的标量解决方案。

上述方法是基于词典比较，从最重要的肢体开始。我看不出用ccmp做这件事的好方法。问题是，在一个没有分支的字典比较中，在每一步中都有三种可能的状态:前肢比较少，前肢比较大，所有先前的肢体比较相等。ccmp不能真正跟踪三个州。如果ccmp在条件为false时的行为是“什么都不做”，比如使用ARM32条件，而不是“立即加载标志”，我们就可以这样做。

因此，这里有一个更基本的方法:做一个多精度的减法，并检查末尾的进位标志。

inline bool lt256(const uint64_t *a, const uint64_t *b) {
    const int limbs = 4;  // number of 64-bit chunks in a full number
    uint64_t a0,a1,b0,b1; // for scratch registers
    bool ret;
    asm(R"(
        ldp %[a0], %[a1], [%[a]]
        ldp %[b0], %[b1], [%[b]]
        subs xzr, %[a0], %[b0]
        sbcs xzr, %[a1], %[b1]
        ldp %[a0], %[a1], [%[a], #16]
        ldp %[b0], %[b1], [%[b], #16]
        sbcs xzr, %[a0], %[b0]
        sbcs xzr, %[a1], %[b1]
        )"
        : "=@cclo" (ret),
          [a0] "=&r" (a0), [a1] "=&r" (a1), [b0] "=&r" (b0), [b1] "=&r" (b1)
        : [a] "r" (a), [b] "r" (b),
          "m" (*(const uint64_t (*)[limbs])a),
          "m" (*(const uint64_t (*)[limbs])b)
        );
    return ret;
}

我选择对结果使用标志输出操作数，而不是显式地将布尔值写入寄存器。(在编写之前的答案时，这个特性并不存在于稳定的GCC版本中，而且ClangforAArch64仍然不支持这个特性。)这可以保存一个指令和一个寄存器，如果结果将被分支。

我还选择在asm中执行负载。我们还可以使用8个输入操作数，并让编译器执行加载，但是接下来我们需要8个寄存器，而不是现有的4-6寄存器。值得一试，如果有理由认为，四肢已经在通用寄存器。或者，您可以进一步减少寄存器的使用，方法是一次加载一对分支，而不是两个，但代价是代码更大，而且可能更慢。

零寄存器提供了一种方便的方法来丢弃减法的数值结果，因为我们不需要它们。

性能应该非常类似于ccmp-based eq256，因为它们本质上都是依赖链中的四个减法。以Cortex-A72为例，cmp/ccmp和subs/sbcs都是可以在两个整数管道之一上执行的单uop指令。他们不会说这些标志是否被重命名，但是如果它们被重命名了，那么您应该能够串联编写两条这样的链，并让它们并行执行。