A64 Neon SIMD - 256-битное сравнение

Я хотел бы сравнить два 256-битных значения с прямым порядком байтов с инструкциями A64 Neon (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 байта, оставив только байт с нулями, если они есть.

            "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?

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

• Есть ли способ еще больше оптимизировать это? Я думаю, что трачу много циклов только на то, чтобы свести весь вектор к одному скалярному логическому значению.

Меньшее сравнение (‹)

Представим два целых числа как кортежи из 64-битных конечностей (с прямым порядком байтов):

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

Затем lhs ‹rhs, если это истинно:

(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-битных чисел, мы можем легко получить все требуемые значения (полезные значения в смелый):

• cmlo.2d => (l1 ‹r1), (l2‹ r2)
• cmlo.2d => (l3 ‹r3), (l4‹ r4)
• cmeq.2d => (l1 = r1), (l2 = r2)
• cmeq.2d => (l3 = r3), (l4 = r4)

Вопросы

• Имея эти значения в четырех регистрах SIMD, я теперь задаюсь вопросом, как лучше всего применять & и | операторы, а затем свести его к одному логическому типу.

Обновить

Я просто собрал рабочую реализацию на «меньше чем».

По сути, я заменил единицы, указанные выше, на повторяющееся условие, потому что A & A == A & 1.

Затем я раскладываю три квадрата 2x2 в своей матрице и выполняю побитовое И их. Теперь я уменьшаю с помощью побитового ИЛИ - сначала с двух векторов до одного вектора, затем до одного байта, затем копирую в регистр ARM и проверяю на 0xFF. Тот же образец, что и для равенства выше.

Вопрос выше по-прежнему в силе. Я не уверен, что код оптимален, и задаюсь вопросом, не пропустил ли я какой-то общий шаблон SIMD, чтобы делать такие вещи более эффективно. Также: Стоит ли NEON для таких случаев, когда входные операнды берутся из памяти?

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;
}