2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




Начать новую тему Ответить на тему На страницу Пред.  1, 2
 
 Re: Приемы программирования SSE/AVX [Обмен опытом]
Сообщение11.10.2017, 02:27 
Заслуженный участник


20/08/14
8871
Россия, Москва

(ARM+NEON)

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

 Профиль  
                  
 
 Re: Приемы программирования SSE/AVX [Обмен опытом]
Сообщение11.10.2017, 02:45 
Аватара пользователя


07/02/12
1399
Питер

(ARM+NEON)

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

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

 Профиль  
                  
 
 Re: Приемы программирования SSE/AVX [Обмен опытом]
Сообщение12.08.2018, 00:55 
Заслуженный участник


20/08/14
8871
Россия, Москва
В одной из тем основным тормозом перебора была проверка чисел на простоту, тогда ещё посокрушались что переписывать на 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 тормозом не является.

 Профиль  
                  
 
 Re: Приемы программирования SSE/AVX [Обмен опытом]
Сообщение18.03.2021, 11:06 
Заслуженный участник


20/08/14
8871
Россия, Москва

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

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, такта на итерацию?

 Профиль  
                  
 
 Re: Приемы программирования SSE/AVX [Обмен опытом]
Сообщение19.06.2021, 23:43 


23/08/17
12
Dmitriy40 в сообщении #1331857 писал(а):
И вот наконец дошли руки до этого предложения и таки написал и умножение 64х64 на AVX2, и его использование для определения делимости 64 бит числа на 4 других 64 бит нечётных числа.

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

 Профиль  
                  
 
 Re: Приемы программирования SSE/AVX [Обмен опытом]
Сообщение20.06.2021, 00:19 
Заслуженный участник


20/08/14
8871
Россия, Москва
case в сообщении #1523497 писал(а):
не выгоднее ли в данном случае вместо команды vpshufb использовать специализированную vpsllq для сдвига 64-битных целых?
Хороший вопрос. Обе команды занимают по одному такту, в данном случае выполняют одно и то же и вполне функционально заменимы, к тому же сдвиг не требует регистра-маски. А разница между ними в используемом порту, перестановка выполняется в пятом порту, который как видно больше никем не занят, а сдвиг выполняется в нулевом порту, который занят пятью другими командами. Заменив перестановку на сдвиг увеличим время цикла на 1 такт, с 5 до 6, по нулевому порту, перестановка же может выполниться параллельно в эти же 5 тактов (разумеется речь лишь про выполнение этого куска в длинном цикле). Вот поэтому нет, не выгодно.
Для более новых микроархитектур раскладку по портам нужно уточнять, могло и поменяться.

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

 Профиль  
                  
 
 Re: Приемы программирования SSE/AVX [Обмен опытом]
Сообщение20.06.2021, 10:40 


23/08/17
12

(Оффтоп)

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

 Профиль  
                  
 
 Re: Приемы программирования SSE/AVX [Обмен опытом]
Сообщение20.06.2021, 16:32 
Заслуженный участник


20/08/14
8871
Россия, Москва

(Оффтоп)

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

 Профиль  
                  
 
 Re: Приемы программирования SSE/AVX [Обмен опытом]
Сообщение20.06.2021, 20:56 


23/08/17
12

(Оффтоп)

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

 Профиль  
                  
 
 Re: Приемы программирования SSE/AVX [Обмен опытом]
Сообщение21.06.2021, 03:11 
Заслуженный участник


20/08/14
8871
Россия, Москва

(Оффтоп)

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

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

 Профиль  
                  
 
 Re: Приемы программирования SSE/AVX [Обмен опытом]
Сообщение15.07.2021, 11:56 


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

 Профиль  
                  
 
 Re: Приемы программирования SSE/AVX [Обмен опытом]
Сообщение05.10.2021, 10:47 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 27 ]  На страницу Пред.  1, 2

Модераторы: maxal, Toucan, PAV, Karan, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group