Instrukční sady SIMD a automatické vektorizace prováděné překladačem GCC (3)

25. 3. 2025
Doba čtení: 40 minut

Sdílet

Autor: Depositphotos
Dnes se budeme zabývat vektorizací smyček, v nichž se zpracovávají pole (vektory), což vyžaduje instrukce SSE2 nebo AVX. Důležité bude taktéž zjištění, jak je vektorizován přístup k prvkům pole s volitelným krokem (stride).

Obsah

1. Instrukční sady SIMD a automatické vektorizace prováděné překladačem GCC (3)

2. Vynulování pole s prvky typu byte

3. Vynulování pole s prvky typu double

4. Přičtení konstanty ke všem prvkům pole typu byte

5. Vysvětlení postupu výpočtu

6. Přičtení konstanty ke všem prvkům pole typu double

7. Součet dvou polí stejné délky s prvky typu byte

8. Výsledek překladu s povolenou autovektorizací

9. Zajištění, že předané ukazatele budou ukazovat na odlišná pole

10. Výsledek překladu s povolenou autovektorizací

11. Vyplatí se přistupovat k prvkům polí od nejnižšího nebo nejvyššího indexu?

12. Vynulování prvků pole od posledního prvku směrem k prvku prvnímu

13. Součet prvků dvou polí: varianta s obecnými ukazateli

14. Součet prvků polí: varianta s nepřekrývajícími se ukazateli

15. Přístup k prvkům polí s krokem rozdílným od jedné (stride)

16. Překlad funkcí pro přístup k jedné barvové složce všech pixelů do assembleru

17. Zápis jedné barvové složky do všech pixelů

18. Repositář s demonstračními příklady

19. Seznam všech předchozích částí tohoto seriálu a článků o SIMD instrukcích

20. Odkazy na Internetu

1. Instrukční sady SIMD a automatické vektorizace prováděné překladačem GCC (3)

Na úvodní dvojici článků o instrukčních sadách SIMD a automatické vektorizaci kódu prováděné překladačem GCC [1], [2] dnes navážeme. Zabývat se totiž budeme vektorizací programových smyček, v nichž se zpracovávají pole (vektory) s prvky, jejichž typy jsou odlišné od FP typu single. To vlastně znamená, že namísto instrukční sady SSE bude nutné, aby překladač vygeneroval instrukce ze sady SSE2 atd. Ovšem to je pouhé rozšíření schopností, o nichž jsme se již zmiňovali.

Zajímavé je, že dnešní verze překladače GCC dokážou vektorizovat i složitější programové konstrukce, například přístup k polím s přeskakováním prvků (stride). V praxi se totiž poměrně často setkáme s tím, že se z pole čte (nebo do něj zapisuje) každý druhý, třetí, resp. obecně n-tý prvek. A i takové varianty programových smyček je nutné optimalizovat. Zmínit se musíme ještě o jedné vlastnosti automatických vektorizací kódu – zpracování programových smyček, ve kterých se k prvkům pole přistupuje sice sekvenčně, ale nikoli od prvku prvního, ale naopak od prvku posledního (což je obecně špatný přístup). Uvidíme zda a jakým způsobem vektorizace dopadne v těchto případech.

2. Vynulování pole s prvky typu byte

Dnešní první funkcí, kterou si necháme přeložit z jazyka C do strojového kódu (resp. do assembleru pro lepší čitelnost), bude funkce, která vynuluje všechny prvky z pole obsahujícího 32 bajtů. Překlad budeme provádět s povolením instrukčních sad SSEx (nejenom SSE1) pro platformu x86–64:

void clear(unsigned char *a) {
    #define SIZE 32
    int i;
    for (i=0; i<SIZE; i++) {
        a[i] = 0;
    }
}

Překladač v tomto případě nebude tvořit programovou smyčku, ale pouze vynuluje obsah registru XMM0 a zapíše tento registr na začátek pole a taktéž na adresu posunutou o offset 16. Toto řešení je plně funkční, protože do jednoho XMM registru lze uložit šestnáct bajtů:

clear:
        pxor    xmm0, xmm0
        movups  XMMWORD PTR [rdi], xmm0
        movups  XMMWORD PTR [rdi+16], xmm0
        ret

Zkusme zjistit, kde je limit proto, aby překladač skutečně použil programovou smyčku. Nulované pole zvětšíme na 64 bajtů:

clear:
        pxor    xmm0, xmm0
        movups  XMMWORD PTR [rdi], xmm0
        movups  XMMWORD PTR [rdi+16], xmm0
        movups  XMMWORD PTR [rdi+32], xmm0
        movups  XMMWORD PTR [rdi+48], xmm0
        ret

K vytvoření smyčky stále nedošlo, takže pole rozšíříme na 128 bajtů s tímto výsledkem:

clear:
        mov     QWORD PTR [rdi], 0
        mov     rax, rdi
        lea     rdi, [rdi+8]
        mov     QWORD PTR [rdi+112], 0
        and     rdi, -8
        sub     rax, rdi
        lea     ecx, [rax+128]
        xor     eax, eax
        shr     ecx, 3
        rep     stosq
        ret

Nyní je situace zajímavá, protože překladač „vzdal“ snahu o použití instrukcí SSE a namísto toho zapisuje 16 bajtů opakující se instrukcí STOSQ s konstantou nula (REP STOSQ). Zápise je proveden na adresu uchovanou v registru RDI (ta se postupně zvyšuje).

3. Vynulování pole s prvky typu double

Ve druhém demonstračním příkladu vynulujeme pole obsahující prvky typu double. Opět začneme malým polem (vektorem), které obsahuje pouze osm prvků:

void clear(double *a) {
    #define SIZE 8
    int i;
    for (i=0; i<SIZE; i++) {
        a[i] = 0.0;
    }
}

Výsledek překladu do assembleru s povolenou vektorizací opět využívá rozbalené smyčky – do paměti se uloží vynulovaný vektor XMM0, a to celkem čtyřikrát, protože každý zápis vynuluje v poli dva prvky:

clear:
        pxor    xmm0, xmm0
        movups  XMMWORD PTR [rdi], xmm0
        movups  XMMWORD PTR [rdi+16], xmm0
        movups  XMMWORD PTR [rdi+32], xmm0
        movups  XMMWORD PTR [rdi+48], xmm0
        ret

Zajímavé je, že při zvětšení pole na 16 prvků typu double překladač namísto SSE instrukcí opět použije pouze celočíselné registry a pro vynulování prvků opakuje instrukci STOSQ:

clear:
        mov     QWORD PTR [rdi], 0
        mov     rax, rdi
        lea     rdi, [rdi+8]
        mov     QWORD PTR [rdi+112], 0
        and     rdi, -8 # tmp105,
        sub     rax, rdi
        lea     ecx, [rax+128]
        xor     eax, eax
        shr     ecx, 3
        rep     stosq
        ret

4. Přičtení konstanty ke všem prvkům pole typu byte

Ve třetím demonstračním příkladu budeme realizovat přičtení konstanty ke všem prvkům pole typu byte. Opět nejdříve začneme krátkým polem s pouhými šestnácti prvky:

void add_delta(unsigned char *a, unsigned char delta) {
    #define SIZE 16
    int i;
    for (i=0; i<SIZE; i++) {
        a[i] += delta;
    }
}

Způsob překladu je zajímavý, protože se zde využívá kombinace instrukcí pro proložení prvků vektorů s přesunem prvků. Musíme totiž dosáhnout stavu, kdy bude vektor obsahovat 16 stejných konstant. Posléze je již možné použít jedinou instrukci PADDB realizující vektorový součet:

add_delta:
        movd       xmm0, esi
        movdqu     xmm1, XMMWORD PTR [rdi]
        punpcklbw  xmm0, xmm0
        punpcklwd  xmm0, xmm0
        pshufd     xmm0, xmm0, 0
        paddb      xmm0, xmm1
        movups     XMMWORD PTR [rdi], xmm0
        ret
Poznámka: v navazující kapitole bude ukázáno, proč se použila právě tato sekvence instrukcí a jak se výpočet provádí krok za krokem.

Po zvětšení pole na 32 prvků (bajtů) bude výsledek vypadat takto:

add_delta:
        movd       xmm0, esi
        movdqu     xmm1, XMMWORD PTR [rdi]
        movdqu     xmm2, XMMWORD PTR [rdi+16]
        punpcklbw  xmm0, xmm0
        punpcklwd  xmm0, xmm0
        pshufd     xmm0, xmm0, 0
        paddb      xmm1, xmm0
        paddb      xmm0, xmm2
        movups     XMMWORD PTR [rdi], xmm1
        movups     XMMWORD PTR [rdi+16], xmm0
        ret

Cílem je stále snaha o „rozšíření“ konstanty do všech prvků registru XMM0 tak, aby bylo možné provést vektorový součet.

Po zvětšení pole na 64 prvků (bajtů) již překladač donutíme k vygenerování nerozbalené programové smyčky:

add_delta:
        movd       xmm1, esi
        lea        rax, [rdi+64]
        punpcklbw  xmm1, xmm1
        punpcklwd  xmm1, xmm1
        pshufd     xmm1, xmm1, 0
.L2:
        movdqu     xmm0, XMMWORD PTR [rdi]
        add        rdi, 16
        paddb      xmm0, xmm1
        movups     XMMWORD PTR [rdi-16], xmm0
        cmp        rax, rdi
        jne        .L2
        ret

5. Vysvětlení postupu výpočtu

Předchozí programy přeložené do assembleru obsahovaly zajímavou sekvenci instrukcí, která vede k tomu, že se původně jedna jednobajtová konstanta rozkopíruje celkem 16× do celého vektoru, což ve výsledku umožní provést vektorový součet instrukcí PADDB. Jedná se o zajímavou techniku, kterou si vysvětlíme po jednotlivých instrukcích.

Nejprve do registru XMM1 načteme vektor s hodnotami od 0 do 15 (což se dobře vizualizuje):

0F 0E 0D 0C 0B 0A 09 08 07 06 05 04 03 02 01 00

Následně dvojicí instrukcí zajistíme zápis konstanty do nejnižšího bitu registru XMM0:

        mov esi, 1                   ; konstanta, kterou budeme pricitat
        movd xmm0, esi               ; nacteni konstanty do druheho vektoru

Výsledek bude vypadat takto:

00 00 00 00 00 00 00 00 00 00 00 00 00 00 00 01

V dalších krocích musíme onen jediný bajt na konci registru XMM0 rozkopírovat do všech ostatních patnácti bajtů. Instrukce PUNPCKLBW provede první krok – zkopírování do druhého prvku (ve skutečnosti se překopírují všechny sudé prvky, ovšem ty jsou nulové a nezajímaí nás):

00 00 00 00 00 00 00 00 00 00 00 00 00 00 01 01

Nyní tedy registr XMM0 obsahuje ve spodních dvou bajtech totožnou konstantu. Instrukcí PUNPCKLWD (ta pracuje po slovech, nikoli po bajtech) provedeme kopii nejnižších dvou prvků do prvků s indexy 2 a 3 (indexuje se od nuly). Opět platí, že podobná operace proběhne i pro vyšší prvky, ale ty nás nezajímají:

00 00 00 00 00 00 00 00 00 00 00 00 01 01 01 01

Již se blížíme ke konci, protože nyní spodní dvojslovo obsahuje konstantu, kterou musíme rozkopírovat do dalších třech dvojslov. A to lze provést jedinou instrukcí PSHUFD. Ta je sice určena pro hodnoty typu float/single, ovšem jedná se o pouhé kopie bez dalších FP manipulací. Výsledkem bude vektor:

01 01 01 01 01 01 01 01 01 01 01 01 01 01 01 01

Nyní nám již zbývá provést instrukci PADDB, která paralelně sečte všech šestnáct dvojic prvků a výsledkem bude vektor:

10 0F 0E 0D 0C 0B 0A 09 08 07 06 05 04 03 02 01

Úplný program (přeložitelný pro Linux), který provede součet a zobrazí přitom všechny mezivýsledky, vypadá takto:

[bits 32]
 
%include "linux_macros.asm"
 
;-----------------------------------------------------------------------------
section .data
 
hex_message:
         times 8 db '?'
         db ' '
         hex_message_length equ $ - hex_message
 
align 16
sse_val_1 db 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15
 
;-----------------------------------------------------------------------------
section .bss
sse_tmp resb 16
 
 
;-----------------------------------------------------------------------------
section .text
        global _start                ; tento symbol ma byt dostupny i linkeru
 
_start:
        mov ebx, sse_val_1
        movdqu xmm1, [ebx]           ; nacteni puvodniho vektoru do registru XMM0
        print_sse_reg_as_hex xmm1    ; tisk hodnoty registru XMM0
 
        mov esi, 1                   ; konstanta, kterou budeme pricitat
        movd xmm0, esi               ; nacteni konstanty do druheho vektoru
        print_sse_reg_as_hex xmm0    ; tisk hodnoty registru XMM0
 
        punpcklbw xmm0, xmm0         ; prolozeni hodnot, zdrojem je jediny registr
        print_sse_reg_as_hex xmm0    ; tisk hodnoty registru XMM0
 
        punpcklwd xmm0, xmm0         ; prolozeni hodnot, zdrojem je jediny registr
        print_sse_reg_as_hex xmm0    ; tisk hodnoty registru XMM0
 
        pshufd xmm0, xmm0, 0         ; rozkopirovani spodnich osmi bajtu do celeho vektoru
        print_sse_reg_as_hex xmm0    ; tisk hodnoty registru XMM0
 
        paddb xmm0, xmm1             ; vektorovy soucet
        print_sse_reg_as_hex xmm0    ; tisk hodnoty registru XMM0
 
        exit                         ; ukonceni procesu
 
 
%include "hex2string.asm"

6. Přičtení konstanty ke všem prvkům pole typu double

Pro úplnost si ještě ukažme, jakým způsobem se přeloží funkce, která bude přičítat konstantu ke všem prvkům pole typu double. Kvůli použití tohoto datového typu opět překladač „donutíme“ k tomu, aby používal instrukce z instrukční sady SSE2 a nikoli z původní sady SSE. Nejprve provedeme operaci přičtení konstanty ke všem prvkům pole o délce 4 prvky:

void add_delta(double *a, double delta) {
    #define SIZE 4
    int i;
    for (i=0; i<SIZE; i++) {
        a[i] += delta;
    }
}

Při pohledu na přeložený kód je zřejmé, že se nejdříve instrukcí UNPCKLPD (oba operandy jsou stejné) provede kopie spodního prvku dvouprvkového vektoru do horního prvku. Po provedení této instrukce tedy budou v registru XMM0 uloženy dvě stejné hodnoty typu double. V dalších krocích je již možné provést vektorový součet instrukcí ADDPD – každá instrukce sečte vždy dvojice prvků z prvního a druhého pole:

add_delta:
        movupd     xmm1, XMMWORD PTR [rdi]
        movupd     xmm2, XMMWORD PTR [rdi+16]
        unpcklpd   xmm0, xmm0
        addpd      xmm1, xmm0
        addpd      xmm0, xmm2
        movups     XMMWORD PTR [rdi], xmm1
        movups     XMMWORD PTR [rdi+16], xmm0
        ret

Zkusme si nyní zvětšit obě pole na délku osmi prvků, abychom zjistili, od jaké meze se překladač uchýlí k vygenerování programové smyčky:

void add_delta(double *a, double delta) {
    #define SIZE 8
    int i;
    for (i=0; i<SIZE; i++) {
        a[i] += delta;
    }
}

Nyní je z výsledného kódu patrné, že se skutečně vygenerovala programová smyčka, která v každé iteraci sečte dvojici hodnot typu double. Konstanta (resp. dvojice konstant) pro přičtení je pochopitelně vypočtena ještě před vstupem do smyčky:

add_delta:
        unpcklpd   xmm0, xmm0
        lea        rax, [rdi+64]
.L2:
        movupd     xmm1, XMMWORD PTR [rdi]
        add        rdi, 16
        addpd      xmm1, xmm0
        movups     XMMWORD PTR [rdi-16], xmm1
        cmp        rax, rdi
        jne        .L2
        ret

7. Součet dvou polí stejné délky s prvky typu byte

V dalším příkladu se pokusíme o provedení součtu prvků dvou polí stejné délky. Pole (resp. přesněji řečeno jejich prvky) budou typu byte, takže překladač pravděpodobně použije rozšířené operace MMX – tedy operace, které již existovaly v instrukční sadě MMX, ale díky SSE/SSE2 je je možné použít i pro vektory obsahující šestnáct hodnot a nikoli pouze osm hodnot.

Součet dvou polí, z nichž každé obsahuje šestnáct prvků typu byte:

void add_arrays(unsigned char *a, unsigned char *b) {
    #define SIZE 16
    int i;
    for (i=0; i<SIZE; i++) {
        a[i] += b[i];
    }
}

Součet dvou polí, z nichž každé obsahuje 32 prvků typu byte:

void add_arrays(unsigned char *a, unsigned char *b) {
    #define SIZE 32
    int i;
    for (i=0; i<SIZE; i++) {
        a[i] += b[i];
    }
}
Poznámka: povšimněte si, že se jedná o jednoduché programové smyčky, ve kterých se žádným způsobem nepokoušíme o nějaké optimalizace.

8. Výsledek překladu s povolenou autovektorizací

Vzhledem k tomu, že součet dvou vektorů se šestnácti prvky typu byte je možné realizovat jedinou instrukcí PADDB, by se mohlo zdát, že se předchozí funkce přeloží do několika instrukcí: načtení vektorů, vektorový součet, uložení výsledku. Ve skutečnosti to není tak jednoduché, protože překladač musí počítat s tím, že se obě pole mohou překrývat. A právě tato větev je realizována ve smyčce začínající lokálním návěštím (label) .L4:

add_arrays:
        lea     rdx, [rsi+1]
        mov     rax, rdi
        sub     rax, rdx
        cmp     rax, 14
        jbe     .L4
        movdqu  xmm0, XMMWORD PTR [rsi]
        movdqu  xmm1, XMMWORD PTR [rdi]
        paddb   xmm0, xmm1
        movups  XMMWORD PTR [rdi], xmm0
        ret
 
.L4:
        xor     eax, eax
.L2:
        movzx   edx, BYTE PTR [rsi+rax]
        add     BYTE PTR [rdi+rax], dl
        add     rax, 1
        cmp     rax, 16
        jne     .L2
        ret

Podobně je tomu i u funkce, která má sečíst 32prvková pole s prvky typu byte:

add_arrays:
        lea     rdx, [rsi+1]
        mov     rax, rdi
        sub     rax, rdx
        cmp     rax, 14
        jbe     .L4
        movdqu  xmm1, XMMWORD PTR [rsi]
        movdqu  xmm0, XMMWORD PTR [rdi]
        movdqu  xmm2, XMMWORD PTR [rdi+16]
        paddb   xmm0, xmm1
        movups  XMMWORD PTR [rdi], xmm0
        movdqu  xmm0, XMMWORD PTR [rsi+16]
        paddb   xmm0, xmm2
        movups  XMMWORD PTR [rdi+16], xmm0
        ret
.L4:
        xor     eax, eax
.L2:
        movzx   edx, BYTE PTR [rsi+rax]
        add     BYTE PTR [rdi+rax], dl
        add     rax, 1
        cmp     rax, 32
        jne     .L2
        ret
Poznámka: proč tomu tak je zjistíte snadno, pokud tyto funkce zavoláte tak, že jim předáte ukazatel na nějaké pole a ukazatel o jedničku vyšší.

9. Zajištění, že předané ukazatele budou ukazovat na odlišná pole

Jakým způsobem lze eliminovat přidané programové smyčky, již víme – musíme překladači jazyka C oznámit, že se pole nebudou překrývat. To se provede klíčovým slovem restrict, které je sice poněkud neznámé, ale o to důležitější:

void add_arrays(unsigned char *restrict a, unsigned char *restrict b) {
    #define SIZE 16
    int i;
    for (i=0; i<SIZE; i++) {
        a[i] += b[i];
    }
}
void add_arrays(unsigned char *restrict a, unsigned char *restrict b) {
    #define SIZE 32
    int i;
    for (i=0; i<SIZE; i++) {
        a[i] += b[i];
    }
}

10. Výsledek překladu s povolenou autovektorizací

Opět se podívejme na to, jak dopadne překlad s autovektorizací obou funkcí, jejichž zdrojové kódy byly ukázány v předchozí kapitole. Překladač má nyní jistotu, že oba ukazatele předávané do funkcí budou odlišné a bude tedy moci ve vygenerovaném kódu odstranit podmínky a větev určenou právě pro tyto případy. I z tohoto důvodu se součet šestnácti prvků typu byte provede jedinou instrukcí PADDB:

add_arrays:
        movdqu  xmm1, XMMWORD PTR [rdi]
        movdqu  xmm0, XMMWORD PTR [rsi]
        paddb   xmm0, xmm1
        movups  XMMWORD PTR [rdi], xmm0
        ret

A varianta sčítající 32 prvků typu byte je stále realizována bez (obecně pomalé) programové smyčky, protože výpočet byl rozbalen. Pokud pomineme přesuny operandů mezi pamětí a registry, bude celý součet realizován dvojicí funkcí PADDB:

add_arrays:
        movdqu  xmm0, XMMWORD PTR [rdi]
        movdqu  xmm1, XMMWORD PTR [rsi]
        movdqu  xmm2, XMMWORD PTR [rdi+16]
        paddb   xmm0, xmm1
        movups  XMMWORD PTR [rdi], xmm0
        movdqu  xmm0, XMMWORD PTR [rsi+16]
        paddb   xmm0, xmm2
        movups  XMMWORD PTR [rdi+16], xmm0
        ret
Poznámka: to ovšem neznamená, že by předchozí kód vytvořený překladačem byl ideální a že ho nelze dále urychlit. Překladač totiž neví, jak jsou pole zarovnána a proto musí vygenerovat instrukce MOVDQU a MOVUPS. Pokud by ovšem věděl, že pole jsou zarovnána na násobky šestnácti bajtů, bude moci využít instrukce MOVDQA a MOVAPS, které mohou být mnohem rychlejší (jediný přenos po sběrnici).

11. Vyplatí se přistupovat k prvkům polí od nejnižšího nebo nejvyššího indexu?

Většina programových smyček, které ve zdrojových kódech popisují nějaký pravidelný průchod polem, zpracovává pole od prvního prvku (s indexem 0) až k prvku poslednímu. Ovšem někdy se můžeme setkat i s opačným průchodem polem. Ten je realizován buď z toho důvodu, že to dobře odpovídá řešenému problému (nalezení posledního prvku odpovídajícího nějaké podmínce atd.) nebo si vývojář zvolil druhý typ smyčky na základě předpokladu, že je vlastně jedno, zda se polem prochází směrem dopředu nebo zezadu. V praxi se ovšem oba přístupy liší a mají vliv na výkon celé aplikace. V první řadě se liší způsob využití vyrovnávacích pamětí a taktéž (před)načtení jednotlivých stránek paměti v případě, že se využívá stránkování (paging). To je sice zajímavá problematika, ale vybočuje z tématu dnešního článku.

Nás dnes bude primárně zajímat to, zda a jak dokáže autovektorizační technika přeložit a optimalizovat zdrojové kódy, v nichž se prochází polem opačným směrem.

12. Vynulování prvků pole od posledního prvku směrem k prvku prvnímu

Začneme jednoduchým příkladem – vynulováním prvků pole v opačném pořadí:

void clear(float *a) {
    #define SIZE 8
    int i;
    for (i=SIZE-1; i>=0; i--) {
        a[i] = 0.0;
    }
}

Překlad do assembleru dopadne následovně:

clear:
        pxor    xmm0, xmm0
        movups  XMMWORD PTR [rdi], xmm0
        movups  XMMWORD PTR [rdi+16], xmm0
        ret

V tomto případě je tedy zcela jedno, jak je smyčka napsána; navíc se v assembleru prvky nulují v pořadí od prvního směrem k poslednímu prvku.

13. Součet prvků dvou polí: varianta s obecnými ukazateli

Další programový kód provádí součet odpovídajících si prvků dvou polí. Tato varianta prozatím používá obecné ukazatele, což překladači neumožní provést všechny možné optimalizace:

void add_delta(float *a, float *b) {
    #define SIZE 16
    int i;
    for (i=SIZE-1; i>=0; i--) {
        a[i] += b[i];
    }
}

Výsledek:

add_delta:
        mov     rax, rdi
        sub     rax, rsi
        add     rax, 12
        cmp     rax, 8
        jbe     .L5
        mov     eax, 48
.L3:
        movups  xmm0, XMMWORD PTR [rdi+rax]
        movups  xmm1, XMMWORD PTR [rsi+rax]
        shufps  xmm0, xmm0, 27
        shufps  xmm1, xmm1, 27
        addps   xmm0, xmm1
        shufps  xmm0, xmm0, 27
        movups  XMMWORD PTR [rdi+rax], xmm0
        sub     rax, 16
        cmp     rax, -16
        jne     .L3
        ret
.L5:
        mov     eax, 60
.L2:
        movss   xmm0, DWORD PTR [rdi+rax]
        addss   xmm0, DWORD PTR [rsi+rax]
        movss   DWORD PTR [rdi+rax], xmm0
        sub     rax, 4
        cmp     rax, -4
        jne     .L2
        ret

Povšimněte si, že jsou vlastně realizovány dvě větve. První z nich je vektorizovaná a prochází polem opačným směrem:

.L3:
        movups  xmm0, XMMWORD PTR [rdi+rax]
        movups  xmm1, XMMWORD PTR [rsi+rax]
        shufps  xmm0, xmm0, 27
        shufps  xmm1, xmm1, 27
        addps   xmm0, xmm1
        shufps  xmm0, xmm0, 27
        movups  XMMWORD PTR [rdi+rax], xmm0
        sub     rax, 16
        cmp     rax, -16
        jne     .L3

Druhá větev vektorizovaná není a realizuje se v ní výpočet pro překryv polí. Ovšem i zde se polem prochází opačným směrem:

.L2:
        movss   xmm0, DWORD PTR [rdi+rax]
        addss   xmm0, DWORD PTR [rsi+rax]
        movss   DWORD PTR [rdi+rax], xmm0
        sub     rax, 4
        cmp     rax, -4
        jne     .L2
        ret
Poznámka: při porovnání s původní verzí smyčky vlastně nedošlo k větším změnám a pokud nebudeme uvažovat horší využití cache či stránek, budou i výsledné doby běhu podobné.

14. Součet prvků polí: varianta s nepřekrývajícími se ukazateli

Zajímavější bude zjistit způsob překladu funkce, v níž je pomocí klíčového slova restrict umožněno překladači provádět další optimalizace – ignorovat možnost překryvu:

void add_arrays(float *restrict a, float *restrict b) {
    #define SIZE 16
    int i;
    for (i=SIZE-1; i>=0; i--) {
        a[i] += b[i];
    }
}

Z přeloženého kódu je patrné, že i nyní se polem skutečně prochází směrem od posledního prvku směrem k prvku prvnímu:

add_arrays:
        mov     eax, 48
.L2:
        movups  xmm0, XMMWORD PTR [rdi+rax]
        movups  xmm1, XMMWORD PTR [rsi+rax]
        shufps  xmm0, xmm0, 27
        shufps  xmm1, xmm1, 27
        addps   xmm0, xmm1
        shufps  xmm0, xmm0, 27
        movups  XMMWORD PTR [rdi+rax], xmm0
        sub     rax, 16
        cmp     rax, -16
        jne     .L2
        ret
Poznámka: zajímavá je už samotná existence programové smyčky v assembleru. Varianta procházející polem od prvního prvku totiž byla přeložena odlišně – bez přeskládání prvků pomocí SHUFPS. Předchozí výsledek tedy bude pomalejší:
add_arrays:
        xor     eax, eax
.L2:
        movups  xmm0, XMMWORD PTR [rdi+rax]
        movups  xmm1, XMMWORD PTR [rsi+rax]
        addps   xmm0, xmm1
        movups  XMMWORD PTR [rdi+rax], xmm0
        add     rax, 16
        cmp     rax, 64
        jne     .L2
        ret

15. Přístup k prvkům polí s krokem rozdílným od jedné (stride)

Poměrně často se v reálných aplikacích sice zpracovávají prvky nějakého pole, ovšem jedná se o každý n-tý prvek, přičemž hodnota n (krok) je v tomto případě větší než 1. Typickým příkladem takového problému je práce s rastrovými obrázky, v nichž je každý pixel uložen formou tří barvových složek RGB a každá tato složka má jeden bajt. Dalším příkladem je zpracování audio signálu se šestnáctibitovými vzorky uloženými tak, že každý lichý vzorek patří pravému kanálu a každý lichý vzorek kanálu levému (nebo naopak – na principu se však nic nemění). A našly by se i další podobné příklady.

Překladač by tedy měl nějakým způsobem umět optimalizovat i tyto algoritmy. Mimochodem – krok n, který jsme zmiňovali v předchozím odstavci (byl nastaven na hodnotu 4 pro bitmapy a na hodnotu 2 pro audio signál) se nazývá stride a i příslušná autovektorizace se jmenuje stride access autovectorization.

Povídejme se na jednoduchý příklad. Je v něm definována trojice funkcí, z nichž každá získá z pole o velikosti SIZE obsahujícího barvy pixelů ve formátu RGB vždy jen jedinou barvovou složku. Celý kód jsem pro jednoduchost rozepsal do tří funkcí, i když by bylo možné napsat jen jedinou funkci, která by navíc akceptovala offset 0, 1 nebo 2 a namísto funkcí by se použila makra (mimochodem – SIZE je nedělitelné třemi – sami si vyzkoušejte variantu se SIZE = 15; bude se výsledek lišit?). Ovšem pro větší čitelnost výsledného assembleru použijeme definice tří samostatných funkcí, které se od sebe odlišují pouze konstantou použitou při výpočtu indexů do pole rgb:

void get_red_component(float *restrict red, float *restrict rgb) {
    #define SIZE 16
    int i;
    for (i=0; i<SIZE/3; i++) {
        red[i] = rgb[3*i];
    }
}
 
void get_green_component(float *restrict green, float *restrict rgb) {
    #define SIZE 16
    int i;
    for (i=0; i<SIZE/3; i++) {
        green[i] = rgb[3*i+1];
    }
}
 
void get_blue_component(float *restrict blue, float *restrict rgb) {
    #define SIZE 16
    int i;
    for (i=0; i<SIZE/3; i++) {
        blue[i] = rgb[3*i+2];
    }
}
Poznámka: povšimněte si, že u parametrů všech funkcí je použito klíčové slovo restrict, kterým překladači naznačujeme, že se nebude jednat o stejná pole nebo o překrývající se pole. Překladač tedy bude moci kód optimalizovat – vynechat specifickou větev pro překrývající se pole.

16. Překlad funkcí pro přístup k jedné barvové složce všech pixelů do assembleru

Nyní se podívejme na způsob překladu výše vypsaných funkcí, které získají vždy jednu barvovou složku pro všechny pixely v rastrovém obrázku (který je reprezentován 1D či 2D polem – to již nemusíme řešit). Díky tomu, že jsme barvové složky reprezentovali hodnotami typu float (což má svůj význam), bylo možné, aby překladač použit instrukci SHUFPS z instrukční sady SSE. Překladač tak pro naše krátké vstupní pole obešel nutnost vygenerovat programovou smyčku, pouze musel zajistit získání každého třetího prvku z pole instrukcí SHUFPS, což je, jak již víme, pravděpodobně nejsložitější a současně i velmi užitečná instrukce SSE:

get_red_component:
        movups  xmm0, XMMWORD PTR [rsi]
        movups  xmm1, XMMWORD PTR [rsi+16]
        shufps  xmm1, xmm0, 10
        shufps  xmm0, xmm1, 140
        movq    xmm1, QWORD PTR [rsi+32]
        shufps  xmm1, xmm0, 165
        shufps  xmm0, xmm1, 36
        movups  XMMWORD PTR [rdi], xmm0
        movss   xmm0, DWORD PTR [rsi+48]
        movss   DWORD PTR [rdi+16], xmm0
        ret

U funkce pro získání zelených barvových složek se jen posunul offset o hodnotu 4 (u všech adres). 4 bajty odpovídají šířce hodnoty typu float v bajtech:

get_green_component:
        movups  xmm0, XMMWORD PTR [rsi+4]
        movups  xmm1, XMMWORD PTR [rsi+20]
        shufps  xmm1, xmm0, 10
        shufps  xmm0, xmm1, 140
        movq    xmm1, QWORD PTR [rsi+36]
        shufps  xmm1, xmm0, 165
        shufps  xmm0, xmm1, 36
        movups  XMMWORD PTR [rdi], xmm0
        movss   xmm0, DWORD PTR [rsi+52]
        movss   DWORD PTR [rdi+16], xmm0
        ret

Totéž platí u funkce pro získání modrých barvových složek, pouze s tím rozdílem, že se pracuje s offset 8 (tedy dvě hodnoty typu float):

get_blue_component:
        movups  xmm0, XMMWORD PTR [rsi+8]
        movups  xmm1, XMMWORD PTR [rsi+24]
        shufps  xmm1, xmm0, 10
        shufps  xmm0, xmm1, 140
        movq    xmm1, QWORD PTR [rsi+40]
        shufps  xmm1, xmm0, 165
        shufps  xmm0, xmm1, 36
        movups  XMMWORD PTR [rdi], xmm0
        movss   xmm0, DWORD PTR [rsi+56]
        movss   DWORD PTR [rdi+16], xmm0
        ret
Poznámka: příště si ukážeme skutečnou vektorizaci podobného kódu u delších polí/vektorů.

17. Zápis jedné barvové složky do všech pixelů

Nyní zkusme namísto funkcí určených pro čtení jedné zvolené barvové složky všech pixelů naprogramovat funkce, které provádí zápis (modifikaci) jedné vybrané barvové složky u všech pixelů. Vstupem je tedy například sekvence hodnot červené barvové složky, která se má propsat do výsledného rastrového obrázku. Opět jsem pro větší čitelnost všechny tři funkce napsal samostatně:

void set_red_component(float *restrict red, float *restrict rgb) {
    #define SIZE 16
    int i;
    for (i=0; i<SIZE/3; i++) {
        rgb[3*i] = red[i];
    }
}
 
void set_green_component(float *restrict green, float *restrict rgb) {
    #define SIZE 16
    int i;
    for (i=0; i<SIZE/3; i++) {
        rgb[3*i+1] = green[i];
    }
}
 
void set_blue_component(float *restrict blue, float *restrict rgb) {
    #define SIZE 16
    int i;
    for (i=0; i<SIZE/3; i++) {
        rgb[3*i+2] = blue[i];
    }
}

Nyní je realizace zápisu řešena „nevektorizovaně“, tedy triviálním zápisem skalárních hodnot do pole s rastrovým obrázkem:

set_red_component:
        movss   xmm0, DWORD PTR [rdi+12]
        movss   xmm1, DWORD PTR [rdi+8]
        movss   xmm2, DWORD PTR [rdi+4]
        movss   xmm3, DWORD PTR [rdi]
        movss   DWORD PTR [rsi+36], xmm0
        movss   xmm0, DWORD PTR [rdi+16]
        movss   DWORD PTR [rsi], xmm3
        movss   DWORD PTR [rsi+12], xmm2
        movss   DWORD PTR [rsi+24], xmm1
        movss   DWORD PTR [rsi+48], xmm0
        ret

Posun offsetů u zápisu u další barvové složky u poslední trojice instrukcí MOVSS:

set_green_component:
        movss   xmm0, DWORD PTR [rdi+12]
        movss   xmm1, DWORD PTR [rdi+8]
        movss   xmm2, DWORD PTR [rdi+4]
        movss   xmm3, DWORD PTR [rdi]
        movss   DWORD PTR [rsi+40], xmm0
        movss   xmm0, DWORD PTR [rdi+16]
        movss   DWORD PTR [rsi+4], xmm3
        movss   DWORD PTR [rsi+16], xmm2
        movss   DWORD PTR [rsi+28], xmm1
        movss   DWORD PTR [rsi+52], xmm0
        ret

Dtto pro třetí barvovou složku:

docker + kubernetes školení s dotací tip

set_blue_component:
        movss   xmm0, DWORD PTR [rdi+12]
        movss   xmm1, DWORD PTR [rdi+8]
        movss   xmm2, DWORD PTR [rdi+4]
        movss   xmm3, DWORD PTR [rdi]
        movss   DWORD PTR [rsi+44], xmm0
        movss   xmm0, DWORD PTR [rdi+16]
        movss   DWORD PTR [rsi+8], xmm3
        movss   DWORD PTR [rsi+20], xmm2
        movss   DWORD PTR [rsi+32], xmm1
        movss   DWORD PTR [rsi+56], xmm0
        ret

18. Repositář s demonstračními příklady

Demonstrační příklady naprogramované v jazyku, které jsou určené pro překlad s využitím assembleru gcc, byly uloženy do Git repositáře, který je dostupný na adrese https://github.com/tisnik/8bit-fame. Kromě zdrojových kódů příkladů jsou do repositáře přidány i výsledky překladu do assembleru v syntaxi kompatibilní s Intelem. Jednotlivé demonstrační příklady si můžete v případě potřeby stáhnout i jednotlivě bez nutnosti klonovat celý (dnes již poměrně rozsáhlý) repositář:

# Příklad Stručný popis Adresa
1 array_clear_size8.c smazání obsahu pole s osmi prvky typu float https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear_size8.c
2 array_clear_size8_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear_size8_non_vect.asm
3 array_clear_size8_no_sse.asm výsledek překladu do assembleru se zákazem SSE instrukcí https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear_size8_no_sse.asm
4 array_clear_size8_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear_size8_vect.asm
       
5 array_clear_size16.c smazání obsahu pole se šestnácti prvky typu float https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear_size16.c
6 array_clear_size16_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear_size16_non_vect.asm
7 array_clear_size16_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear_size16_vect.asm
       
8 array_clear_size18.c smazání obsahu pole se sedmnácti prvky typu float https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear_size18.c
9 array_clear_size18_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear_size18_non_vect.asm
10 array_clear_size18_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear_size18_vect.asm
       
11 add_delta_size16.c přičtení konstanty ke všem prvkům pole obsahujícího 16 hodnot typu float https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta_size16.c
12 add_delta_size16_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta_size16_non_vect.asm
13 add_delta_size16_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta_size16_vect.asm
       
14 add_delta_size17.c přičtení konstanty ke všem prvkům pole obsahujícího 17 hodnot typu float https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta_size17.c
15 add_delta_size17_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta_size17_non_vect.asm
16 add_delta_size17_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta_size17_vect.asm
       
17 add_delta_size24.c přičtení konstanty ke všem prvkům pole obsahujícího 24 hodnot typu float https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta_size24.c
18 add_delta_size24_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta_size24_non_vect.asm
19 add_delta_size24_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta_size24_vect.asm
       
20 array_sqrt.c výpočet druhé odmocniny všech prvků polí https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sqrt.c
21 array_sqrt_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sqrt_non_vect.asm
22 array_sqrt_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sqrt_vect.asm
23 array_sqrt_vect_fast_math.asm výsledek překladu do assembleru s povolením vektorizace a nepřesných výpočtů https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sqrt_vect_fast_math.asm
       
24 dot_product4.c skalární součin vektorů, z nichž každý má délku čtyři prvky https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/dot_product4.c
25 dot_product4_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/dot_product4_non_vect.asm
26 dot_product4_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/dot_product4_vect.asm
       
27 dot_product8.c skalární součin vektorů, z nichž každý má délku osmi prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/dot_product8.c
28 dot_product8_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/dot_product8_non_vect.asm
29 dot_product8_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/dot_product8_vect.asm
       
30 dot_product100.c skalární součin vektorů, z nichž každý má délku 100 prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/dot_product100.c
31 dot_product100_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/dot_product100_non_vect.asm
32 dot_product100_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/dot_product100_vect.asm
       
33 add_arrays_size4.c součet prvků dvojice polí typu float, pole mají délku 4 prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_size4.c
34 add_arrays_size4_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_size4_non_vect.asm
35 add_arrays_size4_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_size4_vect.asm
36 add_arrays_size16.c součet prvků dvojice polí typu float, pole mají délku 16 prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_size16.c
37 add_arrays_size16_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_size16_non_vect.asm
38 add_arrays_size16_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_size16_vect.asm
39 add_arrays_size17.c součet prvků dvojice polí typu float, pole mají délku 17 prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_size17.c
40 add_arrays_size17_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_size17_non_vect.asm
41 add_arrays_size17_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_size17_vect.asm
       
42 add_arrays_restrict_size4.c součet prvků polí se čtyřmi prvky, pole se nepřekrývají https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_restrict_size4.c
43 add_arrays_restrict_size4_non_vec­t.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_restrict_si­ze4_non_vect.asm
44 add_arrays_restrict_size4_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_restrict_si­ze4_vect.asm
45 add_arrays_restrict_size16.c součet prvků polí se šestnácti prvky, pole se nepřekrývají https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_restrict_size16.c
46 add_arrays_restrict_size16_non_vec­t.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_restrict_si­ze16_non_vect.asm
47 add_arrays_restrict_size16_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_restrict_si­ze16_vect.asm
48 add_arrays_restrict_size17.c součet prvků polí se sedmnácti prvky, pole se nepřekrývají https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_restrict_size17.c
49 add_arrays_restrict_size17_non_vec­t.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_restrict_si­ze17_non_vect.asm
50 add_arrays_restrict_size17_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_restrict_si­ze17_vect.asm
       
51 array_sum4.c součet všech prvků v poli se čtyřmi prvky https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sum4.c
52 array_sum4_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sum4_non_vect.asm
53 array_sum4_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sum4_vect.asm
54 array_sum8.c součet všech prvků v poli s osmi prvky https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sum8.c
55 array_sum8_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sum8_non_vect.asm
56 array_sum8_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sum8_vect.asm
57 array_sum100.c součet všech prvků polí se 100 prvky https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sum100.c
58 array_sum100_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sum100_non_vect.asm
59 array_sum100_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_sum100_vect.asm
       
60 find_max4.c vyhledání největšího prvku v poli se čtyřmi prvky https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/find_max4.c
61 find_max4_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/find_max4_non_vect.asm
62 find_max4_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/find_max4_vect.asm
63 find_max8.c vyhledání největšího prvku v poli s osmi prvky https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/find_max8.c
64 find_max8_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/find_max8_non_vect.asm
65 find_max8_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/find_max8_vect.asm
66 find_max100.c vyhledání největšího prvku v poli se 100 prvky https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/find_max100.c
67 find_max100_non_vect.asm výsledek překladu do assembleru se zákazem vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/find_max100_non_vect.asm
68 find_max100_vect.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/find_max100_vect.asm
       
69 array_clear32_bytes.c vynulování pole s prvky typu byte o délce 32 prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear32_bytes.c
70 array_clear32_bytes.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear32_bytes.asm
71 array_clear64_bytes.c vynulování pole s prvky typu byte o délce 64 prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear64_bytes.c
72 array_clear64_bytes.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear64_bytes.asm
73 array_clear128_bytes.c vynulování pole s prvky typu byte o délce 128 prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear128_bytes.c
74 array_clear128_bytes.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear128_bytes.asm
       
75 array_clear8_doubles.c vynulování pole s prvky typu double o délce osmi prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear8_doubles.c
76 array_clear8_doubles.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear8_doubles.asm
77 array_clear16_doubles.c vynulování pole s prvky typu double o délce 16 prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear16_doubles.c
78 array_clear16_doubles.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear16_doubles.asm
       
79 add_delta16_bytes.c přičtení konstanty ke všem prvkům pole typu byte o délce 16 prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta16_bytes.c
80 add_delta16_bytes.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta16_bytes.asm
81 add_delta32_bytes.c přičtení konstanty ke všem prvkům pole typu byte o délce 32 prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta32_bytes.c
82 add_delta32_bytes.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta32_bytes.asm
83 add_delta64_bytes.c přičtení konstanty ke všem prvkům pole typu byte o délce 64 prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta64_bytes.c
84 add_delta64_bytes.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta64_bytes.asm
       
85 add_delta4_doubles.c přičtení konstanty ke všem prvkům pole typu double o délce čtyř prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta4_doubles.c
86 add_delta4_doubles.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta4_doubles.asm
87 add_delta8_doubles.c přičtení konstanty ke všem prvkům pole typu double o délce osmi prvků https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta8_doubles.c
88 add_delta8_doubles.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_delta8_doubles.asm
       
89 add_arrays16_bytes.c součet prvků dvou polí se 16 prvky typu byte: varianta s obecnými ukazateli https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays16_bytes.c
90 add_arrays16_bytes.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays16_bytes.asm
91 add_arrays32_bytes.c součet prvků dvou polí s 32 prvky typu byte: varianta s obecnými ukazateli https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays32_bytes.c
92 add_arrays32_bytes.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays32_bytes.asm
93 add_arrays16_bytes_restrict.c součet prvků polí se 16 prvky typu byte: varianta s nepřekrývajícími se ukazateli https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays16_bytes_restrict.c
94 add_arrays16_bytes_restrict.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays16_bytes_restrict.asm
95 add_arrays32_bytes_restrict.c součet prvků polí s 32 prvky typu byte: varianta s nepřekrývajícími se ukazateli https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays32_bytes_restrict.c
96 add_arrays32_bytes_restrict.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays32_bytes_restrict.asm
       
97 array_clear_size8_backward.c součet prvků dvou polí v pořadí od posledního prvku k prvku prvnímu https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear_size8_backward.c
98 array_clear_size8_backward.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/array_clear_size8_backward.asm
99 add_arrays_size16_backward.c součet prvků dvou polí v pořadí od posledního prvku k prvku prvnímu https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_size16_backward.c
100 add_arrays_size16_backward.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_size16_backward.asm
101 add_arrays_restrict_size16_backward.c součet prvků polí: varianta s nepřekrývajícími se ukazateli https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_restrict_si­ze16_backward.c
102 add_arrays_restrict_size16_bac­kward.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/add_arrays_restrict_si­ze16_backward.asm
       
103 get_color_component.c získání jedné barvové složky ze všech pixelů https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/get_color_component.c
104 get_color_component.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/get_color_component.asm
105 set_color_component.c zápis jedné barvové složky do všech pixelů https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/set_color_component.c
106 set_color_component.asm výsledek překladu do assembleru s povolením vektorizace https://github.com/tisnik/8bit-fame/blob/master/gcc-simd/set_color_component.asm

19. Seznam všech předchozích částí tohoto seriálu a článků o SIMD instrukcích

Podporou SIMD instrukcí na úrovni intrinsic jsme se už na Rootu zabývali, stejně jako samotnými SIMD instrukcemi na úrovni assembleru. Pro úplnost jsou v této příloze uvedeny odkazy na příslušné články:

  1. Užitečné rozšíření GCC: podpora SIMD (vektorových) instrukcí
    https://www.root.cz/clanky/uzitecne-rozsireni-gcc-podpora-simd-vektorovych-instrukci/
  2. Užitečné rozšíření GCC – podpora SIMD (vektorových) instrukcí: nedostatky technologie
    https://www.root.cz/clanky/uzitecne-rozsireni-gcc-podpora-simd-vektorovych-instrukci-nedostatky-technologie/
  3. Podpora SIMD (vektorových) instrukcí na RISCových procesorech
    https://www.root.cz/clanky/podpora-simd-vektorovych-instrukci-na-riscovych-procesorech/
  4. Podpora SIMD operací v GCC s využitím intrinsic pro nízkoúrovňové optimalizace
    https://www.root.cz/clanky/podpora-simd-operaci-v-gcc-s-vyuzitim-intrinsic-pro-nizkourovnove-optimalizace/
  5. Podpora SIMD operací v GCC s využitím intrinsic: technologie SSE
    https://www.root.cz/clanky/podpora-simd-operaci-v-gcc-s-vyuzitim-intrinsic-technologie-sse/
  6. Rozšíření instrukční sady „Advanced Vector Extensions“ na platformě x86–64
    https://www.root.cz/clanky/rozsireni-instrukcni-sady-advanced-vector-extensions-na-platforme-x86–64/
  7. Rozšíření instrukční sady F16C, FMA a AVX-512 na platformě x86–64
    https://www.root.cz/clanky/rozsireni-instrukcni-sady-f16c-fma-a-avx-512-na-platforme-x86–64/
  8. Rozšíření instrukční sady AVX-512 na platformě x86–64 (dokončení)
    https://www.root.cz/clanky/rozsireni-instrukcni-sady-avx-512-na-platforme-x86–64-dokonceni/
  9. SIMD instrukce na platformě 80×86: instrukční sada MMX
    https://www.root.cz/clanky/simd-instrukce-na-platforme-80×86-instrukcni-sada-mmx/
  10. SIMD instrukce na 80×86: dokončení popisu MMX, instrukce 3DNow!
    https://www.root.cz/clanky/simd-instrukce-na-80–86-dokonceni-popisu-mmx-instrukce-3dnow/
  11. SIMD instrukce v rozšíření SSE
    https://www.root.cz/clanky/simd-instrukce-v-rozsireni-sse/
  12. SIMD instrukce v rozšíření SSE (2. část)
    https://www.root.cz/clanky/simd-instrukce-v-rozsireni-sse-2-cast/
  13. Pokročilejší SSE operace: přeskupení, promíchání a rozbalování prvků vektorů
    https://www.root.cz/clanky/po­krocilejsi-sse-operace-preskupeni-promichani-a-rozbalovani-prvku-vektoru/
  14. Od instrukční sady SSE k sadě SSE2
    https://www.root.cz/clanky/od-instrukcni-sady-sse-k-sade-sse2/
  15. Instrukční sady SIMD a automatické vektorizace prováděné překladačem GCC
    https://www.root.cz/clanky/instrukcni-sady-simd-a-automaticke-vektorizace-provadene-prekladacem-gcc/
  16. Instrukční sady SIMD a automatické vektorizace prováděné překladačem GCC (2)
    https://www.root.cz/clanky/instrukcni-sady-simd-a-automaticke-vektorizace-provadene-prekladacem-gcc-2/

20. Odkazy na Internetu

  1. Auto-vectorization in GCC
    https://gcc.gnu.org/projects/tree-ssa/vectorization.html
  2. GCC documentation: Extensions to the C Language Family
    https://gcc.gnu.org/onlinedocs/gcc/C-Extensions.html#C-Extensions
  3. GCC documentation: Using Vector Instructions through Built-in Functions
    https://gcc.gnu.org/online­docs/gcc/Vector-Extensions.html
  4. SSE (Streaming SIMD Extentions)
    http://www.songho.ca/misc/sse/sse­.html
  5. Timothy A. Chagnon: SSE and SSE2
    http://www.cs.drexel.edu/~tc365/mpi-wht/sse.pdf
  6. Intel corporation: Extending the Worldr's Most Popular Processor Architecture
    http://download.intel.com/techno­logy/architecture/new-instructions-paper.pdf
  7. SIMD architectures:
    http://arstechnica.com/ol­d/content/2000/03/simd.ar­s/
  8. Tour of the Black Holes of Computing!: Floating Point
    http://www.cs.hmc.edu/~ge­off/classes/hmc.cs105…/sli­des/class02_floats.ppt
  9. 3Dnow! Technology Manual
    AMD Inc., 2000
  10. Intel MMXTM Technology Overview
    Intel corporation, 1996
  11. MultiMedia eXtensions
    http://softpixel.com/~cwrig­ht/programming/simd/mmx.phpi
  12. AMD K5 („K5“ / „5k86“)
    http://www.pcguide.com/ref/cpu/fam/g5K5-c.html
  13. Sixth Generation Processors
    http://www.pcguide.com/ref/cpu/fam/g6­.htm
  14. Great Microprocessors of the Past and Present
    http://www.cpushack.com/CPU/cpu1.html
  15. Very long instruction word (Wikipedia)
    http://en.wikipedia.org/wi­ki/Very_long_instruction_word
  16. CPU design (Wikipedia)
    http://en.wikipedia.org/wi­ki/CPU_design
  17. Bulldozer (microarchitecture)
    https://en.wikipedia.org/wi­ki/Bulldozer_(microarchitec­ture)
  18. SIMD Instructions Considered Harmful
    https://www.sigarch.org/simd-instructions-considered-harmful/
  19. GCC Compiler Intrinsics
    https://iq.opengenus.org/gcc-compiler-intrinsics/
  20. Scalable_Vector_Extension_(SVE)
    https://en.wikipedia.org/wi­ki/AArch64#Scalable_Vector_Ex­tension_(SVE)
  21. Improve the Multimedia User Experience
    https://www.arm.com/technologies/neon
  22. NEON Technology (stránky ARM)
    https://developer.arm.com/techno­logies/neon
  23. SIMD Assembly Tutorial: ARM NEON – Xiph.org
    https://people.xiph.org/~tte­rribe/daala/neon_tutorial­.pdf
  24. Ne10
    http://projectne10.github.io/Ne10/
  25. NEON and Floating-Point architecture
    http://infocenter.arm.com/hel­p/index.jsp?topic=/com.ar­m.doc.den0024a/BABIGHEB.html
  26. An Introduction to ARM NEON
    http://peterdn.com/post/an-introduction-to-ARM-NEON.aspx
  27. ARM NEON Intrinsics Reference
    http://infocenter.arm.com/hel­p/topic/com.arm.doc.ihi0073a/I­HI0073A_arm_neon_intrinsic­s_ref.pdf
  28. Arm Neon Intrinsics vs hand assembly
    https://stackoverflow.com/qu­estions/9828567/arm-neon-intrinsics-vs-hand-assembly
  29. ARM NEON Optimization. An Example
    http://hilbert-space.de/?p=22
  30. AArch64 NEON instruction format
    https://developer.arm.com/doc­s/den0024/latest/7-aarch64-floating-point-and-neon/73-aarch64-neon-instruction-format
  31. ARM SIMD instructions
    https://developer.arm.com/do­cumentation/dht0002/a/Intro­ducing-NEON/What-is-SIMD-/ARM-SIMD-instructions
  32. Learn the architecture – Migrate Neon to SVE Version 1.0
    https://developer.arm.com/do­cumentation/102131/0100/?lan­g=en
  33. 1.2.2. Comparison between NEON technology and other SIMD solutions
    https://developer.arm.com/do­cumentation/den0018/a/Intro­duction/Comparison-between-ARM-NEON-technology-and-other-implementations/Comparison-between-NEON-technology-and-other-SIMD-solutions?lang=en
  34. NEON Programmer’s Guide
    https://documentation-service.arm.com/static/63299276e68c6809a6b4­1308
  35. Brain Floating Point – nový formát uložení čísel pro strojové učení a chytrá čidla
    https://www.root.cz/clanky/brain-floating-point-ndash-novy-format-ulozeni-cisel-pro-strojove-uceni-a-chytra-cidla/
  36. Other Built-in Functions Provided by GCC
    https://gcc.gnu.org/online­docs/gcc/Other-Builtins.html
  37. GCC: 6.60 Built-in Functions Specific to Particular Target Machines
    https://gcc.gnu.org/online­docs/gcc/Target-Builtins.html#Target-Builtins
  38. Advanced Vector Extensions
    https://en.wikipedia.org/wi­ki/Advanced_Vector_Extensi­ons
  39. Top 10 Craziest Assembly Language Instructions
    https://www.youtube.com/wat­ch?v=Wz_xJPN7lAY
  40. Intel x86: let's take a look at one of the most complex instruction set!
    https://www.youtube.com/wat­ch?v=KBLy23B38-c
  41. x64 Assembly Tutorial 58: Intro to AVX
    https://www.youtube.com/wat­ch?v=yAvuHd8cBJY
  42. AVX512 (1 of 3): Introduction and Overview
    https://www.youtube.com/watch?v=D-mM6X5×nTY
  43. AVX512 (2 of 3): Programming AVX512 in 3 Different Ways
    https://www.youtube.com/wat­ch?v=I3efQKLgsjM
  44. AVX512 (3 of 3): Deep Dive into AVX512 Mechanisms
    https://www.youtube.com/watch?v=543a1b-cPmU
  45. AVX-512
    https://en.wikipedia.org/wiki/AVX-512
  46. AVX-512
    https://iq.opengenus.org/avx512/
  47. SIMD Algorithms Youtube course
    https://denisyaroshevskiy­.github.io/presentations/
  48. Compiler explorer
    https://godbolt.org/
  49. Restricting pointers
    https://gcc.gnu.org/online­docs/gcc/Restricted-Pointers.html
  50. Does the restrict keyword provide significant benefits in gcc/g++
    https://stackoverflow.com/qu­estions/1965487/does-the-restrict-keyword-provide-significant-benefits-in-gcc-g
  51. Demystifying The Restrict Keyword
    https://cellperformance.be­yond3d.com/articles/2006/05/de­mystifying-the-restrict-keyword.html
  52. Basics of Vectorization for Fortran Applications
    https://inria.hal.science/hal-01688488/document
  53. What does the restrict keyword mean in C++?
    https://stackoverflow.com/qu­estions/776283/what-does-the-restrict-keyword-mean-in-c
  54. restrict keyword (Wikipedia)
    https://en.wikipedia.org/wi­ki/Restrict
  55. Reduction operator
    https://en.wikipedia.org/wi­ki/Reduction_operator
  56. The Power of the Dot Product in Artificial Intelligence
    https://medium.com/data-science/the-power-of-the-dot-product-in-artificial-intelligence-c002331e1829
  57. Can any one explain why dot product is used in neural network and what is the intitutive thought of dot product
    https://stats.stackexchan­ge.com/questions/291680/can-any-one-explain-why-dot-product-is-used-in-neural-network-and-what-is-the-in
  58. Aligned and unaligned memory accesses?
    https://stackoverflow.com/qu­estions/1063809/aligned-and-unaligned-memory-accesses
Neutrální ikona do widgetu na odběr článků ze seriálů

Zajímá vás toto téma? Chcete se o něm dozvědět víc?

Objednejte si upozornění na nově vydané články do vašeho mailu. Žádný článek vám tak neuteče.


Autor článku

Vystudoval VUT FIT a v současné době pracuje na projektech vytvářených v jazycích Python a Go.