Как выполнить параллельное сложение с использованием AVX с переносом (переполнением), возвращаемым в тот же элемент (контрольная сумма PE)?

Почему встроенный ассемблер? То, как вы это пишете, с операндами ввода и вывода в память, неэффективно. Инструкции SIMD x86 допускают использование операнда-источника памяти. И вы не получите никакой выгоды от использования устаревшей кодировки SSE movdqa; если вы хотите сохранить размер кода, избегая кодировки VEX, используйте movaps. Но, вероятно, лучше использовать vmovdqa, хотя при использовании 128-битных векторов вы не получите зависаний при переходе SSE/AVX, пока верхние половины регистров YMM/ZMM чистые (vzeroupper)

Ваш существующий код выглядит так, как будто он увеличивает элемент res на 1, если было выполнение. Это очень странно; у переноса есть позиционное значение 2^16, но вы возвращаете его обратно в нижнюю часть того же элемента, позиционное значение 2^0. Обычно вам нужно условно увеличить другой вектор, если вы используете восемь параллельных 32-битных счетчиков, каждый из которых разделен на две 16-битные половины.

Питер, большое спасибо за ваш вклад. Я собираюсь пересмотреть этот материал. Основная идея заключалась в параллельном выполнении восьми 16-битных сложений. Затем, сравнивая с промежуточным результатом до текущего сложения, выясняем, какое из восьми 16-битных значений имело переполнение, исправляя только эти 16-битные значения, добавляя еще одно.

И да, я хотел бы использовать все виды AVX/AVX-512, чтобы оптимизировать это. Этот код используется при вычислении контрольной суммы исполняемых файлов PE, которые требуют сложения всех 16-битных слов (с переносом). Текущая версия хорошо справляется со своей задачей, но все еще неоптимальна...

С этой 16-битной контрольной суммой (подача переноса обратно в перенос) остается ли сложение ассоциативным? Я так думаю, иначе вы бы вообще не смогли векторизовать это. Вы можете сократить задержку критического пути, добавив перенос в другой вектор, добавляя его обратно в основной аккумулятор только в конце.

Вы имеете в виду, что у вас есть все доступные версии AVX1/2/512, и вам нужна одна версия, которая будет максимально быстрой, независимо от того, означает ли это использование AVX2 или AVX-512? Или вы имеете в виду, что вам также нужна версия, использующая только AVX2, и еще одна версия, использующая только AVX1, а также версия, использующая AVX-512BW?

@Devvy Обратите внимание, что в вашем коде вы неправильно распространяете перенос, поскольку добавление переноса также может привести к переполнению, и это переполнение необходимо учитывать в более высоких элементах.

@AndreySemachev: Двойное переполнение невозможно. Рассмотрим 8-битный код с максимально возможными входными данными: 0xFF + 0xFF — это 0xFE с переносом 1. Добавляя его обратно внизу, мы получаем 0xFF без переполнения. Это контрольная сумма, а не сложение bigint, поэтому распространение переноса не происходит в другой элемент.

@PeterCordes Первоначально я думал, что ОП хочет реализовать обычное сложение с переносом, что означает, что перенос распространяется на следующий, более значимый элемент суммы. Да, без распространения двойное переполнение невозможно.

Так как это для контрольной суммы PE (согласно комментариям), то сдвига влево быть не должно, предполагается добавление переноса элемента к этому самому элементу (и тогда цикл тоже не нужен, так как конец -вокруг керри не может генерировать другой керри)

@ user555045: И вы можете добавить в отдельный векторный аккумулятор для переносов, я думаю, это сократит задержку критического пути при использовании этого в цикле по сравнению с более длинной цепочкой операций для обновления одного вектора перед просмотром следующего фрагмента исходных данных. .

Если бы вы пытались реализовать 128-битное сложение, вы бы сделали это с помощью двух 64-битных элементов, просто безоговорочно вычитая 0 или -1 из старшей половины. AVX включает vpcmpgtq, чтобы вы могли обойти недостаток насыщенной математики для элементов других размеров. Конечно, SIMD в этом плане не лучше скалярного на x86-64; add/adc более эффективен, чем махинации с AVX, если только вы не можете использовать хранилище частичных слов для своих чисел, чтобы избежать распространения переноса в большинстве операций, перенормируя только время от времени. (Могут ли подпрограммы с длинными целыми числами выиграть от SSE?)

@user555045 user555045 Тогда я неправильно понял вопрос. Спасибо, что указали на это.

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

Можем ли мы избежать _mm_andnot_si128 и просто использовать _mm_sub_epi16? Или невозможно напрямую получить 0 или -1, которые нам нужны, из pcmpeqw или pcmpgtw, полученных с помощью одной предыдущей инструкции?

@PeterCordes Да, я применил ваше предложение об использовании _mm_sub_epi16. Спасибо. Но я не думаю, что будет какая-либо значительная разница в производительности, если судить по симуляции uica.uops.info. Это сокращает код на 2 мопса и пару инструкций, вот и все. Разница лишь в том, что константу «все единицы» сгенерировать проще, чем вектор из 16-битных. Вам все равно нужно отменить маску переноса, поэтому вы меняете pandn на pxor, что эквивалентно.

Если делать это для нескольких векторов, мы могли бы накапливать инвертированные переносы, поэтому нам нужно будет инвертировать их только один раз. (Или sub их из основного векторного аккумулятора вместо add). Позже выносы будут происходить в разных точках, но итог все равно x + (x/65536) Я думаю. Невозможно использовать в API функции-обертки OP, которая делает все для одного вектора, но автономная функция отвлекает от оптимизации цикла, который ее встраивает.

@PeterCordes Я не уверен, как вы будете накапливать отрицательный перенос. Вам необходимо накопить отрицательные элементы переноса, которые являются нулями, то есть вам нужно сделать эти элементы ненулевыми перед тем, как накапливать так или иначе. На данном этапе имеет ли значение, накапливаете ли вы их отдельно или сразу в конечный результат? Использование отдельного аккумулятора потенциально лучше ILP, но я не уверен, что это будет иметь значение на практике.

Я думал pcmpeqw/psubw carries, cmp_result, а затем добавить или заменить переносы один раз в конце. Так что вам не нужно отрицание для каждого pcmp. Это работает? Я не до конца прошел и не опробовал это.

И да, улучшение ILP от отдельного аккумулятора должно иметь большое значение; Задержка критического пути в 4 цикла для вашей версии (параллельные add и adds) по сравнению с задержкой критического пути в 1 цикл, поэтому просто ограничиваем 3 или 4 векторных ALU-операции за такт (при условии, что внешний интерфейс достаточно широк, чтобы выдерживать нагрузки + накладные расходы цикла) , то есть 5/3 цикла на вектор меньше с 4, для достаточно больших входных блоков, которые неупорядоченный exec не может сильно перекрывать их с окружающим кодом, но где пропускная способность памяти не является узким местом, так что, возможно, уже жарко в L2 кэш.

@PeterCordes Я не думаю, что это работает, если я правильно понимаю. Опять же, вам нужно увеличить результат, если произошло переполнение (т. е. отрицательный результат переноса/pcmpeqw равен нулю). Вы не должны изменять сумму, если не было переполнения. Например, n1 = 0xFFFF, n2 = 1, промежуточная сумма = n1 + n2 = 0, отрицательный перенос = 0, окончательная сумма = сумма + (отрицательный перенос == 0) = 0 + 1 = 1. Пример 2: n1 = 1 , n2 = 1, промежуточная сумма = 2, отрицательный перенос = 0xFFFF, окончательная сумма = 2.

@PeterCordes Я добавил в ответ версию с отдельными аккумуляторами. Ограничивающая задержка в этом случае — это накопление переноса, которое должно быть таким же, как задержка версии без отдельного аккумулятора переноса. Т.е. вам все равно нужно вычислить mm_new_sum, чтобы накопить перенос. Это означает, что весь цикл + последнее сложение (сумма, перенос) должно занять примерно то же время, что и цикл с одним аккумулятором. Я что-то упускаю?

@PeterCordes Одна из оптимизаций, которая может быть полезна, - это развернуть цикл и использовать несколько аккумуляторов суммы и переноса. Это разорвало бы цепочку зависимостей для каждого из аккумуляторов. Но тогда нет необходимости накапливать сумму и перенос отдельно - с таким же успехом можно развернуть одноаккумуляторный вариант.

Параллельная версия имеет две отдельные зависимости, переносимые в цикле, по 1 такту, одна из которых питает другую цепочкой длиной в несколько тактов. Таким образом, один должен опережать другого на пару тактов, но, что особенно важно, carry не имеет обратной связи с sum, поэтому пропускная способность все равно может составлять 1/такт (или ограничиваться пропускной способностью ALU). Ограничения задержки и пропускной способности процессоров для операций, которые должны выполняться последовательно обсуждается более простой пример с двумя цепочками операций, одна из которых связана с другой.

@PeterCordes Даже если мы не будем учитывать накопление задержки mm_sum (при условии, что аккумулятор опережает mm_carry), у вас все равно есть _mm_adds_epu16+_mm_cmpeq_epi16+_mm_xor_si128+_mm_sub_epi16 = 4 цикла задержки для расчета mm_carry на каждой итерации цикла. С одним аккумулятором mm_sum у вас будет то же самое плюс _mm_add_epi16, то есть 5 циклов. Однако, напр. при 2x развертывании вы создаете вторую цепочку зависимостей и вдвое уменьшаете общую задержку цикла для каждой из цепочек. Это гораздо больший выигрыш, чем 5->4 цикла на итерацию.

@AndreySemachev следующая итерация может начаться до того, как закончится цепочка cmp/xor/sub, add/cmp/xor следующей итерации не зависит от результата подпрограммы

@AndreySemachev: Вы прочитали ответ по ссылке в моем последнем комментарии? Он объясняет то, что обобщил пользователь 555.... (и показывает диаграмму в формате ASCII), что exec, находящийся вне порядка, может начать работу раньше на следующей итерации одной цепочки, поэтому им не нужно работать синхронно.

Огромное спасибо за такую ​​прекрасную работу и сотрудничество. Ребята, вы потрясающие! Многим людям может быть полезна эта работа, а также выполнение других задач SIMD. Лично я не совсем разбирался в этой области SIMD, но многому научился у вас. Еще раз спасибо.

Еще один «глупый» вопрос: какой бит CPUID мне нужно проверить на предмет SSE2?

@Devvy На 64-битной версии x86 вам не нужно ничего проверять, поскольку SSE2 неявно присутствует на любом 64-битном процессоре x86. На старых 32-битных процессорах вы можете проверить бит 26 edx, возвращаемый cpuid, с eax=1. См. Определить поддержку процессора для SSE2?.

@PeterCordes Да, я читал ответ, но не осознавал, что _mm_adds_epu16, _mm_cmpeq_epi16 и _mm_xor_si128 не зависят от предыдущей итерации цикла накопления переноса и могут быть выполнены раньше. Комментарий пользователя user555045 вызвал этот щелчок. Спасибо вам обоим.

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

Спасибо за ваш вклад. Конечно, я интегрировал это во встроенную секцию ассемблера, которая выполняет цикл как часть it (метка перехода выровнена по 16 байтам), все чередуется настолько, насколько мне это удается — честно говоря, я не знаю, так ли это Материалы о трубопроводах u/v, созданные 20 лет назад, все еще играют роль? Код работает «как шарм», по крайней мере, на AMD Epyc 7000er.

Проблема с u/v осталась далеко позади, теперь у нас есть внеочередное выполнение, поэтому точное чередование не так важно, как раньше. Я полагаю, что выполнение всего цикла во встроенном ассемблере — это нормально. Тем не менее, я думаю, что последовательность vpaddw/vpcmpltuw/vpaddw имеет задержку в 6 циклов (или, может быть, 5?) в Zen4, поскольку результат привязан обратно к входным данным, что ограничивает выполнение цикла с частотой 1 итерация на 6 циклов, но кажется возможным сделать это быстрее, используя идею Питера Кордеса добавить переносы отдельно (что не связывает вычисления одинаковым образом) и объединить две отдельные суммы после цикла

Спасибо за разъяснения по поводу н/в. Я довольно старый разработчик, 25 лет назад писал ассемблерный код x86 (например, написал расширитель DOS - боже мой, это неловко... :-))