Vectorizare automată - Automatic vectorization

Vectorizarea automată , în calcul paralel , este un caz special de paralelizare automată , în care un program de calculator este convertit dintr-o implementare scalară , care procesează o singură pereche de operanzi la un moment dat, într-o implementare vectorială , care procesează o operație pe mai multe perechi de operanzi deodată. De exemplu, computerele convenționale moderne, inclusiv supercomputerele specializate , au de obicei operații vectoriale care efectuează simultan operații precum următoarele patru adăugiri (prin hardware SIMD sau SPMD ):

{\ displaystyle {\ begin {align} c_ {1} & = a_ {1} + b_ {1} \\ c_ {2} & = a_ {2} + b_ {2} \\ c_ {3} & = a_ {3} + b_ {3} \\ c_ {4} & = a_ {4} + b_ {4} \ end {align}}}

Cu toate acestea, în majoritatea limbajelor de programare se scrie de obicei bucle care efectuează secvențial adăugări de mai multe numere. Iată un exemplu de astfel de buclă, scris în C :

for (i = 0; i < n; i++)
    c[i] = a[i] + b[i];

Un compilator de vectorizare transformă astfel de bucle în secvențe de operații vectoriale. Aceste operații vectoriale efectua adăugări pe blocuri de elemente din matrice a, bși c. Vectorizarea automată este un subiect major de cercetare în informatică.

fundal

Primele computere aveau de obicei o unitate logică, care executa o instrucțiune pe o pereche de operanzi la un moment dat. Prin urmare, limbajele și programele computerizate au fost concepute pentru a fi executate în ordine. Totuși, computerele moderne pot face multe lucruri simultan. Deci, mulți compilatori de optimizare efectuează vectorizarea automată, în care părți ale programelor secvențiale sunt transformate în operații paralele.

Vectorizarea buclei transformă buclele procedurale prin atribuirea unei unități de procesare fiecărei perechi de operanzi. Programele își petrec cea mai mare parte a timpului în astfel de bucle. Prin urmare, vectorizarea le poate accelera semnificativ, în special în cazul seturilor de date mari. Buclă vectorizare este implementat în Intel e MMX , SSE , și AVX , în putere ISA lui AltiVec , în ARM lui NEON , SVE și SVE2 seturi de instrucțiuni.

Multe constrângeri împiedică sau împiedică vectorizarea. Uneori vectorizarea poate încetini execuția, de exemplu din cauza sincronizării conductelor sau a sincronizării mișcării datelor. Analiza dependenței de bucle identifică bucle care pot fi vectorizate, bazându-se pe dependența de date a instrucțiunilor din bucle.

Garanții

Vectorizarea automată, ca orice optimizare de buclă sau altă optimizare în timp de compilare, trebuie să păstreze exact comportamentul programului.

Dependențe de date

Toate dependențele trebuie respectate în timpul execuției pentru a preveni rezultate incorecte.

În general, dependențele invariante în buclă și dependențele lexical forward pot fi ușor vectorizate, iar dependențele lexical înapoi pot fi transformate în dependențe lexical forward. Cu toate acestea, aceste transformări trebuie făcute în siguranță, pentru a se asigura că dependența dintre toate afirmațiile rămâne fidelă originalului.

Dependențele ciclice trebuie procesate independent de instrucțiunile vectorizate.

Precizia datelor

Precizia întregului (dimensiunea de biți) trebuie păstrată în timpul executării instrucțiunilor vectoriale. Instrucțiunea vectorială corectă trebuie aleasă în funcție de mărimea și comportamentul numerelor întregi interne. De asemenea, în cazul tipurilor întregi mixte, trebuie să se acorde o atenție deosebită pentru a le promova / descrește corect, fără a pierde precizia. Trebuie acordată o atenție deosebită extensiei semnelor (deoarece mai multe numere întregi sunt împachetate în același registru) și în timpul operațiilor de schimbare sau a operațiilor cu biți de transport care altfel ar fi luați în considerare.

Precizia în virgulă mobilă trebuie păstrată, de asemenea, cu excepția cazului în care conformitatea IEEE-754 este dezactivată, caz în care operațiunile vor fi mai rapide, dar rezultatele pot varia ușor. Variațiile mari, chiar ignorând IEEE-754, indică de obicei o eroare de programator.

Teorie

Pentru a vectoriza un program, optimizatorul compilatorului trebuie să înțeleagă mai întâi dependențele dintre instrucțiuni și să le alinieze, dacă este necesar. Odată ce dependențele sunt mapate, optimizatorul trebuie să aranjeze corect instrucțiunile de implementare schimbând candidații corespunzători în instrucțiuni vectoriale, care funcționează pe mai multe elemente de date.

Construirea graficului dependenței

Primul pas este de a construi graficul dependenței , identificând ce afirmații depind de ce alte afirmații. Aceasta implică examinarea fiecărei instrucțiuni și identificarea fiecărui element de date la care accesează instrucțiunea, maparea modificatorilor de acces la matrice la funcții și verificarea dependenței fiecărui acces la toate celelalte din toate instrucțiunile. Analiza alias poate fi utilizată pentru a certifica că diferitele variabile accesează (sau intersectează) aceeași regiune din memorie.

Graficul dependenței conține toate dependențele locale cu o distanță nu mai mare decât dimensiunea vectorului. Deci, dacă registrul vector este de 128 de biți, iar tipul matricei este de 32 de biți, dimensiunea vectorului este de 128/32 = 4. Toate celelalte dependențe non-ciclice nu ar trebui să invalideze vectorizarea, deoarece nu va exista niciun acces simultan în aceeași instrucțiune vectorială.

Să presupunem că dimensiunea vectorului este aceeași cu 4 inci:

for (i = 0; i < 128; i++) {
    a[i] = a[i-16]; // 16 > 4, safe to ignore
    a[i] = a[i-1]; // 1 < 4, stays on dependency graph
}

Clustering

Folosind graficul, optimizatorul poate grupa apoi componentele puternic conectate (SCC) și să separe instrucțiunile vectorizabile de restul.

De exemplu, luați în considerare un fragment de program care conține trei grupuri de instrucțiuni în interiorul unei bucle: (SCC1 + SCC2), SCC3 și SCC4, în această ordine, în care numai al doilea grup (SCC3) poate fi vectorizat. Programul final va conține apoi trei bucle, unul pentru fiecare grup, cu doar cel din mijloc vectorizat. Optimizatorul nu se poate alătura primului cu ultimul fără a încălca ordinea de executare a declarațiilor, ceea ce ar invalida garanțiile necesare.

Detectarea expresiilor

Unele dependențe neevidente pot fi optimizate în continuare pe baza unor expresii specifice.

De exemplu, următoarele dependențe de auto-date pot fi vectorizate, deoarece valoarea valorilor din dreapta ( RHS ) este preluată și apoi stocată pe valoarea din stânga, deci nu există nicio modalitate în care datele se vor modifica în cadrul atribuirii.

a[i] = a[i] + a[i+1];

Autodependența de către scalari poate fi vectorizată prin eliminare variabilă .

Cadrul general

Cadrul general pentru vectorizarea buclei este împărțit în patru etape:

Preludiu : în cazul în care variabilele independente de buclă sunt pregătite pentru a fi utilizate în buclă. Aceasta implică în mod normal mutarea lor în registre vectoriale cu modele specifice care vor fi utilizate în instrucțiunile vectoriale. Acesta este, de asemenea, locul pentru a insera verificarea dependenței în timpul rulării. Dacă verificarea decide că vectorizarea nu este posibilă, rulați la Curățare .
Buclă (bucle) : toate buclele vectorizate (sau nu), separate prin clustere SCC în ordinea apariției în codul original.
Postlude : Returnează toate variabilele, inducțiile și reducerile independente de buclă.
Curățare : implementați bucle simple (non-vectorizate) pentru iterații la sfârșitul unei bucle care nu sunt multiple ale dimensiunii vectorului sau când verificările în timp de execuție interzic prelucrarea vectorială.

Timpul de rulare vs. timpul de compilare

Unele vectorizări nu pot fi verificate pe deplin la compilare. De exemplu, funcțiile bibliotecii pot învinge optimizarea dacă datele pe care le procesează sunt furnizate de către apelant. Chiar și în aceste cazuri, optimizarea în timp de execuție poate vectoriza totuși buclele din mers.

Această verificare în timp de execuție se face în etapa preliminară și direcționează fluxul către instrucțiuni vectorizate, dacă este posibil, altfel revine la procesarea standard, în funcție de variabilele care sunt trecute pe registre sau variabile scalare.

Următorul cod poate fi vectorizat cu ușurință la compilare, deoarece nu are nicio dependență de parametrii externi. De asemenea, limbajul garantează că niciuna dintre ele nu va ocupa aceeași regiune în memorie ca orice altă variabilă, deoarece acestea sunt variabile locale și trăiesc doar în stiva de execuție .

int a[128];
int b[128];
// initialize b

for (i = 0; i<128; i++)
    a[i] = b[i] + 5;

Pe de altă parte, codul de mai jos nu are informații despre pozițiile memoriei, deoarece referințele sunt indicatori și memoria spre care se îndreaptă se poate suprapune.

void compute(int *a, int *b)
{
    int i;
    for (i = 0; i < 128; i++, a++, b++)
        *a = *b + 5;
}

O verificare rapidă run-time pe adresa atât a și b , plus spațiul iteratii (128) este suficient pentru a spune dacă matricele se suprapun sau nu, dezvăluind astfel orice dependențe.

Există câteva instrumente pentru a analiza dinamic aplicațiile existente pentru a evalua potențialul latent inerent pentru paralelismul SIMD, exploatabil prin avansuri suplimentare ale compilatorului și / sau prin modificări manuale de cod.

Tehnici

Un exemplu ar fi un program de multiplicare a doi vectori de date numerice. O abordare scalară ar fi ceva de genul:

for (i = 0; i < 1024; i++)
    c[i] = a[i] * b[i];

Acest lucru ar putea fi vectorizat pentru a arăta ca:

for (i = 0; i < 1024; i += 4)
    c[i:i+3] = a[i:i+3] * b[i:i+3];

Aici, c [i: i + 3] reprezintă cele patru elemente matrice de la c [i] la c [i + 3], iar procesorul vectorial poate efectua patru operații pentru o singură instrucțiune vectorială. Deoarece cele patru operații vectoriale se finalizează aproximativ în același timp cu o instrucțiune scalară, abordarea vectorială poate rula de până la patru ori mai rapid decât codul original.

Există două abordări distincte ale compilatorului: una bazată pe tehnica convențională de vectorizare și cealaltă bazată pe derularea buclei .

Vectorizare automată la nivel de buclă

Această tehnică, utilizată pentru mașinile vectoriale convenționale, încearcă să găsească și să exploateze paralelismul SIMD la nivelul buclei. Se compune din doi pași majori, după cum urmează.

Găsiți o buclă interioară care poate fi vectorizată
Transformă bucla și generează coduri vectoriale

În primul pas, compilatorul caută obstacole care pot preveni vectorizarea. Un obstacol major pentru vectorizare este dependența de date adevărată mai mică decât lungimea vectorului. Alte obstacole includ apelurile funcționale și numărul scurt de iterații.

Odată ce bucla este determinată ca vectorizabilă, bucla este stripmined de lungimea vectorului și fiecare instrucțiune scalară din corpul buclei este înlocuită cu instrucțiunea vectorială corespunzătoare. Mai jos, transformările componentelor pentru acest pas sunt prezentate folosind exemplul de mai sus.

După stripmining

for (i = 0; i < 1024; i += 4)
    for (j = 0; j < 4; j++)
        c[i+j] = a[i+j] * b[i+j];

După distribuirea buclei folosind tablouri temporare

for (i = 0; i < 1024; i += 4)
{
    for (j = 0; j < 4; j++) tA[j] = A[i+j];
    for (j = 0; j < 4; j++) tB[j] = B[i+j];
    for (j = 0; j < 4; j++) tC[j] = tA[j] * tB[j];
    for (j = 0; j < 4; j++) C[i+j] = tC[j];
}

După înlocuirea cu coduri vectoriale

for (i = 0; i < 1024; i += 4)
{
    vA = vec_ld(&A[i]);
    vB = vec_ld(&B[i]);
    vC = vec_mul(vA, vB);
    vec_st(vC, &C[i]);
}

Vectorizare automată la nivel de bloc de bază

Această tehnică relativ nouă vizează în mod specific arhitecturile moderne SIMD cu lungimi vectoriale scurte. Deși buclele pot fi derulate pentru a crește cantitatea de paralelism SIMD în blocurile de bază, această tehnică exploatează paralelismul SIMD în cadrul blocurilor de bază, mai degrabă decât buclele. Cei doi pași majori sunt următorii.

Bucla cea mai interioară este derulată de un factor al lungimii vectorului pentru a forma un corp de buclă mare.
Instrucțiunile scalare izomorfe (care efectuează aceeași operație) sunt ambalate într-o instrucțiune vectorială dacă dependențele nu împiedică acest lucru.

Pentru a arăta transformări pas cu pas pentru această abordare, același exemplu este folosit din nou.

După derularea buclei (după lungimea vectorului, presupusă a fi 4 în acest caz)

for (i = 0; i < 1024; i += 4)
{
    sA0 = ld(&A[i+0]);
    sB0 = ld(&B[i+0]);
    sC0 = sA0 * sB0;
    st(sC0, &C[i+0]);
          ...
    sA3 = ld(&A[i+3]);
    sB3 = ld(&B[i+3]);
    sC3 = sA3 * sB3;
    st(sC3, &C[i+3]);
}

După ambalare

for (i = 0; i < 1024; i += 4)
{
    (sA0, sA1, sA2, sA3) = ld(&A[i+0:i+3]);
    (sB0, sB1, sB2, sB3) = ld(&B[i+0:i+3]);
    (sC0, sC1, sC2, sC3) = (sA0, sA1, sA2, sA3) * (sB0, sB1, sB2, sB3);
    st((sC0, sC1, sC2, sC3), &C[i+0:i+3]);
}

După generarea codului

for (i = 0; i < 1024; i += 4)
{
    vA = vec_ld(&A[i]);
    vB = vec_ld(&B[i]);
    vC = vec_mul(vA, vB);
    vec_st(vC, &C[i]);
}

Aici, sA1, sB1, ... reprezintă variabile scalare și vA, vB și vC reprezintă variabile vectoriale.

Cele mai multe vectorizatoare automate ale compilatoarelor comerciale folosesc abordarea convențională la nivel de buclă, cu excepția compilatorului IBM XL, care le utilizează pe ambele.

În prezența fluxului de control

Prezența instrucțiunilor if în corpul buclei necesită executarea instrucțiunilor în toate căile de control pentru a îmbina valorile multiple ale unei variabile. O abordare generală este de a parcurge o succesiune de transformări de cod: predicație → vectorizare (folosind una dintre metodele de mai sus) → eliminarea predicatelor vectoriale → eliminarea predicatelor scalare. Dacă următorul cod este folosit ca exemplu pentru a arăta aceste transformări;

for (i = 0; i < 1024; i++)
    if (A[i] > 0)
        C[i] = B[i];
    else
        D[i] = D[i-1];

După predicție

for (i = 0; i < 1024; i++)
{
    P = A[i] > 0;
    NP = !P;
    C[i] = B[i];     (P)
    D[i] = D[i-1];   (NP)
}

unde (P) denotă un predicat care păstrează afirmația.

După vectorizare

for (i = 0; i < 1024; i += 4)
{
    vP  = A[i:i+3] > (0, 0, 0, 0);
    vNP = vec_not(vP);
    C[i:i+3] = B[i:i+3];     (vP)
    (NP1, NP2, NP3, NP4) = vNP;
    D[i+3] = D[i+2];         (NP4)
    D[i+2] = D[i+1];         (NP3)
    D[i+1] = D[i];           (NP2)
    D[i]   = D[i-1];         (NP1)
}

După eliminarea predicatelor vectoriale

for (i = 0; i < 1024; i += 4)
{
    vP  = A[i:i+3] > (0, 0, 0, 0);
    vNP = vec_not(vP);
    C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vP);
    (NP1, NP2, NP3, NP4) = vNP;
    D[i+3] = D[i+2];         (NP4)
    D[i+2] = D[i+1];         (NP3)
    D[i+1] = D[i];           (NP2)
    D[i]   = D[i-1];         (NP1)
}

După eliminarea predicatelor scalare

for (i = 0; i < 1024; i += 4)
{
    vP  = A[i:i+3] > (0, 0, 0, 0);
    vNP = vec_not(vP);
    C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vP);
    (NP1, NP2, NP3, NP4) = vNP;
    if (NP4) D[i+3] = D[i+2];
    if (NP3) D[i+2] = D[i+1];
    if (NP2) D[i+1] = D[i];
    if (NP1) D[i]   = D[i-1];
}

Reducerea costurilor de vectorizare în prezența fluxului de control

A fi necesar să executați instrucțiunile în toate căile de control din codul vector a fost unul dintre factorii majori care încetinesc codul vector în raport cu linia de bază scalară. Cu cât devine mai complex fluxul de control și cu cât sunt ignorate mai multe instrucțiuni în codul scalar, cu atât devine mai mare cheltuielile de vectorizare. Pentru a reduce acest cost de vectorizare, ramurile vectoriale pot fi inserate pentru a ocoli instrucțiunile vectoriale similare cu modul în care ramurile scalare ocolesc instrucțiunile scalare. Mai jos, predicatele AltiVec sunt utilizate pentru a arăta cum se poate realiza acest lucru.

Linia de bază scalară (cod original)

for (i = 0; i < 1024; i++)
{
    if (A[i] > 0)
    {
        C[i] = B[i];
        if (B[i] < 0)
            D[i] = E[i];
    }
}

După vectorizare în prezența fluxului de control

for (i = 0; i < 1024; i += 4)
{
    vPA = A[i:i+3] > (0, 0, 0, 0);
    C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vPA);
    vT = B[i:i+3] < (0,0,0,0);
    vPB = vec_sel((0, 0, 0, 0), vT, vPA);
    D[i:i+3] = vec_sel(D[i:i+3], E[i:i+3], vPB);
}

După introducerea ramurilor vectoriale

for (i = 0; i < 1024; i += 4)
{
    if (vec_any_gt(A[i:i+3], (0, 0, 0, 0)))
    {
        vPA = A[i:i+3] > (0,0,0,0);
        C[i:i+3] = vec_sel(C[i:i+3], B[i:i+3], vPA);
        vT = B[i:i+3] < (0, 0, 0, 0);
        vPB = vec_sel((0, 0, 0, 0), vT, vPA);
        if (vec_any_ne(vPB, (0, 0, 0, 0)))
            D[i:i+3] = vec_sel(D[i:i+3], E[i:i+3], vPB);
    }
}

Există două lucruri de remarcat în codul final cu ramuri vectoriale; În primul rând, instrucțiunea de definire a predicatului pentru vPA este, de asemenea, inclusă în corpul ramurii vectoriale externe utilizând vec_any_gt. În al doilea rând, profitabilitatea ramurii vectorului interior pentru vPB depinde de probabilitatea condiționată a vPB de a avea valori false în toate câmpurile date vPA are valori false în toate câmpurile.

Luați în considerare un exemplu în care ramura exterioară din linia de bază scalară este întotdeauna luată, ocolind majoritatea instrucțiunilor din corpul buclei. Cazul intermediar de mai sus, fără ramuri vectoriale, execută toate instrucțiunile vectoriale. Codul final, cu ramuri vectoriale, execută atât comparația, cât și ramura în modul vector, câștigând potențial performanță peste linia de bază scalară.

Vectorizare manuală

În majoritatea compilatoarelor C și C ++ , este posibil să se utilizeze funcții intrinseci pentru a vectoriza manual, în detrimentul efortului și mentenanței programatorului.

Languages

In other projects