Vektorizacija
Šiam straipsniui ar jo daliai trūksta išnašų į patikimus šaltinius. Jūs galite padėti Vikipedijai pridėdami tinkamas išnašas su šaltiniais. |
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
[redaguoti | redaguoti vikitekstą]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
[redaguoti | redaguoti vikitekstą]Š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
[redaguoti | redaguoti vikitekstą]Š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
[redaguoti | redaguoti vikitekstą]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
[redaguoti | redaguoti vikitekstą]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.