Гайд [ASM] Ассемблер - введение в векторную математику: основы SIMD. Основа оптимизации программ

[KVANTOR815]

SIMD - что же это такое?
SIMD - так скажем архитектурный трюк, который позволяет процессору обрабатывать пачку данных несколькими командами.
В обычном же скалярном режиме процессор обрабатывает данные побайтово, к примеру в цикле, или складывает числа по одному, то в SIMD-режиме же он сможет проходить в цикле по 16 байт сразу, или если представить внутри двух широких регистров(условно XMM), упакованы числа, процессор сможет их суммировать одновроменно за один такт.
Еще пример, если вам нужно сложить два массива координат(X, Y, Z), вы можете отказаться от цикла по три итерации, вместо этого загружаем все три координаты в один SIMD-регистр и выполняем всего одну инструкцию(к примеру ADDPS).

Спойлер: Макрос section.inc из кода

macro .code {
    section '.text' code readable executable
}

macro .data {
    section '.data' data readable writeable
}

macro .idata {
    section '.idata' import data readable writeable
}

1. Немного поговорим про FPU-инструкции и MMX.
Хотелось бы немного окунутся в историю. Перед тем как я расскажу вам про MMX, хочу рассказать про FPU, важно понимать, что такое FPU-инструкции, т.к MMX заимствовал регистры у математического сопроцессора FPU.
Самое важное, что хотелось бы рассказать, про способ адресации и главную проблемы совместного использования двух этих технологий.
В отличие от двух стандартных регистров(EAX/RAX), где мы обращаемся к конкретному имени, в FPU реализована своя модель стека, где у вас есть 80-битных регистров - st(0) - st(7).
st(0) располагается на вершине стека, st(1) идет ниже в стеке и так далее, большинство операций происходит именно с верхушкой стека - st(0), что заставляет постоянно следить за тем, чтобы стек не переполнился, иначе процессор начнет выдавать ошибки либо же мусор.

MMX же - это первая реализация понятия SIMD, но как я уже описал выше, была проблема, к примеру Intel не хотело резервировать новые физические регистры, вместо этого они просто наложили 64-битные регистры MMX (mm0–mm7) поверх существующих 80-битных регистров FPU.
Это привело к критическому нюансу, а именно: ты не можешь одновременно считать дробные числа через FPU и использовать MMX. Как ты записываешь данные в MM0, содержимое st(0) затирается.
Чтобы пофиксить это, нужно обязательно вызывать инструкцию EMMS, и то, совместно FPU и MMX никогда не использовали, и не используют, это непрактично.

2. Немного поговорим про современные варианты SIMD.
Современные же варианты SIMD стали намного интереснее, к примеру SSE2/AVX, у которых уже имеются свои физические регистры в отличие от MMX.
Нынешние разработчики на ассемблере, да и не только, к примеру даже на ЯВУ, используют векторные инструкции с целью оптимизации программ.

Начнем.
- SSE предоставляет шестнадцать 128-битных регистров XMM(целочисленные/типы с плавающей точкой)
- AVX/AVX2 предоставляет шестнадцать 256-битных регистров YMM(целочислинные типы данных/типы с плавающей точкой)
- AVX-512, поддерживает до 32-х 512 битных регистров ZMM.
Важно понимать, что эти регистры не живут отдельно друг от друга.
128-битный XMM0 является младшей частью 256-битного регистра YMM0, а тот же, в свою очередь младшей частью 512-битного регистра ZMM0, что, фактический обеспечивает обратную совместимость, а именно заключается она в том, что код написаный под SSE, будет физически использовать нижнюю часть широких регистров современных процессоров.

Теперь стоит поговорить про инструкции:
- MOVDQA (Move Double Quadword Aligned) - используется для перемещения 128-битных данных между регистрами XMM или между регистром и памятью. Буква A означает требование к выравниванию: адрес в оперативной памяти обязан быть кратен 16 байтам. Если это условие нарушено, процессор немедленно остановит программу с ошибкой.
- MOVDQU (Move Double Quadword Unaligned) - выполняет ту же задачу, но буква U разрешает использовать невыровненные адреса. Она безопаснее, если вы не уверены, как выделена память, но на старых процессорах она работала медленнее. На современных CPU разница в скорости почти исчезла.
- MOVAPS (Move Aligned Packed Single-precision) работает с числами с плавающей точкой (float). Она загружает сразу четыре 32-битных числа. Если вы работаете с 256-битными регистрами YMM в AVX, инструкция превращается в VMOVAPS, где префикс V открывает доступ к трехоперандной схеме.

Стоит отдельно поговорить касаемо выравнивания, SIMD-инструкции очень капризны к тому, как данные лежат в памяти. Для SSE данные должны быть выровнены по 16-байтной границе, для AVX - по 32-байтной.
Проблема выравнивание кроется непосредственно в устройстве шины данных, процессор читает память блоками, и если 16-байтный вектор пересекает границу двух таких блоков, контроллеру памяти приходится делать два чтения вместо одного, а затем скеливать результат.
Для быстрых же инструкций вроде MOVAPS или MOVDQA это является недопустимым, поэтому архитекторы Intel заложили в них жесткую проверку: если адрес не кратен размеру регистра, генерируется исключение.
В ассемблере для решения этой проблемы используется директива ALIGN. К примеру я создал массив в .data, перед его объявлением пишу align 16 для SSE или align 32 для AVX, - готово, можно работать с MOVDQA.
Перейдем на практику, я использую компилятор FASM.

format PE64 console
entry start

include 'C:\FLAT\INCLUDE\win64a.inc'
include 'C:\FLAT\section.inc'

.data
    result dq 0, 0
align 16
    yougame_array1 dd 1.0, 2.0, 3.0, 4.0
    yougame_array2 dd 5.0, 6.0, 7.0, 8.0

.code
start:
            sub rsp, 28h
            movaps xmm0, dqword [yougame_array1] ;// берем 128 бит(dqword) из памяти и копируем в XMM
            movaps xmm1, dqword [yougame_array2]
            addps xmm0, xmm1

            movaps dqword[result], xmm0 ;// процессор за один такт складывает четыре пары 32-битных чисел
                                        ;// [1.0, 2.0, 3.0, 4.0] + [5.0, 6.0, 7.0, 8.0]
                                        ;// result: (6.0, 8.0, 10.0, 12.0) сохраняется в xmm0.
            add rsp, 28h
            ret

Вот, написал прекрасный пример, который наглядно демонстрирует всю мощь и лаконичность технологии SIMD на ассемблере. Хоть и в комментариях я описал, опишу более подробно
Используя инстркуцию movaps, мы мгновенно загружаем 128 бит данных(т.к тип dqword). Буква A в названии инструкции как я уже писал выше обязывает нас соблюдать правила: данные должны лежать по адресам, кратным 16 байтам. Именно поэтому в секции данных мы используем директиву align 16, гарантируя процессору, что ему не придется спотыкаттся при чтении криво лежащих байтов. Давайте же что-то похожее только без выровненных данных:

format PE64 console
entry start

include 'C:\FLAT\INCLUDE\win64a.inc'
include 'C:\FLAT\section.inc'

.data
    padding db 0
    data dd 1.0, 2.0, 3.0, 4.0

.code
start:
            sub rsp, 28h
            ;// вызвать movaps не получится - данные не выровнены, программа упадает c SF.
            ;// поэтому используем инструкцию для работы с невыровненными данными с префиксом 'U'
            movups xmm0, dqword[data]
            addps xmm0, xmm0
            add rsp, 28h
            ret

Вот еще один прекрасный пример.
В секции данных я специально добавил padding db 0. Этот лишний байт сдвигает массив data, делая его адрес нечетным для SSE. Если вы попробуете применить здесь movaps, процессор мгновенно выбросит исключение Segmentation Fault, так как он ожидает увидеть данные строго по границе 16 байт.
Важно понимать цену этой гибкости. На старых процессорах использование movups вместо movaps могло замедлить программу в полтора-два раза. В современных CPU (начиная с архитектур Skylake или Zen) разница в скорости почти нивелирована, но профессионалы всё равно придерживаются правила: выравнивай всё, что можешь, и используй невыровненный доступ только там, где это неизбежно.

3. Оптимизация программ с помощью SIMD.
Как я уже писал выше, ассемблер-разработчики очень любят оптмизировать свои программы через SIMD, поговорим про оптимизацию.
Для статьи поговорим об оптимизации программ и функций либы msvcrt.dll. Ассемблер-разработчики очень любят делать рефакторинг этой библиотеки, заменяя стандартные реализации на свои, более быстрые версии. Ведь многие функции там до сих пор написаны с расчетом на совместимость, а не на максимальный выжим ресурсов из современного процессора.
Возьмем классический пример - функцию strlen, которая считает длину строки до нулевого байта. В обычном исполнении она перебирает символы по одному (через scasb или обычный цикл с cmp), что на длинных строках работает крайне медленно. Оптимизация через SIMD позволяет нам проверять по 16 байт за один проход. Мы загружаем кусок строки в регистр XMM, сравниваем его с регистром, заполненным нулями, и с помощью маски определяем, попал ли конец строки в этот блок.
Еще как пример, кандитат на оптимизацию - memset. Эта функция заполняет блок памяти определенным значением. Вместо того чтобы писать в память по одному байту через rep stosb, мы упаковываем целевое значение во все ячейки 128-битного регистра.
Ииии функция memcmp для сравнения блоков памяти также расцветает при использовании SSE. Вместо побайтового сравнения мы берем по 16 байт из каждого источника и сравниваем их одной командой pcmpeqb. Если регистры идентичны, мы просто переходим к следующему блоку. На больших массивах данных разница в скорости между стандартной функцией из msvcrt и SIMD-версией может достигать 5-10 раз.
Для статьи я реализовал оптимизированные версии strlen/memcmp:

format PE64 GUI
entry start

include "C:\FLAT\INCLUDE\win64ax.inc"
include 'C:\FLAT\section.inc'

.data
text   db "Yougame.biz/kvantor",0
lenbuf rb 32

.code
start:
    sub  rsp, 28h

    lea  rcx, [text]
    call strlen_sse2

    lea  rcx, [lenbuf]
    call u64_to_dec

    invoke MessageBoxA, 0, lenbuf, "SSE2", 0

    xor  ecx, ecx
    call [ExitProcess]


strlen_sse2:
    mov rdx, rcx  ;// сохраняем начальный адрес строки в rdx для финального расчета длины
    pxor xmm1, xmm1  ;// обнуляем xmm1 (создаем шаблон из 16 нулевых байтов для поиска конца строки)
 
.loop16:
    movdqu xmm0, [rcx] ;// загружаем 16 байт строки в xmm0 (используем U-версию, т.к. адрес может быть любым)
    pcmpeqb xmm0, xmm1 ;// сравниваем каждый байт xmm0 с нулем. Если байт равен 0, в xmm0 запишется FFh, иначе 00h
    pmovmskb eax, xmm0 ;// извлекаем старшие биты каждого байта xmm0 в eax (получаем 16-битную маску совпадений)
    test eax, eax ;// проверка есть ли в eax хоть один установленный  бит(нашелся 0 байт)
    jnz .found ;// если да - прыгаем на выход
    add rcx, 16 ;// сдвиг указателя на 16 байт вперед
    jmp .loop16 ;// повтор цикла для следующей пачки данных
 
.found:
    bsf eax, eax ;// сканируем биты в eax, ищем индекс первого бита равного 1 (позиция нуля в блоке)
    sub rcx, rdx ;// вычисляем, сколько полных блоков по 16 байт мы уже прошли
    add rax, rcx ;// прибавляем позицию нуля внутри последнего блока к общему смещению
    ret


u64_to_dec:
    test rax, rax
    jnz .nz
    mov byte [rcx], '0'
    mov byte [rcx+1], 0
    ret

.nz:
    lea r8, [rcx+21]
    mov byte [r8], 0
    mov r9, 10

.conv_loop:
    xor edx, edx
    div r9      
    add dl, '0'
    dec r8
    mov [r8], dl
    test rax, rax
    jnz .conv_loop

.copy:
    mov al, [r8]
    mov [rcx], al
    inc rcx
    inc r8
    test al, al
    jnz .copy
    ret

.idata
library kernel32, 'KERNEL32.DLL',\
        user32, 'USER32.DLL'

import  kernel32, ExitProcess, 'ExitProcess'
import  user32,   MessageBoxA, 'MessageBoxA'

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

Теперь реализуем свой memcmp и оптимизируем его!

format PE64 GUI
entry start

include 'C:\FLAT\INCLUDE\win64ax.inc'
include 'C:\FLAT\section.inc'

.data
str1 db "Test yougame programm",0
str2 db "Test yougame programm",0

.code
start:
    sub rsp, 28h

    ;// подготовка аргументов для стека
    lea rcx, [str1]
    lea rdx, [str2]
    mov r8, 16      ;// сравниваем 16 байт
    call memcmp
 
    test eax, eax
    jnz .diff
    invoke MessageBoxA, 0, "yes!", "Result", 0
    jmp .exit
.diff:
    invoke MessageBoxA, 0, "not!", "Result", 0

.exit:
    invoke ExitProcess, 0
 
memcmp:
    xor rax, rax             ;// обнуляем результат заранее
    test r8, r8              ;// проверяем длину (r8): если 0, делать нечего
    jz .done
 
.loop16:
    cmp r8, 16               ;// проверяем, осталось ли в буфере хотя бы 16 байт
    jl .scalar_tail          ;// если меньше 16 — уходим на медленный, но безопасный добор
 
    movdqu xmm0, [rcx]       ;// загружаем 16 байт из первого источника (unaligned)
    movdqu xmm1, [rdx]       ;// загружаем 16 байт из второго источника
 
    pcmpeqb xmm0, xmm1       ;// сравниваем байты: если равны, получаем FFh, иначе 00h
    pmovmskb eax, xmm0       ;// собираем маску из 16 бит в обычный регистр EAX
 
    cmp eax, 0xFFFF          ;// проверяем: все ли 16 байт совпали? (FFFFh = все биты 1)
    jne .found               ;// если хотя бы один бит 0 - есть различие
 
    add rcx, 16              ;// прыгаем через 16 байт в первом буфере
    add rdx, 16              ;// прыгаем через 16 байт во втором буфере
    sub r8, 16               ;// вычитаем обработанный блок из общего счетчика
    jnz .loop16              ;// если данные еще есть — крутим цикл дальше
    xor rax, rax             ;// если дошли сюда — блоки полностью идентичны
    ret

.found:
    not ax                   ;// инвертируем маску, чтобы нули стали единицами (ищем место нестыковки)
    bsf ax, ax               ;// сканируем биты: находим индекс самого первого различающегося байта
    movzx rax, ax            ;// расширяем индекс до 64 бит
    add rcx, rax             ;// прыгаем точно к байту-виновнику в первом блоке
    add rdx, rax             ;// прыгаем к нему же во втором блоке
 
    movzx eax, byte[rcx]     ;// берем этот байт
    movzx edx, byte[rdx]     ;// берем байт для сравнения
    sub eax, edx             ;// вычитаем их (стандарт msvcrt: возвращаем разницу)
    ret

.scalar_tail:
    test r8, r8              ;// проверяем, не пуст ли остаток
    jz .done_eq
.s_loop:
    mov al, [rcx]            ;// берем один байт (скалярный режим, опять некая защита как в strlen)
    sub al, [rdx]            ;// вычитаем из него байт второго буфера
    jnz .s_diff              ;// если разница не ноль - блоки разные
    inc rcx                  ;// инкремент адреса (побайтово)
    inc rdx
    dec r8                   ;// уменьшаем счетчик байт
    jnz .s_loop              ;// крутим, пока не кончится "хвост"
.done_eq:
    xor rax, rax             ;// блоки равны
    ret
.s_diff:
    movsx rax, al            ;// возвращаем разницу с учетом знака
.done:
    ret

.idata
 library kernel32, 'kernel32.dll',\
          user32, 'user32.dll'

 import kernel32, ExitProcess, 'ExitProcess'
 import user32, MessageBoxA, 'MessageBoxA'

Смотрим на результат:

Этот код похож тем, что тут тоже есть некая защита в виде скалярного прохода. Это критически важный момент для любого рефакторинга функций
Именно поэтому в нашей реализации memcmp есть четкое разделение труда. Пока счетчик байтов в r8 больше или равен 16, мы летим на форсаже через SSE2. Как только данных остается меньше, управление передается метке .scalar_tail.

Заключение
Простенькое введение, надеюсь будет полезным.
Если будут вопросы - задавайте
Планирую написать 2 часть где мы будем сравнивать компиляторы и смотреть кто лучше оптимизирует, мы - или компилятор.
И ждите новые программки от меня с open-source кодом. Удачи!

 

[artem_gremlin1337]

круто топ жесть мясо