Vektorizacija

Straipsnis iš Vikipedijos, laisvosios enciklopedijos.
Peršokti į: navigaciją, paiešką

Vektorizacija matematikoje. Naudojimui kompiuterinėje grafikoje.

Vektorizacija, kompiuterijoje, yra 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[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

Š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ų:

  1. Suraskite esančią gilumoje kilpą (loop), kuri gali būti vektorizuojama
  2. 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[taisyti | redaguoti kodą]

Š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:

  1. Esanti gilumoje kilpa (loop) yra išvyniota vektoriaus ilgio faktoriaus, kad suformuotų didelį kilpos kūną.
  2. 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[taisyti | redaguoti kodą]

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[taisyti | redaguoti kodą]

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.