Векторизация с неуравновешенными буферами: использование VMASKMOVPS: создание маски из подсчета несоосности? Или не использовать этот insn вообще

Ответ 1

Только для AVX: неуправляемые обращения в начале и конце, конвейерные нагрузки, чтобы избежать проблем при перезаписи на месте.

Благодаря @StephenCanon для указания на то, что это лучше, чем VMASKMOVPS для всего, что VMASKMOVPS может сделать, чтобы помочь с циклизацией по неуравновешенным буферам.

Это может быть немного, что ожидать от компилятора, как преобразования цикла, особенно. так как очевидный способ может сделать Valgrind несчастливым (см. ниже).

section .text
global floatmul   ; (float *rdi)
floatmul:

    lea    rdx, [rdi + 4096 - 32]  ; one full vector less than the end address (calculated *before* masking for alignment).
                ;;  replace 4096 with rsi*4 if rsi has the count (in floats, not bytes)

    vmovups  ymm0, [rdi]
    vaddps   ymm0, ymm0, ymm0   ; *= 2.0
    ; don't store yet

    lea    rax, [rdi+32]
    and    rax, ~0x1c           ; 0x1c = 7 << 2 = 0b11100
    vmovups  ymm1, [rax]        ; first aligned vector, for use by first loop iteration

    vmovups  [rdi], ymm0        ; store the first unaligned vector
    vmovups  ymm0, [rdx]        ; load the *last* unaligned vector

.loop:
      ;; on entry: [rax] is already loaded into ymm1
    vaddps   ymm1, ymm1, ymm1   ; *= 2.0
    vmovups  [rax]              ; vmovaps would fault if p%4 != 0
    add      rax, 32
    vmovups  ymm1, [rax]
    cmp      rax, rdx           ; while( (p+=8) < (endp-8) );
    jb  .loop

    ; discard ymm1.  It includes data from beyond the end of the array (aligned case: same as ymm0)

    vaddss   ymm0, ymm0, ymm0   ; the last 32B, which we loaded before the loop
    vmovups  [rdx], ymm0
    ret

    ;   End alignment:
    ; a[] = XXXX XXXX ABCD E___    _ = garbage past the end
    ;                  ^rdx
    ;       ^rax ^rax ^rax ^rax(loop exit)

    ;   ymm0 = BCDE
    ;   ymm1 loops over ..., XXXX, ABCD, E___
    ;   The last load off the end of the array includes garbage
    ;     because we pipeline the load for the next iteration

Выполнение нагрузки с конца массива в начале цикла кажется немного странным, но, надеюсь, он не путает аппаратные префетеры или замедляет получение потока массива из памяти.

Накладные:

• 2 дополнительных целочисленных значения общего числа (для настройки выровненного старта). Мы уже используем конечный указатель для нормальной структуры цикла, так что бесплатно.

• 2 дополнительных копии тела цикла (load/calc/store). (Первая и последняя итерация очищена).

Составители, вероятно, не будут довольны выдачей кода, подобного этому, при автоиндексировании. Valgrind сообщит о доступе за пределами границ массива, и делает это с помощью инструкций с одним шагом и декодированием, чтобы увидеть, к чему они обращаются. Поэтому просто оставаться на одной странице (и строке кэша), поскольку последний элемент в массиве недостаточен. Также обратите внимание, что если указатель ввода не выровнен по 4B, мы можем потенциально прочитать на другой странице и segfault.

Чтобы Valgrind был счастлив, мы могли бы остановить цикл в два вектора ширины раньше, чтобы выполнить загрузку специального блока невязанной последней ширины вектора массива. Это потребует дублирования тела цикла в дополнительное время (в этом примере это незначительно, но это просто тривиально). Или, может быть, избегайте конвейерной обработки, если код intro перейдет в середину цикла. (Это может быть неоптимальным для uop-cache, хотя: (части) тела цикла могут закончиться в кэше uop дважды.)

TODO: напишите версию, которая переходит в цикл в середине.

Ответ 2

Загрузите маску для VMOVMASKPS из окна в таблицу. AVX2 или AVX1 с несколькими дополнительными инструкциями или большой таблицей.

Маска также может использоваться для ANDPS в регистрах в редукции, которая должна подсчитывать каждый элемент ровно один раз. Как отмечает Стивен Канон в комментариях к OP, конвейерные нагрузки могут позволить перекрывать неглавные магазины для работы даже для функции перезаписи на месте, как в примере, который я выбрал, поэтому VMASKMOVPS НЕ лучший выбор здесь.

Это должно быть хорошо на процессорах Intel, особенно. Haswell и позже для AVX2.

Метод Agner Fog для получения маски pshufb фактически обеспечил идею, которая очень эффективна: выполните неодинаковую нагрузку, беря окно данных из таблицы. Вместо гигантской таблицы масок используйте индекс как способ сделать байтовый сдвиг данных в памяти.

Маски в порядке младшего байта LSB (поскольку они хранятся в памяти), а не обычные обозначения для элементов {X3,X2,X1,X0} в векторе. Как написано, они выстраиваются в линию с выровненным окном, включающим начало/конец входного массива в памяти.

• start misalign count = 0: mask = all-ones (Aligned case)
• start misalign count = 1: mask = {0,-1,-1,-1,-1,-1,-1,-1} (пропустить одно в первом 32B)
• ...

• start misalign count = 7: mask = {0, 0, 0, 0, 0, 0, 0,-1} (пропустите все, кроме одного в первых 32B)

• end misalign count = 0: никаких конечных элементов. mask = all-ones (Приоритет).
  это нечетный случай, не похожий на count = 1. Пара дополнительных инструкций для этого специального случая стоит избегать дополнительной итерации цикла и очистки с маской всех нулей.

• end misalign count = 1: один конечный элемент. mask = {-1, 0, 0, 0, 0, 0, 0, 0}
• ...
• end misalign count = 7: seven trailing elems. mask = {-1,-1,-1,-1,-1,-1,-1, 0}

Неиспользованный код, предположим, что есть ошибки

section .data
align 32  ; preferably no cache-line boundaries inside the table

; byte elements, to be loaded with pmovsx. all-ones sign-extends
    DB  0,  0,  0,  0,  0,  0,  0,  0
masktable_intro:                      ; index with 0..-7
    DB -1, -1, -1, -1, -1, -1, -1, -1
masktable_outro:                      ; index with -8(aligned), or -1..-7
    DB  0,  0,  0,  0,  0,  0,  0,  0

; the very first and last 0 bytes are not needed, since we avoid an all-zero mask.


section .text
global floatmul   ; (float *rdi)
floatmul:
    mov    eax, edi
    and    eax, 0x1c            ; 0x1c = 7 << 2 = 0b11100

    lea    rdx, [rdi + 4096 - 32]  ; one full vector less than the end address (calculated *before* masking for alignment).
                ;;  replace 4096 with rsi*4 if rsi has the count (in floats, not bytes)

    and    rdi, ~0x1c           ; Leave the low 2 bits alone, so this still works on misaligned floats.

    shr    eax, 2               ; misalignment-count, in the range [0..7]

    neg        rax
    vpmovsxbd  ymm0, [masktable_intro + rax]  ; Won't link on OS X: Need a separate LEA for RIP-relative

    vmaskmovps ymm1, ymm0, [rdi]
    vaddps     ymm1, ymm1, ymm1   ; *= 2.0
    vmaskmovps [rdi], ymm0, ymm1

    ;;; also prepare the cleanup mask while the table is still hot in L1 cache

    ; if the loop count known to be a multiple of the vector width,
    ; the alignment of the end will be the same as the alignment of the start
    ; so we could just invert the mask
    ; vpxor    xmm1, xmm1, xmm1     ; doesn't need an execution unit
    ; vpcmpeqd ymm0, ymm1, ymm0

    ; In the more general case: just re-generate the mask from the one-past-the-end addr
    mov    eax, edx
    xor    ecx, ecx      ; prep for setcc
    and    eax, 0x1c     ; sets ZF when aligned
    setz   cl            ; rcx=1 in the aligned special-case, else 0
    shr    eax, 2
    lea    eax, [rax + rcx*8]   ; 1..7, or 8 in the aligned case
    neg    rax
    vpmovsxbd  ymm0, [masktable_outro + rax]


.loop:
    add      rdi, 32
    vmovups  ymm1, [rdi]    ; Or vmovaps if you want to fault if the address isn't 4B-aligned
    vaddps   ymm1, ymm1, ymm1   ; *= 2.0
    vmovups  [rdi], ymm1
    cmp      rdi, rdx           ; while( (p+=8) < (start+1024-8) )
    jb    .loop        ; 5 fused-domain uops, yuck.

    ; use the outro mask that we generated before the loop for insn scheduling / cache locality reasons.

    vmaskmov ymm1, ymm0, [rdi]
    vaddps     ymm1, ymm1, ymm1   ; *= 2.0
    vmaskmovps [rdi], ymm0, ymm1
    ret


    ; vpcmpeqd ymm1, ymm1, ymm1   ; worse way to invert the mask: dep-chain breaker but still needs an execution unit to make all-ones instead of all-zeros.
    ; vpxor    ymm0, ymm0, ymm1

Это требует загрузки из таблицы, которая может пропустить в кеше L1 и 15B данных таблицы. (Или 24B, если количество циклов также является переменной, и мы должны генерировать конечную маску отдельно).

В любом случае, после 4-х инструкций для создания счетчика несоосности и выровненного начального адреса, получение маски принимает только одну команду vpmosvsxbd. (Форма ymm, mem не может быть микро-предохранителем, так что это 2 раза). Для этого требуется AVX2.

Без AVX2:

• 2x vpmovsxbd в два 128b регистра ([masktable_intro + rax] и [masktable_intro + rax + 4])
• vinsertf128

Или: (больше insns и больше давления в поршне, но меньшее давление нагрузки)

• vpmovsxbw в регистр 128b
• vpunpcklwd/vpunpckhwd в две xmm regs (src1 = src2 для обоих)
• vinsertf128

Или:

• vmovdqu из таблицы 60B DWORDs (DD) вместо байтов (DB). Это фактически спасло бы insn относительно AVX2: address & 0x1c - это индекс, без необходимости сдвига вправо на два. Вся таблица все еще вписывается в строку кэша, но без места для других констант, которые может использовать алго.

Накладные:

• Целочисленные операционные системы: 5 удалений в начале, чтобы получить индекс и выровнять указатель начала. 7 uops, чтобы получить индекс для конечной маски. Всего 12 GP-регистров uops за пределами простого использования без выравнивания, если количество элементов цикла кратно ширине вектора.

• AVX2: Два векторных insns 2-fused-domain-uop, чтобы перейти от индекса [0..7] в GP reg к маске в регистре YMM. (Один для стартовой маски, один для маски конца). Использует таблицу 24B, доступную в окне 8B с гранулярностью байт.

• AVX: шесть векторных insns с 1-мя плавными доменами (три в начале, три в конце). С RIP-относительной адресацией для таблицы четыре из этих инструкций будут [base+index] и не будут микро-плавкой, поэтому могут быть лучше два дополнительных целочисленных insns.

Код внутри цикла реплицируется 3 раза.

TODO: напишите еще один ответ, создающий маску "на лету", возможно, как байты в 64b reg, а затем распакуйте ее на 256b. Может быть, с бит-сдвигом, или BMI2 BZHI (-1, count)?