Vektorizacija

Vektorizacija kompiuterijoje – procesas, paverčiantis kompiuterio programą iš skaliarinio realizavimo, kuris atlieka operacijas keliais operandais vienu laiku, į vektorizuotą programą, kur viena instrukcija gali įvykdyti daugialypes operacijas ar vektoriaus poros (gretimų verčių serija) operandus. Vektoriaus apdirbimas yra pagrindinė ypatybė ir tradicinių, ir šiuolaikinių superkompiuterių.

Viena pagrindinė tyrinėjimo tema kompiuterijoje yra automatinės vektorizacijos metodų paieška;
ieškojimas metodų, kurie leistų kompiliatoriui paversti skaliarines programas į vektorizuotas programas be žmogaus pagalbos.

Automatinė vektorizacija 
Automatinis vektorizavimas, kompiuterio programos kontekste, siejasi su automatine transformacija serijos operacijų, įvykdytų iš eilės, viena operacija vienu metu, į operacijas, įvykdytas lygiagrečiai, po kelias vienu metu. Būdas tinkamas apdirbti vektoriaus procesorius.

Pavyzdys būtų programa, kuri padaugina du skaitmeninių duomenų vektorius. Skaliarinis metodas būtų:

  for (i = 0; i < 1024; i++)
  {
     C[i] = A[i]*B[i];
  }

Tai galėjo būti paverčiama į vektorizacijos kodą:

  for (i = 0; i < 1024; i+=4)
  {
     C[i:i+3] = A[i:i+3]*B[i:i+3];
  }

Čia, C [i: i+3] nurodo keturis rinkinio elementus nuo C[i] iki C[i+3], ir mes manome, kad vektoriaus procesorius gali įvykdyti keturias operacijas vienai vektoriaus instrukcijai. Kadangi keturios operacijos yra įvykdytos per laiką, panašų į užimtą vienai skaliarinei instrukcijai, vektoriaus kodas gali vykti keturis kartus greičiau negu originalus kodas.

Yra du skirtingi kompiliatoriaus metodai: vienas pagrįstas tradicine vektorizacijos technika ir kitas pagrįstas „išvyniojančia kilpa“ (loop unrolling).

Kilpos – lygmens (Loop – level) automatinis vektorizavimas 
Ši technika, panaudota tradicinėms vektorinėms mašinoms, bando surasti ir eksploatuoti SIMD lygiagretumą nuo kilpos lygmens (loop level). Jis susideda iš dviejų pagrindinių žingsnių:

 Suraskite esančią gilumoje kilpą (loop), kuri gali būti vektorizuojama
 Paverskite kilpą (loop) ir sukurkite vektoriaus kodus

Pirmame žingsnyje, vektorinimo kompiliatorius ieško kliūčių, kurios gali sutrukdyti vektorizaciją. Pagrindinė vektorizacijos kliūtis yra instrukcijos lygmens lygiagretumas tikrų duomenų priklausomybė trumpesnė negu vektoriaus ilgis. Kitos kliūtys įtraukia funkcijos paklausimus ir trumpus kartojimo skaičiavimus.

Kai tik nutarta kilpą (loop) vektorizuoti, kilpa (loop) yra pridedama prie vektoriaus ilgio, ir kiekvienos skaliarinės instrukcijos kilpos (loop) kūno viduje yra pakeistos atitinkamomis vektoriaus instrukcijomis.

Sudedamąją transformaciją šiam žingsniui parodo naudodama anksčiau minėtą pavyzdį.
 Po apdorojimo
  for (i = 0; i < 1024; i+=4)
  {
    for (ii = 0; ii < 4; ii++)
    {
       C[i+ii] = A[i+ii]*B[i+ii];
    }
  }
 Po kilpos (loop) dalijimo, naudojant laikinus rinkinius
  for (i = 0; i < 1024; i+=4)
  {
    for (ii = 0; ii < 4; ii++) tA[ii] = A[i+ii];
    for (ii = 0; ii < 4; ii++) tB[ii] = B[i+ii];
    for (ii = 0; ii < 4; ii++) tC[ii] = tA[ii]*tB[ii];
    for (ii = 0; ii < 4; ii++) C[i+ii] = tC[ii];
  }
 Po pakeitimo vektoriaus kodais
  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]);
  }

Pagrindinio bloko lygmens automatinis vektorizavimas 
Ši palyginti nauja technika specialiai orientuota į šiuolaikinę SIMD architektūrą su trumpais vektoriaus ilgiais. Nors kilpos (loop) gali būti išvyniotos, kad padidintų kiekį SIMD lygiagretumo pagrindiniuose blokuose, šios technikos tikslas eksploatuoti SIMD lygiagretumą pagrindinių blokų viduje, o ne nuo kilpų. Dėl to, SIMD kodai gali būti sukurti nuo pagrindinių blokų už kilpos lizdų.
Du pagrindiniai žingsniai:

 Esanti gilumoje kilpa (loop) yra išvyniota vektoriaus ilgio faktoriaus, kad suformuotų didelį kilpos kūną.
 Izomorfinės skaliarinės instrukcijos (kurios įvykdo tą pačią operaciją) yra supakuotos į vektoriaus instrukciją, jei priklausomybės netrukdo daryti taip.

Pavyzdys parodantis žingsnis po žingsnio transformaciją šiam metodui.

 Po išvyniojančios kilpos (loop) (prie vektoriaus ilgio, kuris, buvo 4 šiuo atveju)
  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]);
  }
 Po pakavimo
  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]);
  }
 Po kodo generacijos
  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]);
  }
Čia, sA1, sB1… nurodo skaliarinius kintamuosius ir vA, vB, ir vC nurodo vektoriaus kintamuosius.

Dauguma automatinio vektorizavimo komerciniai kompiliatoriai naudoja tradicinį kilpos lygmens (loop level) metodą išskyrus IBM XL Compiler, kuris naudoja abu.

Vektorizacija esant kontrolės srovei 
Kai yra if – konstrukcija loopbody, instrukcijos visuose kontrolės keliuose turi būti atliktos, kad sujungtų daugialypes kintamojo vertes. Vienas bendras būdas yra praeiti kodinės transformacijos seką: predikacija → vektorizacija (naudijant vieną iš dviejų būdų) → pašalinti vektoriaus predikatus → pašalinti skaliarinius predikatus.

Šis kodas yra panaudotas kaip pavyzdys, kad parodytų šitą transformaciją;
  for (i = 0; i < 1024; i++)
  {
     if (A[i] > 0)
       C[i] = B[i];
     else
       D[i] = D[i-1];
  }
 Po predikavimo
  for (i = 0; i < 1024; i++)
  {
     P = A[i] > 0;
     NP = !P;
     C[i] = B[i];     (P)
     D[i] = D[i-1];   (NP)
  }
kur (P) reiškia tarinį, saugantį predikavimą.
 Po vektorizacijos
  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]   = D[i-1];         (NP1)
     D[i+1] = D[i];           (NP2)
     D[i+2] = D[i+1];         (NP3)
     D[i+3] = D[i+2];         (NP4)
  }
 Po vektorių predikatoriaus pašalinimo
  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]   = D[i-1];         (NP1)
     D[i+1] = D[i];           (NP2)
     D[i+2] = D[i+1];         (NP3)
     D[i+3] = D[i+2];         (NP4)
  }
 Po skaliarų predikatorių pašalinimo
  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 (NP1) D[i]   = D[i-1];
     if (NP2) D[i+1] = D[i];
     if (NP3) D[i+2] = D[i+1];
     if (NP4) D[i+3] = D[i+2];
  }

Sumažinimas vektorizacijos viršuje esant kontrolės srovei 
Turint atlikti instrukcijas visuose kontrolės keliuose vektoriaus kode buvo vienas iš pagrindinių faktorių, kurie lėtina vektoriaus kodą dėl skaliarinės pagrindinės linijos. Norint sumažinti šį vektorizacijos viršuje, vektoriaus šakos gali būti įdėtos, kad apeitų vektoriaus instrukcijas, panašias į būdą, kuriuo skaliarinės šakos apeina skaliarines instrukcijas. Apačioje, AltiVec tariniai yra panaudoti, kad parodytų, kaip tai gali būti pasiekiama.

 Skaliarinė pagrindinė linija (originalus kodas)
  for (i = 0; i < 1024; i++)
  {
     if (A[i] > 0)
     {
       C[i] = B[i];
       if (B[i] < 0)
         D[i] = E[i];
     }
  }
 Po vektorizacijos esant kontrolės srovei
  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);
  }
 Po vektoriaus šakų įdėjimo
  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);
        }
     }
  }
Yra du veiksmai pažymėti galutiniam kodui su vektoriaus šakomis; Pirma, predikatas, apibrėžiantis instrukciją vPA, yra taip pat įtrauktas kūno viduje išorinės vektoriaus šakos vartojant vec_any_gt. Antra, pelningumas vidinės vektoriaus šakos vPB priklauso nuo sąlyginės vPB tikimybės, turėjimas neteisingų verčių visuose laukuose, duotuose vPA, turi neteisingas vertes visuose laukuose.

Informatika