Оптимизация вычислений на асме под AVX2

[venco]

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

Я повторю, не надо оптимизировать всю задачу, с этим я вроде справляюсь, непонятка только с переносами

Тогда почему у вас перенос только в 63-ем бите? Посмотрите на мой пример выше.

[Dmitriy40]

venco в сообщении #1030110 писал(а):

К примеру, что получится, если сложить следующуе числа?
0х05050505050505050505050505050505
0х04040404040404040404040404040405

Я же показал только кусочек распространения переносов через границы 64-х битных слов, с чём у меня непонятка. А для сложения этих вот чисел к сумме будет добавлена константа 0x76F6F6F6F6F6F6F6, которая за такт прогонит переносы внутри всех 8-ми цифр (точнее даже за 1 такт для всех 4-х групп по 8 цифр в 256-и битном YMM регистре! ибо константа 4 раза повторена в YMM регистре) и плюс оставит результирующий перенос в 63-м бите. Сама 256-и битная сумма потом при записи будет откорректирована обратно к нормальному десятичному представлению за 3 такта для всех 256-и битов YMM регистра.
Код сомнения вызывает зря, он рабочий, выдрал из 100% проверенной программы.

-- 23.06.2015, 17:15 --

venco в сообщении #1030110 писал(а):

В вышеприведённом коде я не вижу циклов, обрабатывающих этот перенос.

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

[venco]

Ок, поскольку сложение есть максимум для 64-бит, а для алгоритма десятичного сложения нужен полноценный двоичный перенос, я думаю, лучше, чем по 64-бит, обрабатывать и не получится.
Так что используйте обычные 64-битные регистры, вряд ли получится быстрее. Можно и не заморачиваться с SSE/AVX.
Разве что попробовать отложить пост-обработку (приведение к нормальному десятичному виду) на потом, и выполнить его с SSE. Т.е. в обычных регистрах выполняем операцию (a+b+carry+0xf6f6f6f6f6f6f6f6), и собираем результат в xmm/ymm регистр и нормализуем там. (a+b) можно сделать без порчи переноса через LEA.

[Dmitriy40]

Т.е. выходит что никакой хитрости с быстрым распространением переноса в самом YMM регистре через границы 64 бит не придумать? Переразложить по другим регистрам (в обычные не выгодно, удобнее и достаточно в младшую половину XMM, всё же 64 бита вместо 32 в обычных) понятно, так тоже сделал, общий выигрыш 40% ускорения (для всей программы с кучей прочих действий, в том числе и "лишних" - перетасовок слов по регистрам).
Удивляет что восьмикратное увеличение обрабатываемой порции (переход от 32-х бит к 256-ти битам (с обычных регистров к YMM)) даёт менее трёхкратного роста скорости, хотя кроме переносов все остальные действия от разрядности не зависят.

[venco]

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

в обычные не выгодно, удобнее и достаточно в младшую половину XMM, всё же 64 бита вместо 32 в обычных

Опять вы говорите про 32-битные обычные регистры. Вообще-то они 64-битные.
(Хотя, если у вас 32-битная ОС, то, наверно, 64-битные недоступны).

[Dmitriy40]

venco в сообщении #1030152 писал(а):

Хотя, если у вас 32-битная ОС, то, наверно, 64-битные недоступны

Да, компилится в 32-х разрядном режиме, потому думаю что недоступны. Хотя ... Что-то с Вами стал не уверен, пойду просвещаться/уточнять ... Если что - где взять пепел я знаю.

[venco]

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

компилится в 32-х разрядном режиме, потому думаю что недоступны.

Так-то да. Недоступны. А ОС-то 64-битная? Может всё-таки попробуете 64-битный режим? Там, кроме размера регистров, ещё и их количество в два раза больше.

[Dmitriy40]

Или я совсем тупой, или трюки с переходом в 64 битный режим из 32-х битной программы-оболочки не срабатывают - нашёл парочку трюков, проверил, dll системой не загружается. Нагло расставить REX префиксы командам даже не пробовал - должно быть и очевидно будет исключение неверной команды.
Перейти полностью на 64 бит мешает программа-оболочка, откуда вызываются функции работы с числами. Она не требовательная, но искать под неё 64-битный компилятор ... Ради непонятного выигрыша ... не. Выигрыш от перехода на 64 бит регистры не превысит двухкратного. Применение AVX2 вперемешку с SSE4 даёт почти трёхкратный выигрыш, т.е. гарантированно заметно обгоняет любой возможный выигрыш от х64. Потому x64 пока отказать. Решение под AVX2 идеологически более правильное, буду добивать его, ещё пара мыслей появилась в процессе обсуждения (но надо посчитать много таблиц и кода написать, потому проверить не успел пока).

Собственно я надеялся что вдруг просто не знаю какого хитрого трюка с AVX2 командами, который резко ускорит/упростит распространение переноса, бывает же замыливание мыслей, не видишь красивого простого решения, меня ткнут в него носом, я и обрадуюсь ...

(Цифры)

Я кажется немного запутался в относительных скоростях, сведу воедино:
1) не до конца оптимизированные 32 бит регистры (особо в них не упирался т.к. было желание использовать AVX, а эти делал для отработки алгоритма, сравнения и получения образцовых исходных данных) - примем за 1.0;
2) показанный выше AVX2 код с хорошо оптимизированными прочими вычислениями - 2.0х;
3) модификация с использованием для переносов только половин XMM регистров и команд AVX2 - 2.8х.

[Dmitriy40]

Путём небольшой оптимизации улучшил время с 21 такта до 13. Правда на скорости всей программы это практически не отразилось, ускорение всего около 5%.

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

;Условия запуска и времена выполнения команд:             Порты      L/T     Конвейер
;Дальше учёт переноса между границами 64бит в ymm1
                vpsrlq          xmm2,xmm1,63            ;0      1/1     x...................... y2=00XC
                vpshufd         xmm2,xmm2,11001111b     ;5      1/1     -x..................... y2=00C0
                vpaddq          ymm1,ymm1,ymm2          ;15     1/0.5   .-x.................... y1=3210
                vpsrlq          xmm2,xmm1,63            ;0      1/1     ..-x................... y2=00CX
                vpermq          ymm1,ymm1,01001011b     ;5      3/1     ..-xxx................. y1=1023
                vpshufd         xmm2,xmm2,11101111b     ;5      1/1     ...-x.................. y2=00C0
                vpaddq          ymm1,ymm1,ymm2          ;15     1/0.5   ....--x................ y1=1023
                vpsrlq          xmm2,xmm1,63            ;0      1/1     ......-x............... y2=00CX
                vpshufd         xmm2,xmm2,11111110b     ;5      1/1     .......-x.............. y2=000C
                vpaddq          ymm1,ymm1,ymm2          ;15     1/0.5   ........-x............. y1=1023
                vpsrlq          xmm2,xmm1,63            ;0      1/1     .........-x............ y2=00XC
                vpermq          ymm1,ymm1,00011110b     ;5      3/1     .........-xxx.......... y1=3210
                vpshufd         xmm2,xmm2,11111100b     ;0      1/1     ..........-x........... y2=000C
                                                        ;       =13
 

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

[Dmitriy40]

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

[SY1234]

venco в сообщении #1029761 писал(а):

Между прочим, в оптимизированной библиотеке GMP на последних интелах для сложения используется простой ADC с ручной оптимизацией цикла.

Вообще говоря, о GMP на Intel Haswell упоминалось еще в 2013 году: https://gmplib.org/list-archives/gmp-de ... 03353.html
Хотя я предпочитаю отпочковавшуюся от GMP MPIR.
Haswell - очень удачная архитектура: позволяет, например, на 6-ти ядерном процессоре с частотой 3.3 GHz перемножить две квадратные матрицы double с n=10000 всего за 7.0 с для оси x64.

[Dmitriy40]

Какая жаль, что для моей/нашей задачи перемножение double матриц не нужно ... А нужно сложить два десятичных числа длиной более 600М цифр каждое.
Да, архитектура получше предыдущих, за счёт оптимизации целочисленных векторных операций (AVX2), но много нужных команд так и нету, а некоторые очень нужные выполняются долго (3 такта вместо максимум 1). И мало какие целочисленные AVX2 команды выполняются параллельно.
А вообще, не понимаю смысла Вашего сообщения тут. В чём он? Вы можете что-то сказать по теме?

[SY1234]

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

Какая жаль, что для моей/нашей задачи перемножение double матриц не нужно ... А нужно сложить два десятичных числа длиной более 600М цифр каждое.
Да, архитектура получше предыдущих, за счёт оптимизации целочисленных векторных операций (AVX2), но много нужных команд так и нету, а некоторые очень нужные выполняются долго (3 такта вместо максимум 1). И мало какие целочисленные AVX2 команды выполняются параллельно.
А вообще, не понимаю смысла Вашего сообщения тут. В чём он? Вы можете что-то сказать по теме?

причем здесь AVX2 (хотя я AVX2 и использовал для быстрой генерации случайных чисел): я когда говорил о матрицах, то имел в виду FMA. А смысл моего сообщения наверное лучше прокомментировать venco: он затронул тему, к которой и относится мой комментарий. Что касается сложения, то мои интересы в этом вопросе находятся в области вещественных чисел: я не изобретал велосипед, а взял все лучшее, что создало человечество по этой теме, чего и Вам советую.

[Dmitriy40]

SY1234 в сообщении #1043767 писал(а):

причем здесь AVX2 (хотя я AVX2 и использовал для быстрой генерации случайных чисел): я когда говорил о матрицах, то имел в виду FMA. А смысл моего сообщения наверное лучше прокомментировать venco: он затронул тему, к которой и относится мой комментарий. Что касается сложения, то мои интересы в этом вопросе находятся в области вещественных чисел: я не изобретал велосипед, а взял все лучшее, что создало человечество по этой теме, чего и Вам советую.

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

[SY1234]

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

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

Почему не относится: я привел важный пример использования AVX2, т.к. мне показалось, что Вы бросаете тень на AVX2. Что касается непосредственно Вашей темы, то вроде venco уже говорил о том, что YMM регистры созданы не для тех манипуляций, которым Вы пытаетесь их подвергнуть. И я venco отвечал, а не Вам: впрочем, модераторы рассудят.