Vektoriális modell, párhuzamosítás
A vektoriális modell
Amikor már az elérhető legjobb algoritmusunk van a skaláris elemzésnek köszönhetően, akkor dönthetjük el, hogy vertikális vagy horizontális vektorizálást alkalmazunk-e. Alapvetően a SIMD utasításkészlet nagy előnye, hogy több, egymástól független adaton lehet egyszerre dolgozni. Victor Lee a képfeldolgozást említette, amikor például több pixelen lehet ugyanazt a műveletet végrehajtani. Ennek a megoldásnak az előnye, hogy viszonylag egyszerű, és ha a program jól van megírva, akkor a fordító ezt automatikusan meg tudja csinálni. Hátránya viszont, hogy egyszerre nagyobb mennyiségű adaton dolgozva sokkal könnyebb összeszemetelni a cache-t, amitől elég sokat lehet lassulni.
A horizontális vektorizálás az az eset, amikor megpróbálunk ugyanazon az adaton több műveletet elvégezni, ami általában kisebb adatmennyiséget igényel egyszerre, viszont több munkát a programozótól. Adatstruktúrák esetén itt merül fel a kérdés, hogy struktúrákat szervezzünk tömbbe vagy tömböket struktúrába. Hagyományosan legtöbbünk struktúrákat szervez tömbbe (array-of-structure), ami jól olvasható kódot eredményez. Ezzel az a probléma, hogy tipikusan minden egyes struktúrának ugyanazon az elemén akarunk végigmenni, ami azt eredményezi, hogy jó eséllyel csak sok olvasásnyi költséggel tudjuk ezt megvalósítani. Tipikusan, ha például x, y és z koordinátákat tárolunk, és az összes x koordinátán akarunk először végigmenni, akkor float típusú adatok esetén minden 12. bájtra van szükségünk. Erre nincs túlságosan jó hardveres támogatás még akkor sem, ha a prefetch hajlamos felismerni mintákat is. Ezzel szemben, ha az x koordinátákat szervezzük egy tömbbe, az y koordinátákat egy másikba és a z-k kerülnek egy harmadikba, akkor az egymást követő koordinátákon sokkal hatékonyabban tudunk végigmenni. Természetesen ennek is megvan a maga hátránya: ha nem eleve ilyen szervezésű az adatunk, akkor konvertálni kell, ami nagyon költséges is lehet.
Az implementálási szakaszban pl. segíthet az Intel Cilk Plus, használhatunk pragmákat (simd, ivdep, aligned), amelyek a fordítónak segítenek, vagy írhatunk rögtön vektorizált kódot is. Figyeljünk oda, hogy egyszeres vagy kétszeres pontosságú adatokkal dolgozunk-e (az ajánlás szerint törekedjünk a használható legkisebbre), de semmiképp se keverjük, mert akkor a fordító nem tudja automatikusan vektorizálni. Ismét csak használjuk bátran a hardver speciális képességeit, ebben az esetben pl. alignment (palign, valign), pack/unpack stb.
A vektoriális modell analízisénél számolhatunk például vektorsűrűséget (az összes vektorutasítás és az összes utasítás hányadosa) vagy effektív SIMD hányadost (utóbbi megmutatja, hogy a SIMD x utasításszélességét mennyire használjuk ki). A SIMD hányadost a VTune is kiszámolja, aminek egy mostani Xeon processzor esetén illik azért 2 felett lennie, és akkor még nem beszélhetünk hatékony kódról.
Párhuzamosodjunk!
Eddig tartott a klasszikus modell esetén az optimalizálás. Látható, hogy ha komolyan gondolják, akkor igencsak gondolkodás- és erőforrás-igényes folyamat. Vágjunk hát bele az utolsó, de egy ideje talán a legfontosabb szempont szerinti optimalizálásba, a párhuzamosításba!
Ha már egyetlen magon (vagy inkább egyetlen szálon) elégedettek vagyunk a hatékonysággal, ideje kihasználni az összes párhuzamos erőforrásunkat. Rögtön beleütközhetünk Amdahl törvényébe, ami pongyolán fogalmazva azt mondja ki, hogy a párhuzamosítás által elérhető sebességnövekedést korlátozza a szekvenciális kód mennyisége. Tehát el kell dönteni, hogy a kód mekkora/melyik részét akarjuk párhuzamosítani, és melyiket meghagyni szekvenciálisnak. Sajnos a legjobb szekvenciális kód nagyon sokszor nem a legjobban párhuzamosítható. Például ha írtunk egy kis aritmetikai sűrűségű kódot, ami kiválóan fut egyetlen szálon, viszont az adatok függnek egymástól, akkor ez nem párhuzamosítható egyszerűen.
Nagyon fontos a rendelkezésre álló cache és sávszélesség megfelelő kezelése. A processzorok többsége ugyanis úgy van tervezve, hogy az egyes magok valójában nagyobb sávszélességet tudnak felhasználni, mint amennyi a teljes sávszélességből egyenlően rájuk esne. Lee úr ezt úgy magyarázta, hogy a cache nagyon hasonlít az emberi agy működéséhez ilyen szempontból: közepes terhelésen minden rendben, minden szép és sehol egy hiba. Azonban ha az emberi agyat elkezdjük teljesítőképességének határaihoz közel terhelni, akkor előbb-utóbb kiesik a ritmusból, és bizony megakad, belassul néha. A gyorsítótárak hatékonyabb kihasználásában segít a blokkosítás/tömbösítés. Ez azt jelenti, hogy megpróbáljuk a felhasználandó adatokat akkora szeletekre bontani, hogy egyrészt a helyi cache-ekbe beférjenek, másrészt a prefetch algoritmus meg tudja tanulni az adatelérési mintát. Az implementálás területén elég sok segítséget kapunk megfelelő API-któl és könyvtáraktól, úgymint OpenMP, Intel Cilk, Intel Threading Building Blocks, pThreads stb.
Természetesen nincs mindez ingyen, a párhuzamosítással bejönnek annak "költségei" is: programszálak indítása/leállítása, szinkronizálás a szálak között és egyéb korlátozások. Mindezek figyelembevételével dönthetünk úgy, hogy nem akarjuk kihasználni az összes párhuzamos erőforrásunkat, mert egyszerűen nem éri meg. Például egy Xeon Phi 60 magján futó programunk szinkronizálása lehet annyira bonyolult, hogy érdemesebb 4 vagy 8 szálban gondolkodni csak.
Az adatok megosztása a magok között szintén okozhat fejtörést. Előfordulhat például, hogy két mag ugyanazon a cache-line-on elhelyezkedő különböző változót használja, legrosszabb esetben egymást fogják lassítani az állandó frissítéssel. Könnyű tehát elérni, hogy a magok versengjenek egymással az erőforrásokért, így minden további nélkül ki is lehet éheztetni ezeket. És itt jön be megint az analízis! A korábban említett számlálók és egy megfelelő program használatával jól lehet saccolni, hogy mi történik kódunk futása közben. A VTune beépített profiljainak valamelyikével megnézve, hogy hol tölti el a legtöbb időt a programunk, van lehetőségünk célzott módosításokat végrehajtani. Egyszerre látjuk a programforrást és a gépi kódot is az adott utasításban eltöltött idővel együtt. Itt jön jól, ha sejtjük a processzor működését, és láttunk már assembly-t is.
A cikk még nem ért véget, kérlek, lapozz!
