Векторизация с невыровненными буферами: использование VMASKMOVPS: создание маски из числа смещений? Или вообще не использовать этот insn
gcc 5.3 с -O3 -mavx -mtune=haswell для x86-64 делает удивительно громоздкий код для обработки потенциально смещенных входных данных для кода, такого как:
// convenient simple example of compiler input
// I'm not actually interested in this for any real program
void floatmul(float *a) {
for (int i=0; i<1024 ; i++)
a[i] *= 2;
}
clang использует невыровненные инструкции загрузки / сохранения, но gcc выполняет скалярное введение / вывод и выровненный векторный цикл: он снимает первые до 7 невыровненных итераций, полностью разворачивая их в последовательность
vmovss xmm0, DWORD PTR [rdi]
vaddss xmm0, xmm0, xmm0 ; multiply by two
vmovss DWORD PTR [rdi], xmm0
cmp eax, 1
je .L13
vmovss xmm0, DWORD PTR [rdi+4]
vaddss xmm0, xmm0, xmm0
vmovss DWORD PTR [rdi+4], xmm0
cmp eax, 2
je .L14
...
Это кажется довольно ужасным, особенно для процессоров с кэшем UOP. Я сообщил об ошибке gcc по этому поводу с предложением меньшего / лучшего кода, который gcc мог бы использовать при очистке невыровненных итераций. Это, вероятно, все еще не оптимально, хотя.
Этот вопрос о том, что на самом деле будет оптимальным с AVX. Я спрашиваю об общих решениях, которые gcc и другие компиляторы могли бы / должны использовать. (Я не нашел ни одного попадания в список рассылки gcc с обсуждением этого, но не стал долго искать.)
Вероятно, будет несколько ответов, так как то, что оптимально для -mtune=haswell вероятно будет отличаться от того, что оптимально для -mtune=bdver3 (Каток). И затем возникает вопрос о том, что оптимально при разрешении расширений набора команд (например, AVX2 для 256-битных целочисленных данных, BMI1 для преобразования счетчика в битовую маску с меньшим количеством инструкций).
Мне известно руководство по оптимизации сборки Agner Fog, раздел 13.5 Доступ к невыровненным данным и частичным векторам. Он предлагает либо использовать невыровненный доступ, либо выполнить перезаписывающую запись в начале и / или конце, либо перетасовывать данные из выровненных обращений (но PALIGNR принимает только счет imm8, поэтому 2x pshufb / por). Он скидки VMASKMOVPS как бесполезный, вероятно, из-за того, как плохо он работает на AMD. Подозреваю, что если настраивать на Intel, стоит задуматься. Не очевидно, как создать правильную маску, отсюда и название вопроса.
Может оказаться, что лучше просто использовать невыровненный доступ, как это делает clang. Для коротких буферов накладные расходы на выравнивание могут убить любую выгоду от избежания расщепления строки кэша для основного цикла. Для больших буферов основная память или L3 в качестве узкого места могут скрывать штраф за расщепление кеш-линии. Если у кого-то есть экспериментальные данные, подтверждающие это для любого реального кода, который они настроили, это тоже полезная информация.
VMASKMOVPS выглядит полезным для целей Intel. (Версия SSE ужасна, с неявной не временной подсказкой, но в версии AVX этого нет. Есть даже новая функция, гарантирующая, что вы не получите версию SSE для операндов 128b: _mm128_maskstore_ps) AVX-версия на Haswell работает немного медленнее:
- 3 мопа / задержка 4c / пропускная способность 1 на 2c в качестве нагрузки.
- Пропускная способность 4 мегапикселей / задержка 14 с / пропускная способность 1 на 2 с в виде хранилища 256 бит.
- Пропускная способность 4 моп / 13 с / пропускная способность 1 на 1 с в виде хранилища 128 байт.
Форма хранения все еще необычайно медленная на процессорах AMD, как Jaguar (1 на 22c tput), так и на семейство Bulldozer: 1 на 16c на Steamroller (аналогично Bulldozer) или 1 на ~180c на Piledriver.
Но если мы хотим использовать VMASKMOVPSнам нужен вектор с старшим битом, установленным в каждом элементе, который на самом деле должен быть загружен / сохранен. PALIGNR и PSRLDQ (для использования с вектором из всех единиц) принимают только значения постоянной времени компиляции.
Обратите внимание, что другие биты не имеют значения: они не обязательно должны быть единичными, поэтому возможно рассредоточение некоторых установленных битов до старших битов элементов.
2 ответа
Только для AVX: не выровненный доступ в начале / конце, конвейерная загрузка, чтобы избежать проблем при перезаписи на месте.
Спасибо @StephenCanon за указание, что это лучше, чем VMASKMOVPS за все, что VMASKMOVPS мог бы помочь с зацикливанием невыровненных буферов.
Это может быть немного много, чтобы ожидать, что компилятор сделает преобразование цикла, esp. поскольку очевидный путь может сделать Вальгринда несчастным (см. ниже).
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 дополнительные копии тела цикла (загрузка / вычисление / сохранение). (Первая и последняя итерация очищены).
Компиляторы, вероятно, не будут рады создавать подобный код при автоматической векторизации. Valgrind будет сообщать о доступах за пределами границ массива, и делает это с помощью пошаговых инструкций и инструкций по декодированию, чтобы увидеть, к чему они обращаются. Так что простого нахождения на той же странице (и в строке кэша), что и последний элемент в массиве, недостаточно. Также обратите внимание, что если входной указатель не выровнен по 4B, мы можем потенциально прочитать на другую страницу и выполнить segfault.
Чтобы Valgrind был доволен, мы могли бы остановить цикл на две ширины вектора раньше, чтобы выполнить загрузку специального случая для невыровненной последней ширины вектора массива. Это потребовало бы дублирования тела цикла в дополнительное время (незначительно в этом примере, но это тривиально нарочно.) Или, возможно, избегайте конвейерной обработки, заставляя код вступления переходить в середину цикла. (Это может быть неоптимальным для uop-кэша, хотя: (части) тела цикла могут оказаться в кэше uop дважды.)
TODO: напишите версию, которая переходит в цикл в середине пути.
Загрузите маску для VMOVMASKPS из окна в таблицу. AVX2 или AVX1 с несколькими дополнительными инструкциями или таблицей большего размера.
Маска также может быть использована для ANDPS в регистрах в сокращении, которое необходимо считать каждый элемент ровно один раз. Как отмечает Стивен Канон в комментариях к OP, конвейерная загрузка может позволить перекрывающимся невыровненным хранилищам работать даже для функции перезаписи на месте, как в примере, который я выбрал, поэтому VMASKMOVPS НЕ лучший выбор здесь.
Это должно быть хорошо на процессорах Intel, особенно. Haswell и позже для AVX2.
Метод Агнера Фога для получения маски pshufb на самом деле дал очень эффективную идею: выполнить не выровненную загрузку, извлекая окно данных из таблицы. Вместо гигантской таблицы масок используйте индекс как способ сдвига байтов данных в памяти.
Маски в порядке байтов LSB-first (так как они хранятся в памяти), а не обычные обозначения для {X3,X2,X1,X0} элементы в векторе. Как написано, они выровнены с выровненным окном, включая начало / конец входного массива в памяти.
- отсчет начального смещения = 0: маска = все единицы (выровненный регистр)
- отсчет начала смещения = 1: маска =
{0,-1,-1,-1,-1,-1,-1,-1}(пропустить один в первом 32B) - ...
отсчет начала смещения = 7: маска =
{0, 0, 0, 0, 0, 0, 0,-1}(пропустить все, кроме одного в первом 32B)end misalign count = 0: нет конечных элементов. маска = все единицы (выровненный регистр).
это странный случай, не похожий на count = 1. Пара дополнительных инструкций для этого особого случая стоит избегать дополнительной итерации цикла и очистки с помощью маски из всех нулей.- end misalign count = 1: один конечный элемент. маска =
{-1, 0, 0, 0, 0, 0, 0, 0} - ...
- число смещений конца = 7: семь конечных элементов. маска =
{-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 (src1=src2 для обоих)
- vinsertf128
Или же:
- vmovdqu из таблицы DWORD 60B (
DD) вместо байтов (DB). Это на самом деле сохранит insn относительно AVX2:address & 0x1cэто индекс, без необходимости сдвига вправо на два. Вся таблица по-прежнему помещается в строку кэша, но без места для других констант, которые может использовать алгоритм.
Накладные расходы:
Целочисленные операции: 5 моп в начале, чтобы получить индекс и выровнять стартовый указатель. 7 моп, чтобы получить индекс для конечной маски. Всего 12 мопов в регистре GP, кроме простого использования unaligned, если число элементов цикла кратно векторной ширине.
AVX2: Два векторных insn с 2-fused-domain-uop для перехода от индекса [0..7] в регистре GP к маске в рег. YMM. (Один для начальной маски, один для конечной маски). Использует таблицу 24B, доступ к которой осуществляется в окне 8B с гранулярностью байтов.
AVX: шесть векторных insns 1-fused-domain-uop (три в начале, три в конце). С RIP-относительной адресацией для таблицы четыре из этих инструкций будут
[base+index]и не будет микроплавкого предохранителя, так что дополнительные два целочисленных insns могут быть лучше.
Код внутри цикла дублируется 3 раза.
TODO: написать другой ответ, генерирующий маску на лету, возможно, в виде байтов в регистре 64b, затем распаковать его в 256b. Может быть, с бит-сдвигом или BZHI BMI2 (-1, количество)?