Vektorointi (tietokone)

Vectorization (sisällä rinnakkaislaskentana ), on erikoistapaus rinnakkaisuuden , jossa ohjelmisto, joka suorittaa oletusarvoisesti yhtä toimintoa kerrallaan yhden ainoan säikeen on muunnettu suorittamaan useita toimintoja samanaikaisesti.

Vektorointi on prosessi, jolla tietokoneohjelma muunnetaan skalaarisesta toteutuksesta , joka käsittelee yhden operandiparin kerrallaan, vektoritoteutukseksi, joka käsittelee operaation useilla operandipareilla kerrallaan. Termi tulee sopimuksesta, jolla operandit laitetaan vektoreihin tai matriiseihin .

Vektori laskeminen on tärkeä ominaisuus sekä tavanomaisia tietokoneita ja supertietokoneita moderni, joka voi suorittaa vektori toimintoja, jotka suorittavat samanaikaisesti toimintoja, kuten esimerkiksi seuraavat neljä lisäykset:

\ aloita {tasaus} c_1 & = a_1 + b_1 \\ c_2 & = a_2 + b_2 \\ c_3 & = a_3 + b_3 \\ c_4 & = a_4 + b_4 \ loppu {tasaus}

Useimmissa ohjelmointikielissä kirjoitamme kuitenkin yleensä silmukoita, jotka lisäävät peräkkäin suuria lukuja. Tässä on esimerkki tällaisesta silmukasta C : ssä:

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

Automaattinen vektorisointi on merkittävä tietojenkäsittelytieteen tutkimusaihe; se koostuu menetelmien etsimisestä, joiden avulla kääntäjä voi muuntaa (ilman ihmisen apua) skalaariohjelmat vektorisoiduiksi ohjelmiksi.

Asiayhteys

Varhaisissa tietokoneissa oli yleensä looginen yksikkö, joka suoritti käskyn peräkkäin operandiparille kerrallaan. Siksi tietokoneohjelmat ja ohjelmointikielet on suunniteltu suorittamaan käskyt peräkkäin. Nykyaikaiset tietokoneet voivat tehdä paljon asioita kerralla. Suuri määrä optimoivia kääntäjiä suorittaa automaattisen koodivektoroinnin: se on kääntäjän ominaisuus, joka sallii peräkkäisten ohjelmien osien muuntamisen vastaaviksi rinnakkaisohjelmiksi koodin tuottamiseksi, jota vektoriprosessori käyttää hyvin.

Takuut

Automaattisen vektorisoinnin, kuten silmukan optimoinnin tai jonkin muun kokoamisen optimoinnin, on säilytettävä tarkasti ohjelman käyttäytyminen.

Tietojen riippuvuudet

Kaikki riippuvuudet on huomioitava ajon aikana virheellisten tulosten välttämiseksi.

Yleensä silmukka-invariantit ja leksikaalisesti rajatut riippuvuudet voidaan helposti vektorisoida, ja myös laajennamattomat riippuvuudet voidaan vektorisoida, vaikkakin vaikeampia. Mutta nämä muunnokset on tehtävä turvallisesti, jotta voidaan varmistaa kaikkien ilmoitusten välinen riippuvuus ja pysyä samalla uskollisena alkuperäiselle koodille.

Sykliset riippuvuudet on käsiteltävä vektorisoiduista ohjeista riippumatta.

Tietojen tarkkuus

Tarkkuus on koko (binary koko) on säilytettävä suorituksen aikana vektorin opetusta. Viimeksi mainitut on valittava oikein sisäisten kokonaislukujen koon ja käyttäytymisen mukaan. Sekoitettujen kokonaislukutyyppien kohdalla on myös noudatettava erityistä varovaisuutta asianmukaiseen mainostamiseen / alentamiseen tarkkuuden menettämättä. Erityistä huomiota on kiinnitettävä merkkilaajennuksiin (useita kokonaislukuja pakataan samaan rekisteriin) ja muunnosoperaatioiden aikana tai sellaisten bittioperaatioiden kanssa, jotka olisi otettu huomioon.

Liukulukujen tarkkuus tulisi säilyttää myös, ellei IEEE-754 noudattaminen ei ole voimassa, jolloin toiminta on nopeampaa, mutta tulokset vaihtelevat jonkin verran. Suuret vaihtelut, jopa IEEE-754: n huomiotta jättäminen, tarkoittavat yleensä ohjelmointivirheitä. Ohjelmoija voi myös pakottaa yksittäiset tarkkuusvakiot ja silmukkamuuttujat (oletusarvoisesti yleensä kaksi) suorittamaan kaksi kertaa niin monta operaatiota käskyä kohden.

Teoria

Ohjelman vektorisoimiseksi kääntäjän optimoijan on ensin ymmärrettävä ilmoitusten väliset riippuvuudet ja sovitettava ne tarvittaessa. Kun riippuvuudet on kartoitettu, optimoijan on järjestettävä asianmukaisesti asianmukaisten ehdokkaiden käskyjen toteutus useille data-elementeille toimiville käskyvektoreille.

Riippuvuuskaavion rakentaminen

Ensimmäinen vaihe on rakentaa riippuvuuskaavio, tunnistamalla muista ilmoituksista riippuvat ilmoitukset. Tähän sisältyy jokaisen lauseen tutkiminen ja tunnistaminen toisistaan jokaisesta tietoelementistä, jota käsky käyttää. Alias analyysi voidaan todistaa, että eri muuttujien käyttää samoja muistin jakamista.

Riippuvuuskaavio sisältää kaikki paikalliset riippuvuudet, joiden etäisyys on pienempi kuin vektorin koko. Joten jos vektorirekisteri on 128-bittinen ja taulukon tyyppi on 32-bittinen, vektorin koko on 128/32 = 4. Kaikkien muiden ei-syklisten riippuvuuksien ei pitäisi mitätöidä vektorointia, koska se ei ole, ei ole samanaikaista pääsy samaan vektori-käskyyn.

Oletetaan, että vektorin koko on sama kuin 4 kokonaislukua (intia):

for (i = 0; i < 128; i++) { a[i] = a[i-16]; // 16 > 4, ignoré a[i] = a[i-1]; // 1 < 4, reste sur le graphe de dépendances }

Ryhmittely

Käyrän avulla optimoija voi sitten ryhmitellä vahvasti liitetyt komponentit (SCC) ja vektoroitavat lauseet erillään muista.

Tarkastellaan esimerkiksi ohjelmafragmenttia, joka sisältää kolme käskyryhmää silmukan sisällä: (SCC1 + SCC2), SCC3 ja SCC4 siinä järjestyksessä, jossa vain toinen klusteri (SCC3) voidaan vektorisoida. Lopullinen ohjelma sisältää kolme silmukkaa, yhden kutakin klusteria kohti, vain keskimmäinen vektoroidaan. Optimoija ei voi liittyä ensimmäiseen viimeiseen rikkomatta käskyn suorittamisjärjestystä, mikä mitätöi tarvittavat takuut.

Idioomien tunnistus

Joitakin ei-ilmeisiä riippuvuuksia voidaan edelleen optimoida tiettyjen idioomien perusteella.

Esimerkiksi seuraavat datan itseriippuvuudet voidaan vektorisoida, koska oikealla olevien arvojen (RHS) arvo noudetaan ja tallennetaan sitten vasemmalla olevaan arvoon, jotta tiedot eivät voi muuttua tehtävän sisällä.

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

Skalaarien itseriippuvuus voidaan vektorisoida eliminoimalla muuttujat.

Yleiset puitteet

Silmukan vektorisoinnin yleinen kehys on jaettu neljään vaiheeseen:

Alkuosa: Kun itsenäiset silmukka-muuttujat ovat valmiita käytettäväksi silmukan sisällä. Tähän liittyy yleensä niiden siirtäminen vektorirekistereihin, joissa on erityiset mallit, joita käytetään vektoriohjeissa. Tämä on myös paikka, johon ajonaikaisen riippuvuuden tarkistus lisätään. Jos ohjaus päättää, että vektorointi ei ole mahdollista, siirry puhdistusvaiheeseen.
Silmukat (silmukat): kaikki vektorisoidut silmukat (tai ei), erotettu CSSC-klustereilla alkuperäisen koodin ulkoasun järjestyksessä.
Postlude: palauttaa kaikki riippumattomien silmukoiden, induktioiden ja reduktioiden muuttujat.
Siivous: Yksinkertaisesti toteuttaa (ei-vektorisoidut) silmukat iteraatioille silmukan lopussa, jotka eivät ole vektorin koon kerrannaisia, tai kun ajonaikaiset ohjaimet estävät vektorin käsittelyn.

Ajonaikainen vs. kokoelma

Joitakin vektorisaatioita ei voida täysin tarkistaa kokoamisajankohtana. Käännösajan optimointi vaatii nimenomaisen taulukon indeksin . Kirjastotoiminnot voivat myös estää optimoinnin, jos niiden käsittelemät tiedot tarjoavat ulkoiset parametrit. Jopa näissä tapauksissa ajonaikainen optimointi voi silti vektorisoida käynnissä olevat silmukat.

Tämä suorituksen hallinta suoritetaan alkuvaiheessa ja ohjaa virtauksen vektoroitaviin käskyihin, jos mahdollista, muuten palataan normaaliin käsittelyyn riippuen muuttujista, jotka välitetään rekistereihin tai skalaarimuuttujista.

Seuraava koodi voidaan helposti vektorisoida kääntöhetkellä, koska siinä ei ole toimintoja, jotka kutsuvat tai riippuvat ulkoisista parametreista. Lisäksi kieltä takaa, että se ei käytä samaa muistia jakamista kuin muitakin muuttujia, ovat paikalliset muuttujat ja elävät vain suorituksen pinossa .

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

Toisaalta alla olevalla koodilla ei ole tietoa muistipaikoista, koska viitteet ovat osoittimia ja muisti, johon ne on varattu, on dynaaminen.

int *a = malloc(128*sizeof(int)); int *b = malloc(128*sizeof(int)); // initialise b for (i = 0; i<128; i++, a++, b++) *a = *b + 5; // ... // ... // ... free(b); free(a);

Nopea ajonaikainen tarkistus a: n ja b: n osoitteessa sekä iterointisilmukatilassa (128) riittää kertomaan, ovatko matriisit päällekkäisiä vai eivät, paljastamalla kaikki riippuvuudet.

On olemassa työkaluja olemassa olevien sovellusten dynaamiseen analysointiin SIMD- rinnakkaisuuteen liittyvän piilevän potentiaalin arvioimiseksi , joka voidaan hyödyntää kääntäjän kehityksen ja / tai manuaalisten koodimuutosten avulla.

Tekniikat

Esimerkki olisi ohjelma, joka kertoo kaksi digitaalisen datan vektoria. Skalaarinen lähestymistapa olisi jotain:

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

Se voidaan vektoroida näyttämään tältä:

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

Tässä C [i: i + 3] edustaa neljää taulukkoindeksiä välillä C [i] - C [i + 3] ja vektoriprosessori voi suorittaa neljä operaatiota yhdelle vektorikomennolle. Koska kaikki neljä vektoritoimintoa suoritetaan suunnilleen samaan aikaan skalaarikäskyn kanssa, vektorilähestyminen voi suorittaa jopa neljä kertaa nopeammin kuin alkuperäinen koodi.

Kokoamisessa on kaksi erillistä lähestymistapaa: yksi perustuu klassiseen vektorointitekniikkaan ja toinen silmukan purkamiseen .

Automaattinen vektorointi silmukan tasolla

Tämä tekniikka, jota käytetään klassisissa vektorikoneissa, yrittää löytää ja hyödyntää SIMD-rinnakkaisuutta silmukan tasolla. Se koostuu kahdesta päävaiheesta seuraavasti.

Etsi sisäinen silmukka, joka voidaan vektoroida;
Muunna silmukka ja luo vektorikoodit;

Ensimmäisessä vaiheessa kääntäjä etsii esteitä, jotka voivat estää vektorisoinnin. Suurin este vektorisoinnille on todellinen datariippuvuus, joka on lyhyempi kuin vektorin pituus. Muita esteitä ovat toimintokutsu ja lyhyt iterointilaskenta.

Kun silmukka on määritetty vektoroitavaksi, silmukka erotetaan vektorin pituudelta ja kukin silmukan rungossa oleva skalaarikäsky korvataan vastaavalla vektori-käskyllä. Seuraavassa tämän vaiheen komponenttimuunnokset näytetään käyttämällä yllä olevaa esimerkkiä.

Jälkeen nauha-kaivos-

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

Kun olet jakanut silmukoita väliaikaisten taulukoiden avulla

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]; }

Vaihdon jälkeen vektorikoodeilla

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] ); }

Automaattinen vektorointi peruslohkotasolla

Tämä suhteellisen uusi tekniikka kohdistuu erityisesti moderneihin SIMD-arkkitehtuureihin, joilla on lyhyet vektoripituudet. Vaikka silmukat voidaan purkaa SIMD-rinnakkaisuuden lisäämiseksi peruslohkoissa, tämä tekniikka hyödyntää SIMD-rinnakkaisuutta peruslohkoissa silmukoiden sijaan. Kaksi päävaihetta ovat:

Sisin silmukka puretaan vektorin pituuden kertoimella suureksi silmukan rungoksi.
Isomorfiset skalaarikäskyt (jotka suorittavat saman toiminnan) pakataan vektori-käskyyn, jos riippuvuudet eivät estä sitä tekemästä niin.

Tämän lähestymistavan vaiheittaisten muutosten esittämiseksi käytetään jälleen samaa esimerkkiä kuin yllä.

Silmukoiden purkamisen jälkeen (vektorin pituuden mukaan, oletetaan tässä tapauksessa olevan 4)

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] ); }

Pakkauksen jälkeen

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] ); }

Koodin luomisen jälkeen

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] ); }

Tässä sA1, SB1, ... edustavat skalaarimuuttujia ja VA, VB ja Vc vektorimuuttujia.

Kaupalliset automaattivektorointikääntäjät käyttävät enimmäkseen tavanomaista loop-tason lähestymistapaa lukuun ottamatta IBM XL-kääntäjää, joka käyttää molempia.

Säätövirtauksen läsnä ollessa

Läsnäolo , jos kehon silmukan edellyttää suorittamisen lausunnot kaikissa komento polut yhdistää useita arvoja muuttujan. Yleisenä lähestymistapana on käydä läpi koodimuunnosten sarja: Predikaatio → vektorointi (käyttäen yhtä yllä olevista menetelmistä) → predikaattien poistaminen vektoreista → skalaaristen predikaattien poistaminen.

Seuraavaa koodia käytetään esimerkkinä näiden muunnosten osoittamiseksi:

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

Saarnattuaan

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

missä (P) tarkoittaa predikaattia, joka pitää ilmoitusta.

Vektoroinnin jälkeen

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) }

Kun olet poistanut predikaatit vektoreista

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) }

Skalaarien predikaattien poistamisen jälkeen

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]; }

Vektoroinnin lisäkustannusten vähentäminen kontrollivirtauksen läsnä ollessa

Käskyjen suorittaminen kaikilla ohjauspoluilla vektorikoodissa on ollut yksi tärkeimmistä tekijöistä, joka hidastaa vektorikoodia skalaaripohjaan nähden. Mitä monimutkaisemmaksi komentovirta muuttuu ja mitä enemmän ohjeita ohjataan skalaarikoodiin, sitä vaikeampi vektorointi tulee. Sen yleiskustannusten pienentämiseksi voidaan vektorihaaroja lisätä ohituskäyttövektoreihin samalla tavalla kuin skalaarihaarat ohittavat skalaarikäskyt. Alla AltiVec-predikaatteja käytetään osoittamaan, miten tämä voidaan saavuttaa.

Skalaaripohja (alkuperäinen koodi)

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

Vektoroinnin jälkeen kontrollivirtauksen läsnä ollessa

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); }

Lisäyksen jälkeen vektori oksat

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); }

Lopullisessa koodissa on kaksi asiaa, jotka haarautuvat vektoriin. Yhtäältä vPA: n käskyn määrittelevä predikaatti sisältyy myös ulkoisen vektorihaaran runkoon käyttäen vec_any_gt. Toisaalta sisäisen vektorin haarautumisen kannattavuus vPB: lle riippuu ehdollisesta todennäköisyydestä, että vPB: llä on väärät arvot kaikissa kentissä, koska vPA: lla on väärät arvot kaikissa bittikentissä.

Tarkastellaan esimerkkiä, jossa skalaarialustan ulkoinen haarautuminen tehdään aina ohittamalla suurin osa silmukan rungossa olevista ohjeista. Yllä oleva välitapaus, ilman vektorin haarautumista, suorittaa kaikki vektori-käskyt. Lopullinen koodi vektorihaarautumisella suorittaa sekä vertailun että haarautumisen vektorimoodissa, mahdollisesti saavuttaen suorituskyvyn skalaaripohjan yli.

Katso myös

# Ketjutusvektoriprosessori

Viitteet

(en) Tämä artikkeli on osittain tai kokonaan otettu englanninkielisestä Wikipedia- artikkelista " Vectorization_ (parallel_computing) " ( katso luettelo tekijöistä ) .

http://dl.acm.org/citation.cfm?id=2254108
S. Larsen ja S. Amarasinghe , " ACM SIGPLAN -konferenssin aiheet ohjelmointikielen suunnittelusta ja toteutuksesta ", ACM SIGPLAN Notices , voi. 35, n ° 5,2000, s. 145–156 ( DOI 10.1145 / 358438.349320 )
" Koodin optimointi IBM XL-kääntäjillä " ,Kesäkuu 2004(katsottu toukokuussa 2010 )
J. Shin , MW Hall ja J. Chame , " Koodien luomista ja optimointia käsittelevän kansainvälisen symposiumin käsittely ", Supersanatason rinnakkaisuus valvontavirran läsnäollessa ,2005, s. 165–175 ( ISBN 0-7695-2298-X , DOI 10.1109 / CGO.2005.33 )
J. Shin , " Proceedings of the 16th International Conference on Parallel Architecture and Compilation Techniques ", Control Flow: n esittely vektorisoituun koodiin ,2007, s. 280–291 ( DOI 10.1109 / PACT.2007.41 )