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

[Dmitriy40]

Всем здравствуйте.
Есть тут знатоки ассемблера для x86? В частности оптимизации под AVX2?
Мучаюсь с таким вот вопросом, надо просуммировать очень много 256 бит чисел (точнее сложить два 300 млн битных числа), загружаю их в AVX регистры и складываю командой vpaddq, но она не распространяет переносы через границы 64 бит, это приходится делать вручную. И эта вот ручная работа занимает до чёрта много времени, 21 такт (при том что основное сложение всего 0.5-1 такт), в основном из-за тормознутости vpermq (четырежды переставляющей бит переноса в нужную позицию), неспариваемости инструкций так как они все взаимозависимы по данным получаются и почти все ложатся в один порт запуска (AVX перестановщик). Фактически быстрее оказывается разложить 4 слова в отдельные регистры, сложить их последовательно (с выделением переносов) и собрать обратно в 256 бит слово. Мрак, сложить можно два 512 битных числа за такт, а потом 42 такта учитывать внутренние переносы в них.
Собственно вопрос, может кто что посоветует как побыстрее организовать распространение переноса по всему AVX регистру? Я могу переносы оставить в каждом 63-м (63-м, 127-м, 191-м, 255-м) бите, без ухода за разрядную сетку, сейчас так уже и делаю.
Пробовал гуглом искать варианты, не хватает терпения, первые десятки страниц сплошные общие слова и обзоры новых процессоров, а мой вопрос ближе к алгоритмам и оптимизации программ. Если что и встречается, то исключительно про реализацию длинной арифметики (и часто для задач шифрования), а там такты на сложениях особо не экономят, складывают по 64 или даже 32 бита и не парятся. Мне - это слишком долго, хочется сильно быстрее. Помогите идеями?
Может как-то не сдвигом выделять переносы, или не vpermq их расставлять в нужные позиции (но других команд пересылок через 128 бит границу и нет почти) или уйти от зависимости по данным? Можно даже вдвое больше команд выполнять, но чтобы они спаривались и были с малой задержкой.
Задача коммерческого смысла не имеет, делается как хобби.

[venco]

Я думаю, придётся смириться с такой несправедливостью, и использовать простое сложение. В конце концов, MMX/SSE/AVX/... инструкции были созданы специально для параллельной однотипной обработки не связанных данных. Если иногда их удаётся эффективно использовать для чего-то другого - хорошо, а нет - так нет.
Кстати, т.к. у вас современный процессор, посмотрите на инструкции ADCX и ADOX. Они позволяют параллельно выполнять два длинных сложения, а совместно с инструкцией MULX - длинное умножение за один проход.

[venco]

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

[Dmitriy40]

Хм, видимо недостаточно современный - ADX не поддерживается.
Ну да и ладно, вряд ли она выполняется быстрее обычной ADC (что-то Agner Fog про растактовку ADCX молчит), а с ней я конечно первым же делом сделал, но на 32-х битных регистрах скорость ниже втрое (чем на AVX2). Просто нужно не чисто суммирование двух чисел, а более сложные действия, но с ними проблем как раз почти нет, разобрался. И вот их как раз выгоднее делать над как можно большим регистром (там нет зависимости между байтами).
Умножение вообще не нужно, даже сдвиги проще через именно сдвиги делать, чем умножением.
Спасибо что откликнулись.

(Оффтоп)

Наверное Вы правы, придётся мириться с такой несправедливостью - сейчас скорость вычислений уже втрое превышает пропускную способность памяти, т.е. применение AVX2 вообще излишне, операции в обычных регистрах и так утилизируют весь канал памяти (2-х канальная DDR3-1600). Но с этим есть задумки как бороться, сначала хотел выжать всё возможное из вычислений, а уж потом оптимизировать работу с памятью.

[venco]

ADCX не быстрее ADC, он просто позволяет параллельно вести два сложения, т.к. использует только флаг переноса, а ADOX - только флаг переполнения.
Процессор, кстати, какой? В Интелах, вроде, ADX появился вместе с AVX2, хотя всякое может быть, не зря ведь отдельный флаг CPUID отвели.

А почему на 32-битных регистрах? Есть же 64-битные.
И не покажете ваш код с AVX2? Может, что посоветую...

[Dmitriy40]

Процессор Core i5-4690 (Hashwell). Бит ADX в ответе CPUID сброшен.
Функции работы с числами компилятся во внешнюю DLL-ку под 32-битный режим, оттуда достучаться до 64-бит регистров нереально. Переписывать всё под x64 - ну, можно подумать лет через 5 - проблем много, а выигрыша не сильно, да и AVX-то вообще 256 бит.

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

ADCX просто позволяет параллельно вести два сложения,

А это Вы откуда взяли что два? И каких два? Интел по этому поводу специально ничего как-бы не пишет. А если Вы про 4-х портовость запуска команды сложения в АЛУ, то не два, а 4 сложения можно вести, но только для независимых данных, а в длинных числах все сложения последовательно зависимы.Извиняюсь, догнал, всё понятно.

Код покажу, вот:

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

;Условия запуска и времена выполнения команд:             Порты      Задержка/Скорость
;Дальше учёт переноса между границами 64бит
                vpsrlq          xmm2,xmm1,63            ;0      1/1     сдвигаем переносы в младший бит с заполнением нулями (и заодно обнуляем биты 255..128)
                vpshufd         xmm2,xmm2,11001111b     ;5      1/1     сдвигаем перенос на 64бит (и обнуляем биты 191..128 и 63..0)
                vpaddq          ymm1,ymm1,ymm2          ;15     1/0.5
                vpsrlq          xmm2,xmm1,63            ;0      1/1     сдвигаем переносы в младший бит с заполнением нулями (и заодно обнуляем биты 255..128)
                vpermq          ymm2,ymm2,11011111b     ;5      3/1     сдвигаем перенос на 128бит (и обнуляем биты 127..0)
                vpaddq          ymm1,ymm1,ymm2          ;15     1/0.5
                vpermq          ymm2,ymm1,11111110b     ;5      3/1     переносим перенос из 191бита в младшие 64бита
                vpsrlq          xmm2,xmm2,63            ;0      1/1     сдвигаем переносы в младший бит с заполнением нулями (и заодно обнуляем биты 255..128)
                vpermq          ymm2,ymm2,00111111b     ;5      3/1     сдвигаем перенос на 192бит (и обнуляем биты 191..0)
                vpaddq          ymm1,ymm1,ymm2          ;15     1/0.5
                                                        ;       =16
                vpermq          ymm2,ymm1,11111111b     ;5      3/1     переносим перенос из 255бита в младшие 64бита
                vpsrlq          xmm2,xmm2,63            ;0      1/1     сдвигаем переносы в младший бит с заполнением нулями (и заодно обнуляем биты 255..128)
                vpshufd         xmm2,xmm2,11111100b     ;5      1/1     обнуляем биты 127..32
                                                        ;       =21
;y1 - результат, y2 - перенос дальше

Пояснения к коду.
На вход принимается 256 бит число в YMM1 регистре, в нём уже выполнены сложения 64-х битных слов (командой vpaddq), а вот между ними перенос не прошёл, все переносы так и остались в 63,127,191,255 битах. Надо их распространить полностью по всему YMM1 регистру.
И разумеется получить перенос из 255-го бита (для дальнейших операций) - это добавляет ещё 5 тактов, до 21.
Обнулять переносы в 63,127,191,255 битах не обязательно (но если получится быстро - отлично) - потом они всё равно будут обнулены в 3-х случаях из 4-х.
В данном варианте кода все команды получились неспариваемыми т.к. все зависят последовательно друг от друга.
Регистры XMM и YMM смешиваются специально - это позволяет прилично сэкономить код (автообнуление ненужной части регистра), а на скорость влияет лишь положительно (vpshufd быстрее vpermq).

[AlexDem]

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

длинных числах все сложения последовательно зависимы.

Это от системы счисления зависит. Посмотрите, например, здесь: Непейвода Н.Н., И. Н. Григоревский И.Н., Лилитко Е.П. О представлении действительных чисел разделы 3 и 4. В системах с перекрытием дистанция переноса разрядов при сложении ограничена.

(Но поможет ли это Вам с задачей - не знаю, реализация этой арифметики довольно непростая)

[Dmitriy40]

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

-- 23.06.2015, 06:32 --

AlexDem
Да, я слышал про хитрые системы счислений и/или кодирования, но тут потери на преобразования будут огромными и съедят весь предполагаемый выигрыш. Тут числа натуральные, более того, десятичные, да ещё и в каждом байте лишь значения 0..9. Это кстати тоже даёт возможность ускорить вычисления, потому и не перехожу на другое кодирование.
Но книжку на всякий случай гляну, завтра, спасибо.

[AlexDem]

Если Вам просто разово нужно сложить два числа, то да - смысла нет, а если перевести все вычисления на такую арифметику, то может и есть. Всё зависит от задачи.

[venco]

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

На вход принимается 256 бит число в YMM1 регистре, в нём уже выполнены сложения 64-х битных слов (командой vpaddq), а вот между ними перенос не прошёл, все переносы так и остались в 63,127,191,255 битах.

Это как? После сложения 64-битных чисел перенос никак не в 63-ем бите, а вовсе в 64-ом, т.е. за пределами регистра. Чтобы выделить перенос, если он не попадает в специальное место, как, например, во флаги при обычном сложении, надо сравнить результат с одним из слагаемых: если $a+b < a$, то был перенос.
Или вы 63-битные числа складываете?

[Dmitriy40]

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

Или вы 63-битные числа складываете?

Ну можно их считать и 63-х битными. На самом деле это два числа длиной порядка 600млн..миллиарда десятичных цифр, по одной в байте, соответственно 4 старших бита в каждом байте свободны для оптимизации вычислений. Складываются порциями, для AVX по 32 цифры (4 64-х битные порции по 8 цифр в регистре), командой vpaddq после предварительной подготовки (и потом ещё финальное преобразование обратно). И эти 4 свободные бита как раз используются и для распространения переноса внутри этих 8 десятичных цифр (внутри 64/63 бит числа) и для десятичной коррекции и для оставления переносов в рамках регистра - именно чтобы не делать дополнительные сравнения. С десятичной коррекцией и прочими преобразованиями более-менее разобрался, а вот с распространением переносов через 64 бит границы - затык. Про это и спрашиваю.
Но это не догма, можно и сравнениями получать перенос, если так получится быстрее. Я лучшее что придумал - см.выше.

(Оффтоп)

Плохо формулирую задачу, да? Ну вся она чуть сложнее простого сложения чисел, я же прошу помочь лишь в непонятной для меня части, всю перелопачивать не нужно. Ну и для меня то всё в голове и уже очевидно, вот и пропускаю несущественные на мой взгляд детали.

-- 23.06.2015, 14:16 --

А, вспомнил почему отказался от сравнений - vpcmpgtq имеет огромную задержку (latency), аж 5 тактов. vpsrlq и vpermq/vpshufd даже вместе быстрее, да ещё и обнулят почти всё ненужное. А использовать быстрые vpcmpgtd - переносов обрабатывать придётся вдвое больше и команды тоже не спарятся, т.е. всё равно медленнее.

[venco]

А можно вопрос? А зачем по цифре в байте? Это ведь ужасно неэффективно. Почему не используете все биты, и сразу по 64/32, как это делают обычно?

[_Ivana]

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

Тут числа натуральные, более того, десятичные, да ещё и в каждом байте лишь значения 0..9. Это кстати тоже даёт возможность ускорить вычисления, потому и не перехожу на другое кодирование.

Имхо выглядит несколько странно - городить такой огород, оставляя представление чисел в десятичной позиционной системе по цифре в байте. Я вам сейчас предложу киллер-фичу - храните по 2 десятичных разряда в байте (100 то ведь все равно меньше 256) - в 2 раза уменьшите память и возможно не проиграете а еще и выиграете в скорости - вместо смещения адреса и загрузки значения вызывать DivMod 10 или как у вас эта команда зовется в вашем асме.

ЗЫ да, киллер-фича предлагалась на фоне моего бэкграунда 8-битных АВР-ок, для систем другой разрядности можете экстраполировать ее сами.

[venco]

_Ivana в сообщении #1030048 писал(а):

Я вам сейчас предложу киллер-фичу - храните по 2 десятичных разряда в байте

Это не принципиальное улучшение. Надо всю систему менять - переходить на полноценные двоичные разряды. Это позволит складывать по 64-бита за 1.33 такта, или приблизительно 14 десятичных разрядов за такт. Причём код будет простой, в котором гораздо легче будет не наделать ошибок.

А код ТС пока у меня вызывает сильные сомнения. Как там учитываются переносы между байтами?
К примеру, что получится, если сложить следующуе числа?
0х05050505050505050505050505050505
0х04040404040404040404040404040405
Как я понял из описания представления чисел, должен получиться 0 с переносом в следуюший 128-битный разряд. Причём перенос распространяется последовательно с младшего десятичного разряда. В вышеприведённом коде я не вижу циклов, обрабатывающих этот перенос.

[Dmitriy40]

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

Почему не используете все биты, и сразу по 64/32, как это делают обычно?

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

_Ivana
Простите, Вы не поняли задачи. Предложенная киллер-фича известна, проверена и даёт существенный проигрыш за счёт усложнения дополнительных действий кроме самого сложения. Единственное её применение - двойная экономия пропускной способности памяти, этим я займусь позже, когда выжму всё из вычислений. Экономия размера памяти не требуется, существующего предела хватит минимум на два года счёта.
Если хранить 2 цифры в байте каждую в своём полубайте, то сложно получить перенос между ними. А если две цифры хранить как число 0..99, то нереально сложно выполнить прочие необходимые действия кроме самого сложения.
Даже табличное вычисление переносов (и десятичная коррекция) будет долго, придётся для каждого байта делать, а их 32шт в регистре, в 21 такт уложиться думаю нереально.
С DivMod Вы вообще мимо, любая операция деления на порядок медленнее сдвигов, перестановок и сложений/вычитаний. Тоже проверено.