Если вы заботитесь о производительности, избегайте инструкции loop на современных процессорах. Почему инструкция цикла слишком медленная? Разве Intel не смогла реализовать это эффективно? . Также используйте SSE2 вместо MMX; ваш размер массива кратен 16 и 8, и вы используете x86-64, который гарантированно будет иметь SSE2. MMX абсолютно бессмысленен, если вы не делаете 32-битную версию для Pentium III / Athlon-XP и более ранних версий.
(Весь код в моем ответе будет работать с 8-байтовыми регистрами MMX вместо 16-байтовых регистров XMM, потому что есть MMX-версии всех инструкций, которые я использовал. Согласно приложению B к руководству NASM , pmullw, pxor, pcmpgtw и paddusw были доступны в оригинальном P5 Pentium MMX. Некоторые инструкции, которые в руководстве Intel указаны как «MMX» (например, pmulhuw и pshufw) ) были добавлены только позже, как, например, с Pentium II, или вместе с SSE в Pentium III, но это не относится ни к одной из инструкций, которые были здесь полезны.)
См. https://stackoverflow.com/tags/x86/info для руководств по производительности / оптимизации, а также для ссылок ABI / соглашений о вызовах, которые объясняют 16-байтовое выравнивание стека, необходимое для вызова функций.
mov rax, 0 / mov ax, [r8] действительно глупо. Используйте movzx eax, word [r8] как обычный человек. Вам также не нужно jmp переходить к следующей исходной строке, например jmp .square_loop / .square_loop: Выполнение всегда проваливается на следующую строку самостоятельно, если нет инструкции перехода.
x86 SIMD не имеет умножающего насыщения, только насыщающее добавление со знаком / без знака и насыщающее уплотнение для более узких элементов . (MMX / SSE2 paddsw / paddusw). Поскольку вы печатаете с %d, может быть, вы хотите подписанную насыщенность? Но это только после распаковки в 32-битную версию, и ваша формула всегда будет давать положительный результат, поэтому вы можете использовать беззнаковое насыщение. Я вижу, это то, что ваш код использует paddusw.
Кроме того, использование 3 отдельных циклов, которые сохраняют / перезагружают ваши данные между каждым шагом формулы, действительно ужасно . Вы (почти) всегда хотите увеличить вычислительную интенсивность (объем работы ALU, выполненной над вашими данными в расчете на пропускную способность памяти / кэша). Вам также не нужна инструкция умножения, чтобы удвоить число: просто добавьте его к себе. padd* работает на большем количестве портов, чем pmul*, и имеет лучшую задержку и (в данном случае соответствующую) пропускную способность.
default rel
;;; Efficient but *doesn't* saturate the multiply
lea rcx, [rsi + length] ; rcx = end_pointer
movdqa xmm5, [fives]
.loop: ; do{
movdqu xmm0, [rsi] ; use movdqa if your data is aligned, faster on very old CPUs.
pmullw xmm0, xmm0 ; x*x ; does NOT saturate. will wrap.
paddusw xmm0, xmm0 ; *= 2 ; with unsigned saturation
paddusw xmm0, xmm5 ; += 5 ; xmm5 = _mm_set1_epi16(5) outside the loop
movdqu [rsi], xmm0
add rsi, 16
cmp rsi, rcx ; }while(p<endp);
jb .loop
...
section .rodata
align 16
fives: times 8 dw 5
Для насыщения вы можете использовать SSSE3 https://www.felixcloutier.com/x86/pmaddubsw,, но для этого требуются только байтовые входы. Насыщает горизонтальную сумму пар i8 x u8 => i16 продуктов.
В противном случае вам, вероятно, придется распаковать в dwords и packssdw (подпись) или packusdw (насыщение без знака) обратно в слова. Но умножение меча происходит медленно с SSE4.1 pmulld (2 мопа на Haswell и позже). Однако на некоторых старых процессорах это всего 1 моп. И, конечно, распаковка создает вдвое больше работы благодаря наличию более широких элементов.
В этом случае ваша формула монотонна с величиной входа, поэтому вы можете просто сравнить на входе и насытить вручную.
Если мы предположим, что ваши входные данные также не подписаны, нам не нужно вводить абсолютное значение перед сравнением. Но (до AVX512) у нас нет сравнения целых чисел без знака, только подписи больше-больше, поэтому большие входы без знака будут сравниваться как отрицательные.
2 * 0x00b5^2 + 5 = 0xfff7, который умещается в 16 бит 2 * 0x00b6^2 + 5 = 0x102cd, который не делает, и мы хотим, чтобы он был насыщен до 0xffff
Точка отсечения переполнения является четным числом, поэтому мы могли бы справиться с проблемой сравнения со знаком путем смещения вправо. Это было бы беззнаковым делением на 2, что позволило бы безопасно использовать результат как неотрицательное целое число со знаком. 0xb6 >> 1 = 0x5b. Но pcmpgtw - это сравнение для >, а не >=.
Если мы обратим операнды к pcmpgtw для сравнения для (x>>1) < (0xb6>>1), то нам потребуется movdqa константа, чтобы избежать ее уничтожения, но нам все равно нужно сдвинуть вправо x с помощью movdqa + psrlw. И более эффективно иметь вектор, равный 0xffff, когда необходимо насыщение (иначе 0), потому что мы можем применить его непосредственно с помощью POR или PADDUSW.
Таким образом, наша лучшая ставка - просто сместить диапазон x и 0xb5 к знаку и сделать (x-0x8000) > (0xb5 - 0x8000), используя pcmpgtw SIMD со знаком сравнения.
Другие худшие варианты включают:
- Проверка на переполнение при умножении с помощью
pmulhuw, чтобы вычислить верхнюю половину (и проверить, не ненулевое ли оно). Мы были бы в опасности узкого места при умножении пропускной способности, и проверка на ненулевое значение с pcmpeqw является обратным условием, которое мы хотим.
psubusw x, 0xb5 и убедитесь, что это == 0. pcmpeqw даст нам инвертированную маску, но мы не можем использовать pcmpgtw для проверки usat16(x-0xb5) > 0, потому что большие входы (с установленным старшим битом) будут оставаться "отрицательным" после вычитания только небольшого числа, как 0xb5. paddusw и проверьте на == 0xffff: только достаточно малые входы оставят конечный результат ненасыщенным. Некоторые процессоры могут запускать pxor на большем количестве портов, чем padd*, и для этого не требуется меньше ненулевых векторных констант, так что это ни в коем случае не лучше. Но это одинаково хорошо на Скайлэйке.
default rel
;;; With a check on the input to saturate the output
lea rcx, [rsi + length] ; rcx = end_pointer
movdqa xmm4, [input_saturation_cutoff]
movdqa xmm5, [fives]
pcmpeqd xmm3, xmm3
psllw xmm3, 15 ; xmm3 = set1_epi16(0x8000) for range-shifting to signed
.loop:
movdqu xmm0, [rsi]
movdqa xmm1, xmm0
; if x>0xb5 (unsigned), saturate output to 0xffff
pxor xmm1, xmm3 ; x - 0x8000 = range shift to signed for compare
pcmpgtw xmm1, xmm4 ; xmm1 = (x > 0xb5) ? -1 : 0
pmullw xmm0, xmm0 ; x*x
paddusw xmm0, xmm0 ; *= 2 ; saturating add or not doesn't matter here
por xmm1, xmm5 ; 0xffff (saturation needed) else 5. Off the critical path to give OoO exec an easier time.
paddusw xmm0, xmm1 ; += 5 or += 0xffff with unsigned saturation.
movdqu [rsi], xmm0
add rsi, 16
cmp rsi, rcx
jb .loop
...
section .rodata
align 16
input_saturation_cutoff: times 8 dw (0x00b5 - 0x8000) ; range-shifted to signed for pcmpgtw
fives: times 8 dw 5
; 5 = 0xb6 >> 5 or 0xb6 >> 5 but we'd need to knock off the high bit from input_saturation_cutoff
; Or we could materialize constants like this:
; movdqa xmm4, [set1w_0xb5]
; pcmpeqd xmm3, xmm3
; psllw xmm3, 15 ; rangeshift_mask = set1(0x8000)
; movdqa xmm5, xmm4
; psrlw xmm5, 5 ; fives = set1(5)
; pxor xmm4, xmm3 ; input_sat_cutoff = set1(0x80b5)
;; probably not worth it since we already need to load 1 from memory.
Я проверял это, и paddusw делает 0x2 + 0xffff = 0xffff, например.
Мы могли бы просто POR окончательного результата с 0 или 0xffff, чтобы либо оставить его неизмененным, либо установить его на 0xffff, но изменение ввода до последнего paddusw создает больше параллелизма на уровне команд за одну итерацию. Таким образом, выполнение вне порядка не должно перекрывать столько независимых итераций, чтобы скрыть задержку тела цикла. (Если бы мы планировали это для Atom или P5 Pentium-MMX по порядку, мы бы чередовали больше из двух цепочек dep.)
На самом деле, смещение вправо на 1 сработало бы : нам нужно только сравнение, чтобы поймать входные данные настолько большие, что умножение оборачивается в маленький результат . 0xb6 * 0xb6 не переносится, поэтому сам по себе просто отлично насыщается с paddubsw.
Хорошо, если мы проверим (x>>1) > (0xb6>>1) с помощью pcmpgtw (вместо >=), чтобы перехватить вводы типа 0xffff (где pmullw с 0xffff дает нам 0x0001). Таким образом, мы могли бы сохранить 1 векторную константу, но в остальном это не лучше.
pxor + pcmpgtw, по крайней мере, столь же дешев, как psrlw xmm, 1 + pcmpgtw, если, возможно, мы не настраиваемся на семейство Intel P6 (Core2 / Nehalem) и работаем в стойках регистрации-чтения-порта. Но это маловероятно: xmm0, xmm1 и rsi всегда должны быть горячими (недавно записанными и, таким образом, прочитанными из ROB, а не из файла постоянного реестра). Мы читаем только 2 векторных константы в первой группе из 4 инструкций в цикле, а затем 1 позже.
Как я говорю ниже, на многих процессорах Intel psrlw может работать только на том же порту, что и pmullw, на модуле исполнения vec-int shift + multiply. Вероятно, здесь нет узкого места в пропускной способности.
Но pcmp и padd работают на ограниченных портах (на Intel до Skylake), тогда как pxor может работать на любом векторном порте ALU. Сочетание чисто padd / pcmp / pmul / psrl` оставляет один векторный порт ALU неиспользованным.
Идея проверки альтернативной насыщенности
(я написал эту часть, забывая о * 2 в формуле, когда искал самый высокий ввод, который не переполнялся бы.)
Если бы формула была (0x00ff)^2 + 5, проверка насыщения была бы проще.
Мы могли бы просто проверить битовые позиции.
(0x00ff)^2 + 5 = 0xfe06, который умещается в 16 бит (0x0100)^2 + 5 = 0x10005 что не так, и мы хотим, чтобы оно было насыщенным до 0xffff
Итак, нам нужно проверить, что все старшие 16 бит равны нулю, или что x&0xFF == x, или что x>>8 == 0.
Для этого требуется меньше констант, но на самом деле это хуже, чем смещение диапазона для подписи с помощью PXOR, потому что на некоторых процессорах исполнительные блоки с векторным смещением и векторным умножением находятся на одном порту. (И, таким образом, psrlw и pmullw конкурируют друг с другом за пропускную способность. Этого вполне достаточно, чтобы не было узкого места на порту 0 в Nehalem / Sandybridge / Haswell, но это не повредит.)
lea rcx, [rsi + length] ; rcx = end_pointer
movq xmm5, [fives]
punpcklqdq xmm5, xmm5 ; or with SSE3, movddup xmm5, [fives] to broadcast-load
pxor xmm4, xmm4 ; xmm4 = 0
.loop:
movdqu xmm0, [rsi]
movdqa xmm1, xmm0
; if x>0xffU, i.e. if the high byte >0, saturate output to 0xffff
psrlw xmm1, 8 ; x>>8 (logical right shift)
pcmpgtw xmm1, xmm4 ; xmm1 = ((x>>8) > 0) ? -1 : 0
pmullw xmm0, xmm0 ; x*x ; does NOT saturate. will wrap.
paddusw xmm0, xmm0 ; *= 2 ; with unsigned saturation
por xmm1, xmm5 ; 0xffff (saturation needed) or 5 (normal). Off the critical path to give OoO exec an easier time.
paddusw xmm0, xmm1 ; += 5 or += 0xffff with unsigned saturation.
movdqu [rsi], xmm0
add rsi, 16
cmp rsi, rcx
jb .loop
С AVX512BW (Skylake-X) для сравнения без знака с использованием регистров маски
Наконец, мы можем сравнивать целое число без знака с AVX512F, а по размеру элемента word - с AVX512BW. Но результат находится в регистре маски вместо вектора, поэтому мы не можем просто vpor сделать его с вектором set1(5), чтобы создать вход для насыщающего сложения.
Вместо этого мы можем смешивать вектор 5 и 0xffff в соответствии с маской сравнения.
;; AVX512BW version
;; On a Skylake Xeon you probably only want to use YMM regs unless you spend a lot of time in this
;; to avoid reducing max turbo much.
;; Even with xmm or ymm regs (AVX512VL + BW), this demonstrates
;; that we gain even more efficiency than just widening the vectors
;; Just having non-destructive AVX encodings saves the `movdqa xmm1,xmm0` in the SSE2 version.
;; With YMM or XMM regs, most of these instructions can still use shorter VEX encoding (AVX), not the longer EVEX (AVX512)
;; (Use vmovdqa/u instead of vmovdqu64. The 64 is element-size, irrelevant when not masking.)
;;;;;;;;;;; UNTESTED ;;;;;;;;;;;;;;;;;
mov eax, 0xb5 ;; materialize vector constants from an immediate
vpbroadcastd zmm4, eax ; largest input that won't overflow/saturate
vpsrlw zmm5, zmm4, 5 ; fives = 0xb5 >> 5 = 5
;vpcmpeqd xmm3, xmm3 ; all-ones: result on saturation
vpternlogd zmm3,zmm3,zmm3, 0xff ; alternative for ZMM regs, where there's no compare-into-vector
.loop:
; alignment recommended for 512-bit vectors, but `u` lets it still work (slower) on unaligned.
vmovdqu64 zmm0, [rsi]
;; if x>0xb5 (unsigned), saturate output to 0xffff
vpcmpuw k1, zmm0, zmm4, 2 ; k1 = x <= 0xb5. 2 = LE predicate
; k1 set for elements that WON'T overflow
vpmullw zmm0, zmm0 ; x*x
vpaddusw zmm0, zmm0 ; *= 2 ; saturating add or not doesn't matter here
vmovdqa64 zmm1, zmm3 ; 0xffff
vpaddusw zmm1{k1}, zmm0, zmm5 ; 0xffff or 2*x^2 + 5 merge masking
vmovdqu64 [rsi], zmm1
add rsi, 64
cmp rsi, rcx
jb .loop
(NASM позволяет vpmullw a, b в качестве ярлыка для vpaddusw a, a, b, когда вы не хотите использовать неразрушающее кодирование с 3 операндами назначения, как это делает для imul eax, 123.)
Более ранняя идея применения насыщенности состояла в том, чтобы использовать vpblendmw для выбора между векторами 5 и 0xffff в соответствии с маской.
vpcmpuw k1, xmm4, xmm0, 1 ; k1 = 0xb5<x = x>0xb5. 1 = LT predicate numerically because NASM doesn't seem to accept vpcmpltuw the way it accepts vpcmpeqb
; k1 = 1 for elements that WILL overflow.
multiply and add as usual
...
vpblendmw xmm1{k1}, xmm5, xmm3 ; select (k1==0) ? 5 : 0xffff
vpaddusw xmm0, xmm1 ; += 5 or += 0xffff with unsigned saturation.
Копирование регистра по-прежнему занимает входную операцию, но не внутреннюю операцию ALU. Поэтому (особенно для 512-битных регистров, где порт 1 отключается для векторных мопов в SKX), эта vpblendmb идея хуже, чем маска копирования и слияния.
Кроме того, IACA считает, что vpblendmw xmm1{k1}, xmm3, xmm5 имеет выходную зависимость от XMM1, даже если на самом деле она только для записи . (Я проверил, поместив 8 из них в цикл, с / без прерывания vpxor). Инструкции наложения маски являются особым случаем: для неустановленных битов маски означает, что он копирует из src1 (или ноль для маскирования нуля), а для установленных битов маски он копирует из src2.
Но машинное кодирование использует маскирование слиянием, поэтому возможно, что HW будет рассматривать его как любую другую операцию ALU с маскированием слиянием. (Если выходной вектор является третьей входной зависимостью, vpaddw xmm1{k1}, xmm2, xmm3: если маска имеет какие-либо нули, результатом в XMM1 будет входное значение этого элемента.)
Вероятно, это не проблема: в соответствии с IACA, SKX может выполнять это за одну итерацию на 2,24 цикла (узкое место на внешнем интерфейсе), так что переносимая в цикле цепь депозита через XMM1 не является проблемой, пока это только 1 цикл задержки. (При развертывании с целью уменьшения узких мест в верхней / внешней части цикла вы должны использовать отдельный вектор для мест назначения смешивания, чтобы разделить итерации, даже если вы не можете получить его где-либо около 1 цикла за итерацию.)
(И версия, использующая копирование + маскирование слиянием в вектор 0xffff, также работает с такой пропускной способностью, даже для векторов ZMM. Но IACA считает, что версия vpblendmb будет медленнее с ZMM, даже если она говорит, что оба узких места на внешний интерфейс ...)