Pohled pod kapotu formátu WebAssembly: SIMD (vektorové) operace

Obsah

1. WebAssembly a vektorové operace

2. Podpora SIMD operací na historických i současných architekturách mikroprocesorů

3. Podpora SIMD operací ve WebAssembly

4. Typ v128

5. Instrukční prefix 0×FD

6. Jakým způsobem lze SIMD využít pro programy psané v jazyku C?

7. Definice vektorů podporované překladači jazyka C

8. Vektory shodné bitové šířky, ovšem obsahující prvky odlišných typů

9. Operace prováděné s celými vektory

10. Překlad funkce pro součet dvou vektorů do WebAssembly

11. Překlad do WebAssembly s explicitním povolením vektorových instrukcí

12. Součet vektorů s dvojnásobným počtem prvků

13. Součet vektorů s celočíselnými prvky různých typů

14. Součet vektorů s prvky s plovoucí řádovou čárkou

15. Všechny instrukce pro součet vektorů

16. Další celočíselné operace prováděné s prvky vektorů

17. Obsah navazujícího článku

18. Tabulka se všemi doposud popsanými instrukcemi

19. Články o SIMD, které doposud na Rootu vyšly

20. Odkazy na Internetu

1. WebAssembly a vektorové operace

Do specifikace WebAssembly byly k základním instrukcím později přidány i další rozšiřující instrukce a dokonce celé sady nových instrukcí. Mezi tyto instrukce patří zejména instrukce umožňující provádět vektorové operace (resp. přesněji řečeno SIMD operace). Překladače LLVM tyto instrukce podporují a navíc pro ně máme přímou podporu i přímo v Clangu (a to dokonce na několika úrovních). A právě s tímto (ve světě videí a umělé inteligence) velmi důležitým rozšířením WebAssembly se budeme zabývat v dnešním článku.

„…sequential computers are approaching a fundamental physical limit on their potential power. Such a limit is the speed of light…“

Budeme se tedy zabývat popisem způsobu implementace operací typu SIMD (Single Instruction, Multiple Data) ve WebAssembly. Jedná se o velmi důležitou technologii protože SIMD neboli (poněkud nepřesně řečeno) vektorové instrukce v současnosti patří ke standardní výbavě prakticky všech variant moderních mikroprocesorů. Připomeňme si, že z hlediska dosahovaného výpočetního výkonu leží na samém „výkonnostním dně“ klasické skalární mikroprocesory s architekturou CISC, které vykonávají všechny instrukce postupně a dokončení jedné instrukce může v závislosti na jejich složitosti trvat i několik desítek strojových taktů.

Předností těchto procesorů (v případě WebAssembly pak virtuálních strojů) může být poměrně velká informační hustota instrukční sady (například i díky tomu, že operandy některých instrukcí jsou zadány implicitně popř. jsou podporovány instrukce proměnné délky), což mj. znamená, že se procesory tohoto typu po poměrně dlouhou dobu obešly bez nutnosti využití drahých vyrovnávacích pamětí první a druhé úrovně (L1 cache, L2 cache). Klasické procesory s architekturou CISC byly založeny na mikroprogramovém řadiči vybaveném pamětí mikroinstrukcí a teprve později začaly být tyto procesory doplňovány technologiemi získanými z jiných architektur – instrukční pipeline, prediktorem skoků, vektorovými instrukcemi (což byly oblasti klasických RISCových architektur) atd. Moderní mikroprocesory se tak od klasických CISC prakticky ve všech technologických detailech odlišují.

Výpočetní výkon mikroprocesorů se podařilo poměrně výrazným způsobem zvýšit u konkurenční architektury RISC zavedením takzvané instrukční pipeline. Provedení jedné instrukce sice stále trvalo větší počet strojových cyklů, ovšem díky rozfázování operací v instrukční pipeline bylo umožněno překrývání většího množství instrukcí, a to bez nutnosti zavádění skutečné paralelizace (která vede k velkému nárůstu složitosti a tím i ceny čipu). Spolu se zavedením mikroprocesorů RISC se skutečně stalo, že reálný i špičkový výpočetní výkon procesorů vzrostl, ale relativně brzy bylo nutné k těmto čipům přidat vyrovnávací paměti (cache), jelikož rychlost procesorů rostla mnohem rychleji, než vybavovací doba pamětí. Tento rozpor mezi rychlostmi obou nejdůležitějších součástí moderních počítačů ostatně trvá dodnes.

Programátoři, co nesnášíte BS, ale máte rádi business! Y Soft je česká firma s globálním dopadem (100+ zemí, 1M+ uživatelů a >100% meziroční růst). R&D úplně bez manažerů (130 developerů). Otevíráme 30 pozic pro Cloud a AI: Praha/Brno/Ostrava/remote. Zodpovědnost ano, mikro-management ne. Pojď někam, kde můžeš věci změnit.

Pro další zvýšení výpočetního výkonu však bylo nutné použít další technologie, například instrukční sadu VLIW (Very Long Instruction Word), která však – opět – měla velké nároky na rychlost pamětí. Podobně jako u procesorů RISC, i u VLIW bylo pro zmírnění požadavků na rychlost pamětí možné použít Harvardskou architekturu, tj. oddělení paměti programu od paměti dat (programová paměť navíc mohla mít větší šířku datové sběrnice odpovídající šířce instrukčních slov). Kombinace VLIW a Harvardské architektury byla používána například u digitálních signálových procesorů (DSP).

Další zvýšení výkonu umožňují právě vektorové instrukce (přesněji SIMD instrukce), které ale mají jeden poměrně zásadní nedostatek – sémantickou mezeru mezi imperativním „skalárním“ kódem psaným například v jazyku C (C++ atd.) a instrukční sadou, která je SIMD (jinými slovy – běžné programovací jazyky neumožňují dostatečně popsat vektorové operace). Totéž ostatně platí i pro WebAssembly, takže si dnes ukážeme, jakým způsobem je tato problematika řešena a jak lze vektorové instrukce ve WebAssembly využít.

2. Podpora SIMD operací na historických i současných architekturách mikroprocesorů

SIMD operace nalezneme v mnoha historických architekturách mikroprocesorů, ale (což je důležitější) i v prakticky všech moderních mikroprocesorech. V této kapitole se o nejvýznamnějších historických i současných technologiích zmíníme.

Nejznámější implementace instrukcí typu SIMD na mikroprocesorech s architekturou RISC, ať již se jedná o instrukce určené pro operace s celými čísly či s čísly reálnými (přesněji řečeno s plovoucí řádovou čárkou), jsou vypsány v následující tabulce:

Zkusme se nyní podívat na seznam různých SIMD (neboli nesprávně řečeno „vektorových“) rozšíření původní instrukční sady x86:

Pro někoho může být taktéž zajímavá i informace o tom, jak velké změny v instrukční sadě mikroprocesorů byly vlastně při přidávání nových „vektorových“ rozšiřujících instrukčních sad typu SIMD provedeny. To nám ukáže další tabulka. Je pouze nutné dát si pozor na to, že počty nových instrukcí zavedených v rámci těchto nových technologií, které jsou vypsány v tabulce pod odstavcem, nemusí přesně souhlasit s počty uváděnými v jiných informačních materiálech. Je tomu tak především z toho důvodu, že se v některých případech rozlišuje i datový typ, s nímž instrukce pracují (například se může jednat o součet vektoru s 32 bitovými hodnotami nebo 64bitovými hodnotami reprezentovanými v obou případech ve formátu s plovoucí řádovou čárkou) a někdy se taková instrukce do celkové sumy započítává pouze jedenkrát. Nicméně údaje vypsané v níže uvedené tabulce by měly být konzistentní, protože se jedná o počty nově přidaných operačních kódů instrukcí (například u dále zmíněné instrukční sady SSE2 končí instrukce znakem D, S, I či Q podle typu zpracovávaných dat/operandů):

3. Podpora SIMD operací ve WebAssembly

Nyní se konečně dostáváme k WebAssembly. Původní instrukční sada WebAssembly byla čistě „skalární“, což znamená, že veškeré operace (výpočty, podmínky pro smyčky a rozvětvení atd.) probíhaly se skalárními hodnotami. Ovšem v době uvádění WebAssembly se na mainstreamových platformách mikroprocesorů začaly poměrně rychlým způsobem rozvíjet instrukční sady se SIMD operacemi. To, společně s tím, že bylo nutné podporovat například přehrávání videí a popř. i celé SW kodeky, vedlo k tomu, že do WebAssembly byla přidána podpora pro operace s vektory hodnot. Tyto vektory mají vždy šířku 128 bitů (minimálně v současné verzi WebAssembly), přičemž těchto 128 bitů může být rozděleno do různých typů prvků. Typicky se pracuje s vektory obsahujícími čtyři hodnoty typu single/float, ale může se jednat i o osmici celých čísel atd.

Toto vektorové rozšíření WebAssembly je v současnosti široce podporováno:

4. Typ v128

O datových typech, které jsou podporovány běžnými skalárními instrukcemi WebAssembly, jsme se již zmínili v úvodním článku. Připomeňme si, že se jedná o typy se jmény i32, i64, f32 a f64. V rámci rozšíření WebAssembly o SIMD operace byla přidána podpora pro další datový typ nazvaný v128. Název tohoto typu prozrazuje jeho základní vlastnosti – jedná se o vektor, který je uložen ve 128 bitech. Ovšem jaké prvky budou ve vektoru uloženy závisí na konkrétní instrukci – může se jednat o celá čísla se znaménkem nebo bez znaménka, hodnoty s plovoucí řádovou čárkou s jednoduchou nebo dvojitou přesností nebo dokonce o jedinou 128bitovou hodnotu (ostatně i některé skalární instrukce mají různé varianty, podle použitých typů operandů).

V jazyce C je tento typ definován následujícím způsobem:

typedef int32_t v128_t __attribute__((__vector_size__(16), __aligned__(16)));

S tím, jakým způsobem se 128bitový vektor „rozpadá“ do jednotlivých prvků vektorů (různého typu) se podrobněji seznámíme v praktické části dnešního článku. V Clangu ovšem můžeme v případě potřeby využít následující definice (ovšem podtržítka naznačují, že se jedná o interní identifikátory):

typedef int32_t            __v128_u __attribute__((__vector_size__(16), __aligned__(1)));
typedef signed char        __i8x16 __attribute__((__vector_size__(16), __aligned__(16)));
typedef unsigned char      __u8x16 __attribute__((__vector_size__(16), __aligned__(16)));
typedef short              __i16x8 __attribute__((__vector_size__(16), __aligned__(16)));
typedef unsigned short     __u16x8 __attribute__((__vector_size__(16), __aligned__(16)));
typedef int                __i32x4 __attribute__((__vector_size__(16), __aligned__(16)));
typedef unsigned int       __u32x4 __attribute__((__vector_size__(16), __aligned__(16)));
typedef long long          __i64x2 __attribute__((__vector_size__(16), __aligned__(16)));
typedef unsigned long long __u64x2 __attribute__((__vector_size__(16), __aligned__(16)));
typedef float              __f32x4 __attribute__((__vector_size__(16), __aligned__(16)));
typedef double             __f64x2 __attribute__((__vector_size__(16), __aligned__(16)));
typedef __fp16             __f16x8 __attribute__((__vector_size__(16), __aligned__(16)));
typedef signed char        __i8x8 __attribute__((__vector_size__(8), __aligned__(8)));
typedef unsigned char      __u8x8 __attribute__((__vector_size__(8), __aligned__(8)));
typedef short              __i16x4 __attribute__((__vector_size__(8), __aligned__(8)));
typedef unsigned short     __u16x4 __attribute__((__vector_size__(8), __aligned__(8)));
typedef int                __i32x2 __attribute__((__vector_size__(8), __aligned__(8)));
typedef unsigned int       __u32x2 __attribute__((__vector_size__(8), __aligned__(8)));
typedef float              __f32x2 __attribute__((__vector_size__(8), __aligned__(8)));

5. Instrukční prefix 0×FD

Všechny doposud popsané instrukce WebAssembly používaly jediný bajt pro uložení operačního kódu instrukce a většinou i pro určení, s jakými operandy se má instrukce provést (připomeňme si například několik variant instrukce pro součet dvou skalárních hodnot). Teoreticky tedy byla instrukční sada WebAssembly omezena na 256 instrukcí. U SIMD instrukcí je tomu jinak, protože těchto instrukcí existuje takové množství, že bylo nutné je všechny sjednotit do jediné skupiny. Tato skupina začíná prefixem 0×FD, za kterým následuje operační kód instrukce – SIMD instrukcí tedy může být definováno až 256 – a nutno říci, že prakticky všechny dostupné operační kódy z této skupiny byly skutečně využity.

6. Jakým způsobem lze SIMD využít pro programy psané v jazyku C?

SIMD operace (resp. přesněji řečeno instrukce) podporované ve WebAssembly je v praxi možné generovat různými způsoby, které se od sebe odlišují mírou abstrakce (a tedy vlastně i pracností):

1. Povolením automatické vektorizace kódu, což kombinace frontend překladače Clang a backend překladače LLVM v současné verzi plně podporuje. Výhodou tohoto řešení je fakt, že není nutné modifikovat existující zdrojové kódy, nevýhodou pak stále ještě nedokonalosti překladačů v této oblasti (i když se situace stále zlepšuje).
2. Taktéž je možné využít takzvané vektorové rozšíření Clangu, které se podobá vektorovému rozšíření GCC, jímž jsme se na stránkách Roota již zabývali (viz též odkazy na příslušné články uvedené na konci článku). Základní operace s vektory definovanými tímto způsobem jsou totiž prováděny právě SIMD instrukcemi definovanými ve WebAssembly.
3. Další nabízenou možností je použití specializovaných intrinsic definujících SIMD operace podporované ve WebAssembly. Tyto intrinsic jsou definovány v hlavičkovém souboru wasm_simd128.h. Pozor: jedná se o odlišné intrinsic, než jaké jsme si popsali v souvislosti s GCC (viz další dva body).
4. Alternativně je možné použít původní intrinsic pro rozšíření instrukční sady x86: x86 SSE, SSE2, SSE3, SSSE3, SSE4.1, SSE4.2, AVX, AVX2 nebo AVX-512 (popř. různé podsady instrukcí). Tyto intrinsic jsou definovány v hlavičkových souborech *mmintrin.h a ještě se k nim později vrátíme.
5. Podobné intrinsic existují i pro architekturu ARM a rozšíření instrukční sady NEON. Tyto intrinsic jsou definovány v hlavičkovém souboru arm_neon.h.

7. Definice vektorů podporované překladači jazyka C

V oblasti SIMD vládne „instrukční babylon“, a to jak na architektuře x86, tak i u ARMu. Ani vývojářům a ani autorům překladačů to nijak neulehčuje život. Jedno z řešení tohoto stavu spočívá v tom, že překladače jazyka C podporují takzvané obecné vektorové operace. A jednou z realizací této myšlenky je rozšíření Clangu i GCC C (a C++) o de facto nové datové typy „vektor určité bajtové délky“ (dále se soustředíme pouze na Clang).

Podívejme se na následující demonstrační příklad, v němž je definován nový datový typ nazvaný i8×16 (jméno může být pochopitelně jakékoli). Jedná se o vektor o délce šestnácti bajtů, který obsahuje prvky typu signed char, což zde konkrétně může znamenat, že se do vektoru vejde celkem šestnáct těchto prvků za předpokladu, že sizeof(signed char)==1 (a to při překladu pro WebAssembly pochopitelně platí):

#include <stdio.h>
 
typedef signed char i8x16 __attribute__((vector_size(16)));
 
int main(void)
{
    printf("scalar signed byte:   %ld byte(s)\n", sizeof(signed char));
    printf("vector signed bytes:  %ld byte(s)\n", sizeof(i8x16));
    return 0;
}

Výsledek, který získáme po překladu a spuštění tohoto demonstračního příkladu:

scalar signed byte:   1 byte(s)
vector signed bytes:  16 byte(s)

8. Vektory shodné bitové šířky, ovšem obsahující prvky odlišných typů

Naprosto stejným způsobem si můžeme nadefinovat vektory o šířce šestnácti bajtů (tedy stále 128 bitů) s prvky různých typů:

#include <stdio.h>
 
typedef signed   char      i8x16 __attribute__((vector_size(16)));
typedef unsigned char      u8x16 __attribute__((vector_size(16)));
typedef signed   short int i16x8 __attribute__((vector_size(16)));
typedef unsigned short int u16x8 __attribute__((vector_size(16)));
typedef signed   int       i32x4 __attribute__((vector_size(16)));
typedef unsigned int       u32x4 __attribute__((vector_size(16)));
typedef   signed long int  i64x2 __attribute__((vector_size(16)));
typedef unsigned long int  u64x2 __attribute__((vector_size(16)));
 
int main(void)
{
    printf("signed char:    %ld bytes\n", sizeof(signed char));
    printf("unsigned char:  %ld bytes\n", sizeof(unsigned char));
    printf("signed short:   %ld bytes\n", sizeof(signed short int));
    printf("unsigned short: %ld bytes\n", sizeof(unsigned short int));
    printf("signed int:     %ld bytes\n", sizeof(signed int));
    printf("unsigned int:   %ld bytes\n", sizeof(unsigned int));
    printf("signed long:    %ld bytes\n", sizeof(signed long int));
    printf("unsigned long:  %ld bytes\n", sizeof(unsigned long int));
 
    printf("\n");
 
    printf("vector signed char:    %ld bytes\n", sizeof(i8x16));
    printf("vector unsigned char:  %ld bytes\n", sizeof(u8x16));
    printf("vector signed short:   %ld bytes\n", sizeof(i16x8));
    printf("vector unsigned short: %ld bytes\n", sizeof(u16x8));
    printf("vector signed int:     %ld bytes\n", sizeof(i32x4));
    printf("vector unsigned int:   %ld bytes\n", sizeof(u32x4));
    printf("vector signed long:    %ld bytes\n", sizeof(i64x2));
    printf("vector unsigned long:  %ld bytes\n", sizeof(u64x2));
  
    return 0;
}

Výsledky by měly vypadat následovně:

signed char:    1 bytes
unsigned char:  1 bytes
signed short:   2 bytes
unsigned short: 2 bytes
signed int:     4 bytes
unsigned int:   4 bytes
signed long:    8 bytes
unsigned long:  8 bytes
 
vector signed char:    16 bytes
vector unsigned char:  16 bytes
vector signed short:   16 bytes
vector unsigned short: 16 bytes
vector signed int:     16 bytes
vector unsigned int:   16 bytes
vector signed long:    16 bytes
vector unsigned long:  16 bytes

A konečně – vyzkoušíme si definici vektorů o šířce 128bitů, které budou obsahovat čtyři prvky typu float (jednoduchá přesnost) nebo dva prvky typu double (dvojnásobná přesnost) popř. osm prvků typu fp16 (poloviční přesnost):

#include <stdio.h>
 
typedef float  f32x4 __attribute__((vector_size(16)));
typedef double f64x2 __attribute__((vector_size(16)));
typedef __fp16 f16x8 __attribute__((vector_size(16)));
 
int main(void)
{
    printf("float:  %ld bytes\n", sizeof(float));
    printf("double: %ld bytes\n", sizeof(double));
    printf("fp16:   %ld bytes\n", sizeof(__fp16));
 
    printf("\n");
 
    printf("vector float:  %ld bytes\n", sizeof(f32x4));
    printf("vector double: %ld bytes\n", sizeof(f64x2));
    printf("vector fp16:   %ld bytes\n", sizeof(f16x8));
 
    return 0;
}

Opět se podívejme na zobrazené výsledky:

float:  4 bytes
double: 8 bytes
fp16:   2 bytes
 
vector float:  16 bytes
vector double: 16 bytes
vector fp16:   16 bytes

9. Operace prováděné s celými vektory

S celými vektory (definovanými tak, jak jsme si ukázali v předchozích dvou kapitolách) lze pochopitelně provádět i základní aritmetické operace, což je ukázáno na dalším příkladu, společně s ukázkou toho, jak se vlastně vektory naplní daty. Budeme provádět součet vektorů obsahujících šestnáct prvků typu signed char:

#include <stdio.h>
 
typedef signed char i8x16 __attribute__((vector_size(16)));
 
i8x16 add(i8x16 x, i8x16 y) {
    return x+y;
}
 
void print_vector(i8x16 *v) {
    int i;
 
    printf("[");
    for (i=0; i<16; i++) {
        printf(" %2d", (*v)[i]);
    }
    printf("]\n");
}
 
int main(void) {
    i8x16 v1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16};
    i8x16 v2 = {10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10, 10};
    i8x16 v3 = v1+v2;
 
    print_vector(&v1);
    print_vector(&v2);
    print_vector(&v3);
 
    return 0;
}

Po překladu a spuštění tohoto demonstračního příkladu (na běžné platformě x86 atd.) by se měly napřed zobrazit obsahy původních vektorů a následně i vektor, který vznikne jejich součtem:

[  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15 16]
[ 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10 10]
[ 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26]

Pro účely překladu do WebAssembly příklad zkrátíme do jediné funkce add, pochopitelně doplněné definicí typu vektorů, které se budou sčítat:

typedef signed char i8x16 __attribute__((vector_size(16)));
 
i8x16 add(i8x16 x, i8x16 y) {
    return x+y;
}

10. Překlad funkce pro součet dvou vektorů do WebAssembly

Funkci add z předchozí kapitoly přeložíme standardním způsobem, který jsme až doposud (úspěšně) používali, tedy s využitím tohoto skriptu:

clang -Os --target=wasm32 -emit-llvm -c -S ${1}.c
llc -march=wasm32 -filetype=obj ${1}.ll -o ${1}.wasm
wasm-objdump -d ${1}.wasm

Výsledek může vypadat následovně (ovšem různé verze Clangu generují nepatrně odlišný kód):

simd_5.wasm:    file format wasm 0x1
 
Code Disassembly:
 
000062 func[0] <add>:
 000063: 20 00                      | local.get 0
 000065: 20 19                      | local.get 25
 000067: 20 09                      | local.get 9
 000069: 6a                         | i32.add
 00006a: 3a 00 08                   | i32.store8 0 8
 00006d: 20 00                      | local.get 0
 00006f: 20 15                      | local.get 21
 000071: 20 05                      | local.get 5
 000073: 6a                         | i32.add
 000074: 3a 00 04                   | i32.store8 0 4
 000077: 20 00                      | local.get 0
 000079: 20 13                      | local.get 19
 00007b: 20 03                      | local.get 3
 00007d: 6a                         | i32.add
 00007e: 3a 00 02                   | i32.store8 0 2
 000081: 20 00                      | local.get 0
 000083: 20 12                      | local.get 18
 000085: 20 02                      | local.get 2
 000087: 6a                         | i32.add
 000088: 3a 00 01                   | i32.store8 0 1
 00008b: 20 00                      | local.get 0
 00008d: 20 11                      | local.get 17
 00008f: 20 01                      | local.get 1
 000091: 6a                         | i32.add
 000092: 3a 00 00                   | i32.store8 0 0
 000095: 20 00                      | local.get 0
 000097: 41 0f                      | i32.const 15
 000099: 6a                         | i32.add
 00009a: 20 20                      | local.get 32
 00009c: 20 10                      | local.get 16
 00009e: 6a                         | i32.add
 00009f: 3a 00 00                   | i32.store8 0 0
 0000a2: 20 00                      | local.get 0
 0000a4: 41 0e                      | i32.const 14
 0000a6: 6a                         | i32.add
 0000a7: 20 1f                      | local.get 31
 0000a9: 20 0f                      | local.get 15
 0000ab: 6a                         | i32.add
 0000ac: 3a 00 00                   | i32.store8 0 0
 0000af: 20 00                      | local.get 0
 0000b1: 41 0d                      | i32.const 13
 0000b3: 6a                         | i32.add
 0000b4: 20 1e                      | local.get 30
 0000b6: 20 0e                      | local.get 14
 0000b8: 6a                         | i32.add
 0000b9: 3a 00 00                   | i32.store8 0 0
 0000bc: 20 00                      | local.get 0
 0000be: 41 0c                      | i32.const 12
 0000c0: 6a                         | i32.add
 0000c1: 20 1d                      | local.get 29
 0000c3: 20 0d                      | local.get 13
 0000c5: 6a                         | i32.add
 0000c6: 3a 00 00                   | i32.store8 0 0
 0000c9: 20 00                      | local.get 0
 0000cb: 41 0b                      | i32.const 11
 0000cd: 6a                         | i32.add
 0000ce: 20 1c                      | local.get 28
 0000d0: 20 0c                      | local.get 12
 0000d2: 6a                         | i32.add
 0000d3: 3a 00 00                   | i32.store8 0 0
 0000d6: 20 00                      | local.get 0
 0000d8: 41 0a                      | i32.const 10
 0000da: 6a                         | i32.add
 0000db: 20 1b                      | local.get 27
 0000dd: 20 0b                      | local.get 11
 0000df: 6a                         | i32.add
 0000e0: 3a 00 00                   | i32.store8 0 0
 0000e3: 20 00                      | local.get 0
 0000e5: 41 09                      | i32.const 9
 0000e7: 6a                         | i32.add
 0000e8: 20 1a                      | local.get 26
 0000ea: 20 0a                      | local.get 10
 0000ec: 6a                         | i32.add
 0000ed: 3a 00 00                   | i32.store8 0 0
 0000f0: 20 00                      | local.get 0
 0000f2: 41 07                      | i32.const 7
 0000f4: 6a                         | i32.add
 0000f5: 20 18                      | local.get 24
 0000f7: 20 08                      | local.get 8
 0000f9: 6a                         | i32.add
 0000fa: 3a 00 00                   | i32.store8 0 0
 0000fd: 20 00                      | local.get 0
 0000ff: 41 06                      | i32.const 6
 000101: 6a                         | i32.add
 000102: 20 17                      | local.get 23

Povšimněte si, že se v tomto případě ve skutečnosti žádná vektorová operace neprovedla, protože zde můžeme vidět sérii „skalárních“ součtů:

 000069: 6a                         | i32.add
 ...
 000073: 6a                         | i32.add
 ...
 00007d: 6a                         | i32.add
 ...
 000087: 6a                         | i32.add
 ...
 000091: 6a                         | i32.add
 ...
 000099: 6a                         | i32.add
 ...
 00009e: 6a                         | i32.add
 ...
 0000a6: 6a                         | i32.add
 ...
 0000ab: 6a                         | i32.add
 ...
 0000b3: 6a                         | i32.add
 ...
 0000b8: 6a                         | i32.add
 ...
 0000c0: 6a                         | i32.add
 ...
 0000c5: 6a                         | i32.add
 ...
 0000cd: 6a                         | i32.add
 ...
 0000d2: 6a                         | i32.add
 ...
 0000da: 6a                         | i32.add
 ...
 0000df: 6a                         | i32.add
 ...
 0000e7: 6a                         | i32.add
 ...
 0000ec: 6a                         | i32.add
 ...
 0000f4: 6a                         | i32.add
 ...
 0000f9: 6a                         | i32.add
 ...
 000101: 6a                         | i32.add

11. Překlad do WebAssembly s explicitním povolením vektorových instrukcí

Aby se ve WebAssembly používaly vektorové instrukce, je nutné skript určený pro překlad nepatrným způsobem upravit. Budeme muset překladači Clang explicitně povolit generování SIMD instrukcí, a to přepínačem -msimd128. Upravený skript by tedy mohl vypadat následovně:

clang -Os -msimd128 --target=wasm32 -emit-llvm -c -S ${1}.c
llc -march=wasm32 -filetype=obj ${1}.ll -o ${1}.wasm
wasm-objdump -d ${1}.wasm

Nyní se funkce add skutečně přeloží do podoby, v níž je použita SIMD instrukce nazvaná i8×16.add, tedy „vektorová“ podoba skalární operace add:

simd_5.wasm:    file format wasm 0x1
 
Code Disassembly:
 
000043 func[0] <add>:
 000044: 20 01                      | local.get 1
 000046: 20 00                      | local.get 0
 000048: fd 6e                      | i8x16.add
 00004a: 0b                         | end

Výsledek by tedy měl být při interpretaci nebo JITování cca 16× rychlejší!

12. Součet vektorů s dvojnásobným počtem prvků

WebAssembly sice omezuje vektorové operace na 128bitové vektory, ovšem to neznamená, že se musíme tímto omezením řídit i v céčku. Pokusme se nyní realizovat funkci pro součet vektorů, které budou obsahovat 32 prvků typu signed char. Bude se tedy jednat o 256bitové vektory:

typedef signed char i8x32 __attribute__((vector_size(32)));
 
i8x32 add(i8x32 x, i8x32 y) {
    return x+y;
}

Z výsledku překladu do WebAssembly je patrné, že se vektory sečtou po částech (nyní zcela přesně po polovinách):

simd_6.wasm:    file format wasm 0x1
 
Code Disassembly:
 
000045 func[0] <add>:
 000046: 20 00                      | local.get 0
 000048: 20 04                      | local.get 4
 00004a: 20 02                      | local.get 2
 00004c: fd 6e                      | i8x16.add
 00004e: fd 0b 04 10                | v128.store 4 16
 000052: 20 00                      | local.get 0
 000054: 20 03                      | local.get 3
 000056: 20 01                      | local.get 1
 000058: fd 6e                      | i8x16.add
 00005a: fd 0b 04 00                | v128.store 4 0
 00005e: 0b                         | end

13. Součet vektorů s celočíselnými prvky různých typů

Prozatím víme, jakým způsobem je realizován součet vektorů s prvky typu signed char. Pokusme se nyní o realizaci součtu vektorů s celočíselnými prvky jiných typů (s odlišnou bitovou šířkou a popř. bez znaménka). Předchozí demonstrační příklad bude rozšířen do podoby:

typedef signed   char      i8x16 __attribute__((vector_size(16)));
typedef unsigned char      u8x16 __attribute__((vector_size(16)));
typedef signed   short int i16x8 __attribute__((vector_size(16)));
typedef unsigned short int u16x8 __attribute__((vector_size(16)));
typedef signed   int       i32x4 __attribute__((vector_size(16)));
typedef unsigned int       u32x4 __attribute__((vector_size(16)));
typedef   signed long int  i64x2 __attribute__((vector_size(16)));
typedef unsigned long int  u64x2 __attribute__((vector_size(16)));
 
i8x16 add_i8x16(i8x16 x, i8x16 y) {
    return x+y;
}
 
u8x16 add_u8x16(u8x16 x, u8x16 y) {
    return x+y;
}
 
i16x8 add_i16x8(i16x8 x, i16x8 y) {
    return x+y;
}
 
u16x8 add_u16x8(u16x8 x, u16x8 y) {
    return x+y;
}
 
i32x4 add_i32x4(i32x4 x, i32x4 y) {
    return x+y;
}
 
u32x4 add_u32x4(u32x4 x, u32x4 y) {
    return x+y;
}
 
i64x2 add_i64x2(i64x2 x, i64x2 y) {
    return x+y;
}
 
u64x2 add_u64x2(u64x2 x, u64x2 y) {
    return x+y;
}

Ve výsledném bajtkódu můžeme vidět různé varianty vektorových instrukcí pro součet, u kterých se však (logicky) nerozlišuje mezi tím, zda jsou prvky vektorů se znaménkem nebo bez znaménka:

simd_7.wasm:    file format wasm 0x1
 
Code Disassembly:
 
00004a func[0] <add_i8x16>:
 00004b: 20 01                      | local.get 1
 00004d: 20 00                      | local.get 0
 00004f: fd 6e                      | i8x16.add
 000051: 0b                         | end
 
000053 func[1] <add_u8x16>:
 000054: 20 01                      | local.get 1
 000056: 20 00                      | local.get 0
 000058: fd 6e                      | i8x16.add
 00005a: 0b                         | end
 
00005c func[2] <add_i16x8>:
 00005d: 20 01                      | local.get 1
 00005f: 20 00                      | local.get 0
 000061: fd 8e 01                   | i16x8.add
 000064: 0b                         | end
 
000066 func[3] <add_u16x8>:
 000067: 20 01                      | local.get 1
 000069: 20 00                      | local.get 0
 00006b: fd 8e 01                   | i16x8.add
 00006e: 0b                         | end
 
000070 func[4] <add_i32x4>:
 000071: 20 01                      | local.get 1
 000073: 20 00                      | local.get 0
 000075: fd ae 01                   | i32x4.add
 000078: 0b                         | end
 
00007a func[5] <add_u32x4>:
 00007b: 20 01                      | local.get 1
 00007d: 20 00                      | local.get 0
 00007f: fd ae 01                   | i32x4.add
 000082: 0b                         | end
 
000084 func[6] <add_i64x2>:
 000085: 20 01                      | local.get 1
 000087: 20 00                      | local.get 0
 000089: fd ae 01                   | i32x4.add
 00008c: 0b                         | end
 
00008e func[7] <add_u64x2>:
 00008f: 20 01                      | local.get 1
 000091: 20 00                      | local.get 0
 000093: fd ae 01                   | i32x4.add
 000096: 0b                         | end

14. Součet vektorů s prvky s plovoucí řádovou čárkou

Vektory mohou obsahovat prvky s plovoucí řádovou čárkou. Datové typy jednotlivých prvků mohou být s poloviční přesností (half float, k tomuto tématu se ještě vrátíme), s jednoduchou přesností (single) i s dvojitou přesností (double). To si pochopitelně můžeme snadno ověřit:

typedef float  f32x4 __attribute__((vector_size(16)));
typedef double f64x2 __attribute__((vector_size(16)));
typedef __fp16 f16x8 __attribute__((vector_size(16)));
 
f16x8 add_f16x8(f16x8 x, f16x8 y) {
    return x+y;
}
 
f32x4 add_f32x4(f32x4 x, f32x4 y) {
    return x+y;
}
 
f64x2 add_f64x2(f64x2 x, f64x2 y) {
    return x+y;
}

Překlad do WebAssembly dopadne následovně:

simd_8.wasm:    file format wasm 0x1
 
Code Disassembly:
 
000045 func[0] <add_f16x8>:
 000046: 20 01                      | local.get 1
 000048: 20 00                      | local.get 0
 00004a: fd 8e 01                   | i16x8.add
 00004d: 0b                         | end
 
00004f func[1] <add_f32x4>:
 000050: 20 00                      | local.get 0
 000052: 20 01                      | local.get 1
 000054: fd e4 01                   | f32x4.add
 000057: 0b                         | end
 
000059 func[2] <add_f64x2>:
 00005a: 20 00                      | local.get 0
 00005c: 20 01                      | local.get 1
 00005e: fd f0 01                   | f64x2.add
 000061: 0b                         | end

15. Všechny instrukce pro součet vektorů

Nyní si již můžeme vytvořit soupis všech instrukcí WebAssembly, které dokážou sečíst dvojici vektorů. Všechny tyto instrukce byly použity v předchozích demonstračních příkladech:

16. Další celočíselné operace prováděné s prvky vektorů

Pokusme se o implementaci dalších základních aritmetických operací prováděných s prvky vektorů. Použijeme vektory se čtyřmi 32bitovými prvky a budeme implementovat operaci změny znaménka a dále součet (ten už známe), rozdíl, součin i podíl:

typedef unsigned int i32x4 __attribute__((vector_size(16)));
 
i32x4 neg(i32x4 x) {
    return -x;
}
 
i32x4 add(i32x4 x, i32x4 y) {
    return x+y;
}
 
i32x4 sub(i32x4 x, i32x4 y) {
    return x-y;
}
 
i32x4 mul(i32x4 x, i32x4 y) {
    return x*y;
}
 
i32x4 div(i32x4 x, i32x4 y) {
    return x/y;
}

Většina operací bude přeložena do jediné instrukce WebAssembly, ovšem s výjimkou podílu (k tomu, proč výsledek vypadá tak jak vypadá, se vrátíme příště):

simd_9.wasm:    file format wasm 0x1

Code Disassembly:

00004c func[0] <neg>:
 00004d: 20 00                      | local.get 0
 00004f: fd a1 01                   | i32x4.neg
 000052: 0b                         | end
 
000054 func[1] <add>:
 000055: 20 01                      | local.get 1
 000057: 20 00                      | local.get 0
 000059: fd ae 01                   | i32x4.add
 00005c: 0b                         | end
 
00005e func[2] <sub>:
 00005f: 20 00                      | local.get 0
 000061: 20 01                      | local.get 1
 000063: fd b1 01                   | i32x4.sub
 000066: 0b                         | end
 
000068 func[3] <mul>:
 000069: 20 01                      | local.get 1
 00006b: 20 00                      | local.get 0
 00006d: fd b5 01                   | i32x4.mul
 000070: 0b                         | end
 
000072 func[4] <div>:
 000073: 20 00                      | local.get 0
 000075: fd 1b 00                   | i32x4.extract_lane 0
 000078: 20 01                      | local.get 1
 00007a: fd 1b 00                   | i32x4.extract_lane 0
 00007d: 6e                         | i32.div_u
 00007e: fd 11                      | i32x4.splat
 000080: 20 00                      | local.get 0
 000082: fd 1b 01                   | i32x4.extract_lane 1
 000085: 20 01                      | local.get 1
 000087: fd 1b 01                   | i32x4.extract_lane 1
 00008a: 6e                         | i32.div_u
 00008b: fd 1c 01                   | i32x4.replace_lane 1
 00008e: 20 00                      | local.get 0
 000090: fd 1b 02                   | i32x4.extract_lane 2
 000093: 20 01                      | local.get 1
 000095: fd 1b 02                   | i32x4.extract_lane 2
 000098: 6e                         | i32.div_u
 000099: fd 1c 02                   | i32x4.replace_lane 2
 00009c: 20 00                      | local.get 0
 00009e: fd 1b 03                   | i32x4.extract_lane 3
 0000a1: 20 01                      | local.get 1
 0000a3: fd 1b 03                   | i32x4.extract_lane 3
 0000a6: 6e                         | i32.div_u
 0000a7: fd 1c 03                   | i32x4.replace_lane 3
 0000aa: 0b                         | end

17. Obsah navazujícího článku

Ve skutečnosti je ve WebAssembly definováno přibližně dvě stě různých vektorových instrukcí. Některé z těchto instrukcí si popíšeme v navazujícím článku.

18. Tabulka se všemi doposud popsanými instrukcemi

Všechny instrukce WebAssembly, které jsme si až doposud popsali, jsou vypsány v následující tabulce, kde jsou seřazeny podle svého operačního kódu (tedy na základě hodnoty svého prvního bajtu). Aby bylo zřejmé, jaký rozsah instrukčního souboru již byl popsán, obsahuje tabulka i (prozatím) prázdné řádky:

19. Články o SIMD, které doposud na Rootu vyšly

Podporou SIMD instrukcí na úrovni takzvaných intrinsic v jazyku C jsme se už na Rootu zabývali, stejně jako samotnými SIMD instrukcemi na úrovni assembleru (i když jen pro platformu x86 či x86–64 a nikoli pro WebAssembly). 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. Compiling C to WebAssembly without Emscripten
   https://surma.dev/things/c-to-webassembly/
2. Web Assemply: Text Format
   https://webassembly.github­.io/spec/core/text/index.html
3. WebAssembly: Binary Format
   https://webassembly.github­.io/spec/core/binary/index­.html
4. WebAssembly
   https://webassembly.org/
5. WebAssembly na Wiki Golangu
   https://github.com/golang/go/wi­ki/WebAssembly
6. The future of WebAssembly – A look at upcoming features and proposals
   https://blog.scottlogic.com/2018/07/20/wasm-future.html
7. WebAssembly Design
   https://github.com/WebAssembly/design
8. Využití WebAssembly z programovacího jazyka Go
   https://www.root.cz/clanky/vyuziti-webassembly-z-programovaciho-jazyka-go/
9. WebAssembly slibuje podstatné zrychlení webů, konec JavaScriptu se ale nekoná
   https://www.lupa.cz/clanky/webassembly-slibuje-podstatne-zrychleni-webu-konec-javascriptu-se-ale-nekona/
10. List of languages that compile to JS
    https://github.com/jashke­nas/coffeescript/wiki/List-of-languages-that-compile-to-JS
11. asm.js
    http://asmjs.org/
12. Top 23 WASM Open-Source Projects
    https://www.libhunt.com/topic/wasm
13. Made with WebAssembly
    https://madewithwebassembly.com/
14. The Top 1,790 Wasm Open Source Projects on Github
    https://awesomeopensource­.com/projects/wasm
15. Sanspiel
    https://sandspiel.club/
16. Painting on HTML5 Canvas with Rust WASM
    https://www.subarctic.org/pa­inting_on_html5_canvas_wit­h_rust_wasm.html
17. Writing WebAssembly By Hand
    https://blog.scottlogic.com/2018/04/26/we­bassembly-by-hand.html
18. WebAssembly Specification
    https://webassembly.github­.io/spec/core/index.html
19. Index of Instructions
    https://webassembly.github­.io/spec/core/appendix/in­dex-instructions.html
20. The WebAssembly Binary Toolkit
    https://github.com/WebAssembly/wabt
21. Will WebAssembly replace JavaScript? Or Will WASM Make JavaScript More Valuable in Future?
    https://dev.to/vaibhavshah/will-webassembly-replace-javascript-or-will-wasm-make-javascript-more-valuable-in-future-5c6e
22. Webassembly as 32bit and 64bit
    https://stackoverflow.com/qu­estions/78580226/webassem­bly-as-32bit-and-64bit
23. Portability
    https://webassembly.org/doc­s/portability/
24. Hexadecimální prohlížeče a editory s textovým uživatelským rozhraním
    https://www.root.cz/clanky/he­xadecimalni-prohlizece-a-editory-s-textovym-uzivatelskym-rozhranim/
25. Nástroj objdump: švýcarský nožík pro vývojáře
    https://www.root.cz/clanky/nastroj-objdump-svycarsky-nozik-pro-vyvojare/
26. Getting Started: Building and Running Clang
    https://clang.llvm.org/get_star­ted.html
27. Clang: a C language family frontend for LLVM
    https://clang.llvm.org/
28. Scheduling LLVM Passes with the New Pass Manager
    https://stephenverderame.git­hub.io/blog/scheduling_llvm/
29. C data types
    https://en.wikipedia.org/wi­ki/C_data_types
30. WebAssembly data types
    https://webassembly.github­.io/spec/core/syntax/types­.html
31. WebAssembly Opcodes
    https://pengowray.github.io/wasm-ops/
32. Advanced tools (for WebAssembly)
    https://webassembly.org/getting-started/advanced-tools/
33. Binaryen
    https://github.com/WebAssem­bly/binaryen
34. Using SIMD with WebAssembly
    https://emscripten.org/doc­s/porting/simd.html
35. GCC documentation: Extensions to the C Language Family
    https://gcc.gnu.org/onlinedocs/gcc/C-Extensions.html#C-Extensions
36. GCC documentation: Using Vector Instructions through Built-in Functions
    https://gcc.gnu.org/online­docs/gcc/Vector-Extensions.html
37. SSE (Streaming SIMD Extentions)
    http://www.songho.ca/misc/sse/sse­.html
38. Timothy A. Chagnon: SSE and SSE2
    http://www.cs.drexel.edu/~tc365/mpi-wht/sse.pdf
39. Intel corporation: Extending the Worldr's Most Popular Processor Architecture
    http://download.intel.com/techno­logy/architecture/new-instructions-paper.pdf
40. SIMD architectures:
    http://arstechnica.com/ol­d/content/2000/03/simd.ar­s/
41. 3Dnow! Technology Manual
    AMD Inc., 2000
42. Intel MMX^TM Technology Overview
    Intel corporation, 1996
43. MultiMedia eXtensions
    http://softpixel.com/~cwrig­ht/programming/simd/mmx.phpi
44. AMD K5 („K5“ / „5k86“)
    http://www.pcguide.com/ref/cpu/fam/g5K5-c.html
45. Arm Helium
    https://www.arm.com/techno­logies/helium
46. SIMD proposal for WebAssembly
    https://github.com/webassembly/simd/
47. Single instruction, multiple data
    https://en.wikipedia.org/wi­ki/Single_instruction%2C_mul­tiple_data
48. Parallel computing
    https://en.wikipedia.org/wi­ki/Parallel_computing
49. Flynn's taxonomy
    https://en.wikipedia.org/wi­ki/Flynn%27s_taxonomy