какой наиболее эффективный код для расширения больших целых чисел по знаку?

Я пишу библиотеку кода на языке ассемблера x86-64, чтобы предоставить все обычные побитовые, сдвиговые, логические, сравнительные, арифметические и математические функции для s0128, s0256, s0512, s1024, s2048 и s4096 целочисленных типов со знаком и f0128, f0256 , f0512, f1024, f2048 и f4096 типы с плавающей запятой.

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

Младшие 128 бит результата s0256 — это просто копия входного аргумента s0128, а все биты старших 128 бит результата s0256 должны быть установлены на самый старший бит во входном аргументе s0128.

Просто, да? Но вот пока лучшее, что я могу придумать, чтобы преобразовать s0256 в s0128. Игнорируйте первые 4 строки (они просто проверяют ошибки аргументов) и последние 2 строки (возврат из функции без ошибок (rax == 0)). 5 строк в середине - это рассматриваемый алгоритм. Старайтесь избегать [условных] инструкций перехода.

.text
.align 64
big_m63:
.quad  -63, -63                       # two shift counts for vpshaq instruction

big_s0256_eq_s0128:    # (s0256* arg0, const s0128* arg1); # s0256 = s0256(s0128)
  orq        %rdi, %rdi               # is arg0 a valid address ???
  jz         error_argument_invalid   # nope
  orq        %rsi, %rsi               # is arg1 a valid address ???
  jz         error_argument_invalid   # nope

  vmovapd    (%rsi), %xmm0            # ymm0 = arg1.ls64 : arg1.ms64 : 0 : 0
  vmovhlps   %xmm0, %xmm0, %xmm1      # ymm1 = arg1.ms64 : arg1.ms64 : 0 : 0
  vpshaq     big_m63, %xmm1, %xmm1    # ymm1 = arg1.sign : arg1.sign : 0 : 0
  vperm2f128 $32, %ymm1, %ymm0, %ymm0 # ymm1 = arg1.ls64 : arg1.ms64 : sign : sign
  vmovapd    %ymm0, (%rdi)            # arg0 = arg1 (sign-extended to 256-bits)

  xorq       %rax, %rax               # rax = 0 == no error
  ret                                 # return from function

Эта процедура также неоптимальна в том смысле, что для каждой инструкции требуется результат предыдущей инструкции, что предотвращает параллельное выполнение любых инструкций.

Есть ли лучшая инструкция для сдвига вправо с расширением знака? Я не могу найти такую ​​инструкцию, как vpshaq, которая принимает немедленный байт для указания счетчика сдвига, хотя я не знаю почему (многие SIMD-инструкции имеют немедленные 8-битные операнды для различных целей). Кроме того, Intel не поддерживает vpshaq. Ой!

Но смотри! У StephenCanon есть блестящее решение этой проблемы ниже! Потрясающий! В этом решении на одну инструкцию больше, чем в приведенном выше, но инструкция vpxor может быть помещена после первой инструкции vmovapd и фактически должна занимать не больше циклов, чем версия с 5 инструкциями выше. Браво!

Для полноты и удобства сравнения вот код с последним улучшением StephenCanon:

.text
.align 64
big_s0256_eq_s0128:    # (s0256* arg0, const s0128* arg1); # s0256 = s0256(s0128)
  orq        %rdi, %rdi               # is arg0 a valid address ???
  jz         error_argument_invalid   # nope
  orq        %rsi, %rsi               # is arg1 a valid address ???
  jz         error_argument_invalid   # nope

  vmovapd    (%rsi), %xmm0            # ymm0 = arg1.ls64 : arg1.ms64 : 0 : 0
  vpxor      %xmm2, %xmm2, %xmm2      # ymm2 = 0 : 0 : 0 : 0
  vmovhlps   %xmm0, %xmm0, %xmm1      # ymm1 = arg1.ms64 : arg1.ms64 : 0 : 0
  vpcmpgtq   %xmm1, %xmm2, %xmm1      # ymm1 = arg1.sign : arg1.sign : 0 : 0
  vperm2f128 $32, %ymm1, %ymm0, %ymm0 # ymm1 = arg1.ls64 : arg1.ms64 : sign : sign
  vmovapd    %ymm0, (%rdi)            # arg0 = arg1 (sign-extended to 256-bits)

  xorq       %rax, %rax               # rax = 0 == no error
  ret                                 # return from function

Я не уверен, но отсутствие необходимости чтения этих двух 64-битных счетчиков сдвига из памяти также может немного ускорить код. Хороший.


x86-64 bigint assembly avx sign-extension
person Community    schedule 12.01.2014    source источник
comment
используйте test %rdi, %rdi / jz для перехода к нулевому регистру. Это может объединяться в одну операцию тестирования и ответвления как на AMD, так и на Intel и позволяет избежать дополнительного цикла задержки в цепочке отложений, ведущей к нагрузке. Или, что еще лучше, потребуйте, чтобы ваш вызывающий объект передал допустимые аргументы, чтобы вы просто segfault использовали неверные указатели.   -  person Peter Cordes    schedule 21.10.2020

Ответы (1)


arrow_upward
4
arrow_downward

Вы слишком все усложняете. Когда у вас есть вход в rax, просто сделайте оттуда два хранилища 64b вместо того, чтобы пытаться собрать результат в ymm0. На одну инструкцию меньше и цепочка зависимостей намного короче.

По мере того, как тип назначения становится больше, конечно, имеет смысл использовать более широкие хранилища (AVX). С AVX2 вы можете использовать vbroadcastq, чтобы сделать знак более эффективным, но похоже, что вы ориентируетесь на базовый AVX?

Я также должен отметить, что как только вы доберетесь до ~ 512b целых чисел, для большинства алгоритмов стоимость суперлинейных операций, таких как умножение, настолько полностью доминирует над временем выполнения, что выжимание каждого последнего цикла из операций, таких как расширение знака, быстро начинает терять ценность. Это хорошее упражнение, но, в конечном счете, не самое продуктивное использование вашего времени, если ваши реализации «достаточно хороши».

После дальнейших размышлений у меня есть следующее предложение:

vmovhlps  %xmm0, %xmm0, %xmm1 // could use a permute instead to stay in integer domain.
vpxor     %xmm2, %xmm2, %xmm2
vpcmpgtq  %xmm1, %xmm2, %xmm2 // generate sign-extension without shift

Это имеет следующие достоинства: (а) не требует постоянной нагрузки и (б) работает как на Intel, так и на AMD. Xor для генерации нуля выглядит как дополнительная инструкция, но на практике эта идиома обнуления даже не требует слота выполнения на последних процессорах.

FWIW, если ориентироваться на AVX2, я мог бы написать это так:

vmovdqa (%rsi),        %xmm0 // { x0, x1, 0,  0  }
vpermq   $0x5f, %ymm0, %ymm1 // { 0,  0,  x1, x1 }
vpxor    %ymm2, %ymm2, %ymm2 // { 0,  0,  0,  0  }
vpcmpgtq %ymm1, %ymm2, %ymm2 // { 0,  0,  s,  s  } s = sign extension
vpor     %ymm2, %ymm0, %ymm0 // { x0, x1, s,  s  }
vmovdqa  %ymm0,       (%rdi)

К сожалению, я не думаю, что vpermq доступен на AMD.

person Stephen Canon    schedule 12.01.2014
comment
Я не знал, что AVX2 еще не был доступен. Процессоры, которые я должен протестировать, это FX8150 и FX8350. Я готов принять любую инструкцию, которую имеют эти процессоры. Да, я поддерживаю следующие типы данных: s0128, s0256, s0512, s1024, s2048, s4096 целые числа и f0128, f0256, f0512, f1024, f2048, f4096 числа с плавающей запятой. Для больших размеров лучший подход меняется по мере того, как число 64-битных фрагментов, заполняемых знаковым битом, становится большим. Вот почему я попытался сделать как можно больше в регистрах SIMD ymm, что, надеюсь, более эффективно для больших типов данных. - person honestann; 12.01.2014
comment
@honestann: правильно, для больших типов данных вы захотите выделить знаковый бит с помощью AVX, как в вашем примере. Для конкретного случая 128->256 (который вы использовали здесь) немного удобнее просто сохранить из GPR. AVX2 доступен в микроархитектуре Intel Haswell, но пока недоступен в компонентах AMD, так что это не вариант для вас. - person Stephen Canon; 12.01.2014
comment
@StevenCanon: Также меня немного беспокоило то, что схема кэширования вызывает проблемы и задержки ЦП из-за многократной записи разных значений в одну 64-байтовую строку кэша. Со всеми слияниями, которые необходимо выполнить, я опасаюсь, что передача битов и фрагментов одной строки кэша в кэш (особенно в последовательных инструкциях) может заставить схему кэша ввести дополнительные задержки. Я бы не хотел быть бедным ублюдком, который должен проектировать схему кэш-памяти, чтобы справляться с такими ситуациями! - person honestann; 12.01.2014
comment
Большинство кэшей отлично справляются с обработкой соседних 64-битных хранилищ. Вы сталкиваетесь с проблемами на некоторых архитектурах, когда вы создаете перекрывающиеся хранилища, и вам нужно быть осторожным при сохранении и последующей немедленной перезагрузке данных, когда размеры доступа различаются, но для вашего использования здесь вы было бы довольно безопасно. - person Stephen Canon; 12.01.2014
comment
Кстати, если вы можете легко проверить, правильно ли работает инструкция vpshaq на вашем процессоре, это бы мне очень помогло. На моих процессорах сдвигаются только младшие 64 бита исходного операнда. В документации говорится, что обе 64-битные части исходного регистра xmm должны быть сдвинуты, и имя инструкции указывает, что обе должны (как упакованная инструкция). Если у вас есть процессоры Intel, было бы неплохо узнать, сдвигают ли они обе 64-битные части или только одну. - person honestann; 12.01.2014
comment
Величина сдвига для каждой дорожки должна присутствовать в соответствующей дорожке вектора счетчика смен. Поэтому, если вы хотите сдвинуться без предварительного выполнения movhlps, вам нужно иметь {x,63} для вектора счета смен. Прямо сейчас ваш код использует память, которую вы не установили для верхней полосы счетчика смен, хотя она, вероятно, будет равна нулю. Имейте в виду, что vpshaq недоступно для процессоров Intel, это расширение AMD. - person Stephen Canon; 13.01.2014
comment
Дох! Да, моя ошибка! Я думал, что инструкция vpshaq принимает только одну спецификацию сдвига, но теперь я вижу, что инструкция vpshaq принимает одно 64-битное поле счетчика сдвига для каждого 64-битного поля, которое она сдвигает. Я исправил код. Хотя теперь это выглядит намного лучше, всего с 5 инструкциями каждая инструкция должна ждать результата предыдущей инструкции, поэтому, вероятно, ей придется остановиться на пару циклов, прежде чем она запустит каждую из 5 инструкций. Хммм ... Интересно, есть ли хороший способ с инструкциями как для процессоров INTEL, так и для процессоров AMD. movhlps необходим, поэтому мы создаем 128-битный знаковый бит. - person honestann; 13.01.2014