Приемы программирования SSE/AVX [Обмен опытом]

[Dmitriy40]

(ARM+NEON)

bondkim137 в сообщении #1254646 писал(а):

А на ARM с последними NEON-командами можно то же самое эффективно сделать?

Вот не знаю, я последней архитектурой интересовался лишь ARMv4T (ARM7TDMI), в ней NEON ещё нету. Условные операции очень впечатлили, как и возможность сдвига операнда, иногда (но очень иногда) это существенно ускоряет вычисления. По грубой прикидке, если NEON оперирует 128 битами, да ещё и обычно на частотах порядка 1ГГц, это минимум в 7 раз медленнее (на ядро), интереса не представляет. Это при условии наличия не менее удобных команд.
Но в общем да, в NEON должны быть похожие команды и методы ускорения.

[bondkim137]

(ARM+NEON)

Dmitriy40 в сообщении #1254678 писал(а):

если NEON оперирует 128 битами, да ещё и обычно на частотах порядка 1ГГц, это минимум в 7 раз медленнее (на ядро)

До ~2-2.5ГГц, ~4 ядра, ну и речь не в том, что на мобильных процессорах быстрее считать - речь о том, что бы впринципе считать на мобильниках достаточно быстро. Ибо это сильно кореллирует с монетизацией (и не только) при решении некоторых прикладных задач :)

[Dmitriy40]

В одной из тем основным тормозом перебора была проверка чисел на простоту, тогда ещё посокрушались что переписывать на AVX нет смысла из-за отсутствия как команд целочисленного деления, так и даже умножения 64-битных целых чисел. Тогда же было высказано предложение использовать модулярную арифметику в умножении вместо деления. И вот наконец дошли руки до этого предложения и таки написал и умножение 64х64 на AVX2, и его использование для определения делимости 64 бит числа на 4 других 64 бит нечётных числа. Может кому пригодится. Архитектура Haswell.

Используется синтаксис ASM

;Инициализация
                vmovq           xmm0,RCX        ;Проверяемое число, единственное место где влияет разрядность x32/x64
                vpbroadcastq    ymm0,xmm0
                vpsrlq          ymm1,ymm0,32    ;Выдедение старших 32 бит отдельно, младщие выделять не нужно, vpmuludq игнорирует биты 63..32
                vmovdqu         ymm2,[mem]      ;Чтение констант делителей обратных по модулю
                vpsrlq          ymm3,ymm2,32    ;Выдедение старших 32 бит отдельно, младщие выделять не нужно, vpmuludq игнорирует биты 63..32
                vpmovdqu        ymm4,[mem]      ;Загрузка констант частных (2^64-1)/делитель с инвертированным битом знака
                vpmovdqu        ymm5,[mem]      ;Загрузка 4-х констант 0x8000000000000000
                vpmovdqu        ymm6,[mem]      ;Загрузка 2-х констант 0x0B0A0908808080800302010080808080
;Регистры y6..y2 в коде ниже могут быть без уменьшения скорости заменены на чтение из памяти
;Сама проверка делимости                   ;Порт       Латентность/В_потоке
                vpmuludq        ymm3,ymm0,ymm3  ;0      5/1
                vpmuludq        ymm7,ymm1,ymm2  ;0      5/1
                vpmuludq        ymm2,ymm0,ymm2  ;0      5/1
                vpaddq          ymm3,ymm3,ymm7  ;15     1/0.5
                vpshufb         ymm3,ymm3,ymm6  ;5      1/1     сдвиг младшего 32 бит слова в старшее с обнулением младшего
                vpaddq          ymm2,ymm2,ymm3  ;15     1/0.5   y2 - младшие 64 бита произведения
                vpxor           ymm2,ymm2,ymm5  ;015    1/0.33  инверсия знакового бита
                vpcmpgtq        ymm2,ymm2,ymm4  ;0      5/1     сравнение с частным (2^64-1)/делитель
                vpmovmskb       EAX,ymm2        ;0      3/1     нулевые биты означают что что-то разделилось
                cmp             EAX,-1          ;0156   1/0.25
;ZF=0 если разделилось на любое из 4-х чисел

Итого: в потоке скорость 5 тактов на 4 делителя или 1.25 тактов на делитель (что подтверждает Intel® Architecture Code Analyzer), реальное измерение даёт 1.33 такта.
Один такт на число получить не удалось, но развернув цикл можно приблизиться к этому, например 4-х кратный разворот уменьшает до 1.12 такта (теоретически 1.06). При этом весь внутренний цикл обработки 16 делителей занимает всего 58 микроопераций и укладывается даже в очередь декодированых, т.е. Front-end тормозом не является.

[Dmitriy40]

(Странное расхождение теории от практики)

Dmitriy40 в сообщении #1253977 писал(а):

В итоге время обработки 32-х чисел сократилось до примерно 8 тактов, т.е. 4 числа на такт.

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

Используется синтаксис ASM

                                                        ;Порты     Такты
.loop13:        vmovdqu         ymm0,[ESI+EDX]          ;23     3/0.5
                vpaddb          ymm0,ymm0,[EDX+const]   ;15     1/0.5
                vpsubb          ymm1,ymm0,[EDX+const]   ;15     1/0.5
                vpminub         ymm0,ymm1,ymm0          ;15     1/0.5
                vmovdqu         ymm2,[EDX+const]        ;23     3/0.5
                vpand           ymm1,ymm0,ymm6          ;015    1/0.33  маска 0x78
                vpand           ymm0,ymm0,ymm5          ;015    1/0.33  маска 0x07
                vpsrlw          ymm1,ymm1,3             ;0      1/1
                vpshufb         ymm0,ymm7,ymm0          ;5      1/1
                vpshufb         ymm1,ymm2,ymm1          ;5      1/1
                vpand           ymm0,ymm0,ymm1          ;015    1/0.33
                vpcmpeqb        ymm0,ymm0,ymm4          ;15     1/0.5   маска 0x00
                vpmovmskb       EAX,ymm0                ;0      3/1
                not             EAX                     ;0156   1/0.25
                and             EBX,EAX                 ;0156   1/0.25
                jz              .exit                   ;06     1/0.5
                add             EDX,32                  ;0156   1/0.25
                cmp             EDX,32*const            ;0156   1/0.25
                jc              .loop13                 ;06     1/0.5

Ручная раскладка команд по портам запуска для Haswell даёт абсолютный минимум в 3.5 такта на итерацию в каждом из 0,1,5,6 портах (при условии предсказанных переходов). Данные разумеется взяты у Фога и в других случаях они более-менее подтверждались, да и команды все в общем-то простые. Анализ в Intel® Architecture Code Analyzer даёт цифру 5.3 такта, что неприятно, но как-то поверить ещё можно. Причём ругается на затык в FrontEnd, там то чего за пробка ...
Но проблема что реальные измерения дают совершенно непонятную цифру в более 9 тактов на итерацию! Это уже ни в какие ворота ...
Замена обращений в память на регистровые операции ускоряет на 10%, т.е. дело не в кэшах.
Разворот цикла ускоряет меньше погрешности измерений.
Увеличение количества итераций цикла в 10 раз ускоряет в полтора раза, хотя весь остальной код теста занимает менее 0.5 такта на итерацию. Это ещё одна странность, что же мешает процессору прогнозировать выполнение полтора десятка итераций из 22 микроопераций. В принципе этим могут объясняться намерянные 9 тактов, но причина всё равно непонятна.

Может у кого будут мысли где мои 3.5, ну пусть даже 4, такта на итерацию?

[case]

Dmitriy40 в сообщении #1331857 писал(а):

И вот наконец дошли руки до этого предложения и таки написал и умножение 64х64 на AVX2, и его использование для определения делимости 64 бит числа на 4 других 64 бит нечётных числа.

Не замечание, скорее вопрос - не выгоднее ли в данном случае вместо команды vpshufb использовать специализированную vpsllq для сдвига 64-битных целых?

[Dmitriy40]

case в сообщении #1523497 писал(а):

не выгоднее ли в данном случае вместо команды vpshufb использовать специализированную vpsllq для сдвига 64-битных целых?

Хороший вопрос. Обе команды занимают по одному такту, в данном случае выполняют одно и то же и вполне функционально заменимы, к тому же сдвиг не требует регистра-маски. А разница между ними в используемом порту, перестановка выполняется в пятом порту, который как видно больше никем не занят, а сдвиг выполняется в нулевом порту, который занят пятью другими командами. Заменив перестановку на сдвиг увеличим время цикла на 1 такт, с 5 до 6, по нулевому порту, перестановка же может выполниться параллельно в эти же 5 тактов (разумеется речь лишь про выполнение этого куска в длинном цикле). Вот поэтому нет, не выгодно.
Для более новых микроархитектур раскладку по портам нужно уточнять, могло и поменяться.

PS. Я специально искал функционально эквивалентные команды, но выполняющиеся в разных портах, чтобы можно было выбирать менее загруженный порт. Например иногда vpmovmskb заменима на vptest даже с дополнительной логической операцией. А иногда наоборот, некоторые операции выгоднее вынести из AVX в обычные регистры, там они уходят в 4 порта вместо 2-3 для AVX и тем самым могут выполняться параллельно другим командам AVX.

[case]

(Оффтоп)

Понял, спасибо. А с расхождением теории и практики удалось разобраться?

[Dmitriy40]

(Оффтоп)

case
Нет, не удалось. Мы с GAA порассуждали тогда, я тестов понаделал, но ситуация лишь сильнее запуталась. Например в одном из 4-х вариантов удаление всех операций обращения к памяти сильно замедляет цикл. Возможно причина расхождений даже и не одна, а комбинация нескольких, тогда ещё можно придумать объяснение.

[case]

(Оффтоп)

На уровне предположения - а если сделать одну точку выхода из цикла? Хотя вроде Vtune должен вроде показывать ошибки предсказаний ветвлений

[Dmitriy40]

(Оффтоп)

case в сообщении #1523598 писал(а):

На уровне предположения - а если сделать одну точку выхода из цикла? Хотя вроде Vtune должен вроде показывать ошибки предсказаний ветвлений

Команда jz .exit никогда не срабатывает, это заглушка на всякий случай, если вдруг попадутся данные на которых цикл вычислений самоликвидируется до прохождения всех итераций. Так что точка выхода из цикла и так одна, в конце.
Кроме того, это переход "вперёд", а он статически предсказывается как не выполняющийся и соответственно конвейер не тормозит, ни в первый раз, ни в остальные. Ну и если бы он вдруг срабатывал, то время вычислений бы уменьшалось от расчётного, а не возрастало. Плюс контроль показывает что итерации выполнились все.

Пока я склоняюсь к мысли о недостаточном понимании работы sheduller-а в комбинации с алгоритмами виртуальных регистров и ROB. По отдельности они картину не объясняют, но вот вместе ...

[traffic_lights]

Переведена книга Daniel Kusswurm Modern X86 Assembly Language Programming Covers x86 64-bit, AVX, AVX2, and AVX-512
Second Edition (2019).

[traffic_lights]

Использование инструкций AVX-512 IFMA позволяет увеличить скорость умножения больших целых чисел в 3 раза по сравнению с GMP (Takuya Edamatsu, D. Takahashi Published in ICA3PP 2019: Accelerating Large Integer Multiplication Using Intel AVX-512IFMA).

[traffic_lights]

Появилась в свободном доступе
Daniel Kusswurm
Modern Parallel Programming with C++ and Assembly Language (X86 SIMD Development Using AVX, AVX2, and AVX-512) (2022)

[traffic_lights]

traffic_lights в сообщении #1552323 писал(а):

Появилась в свободном доступе
Daniel Kusswurm
Modern Parallel Programming with C++ and Assembly Language (X86 SIMD Development Using AVX, AVX2, and AVX-512) (2022)

Примеры исходного кода этой книги должны быть здесь: https://github.com/Apress/modern-parall ... p-assembly, но отсутствуют. В книге исходный код урезан: недостающий код можно взять из примеров исходного кода для книги "Профессиональное программирование на ассемблере x64 с расширениями AVX, AVX2 и AVX-512".

[Dmitriy40]

Глянул ради интереса книгу "Профессиональное программирование на ассемблере x64 с расширениями AVX, AVX2 и AVX-512", только главы 15 и 16, что хочу сказать, написано в общем всё верно, только треть советов по оптимизации уже не действенна, а ещё треть спорна — может как ускорять выполнение, так и замедлять, или применимость существенно зависит от прочего окружения. Например я где-то выше или в соседних темах приводил пример как логичная замена условного перехода на cmov существенно замедляла программу. Или совет всегда загружать всё в регистры, по идее верный, на практике часто выгодно ровно обратное, освободить максимум регистров под вычисления, а все константы читать из памяти (если их адрес известен на момент компиляции), потому что порты чтения памяти часто простаивают и такие чтения хорошо предсказываются, регистров же вечно не хватает. Пример недейственных советов: замена mov r,0 на xor/sub r,r, это очень существенно зависит от конкретной архитектуры и за последние лет 20 менялось несколько раз, становилось то выгоднее, то наоборот, сейчас же это обычно выполняется одинаково, как и многое другое, и на общую скорость практически всегда влияет ничтожно мало. Пример спорного совета: заменять cmp на test, он противоречит совету далее заменять inc/dec на add/sub, а спариваются (macrofusion) с условным переходом все эти команды одинаково. Ещё часть советов банальна до невозможности, типа "переходите на векторные команды", "заменяйте double на single", "уменьшайте длину команд за счёт ненужных префиксов", ... А некоторых полезных советов нету или хорошо замаскированы, например переупорядочивание кода чтобы более вероятным становился линейный путь выполнения даже ценой лишних переходов, или замена div r64 на пару div r32 (для делителей меньше $2^{32}$, которые в некоторых случаях могут выполниться быстрее!), или замена медленной vpblend на эквивалентную связку vpand+vpand+vpor, или замена векторной связки сравнений cmp с and и or на одну min/max, или методы размена памяти на скорость (и не только разворачиванием циклов, о котором сказано), да много чего ...
Пожалуй единственным бесспорным не банальным советом остаётся недостаточно прямо озвученный "относитесь с осторожностью к советам и всё проверяйте тестами/профилировщиком".

Так что книгу следует считать скорее введением в тему оптимизации на ассемблере, поверхностным обзором методов, она поможет повысить уровень со среднего немного выше, до начинающего профессионала (как бы глупо это не звучало), до реальных вершин скорости выполнения (достижения пиковой скорости работы) ещё пахать и пахать, уже по другим источникам.

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