Упаковка BCD в DPD: как улучшить эту процедуру сборки amd64?

Ответ 1

(я разделил версию BMI2 на отдельный ответ, так как он может оказаться совершенно другим)

Увидев, что вы делаете с этим imul/shr, чтобы получить индекс таблицы, я могу увидеть, где вы можете использовать BMI2 pextr для замены and/imul/shr или BMI1 bextr, чтобы заменить только shr (позволяя использовать imul32 вместо imul16, так как вы просто извлекаете нужные вам биты, вместо необходимости сдвигать нули с верхнего уровня16). Есть процессоры AMD с BMI1, но даже у катка нет BMI2. Intel представила BMI1 и BMI2 одновременно с Haswell.

Вы могли бы обработать два или четыре 16-битных слова одновременно, с 64-битным pextr. Но не для всего алгоритма: вы не можете выполнять 4 параллельных поиска таблиц. (AVX2 VPGATHERDD не стоит использовать здесь.) На самом деле вы можете использовать pshufb для реализации LUT с индексами до 4 бит, см. Ниже.

Малая версия улучшения:

.section .rodata
  # This won't won't assemble, written this way for humans to line up with comments.

extmask_lobits:     .long           0b0000 0111 0111 0111
extmask_hibits:     .long           0b0000 1000 1000 1000

# pext doesn't have an immediate-operand form, but it can take the mask from a memory operand.
# Load these into regs if running in a tight loop.

#### TOTALLY UNTESTED #####
.text
.p2align 4,,10
bcd2dpd_bmi2:
#       mov   %edi,%eax           #   = 0000 abcd efgh iklm
#       shl   %al                 #   = 0000 abcd fghi klm0
#       shr   %eax                #   = 0000 0abc dfgh iklm

        pext  extmask_lobits, %edi, %eax
                                #   = 0000 0abc dfgh iklm
        mov   %eax, %esi        # insn scheduling for 4-issue front-end: Fast-path is 4 fused-domain uops
          # And doesn't waste issue capacity when we're taking the slow path.  CPUs with mov-elimination won't waste execution units from issuing an extra mov
        test  $0x880, %edi        # fast path for a = e = 0
        jnz .Lslow_path
        ret

.p2align 4
.Lslow_path:
        # 8 uops, including the `ret`: can issue in 2 clocks.

        # replaces and/imul/shr
        pext  extmask_hibits, %edi, %edi #u= 0000 0000 0000 0aei
        and   $0x66, %esi                # q = 0000 0000 0fg0 0kl0
        imul  tab-8(,%rdi,4), %esi       # v = q * tab[u-2][0]
        and   $0x397, %eax               # r = 0000 00bc d00h 0klm
        xor   %esi, %eax                 # w = r ^ v
        or    tab-6(,%rdi,4), %eax       # x = w | tab[u-2][1]
        and   $0x3ff, %eax               #   = 0000 00xx xxxx xxxx
        ret

Конечно, если вы сделаете это inline-asm, а не автономной функцией, вы вернетесь к ветки быстрого пути до конца, а медленный путь провалится. И вы не потеряете пространство с помощью средней функции выравнивания.

Может быть больше возможностей для использования pextr и/или pdep для большей части остальной функции.

Я думал о том, как сделать лучше с BMI2. Я думаю, мы могли бы получить несколько селекторов aei из четырех шорт, упакованных в 64b, а затем использовать pdep для их размещения в младших битах разных байтов. Тогда movq, что для векторного регистра, где вы используете его в качестве маски управления тасованием для pshufb для выполнения нескольких 4-битных поисковых запросов.

Таким образом, мы могли бы перейти от 60 бит BCD до 50 бит DPD за раз. (Используйте shrd для смещения бит между регистрами для обработки нагрузок/хранилищ в памяти с байтовым адресом.)

На самом деле 48 бит BCD (4 группы по 12 бит каждый) → 40 бит DPD, вероятно, намного проще, потому что вы можете распаковать это до 4 групп из 16 бит в 64-битном целочисленном регистре, используя pdep. Работа с селекторами для 5 групп в порядке, вы можете распаковать с помощью pmovzx, но для работы с остальными данными потребуется перетасовка символов в векторных регистрах. Даже медленные переменные с переменным сдвигом AVX2 сделали бы это легко сделать. (Хотя может быть интересно рассмотреть, как реализовать это с BMI2 вообще, для больших ускорений на процессорах с только SSSE3 (т.е. Каждый соответствующий процессор) или, возможно, SSE4.1.)

Это также означает, что мы можем поместить два кластера из 4 групп в нижнюю и верхнюю половинки регистра 128b, чтобы получить еще больше parallelism.

В качестве бонуса, 48 бит - это целое число байтов, поэтому чтение из буфера цифр BCD не потребует каких-либо shrd insns, чтобы получить оставшиеся 4 бита из последних 64b в нижний 4 для следующего. Или две смещенные маски pextr для работы, когда 4 игнорируемых бита были низкими или высокими 4 из 64b.... В любом случае, я думаю, что сразу 5 групп просто не стоит рассматривать.

Полная версия BMI2/AVX pshufb LUT (с возможностью векторизации)

Движение данных может быть:

ignored | group 3        | group 2        | group 1        |  group 0
16bits  | abcd efgh iklm | abcd efgh iklm | abcd efgh iklm | abcd efgh iklm

         3   2   1 | 0
pext -> aei|aei|aei|aei  # packed together in the low bits

          2  |      1            |        0
pdep ->  ... |0000 0000 0000 0aei|0000 0000 0000 0aei  # each in a separate 16b word

movq -> xmm vector register.
 (Then pinsrq another group of 4 selectors into the upper 64b of the vector reg).  So the vector part can handle 2 (or AVX2: 4) of this at once

vpshufb xmm2 -> map each byte to another byte (IMUL table)
vpshufb xmm3 -> map each byte to another byte (OR table)


Get the bits other than `aei` from each group of 3 BCD digits unpacked from 48b to 64b, into separate 16b words:

                  group 3       | group 2             | group 1             |  group 0
pdep(src)-> 0000 abcd efgh iklm | 0000 abcd efgh iklm | 0000 abcd efgh iklm | 0000 abcd efgh iklm

 movq this into a vector reg (xmm1).  (And repeat for the next 48b and pinsrq that to the upper64)

VPAND  xmm1, mask  (to zero aei in each group)

 Then use the vector-LUT results:
VPMULLW xmm1, xmm2 -> packed 16b multiply, keeping only the low16 of the result

VPAND   xmm1,  mask
VPXOR   xmm1, something
VPOR    xmm1, xmm3

movq / pextrq back to integer regs

pext to pack the bits back together
  You don't need the AND 0x3ff or equivalent:
  Those bits go away when you pext to pack each 16b down to 10b

shrd or something to pack the 40b results of this into 64b chunks for store to memory.
  Or: 32b store, then shift and store the last 8b, but that seems lame
  Or: just do 64b stores, overlapping with the previous.  So you write 24b of garbage every time.  Take care at the very end of the buffer.

Используйте AVX 3-операндовые версии инструкций SSE 128b, чтобы избежать необходимости movdqa не перезаписывать таблицу для pshufb. Пока вы не запускаете 256-битную инструкцию AVX, вам не нужно возиться с vzeroupper. Вы также можете использовать версии v (VEX) всех векторных инструкций, хотя, если вы используете их. Внутри виртуальной машины вы можете работать на виртуальном процессоре с BMI2, но не с поддержкой AVX, поэтому это проблема. по-прежнему неплохо проверить флаги функций процессора, а не предполагать AVX, если вы видите BMI2 (хотя это и безопасно для всего физического оборудования, которое в настоящее время существует).

Это начинает выглядеть действительно эффективно. Возможно, стоит сделать mul/xor/и материал в векторных regs, даже если у вас нет BMI2 pext/pdep, чтобы выполнить упаковку/распаковку бит. Я предполагаю, что вы могли бы использовать код, например, существующую сканирующую маршрутизацию без BMI, чтобы получить селектор, а также маску/сдвиг/или могли бы генерировать данные без селектора в 16b кусках. Или, может быть, shrd для переноса данных из одного рег в другой?

Ответ 2

TYVM для комментирования кода четко и хорошо, BTW. Это очень легко понять, что происходит, и где биты идут. Я никогда не слышал о DPD раньше, так что это озадачило его из раскованного кода, и статья wikipedia была бы сосать.

Соответствующие getchas:

• Избегайте 16-разрядного размера операнда для инструкций с непосредственными константами на процессорах Intel. (Стойки LCP)
• избегайте чтения полного 32-битного или 64-битного регистра после записи только низких 8 или 16 на Intel pre-IvyBridge. (неполный регистр). (IvB все еще имеет такое замедление, если вы изменяете верхнюю регистрацию типа AH, но Haswell тоже ее удаляет). Это не просто дополнительный uop: штраф на Core2 составляет от 2 до 3 циклов, сообщает Agner Fog. Возможно, я ошибаюсь, но на SnB это кажется намного хуже.

Подробнее см. http://agner.org/optimize/.

Кроме этого, нет общей проблемы со смешением в некоторых инструкциях с использованием префикса размера операнда, чтобы сделать их 16-разрядными.

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

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

Возможные предложения кода: Переключите ветвление, чтобы на быстром пути была не принятая ветвь. На самом деле, в этом случае он не может иметь никакого различия, или может улучшить выравнивание кода медленного пути.

.p2align 4,,10   # align to 16, unless we're already in the first 6 bytes of a block of 16
bcd2dpd_mul:
        mov %edi,%eax           #   = 0000 abcd efgh iklm
        shl %al                 #   = 0000 abcd fghi klm0
        shr %eax                #   = 0000 0abc dfgh iklm
        test $0x880,%edi        # fast path for a = e = 0
        jnz .Lslow_path
        ret

.p2align 4    # Maybe fine-tune this alignment based on how the rest of the code assembles.    
.Lslow_path:

        ...
        ret

Иногда лучше дублировать инструкции возврата, чем полностью сводить к минимуму размер кода. Сравнительная и ветвь в этом случае - это 4-й уровень функции, однако, поэтому принятая ветвь не предотвратила бы выпуск 4-х тактов в первом такте, а правильно спрогнозированная ветвь все равно выдаст 2-й такт.

Вы должны использовать 32-битный imul для одного с источником таблицы. (см. следующий раздел о выравнивании table, поэтому чтение дополнительного 2B в порядке). 32bit imul - это один uop вместо двух на микрочипах семейства Intel SnB. Результат в low16 должен быть таким же, поскольку знаковый бит не может быть установлен. Верхний 16 обнуляется окончательным and до ret и не используется каким-либо образом, когда в нем находится мусор в верхнем 16.

Однако ваш imul с немедленным операндом проблематичен.

При декодировании на Intel это приводит к остановке LCP, и он записывает значение low16 регистра, которое позже считывается с полной шириной. Его upper16 будет проблемой, если не замаскирован (поскольку он используется как индекс таблицы). Его операнды достаточно велики, чтобы они помещали мусор в верхний 16, поэтому его нужно отбросить.

Я думал, что ваш способ сделать это будет оптимальным для некоторых архитектур, но оказывается, что imul r16,r16,imm16 сам медленнее, чем imul r32,r32,imm32 для каждой архитектуры, кроме VIA Nano, AMD K7 (где он быстрее imul32) и Intel P6 (где использование его из 32-битного/64-битного режима будет LCP-stall, и где замедление частичного регрессинга является проблемой).

В процессорах Intel SnB-семейства, где imul r16,r16,imm16 - два uops, imul32/movzx будет строго лучше, без недостатка, кроме размера кода. На процессорах P6-семейства (например, PPro-Nehalem) imul r16,r16,imm16 - это один uop, но эти CPU не имеют кэш-памяти uop, поэтому стойка LCP, вероятно, имеет решающее значение (за исключением, может быть, Nehalem, вызывающего это в узком цикле, буфер 28 мкп-цикла). И для этих процессоров явный movzx, вероятно, лучше с точки зрения частичной регистрации. Agner Fog говорит что-то о том, что есть дополнительный цикл, в то время как CPU вставляет слияние uop, что может означать цикл, когда этот дополнительный uop выдается отдельно.

В AMD K8-Steamroller imul imm16 составляет 2 м-op вместо 1 для imul imm32, поэтому imul32/movzx примерно равно imul16. Они не страдают от киосков LCP или от проблем с частичной регистрацией.

В Intel Silvermont imul imm16 - 2 устройства (с 1 пропускной способностью 4 такта), а imul imm32 - 1 мкп (с 1 на 1 такт). То же самое на Atom (предшественник in-order to Silvermont): imul16 является дополнительным uop и намного медленнее. На большинстве других микроархитектур пропускная способность не хуже, просто латентность.

Итак, если вы хотите увеличить размер кода в байтах, где он даст ускорение, , вы должны использовать 32-битные imul и movzwl %di, %edi, На некоторых архитектурах это будет примерно такой же скорости, что и imul imm16, а на других - намного быстрее. Это может быть немного хуже для семейства бульдозеров AMD, что не очень удобно использовать оба целочисленных исполнительных блока сразу, по-видимому, поэтому команда 2 м-op для EX1 может быть лучше двух команд 1 м-op, где одна из они все еще являются инструкцией только для EX1. Если это вам интересно, отметьте это.

Выровняйте tab по крайней мере до границы 32B, поэтому ваши 32-битные imul и or могут выполнять нагрузку 4B из любой выровненной по 2B записи в ней, не пересекая границу линии кэша. Неуправляемые обращения не накладывают никаких штрафных санкций на все последние процессоры (Nehalem и более поздние версии и недавние AMD), если они не охватывают две строки кэша.

Выполнение операций, которые считываются из таблицы 32bit, позволяет избежать штрафа частичного регистра, который имеет процессор Intel. AMD CPU и Silvermont не отслеживают частичные регистры отдельно, поэтому даже инструкции, которые только для записи на low16 должны ждать результата в остальной части reg. Это останавливает 16-битные insns от разрыва цепей зависимостей. Семейства микроархивов Intel P6 и SnB отслеживают частичные регистры. Хасуэлл делает полную двойную бухгалтерскую книгу или что-то в этом роде, потому что нет никакого штрафа при слиянии, например, после того, как вы переместили al, а затем смените eax. SnB добавит туда лишний юп, и может быть наказание за цикл или два, пока он это делает. Я не уверен и не проверял. Тем не менее, я не вижу приятного способа избежать этого.

shl %al можно заменить на add %al, %al. Это может работать на большем количестве портов. Наверное, никакой разницы, поскольку port0/5 (или port0/6 на Haswell и позже), вероятно, не насыщены. Они оказывают одинаковое влияние на биты, но устанавливают флаги по-разному. В противном случае их можно было бы декодировать до того же самого uop.

: разделить версию pext/pdep/vectorize на отдельный ответ, отчасти потому, что он может иметь свой собственный поток комментариев.